暗号実装最適化— 暗号実装屋の不毛な戦い
青木 和麻呂NTT

Copyright 2012 c NTT – p.1/35

自己紹介
某電話会社に勤めています。
暗号学者です。
暗号の解読と高速実装が好きです。
本業では Camellia 暗号の設計とか、768ビット数の素因数分解とかやりました。

Copyright 2012 c NTT – p.2/35

注(詳細な) 知識は Pentium 4 と初代 Opteronで止まってます。なるべく最新の話も入れますけど。

紹介するネタは他人が発見したネタもあります。

Copyright 2012 c NTT – p.3/35

内容
暗号実装
公開鍵暗号の実装
共通鍵暗号の実装
まとめ

Copyright 2012 c NTT – p.4/35

暗号実装
高速実装が求められる最後の領域 (?)(画像屋は GPU にいっちゃったし…)

Copyright 2012 c NTT – p.5/35

暗号実装
高速実装が求められる最後の領域 (?)(画像屋は GPU にいっちゃったし…)(一般人には) 安全性は謎。優劣は速度でしか比較できない。

Copyright 2012 c NTT – p.5/35

暗号実装
高速実装が求められる最後の領域 (?)(画像屋は GPU にいっちゃったし…)(一般人には) 安全性は謎。優劣は速度でしか比較できない。

でも、暗号アプリケーションからはいくら高速にしたところで間に合わない

Copyright 2012 c NTT – p.5/35

暗号実装
高速実装が求められる最後の領域 (?)(画像屋は GPU にいっちゃったし…)(一般人には) 安全性は謎。優劣は速度でしか比較できない。

でも、暗号アプリケーションからはいくら高速にしたところで間に合わない
十分に高速で速くする意味がない

Copyright 2012 c NTT – p.5/35

暗号実装
高速実装が求められる最後の領域 (?)(画像屋は GPU にいっちゃったし…)(一般人には) 安全性は謎。優劣は速度でしか比較できない。

でも、暗号アプリケーションからはいくら高速にしたところで間に合わない
十分に高速で速くする意味がないでも、最適化しますけどね。楽しいから。
Copyright 2012 c NTT – p.5/35

公開鍵暗号の実装
アルゴリズムレベルでの最適化がメイン(x86 だから…という話はかなり末端処理)
1 単位の処理が 100µ 秒前後 (≈100k cycle)

イマドキだと、自作セマフォを使った
thread 同期処理とか (by 光成さんペアリング)
お題を 5 つ: OEF、素体逆元、多倍長整数演算、篩処理、高速完全性検証

Copyright 2012 c NTT – p.6/35

OEF
最適拡大体 (Optimal Extension Fields)。
有限体の一種。
イマドキの CPU (通常の回路を起こすと乗算とかは遅いが、回路面積を割いて高速になっている) で高速になるように有限体のパラメータを選択。
高速な楕円曲線暗号の設計などで利用。
1998 年 Bailey らにより発表。(チーム内で同じようなことを考えていたけど、査読でまわってきて負けを悟る)

Copyright 2012 c NTT – p.7/35

OEF の定義
nGF(p ) ≈ GF(p)[x]/(f (x))(deg f = n, f は GF(p) 上既約)
p = 2m ± c (c は小さい、m はワードサイズぐらいかその半分)、
nf (x) = x ± b (b は小さい)
色々拡張されている。

Copyright 2012 c NTT – p.8/35

OEF での演算内部では、ワードサイズに納まる

aL + c × aH(c は小)という演算多数。
解決策はCopyright 2012 c NTT – p.9/35

OEF での演算内部では、ワードサイズに納まる

aL + c × aH(c は小)という演算多数。
解決策は

lea
Copyright 2012 c NTT – p.9/35

lea
lea r1, [r2 + scale * r3](r1, r2, r3…一般レジスタ、scale=1,2,4,8)
r1 ← r2 + scale × r3
入力を潰さない…神!
(最近は V 始まり命令があるが…)
まさに「aL + c × aH 」が出来る。
(α だと s{4,8}{add,sub}{l,q}とか)Copyright 2012 c NTT – p.10/35

lea の注意点
昔は AGI とかあった。
フラグが変わらないのは善し悪し。
使える ALU が少ないかも。

Copyright 2012 c NTT – p.11/35

modp の C 言語実装
a + b mod p (a, b, p はワードサイズ以内、0 ≤ a, b < p)a = a + b;
if(a >= p){ /* 分岐確率 50% */a -= p;}a = a + b;a -= (-(a >= p)) & p;
SIMD 系の命令ではありがちの方法
Copyright 2012 c NTT – p.12/35

modp の asm 実装
add a, b
mov t, a
sub a, p
jnc l0
mov a, tl0:add a, b
sub a, p
jnc l1
add a, pl1:add a, b
mov t, a
sub a, p
cmovc a, t
cmovc がない環境では setc や sbb で同様のことが出来るが、そういう CPU では分岐はあんまり遅くない…
Copyright 2012 c NTT – p.13/35

素体逆元
a−1 mod p の計算(ax + py = 1 となる x の計算)
最大公約数 (GCD) 計算の変形で計算できる「拡張 Euclid の互除法」vs「バイナリ GCD」
拡張 Euclid の互除法: 割算がメイン
バイナリ GCD: ループ内部で 4 分岐 (それぞれ確率 1/4)
Copyright 2012 c NTT – p.14/35

GCD 計算の原理
素体逆元と基本は同じなので GCD の説明
GCD(a, b) の計算 (a ≥ b)
Euclid の互除法:

GCD(a, b) = GCD(b, a mod b)
バイナリ
GCD: GCD(a, b) =
2GCD(a/2, b/2) a: even, b: even
 GCD(a/2, b)
a: even, b: odd

GCD(a, b/2)
a: odd, b: evenGCD(a − b, b) a: odd, b: odd

Copyright 2012 c NTT – p.15/35

Euclid の互除法の最適化
基本的に割算、しかもレジスタ縛り(rax,rdx) なので、最適化の余地は少ない
実は、商 (a mod b) に偏りあり

if(a - b < b){
商=1, 余り a-b}else if(a - b - b < b){
商=2, 余り a-b-b}else · · ·拡張 Euclid の互除法の場合 P3 で 10 回展開ぐ
らいまでは速い？
Copyright 2012 c NTT – p.16/35

バイナリ GCD の最適化 (1/2)
最内周ループの分岐予測が問題。
(GCD(a − b, b) a > b
GCD(a, b) =GCD(a, b − a) a < ba + b mod p と同様に分岐を削ると
a -= (-(a > b)) & b;
b -= (-(b > a)) & a;
cmov でも同様に実現可。
拡張バイナリ GCD では、複数の変数を最内周ループで更新する必要がある。効率微妙。
Copyright 2012 c NTT – p.17/35

バイナリ GCD の最適化 (2/2)
x[0]=a, x[1]=b と変数を割り当て
i= x[0] > x[1];x[i] -= x[1 - i];addressing でも分岐除去可。
Euclid の互除法とバイナリ GCD のどちらが速いかは、architecture と code により、すぐに入れ替わるので、どちらともいえない。

Copyright 2012 c NTT – p.18/35

多倍長整数演算
de facto の公開鍵暗号では多倍長整数の四則演算が必要。

例えば、RSA では 1024 ビット (128 バイト)とか 2048 ビットとか。
64 ビットレジスタでも 16(32) ワードも必要。

Copyright 2012 c NTT – p.19/35

多倍長整数加算 (素朴)ri, si を 64 ビットレジスタ、3 倍長整数:
a=2X
i=064iri 2,

b=2X64isi 2

i=0

a + b の素朴な問題点 1: critical path が長い
実装:
add r0, s0 問題点 2: carry の 1 ビットを足すためだけに
adc r1, s1
1µop 使われる
adc r2, s2
Copyright 2012 c NTT – p.20/35

多倍長整数加算 (冗長表現)
ri, si を 64 ビットレジスタ、3 倍長整数:
a=3
X
i=0

a + b の実装:
add r0, s0
add r1, s1
add r2, s2
add r3, s3

48i

ri 2,

b=3
X

48i

si 2i=0○ µop 数が減少
○ 命令依存性なし
× 時々正規化が必要
扱う計算 (Karatsuba 乗算とか) により空ける上位ビット数の評価が必要
Copyright 2012 c NTT – p.21/35

篩処理多倍長の合成数の素因数分解が出来る⇒RSA が解読できる
現状、ある程度以上大きな数に対しては数体篩法がもっとも高速な素因数分解法
forprime pcompute staring point xp (≈ 0)
while(x < H )s[x] += log px += pend while
end forprime
Copyright 2012 c NTT – p.22/35

篩処理の最適化
問題点:

p が小さいものについては問題なし
p が H に近くなってくると s[x] へのアクセスは殆んどキャッシュミス (H は実メモリの大きさに近い)解決策: 加算は可換であることを利用し、前もってアクセス先により更新内容 (x, log p)を整列しておく
整列なんかしていたら…と思うが、実は数倍速くなる (ことがある)
Copyright 2012 c NTT – p.23/35

高速完全性検証 (宣伝)
転送したファイルの SHA-256 ハッシュ値の検証と同等の機能
比較対象をメモリにおいて単純にmemcmp() するより高速
残念ながら、タグ (SHA-256 ハッシュ値のようなもの) 生成は超遅く、しかもそれなりに大きい
興味ある人は「SCIS2007 1C2-3 高速データ検証」を見て下さい。
Copyright 2012 c NTT – p.24/35

共通鍵暗号の実装
ブロック暗号限定ということで (その他の実装経験はないので)
1 単位は数百 cycle

対象暗号毎、x86 のコアのアーキテクチャ毎にかなりの違い
一般論: (self-)bitslice, 等価変形, 副鍵埋め込み, T-box, エンディアン変換
個別: SWAPMOVE, 4-bit table (pshufb)
Copyright 2012 c NTT – p.25/35

bitslice 実装
64(32) ビットレジスタを 1-bit が 64 並列のSIMD と思う

全ての演算を and, or, xor などの論理式で速くなればラッキー (鍵の全数探索とか)実行時間が命令には依らなくなる (cacheとかの影響少)最適化対象によっては、1(暗号化) 単位の中で bitslice できることもある(self-bitslice)
Copyright 2012 c NTT – p.26/35

等価変形による依存性緩和
仕様通りではなく、同じ結果を得る違う計算 (順序) を考える
Feistel 構造 (1 ≤ i ≤ 16 とか):(Li+1 ← f (Li ⊕ ki) ⊕ Ri
Ri+1 ← Li⇓(Li+1 ← f (Li) ⊕ Ri ⊕ (ki−1 ⊕ ki+1)
Ri+1 ← Li
Copyright 2012 c NTT – p.27/35

副鍵埋め込み
通常、共通鍵ブロック暗号は、秘密鍵を鍵スケジューリングというものを用いて副鍵に変形し、暗号化では副鍵のみを用いる
多ブロックの暗号化では副鍵の実行コードへの埋め込みが有利
最近は χbyak とかがあり便利

Copyright 2012 c NTT – p.28/35

副鍵埋め込み例
関係箇所のみ抽出
NASM%macro SMcamelliaRound 7
global Camelliak%5r
xor esp, 0x89abcdef
Camelliak%5r:%endmacro
C 言語から#define OFFSET(label) ((uint32 t)&(label) -\(uint32 t)SMcamelliaEnc128)
extern uint32 t Camelliak1r;
memcpy(code, SMcamelliaEnc128,OFFSET(endOfSMcamelliaEnc128));(uint32 t*)&code[OFFSET(Camelliak1r)-4]=r[2];Copyright 2012 c NTT – p.29/35

T-box 実装
AES などの byte-oriented 暗号は、1 バイト→4 バイトとかの表 Ti [] と論理演算の組合せが多い。平文データを (eax, ebx, ecx,edx) にもち

movzx esi, almovzx edi, ah
xor ebp, T0[4*esi]
xor esp, T1[4*edi]
rol eax, 16
movzx esi, almovzx edi, ah
xor ebp, T2[4*esi]
xor esp, T3[4*esi]

といった処理の繰返し。
Copyright 2012 c NTT – p.30/35

endian 変換
32 ビットデータ x の endian 変換(x ≪ 24) + ((x&0xff00) ≪8) + ((x ≫ 8)&0xff00) + (x ≫ 24)

Copyright 2012 c NTT – p.31/35

endian 変換
32 ビットデータ x の endian 変換(x ≪ 24) + ((x&0xff00) ≪8) + ((x ≫ 8)&0xff00) + (x ≫ 24)((x&0xff00ff) ≫ 8) + ((x ≪8)&0xff00ff)

Copyright 2012 c NTT – p.31/35

endian 変換
32 ビットデータ x の endian 変換(x ≪ 24) + ((x&0xff00) ≪8) + ((x ≫ 8)&0xff00) + (x ≫ 24)((x&0xff00ff) ≫ 8) + ((x ≪8)&0xff00ff)
bswap

Copyright 2012 c NTT – p.31/35

SWAPMOVE
SWAPMOVE(A,B,N,M)

T = ((A ≫ N ) ⊕ B)&M ;B = B ⊕ T;
A = A ⊕ (T ≪ N );B の M で mask されたビットが、A のM ≪ N で mask されたビットと入れ替わる
DES の IP/FP は SWAPMOVE 5 回
行列転置とかでも便利punpck の一般形

Copyright 2012 c NTT – p.32/35

pmovmskb
DES IP:0 1 2 3 4 5 6 762 54 46 38 30 22 14 660 52 44 36 28 20 12 48 9 10 11 12 13 14 1558 50 42 34 26 18 10 216 17 18 19 20 21 22 2324 25 26 27 28 29 30 3156 48 40 32 24 16 8 032 33 34 35 36 37 38 39→ 63 55 47 39 31 23 15 740 41 42 43 44 45 46 47
61 53 45 37 29 21 13 559 51 43 35 27 19 11 348 49 50 51 52 53 54 5557 49 41 33 25 17 9 156 57 58 59 60 61 62 63
pmovmskb 8 回と位置合わせで完了

興味ある人は「SCIS2002 12C2-2 Pentium III 上の Triple DES 実装最適化記」参照のこと
Copyright 2012 c NTT – p.33/35

4-bit table lookup
SSSE3 で pshufb 命令が追加された!

t[0], t[1], . . . , t[15]xmm1: x0 , x1 , . . . , x15⇓pshufb xmm0, xmm1
xmm0: t[x0 ], t[x1 ], . . . , t[x15 ]xmm0:

定数時間実行
GF(28) ∼= GF(24 )[x]/(2 次既約式) を利用した x−1 の計算などの応用。
Copyright 2012 c NTT – p.34/35

まとめ

Copyright 2012 c NTT – p.35/35

まとめ
結局はスケジューリング

Copyright 2012 c NTT – p.35/35

まとめ
結局はスケジューリング
Out-Of-Order 嫌い。直接 µop 書きたい。

Copyright 2012 c NTT – p.35/35

まとめ
結局はスケジューリング
Out-Of-Order 嫌い。直接 µop 書きたい。

個別技ばっかり。研究者としては体系化したいんだけど。(せめて Hacker’s delight程度には)Copyright 2012 c NTT – p.35/35

まとめ
結局はスケジューリング
Out-Of-Order 嫌い。直接 µop 書きたい。

個別技ばっかり。研究者としては体系化したいんだけど。(せめて Hacker’s delight
程度には)
AES-NI で玉砕

Copyright 2012 c NTT – p.35/35

まとめ
結局はスケジューリング
Out-Of-Order 嫌い。直接 µop 書きたい。

個別技ばっかり。研究者としては体系化したいんだけど。(せめて Hacker’s delight
程度には)
AES-NI で玉砕

一子相伝にならないようにするには…

Copyright 2012 c NTT – p.35/35