セキュリティキャンプ 修了生進捗 #seccamp OB/OG Advent Calendar 2018 2日目.
この記事はセキュリティ・キャンプ全国大会2018で実装したTLS1.3(の筆者が担当した暗号部分)の再実装と解説を目的としている.
なんだこれは を読み返すと意味がわからなくなったので, これを機におさらいをする.
表記揺れについて
許して
どうやって実装するの??
chacha20-poly1305の実装を詳しく解説している日本語のドキュメントはあまりない. この記事を読めば理解できる(はず). 多分これが一番わかりやすいと思います
RFCでところどころさんtest vectorが用意されているので, 新しく実装した部分はちゃんとテストしておくとよい.
Chacha20-Poly1305
Chacha20-Poly1305は暗号スイートの一種で, Chacha20(暗号化)とPoly1305(認証タグの生成)を組み合わせて使用する.
Chacha20
公開鍵暗号のストリーム暗号に分類されるアルゴリズムである.
ステート(state)と呼ばれるバイト列を使い, 平文とXORを取ることで暗号化する.
以下にChacha20のstateを示す.
ステートを見るとまるでブロック暗号かのように思えるが, 任意長の平文を暗号化できパディングも必要ない. つまりストリーム暗号である.
ステートのブロックはそれぞれ 4 [Bytes] だが, 注意すべきはcounter以外はリトルエンディアンであること.
たとえばnonceとして0123456789AB を渡すと, stateでは
nonce1 = 3210 nonce2 = 7654 nonce3 = BA98
となる.
counterはビッグエンディアンでよいので counter=1は \x00\x00\x00\x01 になる.
上で示したstateはあくまで初期状態で, 暗号化に使われるstateは初期状態をもとにごちゃ混ぜにされる(といっても計算を施すだけだが).
Quarter Round
stateを変化させる計算を行う関数Quarter Roundについて.
Quarter Roundは4つの引数をとり足し算, XOR, bitローテーションを行う.
ただしステートは4 Bytes/block であることに注意(& 0xFFFFFFFFをすればよい).
1. a += b; d ^= a; d <<<= 16; 2. c += d; b ^= c; b <<<= 12; 3. a += b; d ^= a; d <<<= 8; 4. c += d; b ^= c; b <<<= 7;
ステートを4 × 4 の行列と見立て(上記画像参照), 列要素ごとに4回, 対角要素ごとに4回行いこれを10回繰り返す.
Chacha20の20は
(Quarter Round(列要素) × 4 + Quarter Round(対角要素) × 4) × 10 = 20
から来ている.
1. QUARTERROUND ( 0, 4, 8,12) 2. QUARTERROUND ( 1, 5, 9,13) 3. QUARTERROUND ( 2, 6,10,14) 4. QUARTERROUND ( 3, 7,11,15) 5. QUARTERROUND ( 0, 5,10,15) 6. QUARTERROUND ( 1, 6,11,12) 7. QUARTERROUND ( 2, 7, 8,13) 8. QUARTERROUND ( 3, 4, 9,14)
1~4が列要素, 5~8が対角要素のQuarter Roundで, 引数はstateのインデックスを表す.
10回繰り返した時点でstateはごちゃ混ぜにされているが, これに初期状態のstateを足し合わせてようやく完成.
擬似コードは以下のように示されている. 参照 - The ChaCha20 Block Function in Pseudocode
inner_block (state):
Qround(state, 0, 4, 8,12)
Qround(state, 1, 5, 9,13)
Qround(state, 2, 6,10,14)
Qround(state, 3, 7,11,15)
Qround(state, 0, 5,10,15)
Qround(state, 1, 6,11,12)
Qround(state, 2, 7, 8,13)
Qround(state, 3, 4, 9,14)
end
chacha20_block(key, counter, nonce):
state = constants | key | counter | nonce
working_state = state
for i=1 upto 10
inner_block(working_state)
end
state += working_state
return serialize(state)
end
ここまでで暗号化に使用されるバイト列が生成できた. あとは平文とXORを取ればよい.
同じkey, nonceを使うと必ず同じstateが得られるので暗号文とXORを取れば復号が可能.
64バイトを超えた場合について.
The ChaCha20 Encryption Algorithm in Pseudocode
chacha20_encrypt(key, counter, nonce, plaintext):
for j = 0 upto floor(len(plaintext)/64)-1
key_stream = chacha20_block(key, counter+j, nonce)
block = plaintext[(j*64)..(j*64+63)]
encrypted_message += block ^ key_stream
end
if ((len(plaintext) % 64) != 0)
j = floor(len(plaintext)/64)
key_stream = chacha20_block(key, counter+j, nonce)
block = plaintext[(j*64)..len(plaintext)-1]
encrypted_message += (block^key_stream)[0..len(plaintext)%64]
end
return encrypted_message
end
counterを1ずつ増やしながら新しくstateを得, 同じように暗号化するだけ.
counterの初期値は1であることに注意(counter=0はPoly1305で使用).
Poly1305
Poly1305は認証用のメッセージと鍵(32 [Bytes]を使って認証タグ(16 [Bytes])を生成する.
Chacha20のステートを利用してPoly1305の鍵を取得するためChacha20を先に実装しておく必要がある.
鍵生成の流れとしては,
- chacha_key, nonceを準備
- これらを使ってChacha20のstateを得る(counter=0)
- r = state[0 .. 15], s = state[16 .. 31] をPoly1305の鍵とする
stateのはじめの4ブロックが "r", 次の4ブロックが "s"
鍵r, sそれぞれ16バイトのリトルエンディアンになることに注意しよう. 4バイトではない.
また, rはリトルエンディアンとして値を得てからclamp関数を適用し, 部分的にビットを落として利用する.
clamp関数の定義を以下に示す.
clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
鍵を取得したらあとはタグを計算するだけである. 参照 - The Poly1305 Algorithms in Pseudocode
poly1305_mac(msg, key):
r = (le_bytes_to_num(key[0..15])
clamp(r)
s = le_num(key[16..31])
accumulator = 0
p = (1<<130)-5
for i=1 upto ceil(msg length in bytes / 16)
n = le_bytes_to_num(msg[((i-1)*16)..(i*16)] | [0x01])
a += n
a = (r * a) % p
end
a += s
return num_to_16_le_bytes(a)
end
まずkeyからr, sに切り分ける.
次にAccumulatorとModulus pを定義する. pは2130 - 5という16 [Bytes]よりも少し大きな素数である.
msgを16バイトに切り分け, それぞれの末尾に0x01をくっつける. 最後のmsgが16バイトに満たない場合は気にせずそのまま0x01をくっつけてよい.
0x01をくっつけたバイト列をリトルエンディアンで数値に変換し順に計算を行う.
切り分けた全てのmsgに対して計算を行い, 最後に鍵sを足し合わせてタグの生成終了.. と思いきやまだ終わらない.
Accumulatorに s を足したものをまずは16バイトにそろえる必要がある(pが128 [Bits]を超えていることに注意).
mod 2**128 を取るか AND 0xFFFF...FF を取ろう.
あとはこの値をリトルエンディアンでバイト列に変換して終了となる.
Poly1305の安全性
Poly1305は認証タグを生成し, これはいわゆるハッシュ関数のようなものだがmd5やSHA1/SHA2のような純粋なハッシュ関数と異なるのはメッセージの他にkeyを使用する点である.
これが何を意味するかと言うと, たとえば純粋なハッシュ関数H_FUNCを使用する場合
H_FUNC(data) = ハッシュ化された攻撃対象(解読したい)のメッセージ
となるdataを総当たり等で発見できた時, 攻撃が成功したことが明らかになる(ハッシュ衝突が起こり得ない空間であるとして).
対してPoly1305はメッセージが同じでもkeyが異なれば異なるハッシュ値を出力するため
Poly1305(data, key) = ハッシュ化された攻撃対象(解読したい)のメッセージ
となるdata, keyの組み合わせが万一発見できたとしても data = 攻撃対象のメッセージ である可能性は低い.
AEAD
暗号化と同時に認証タグを生成する.
Chacha20とPoly1305の実装ができていればタグの生成は難しくない.
chacha20_aead_encrypt(aad, key, iv, constant, plaintext):
nonce = constant | iv
otk = poly1305_key_gen(key, nonce)
ciphertext = chacha20_encrypt(key, 1, nonce, plaintext)
mac_data = aad | pad16(aad)
mac_data |= ciphertext | pad16(ciphertext)
mac_data |= num_to_4_le_bytes(aad.length)
mac_data |= num_to_4_le_bytes(ciphertext.length)
tag = poly1305_mac(mac_data, otk)
return (ciphertext, tag)
constant [4 Bytes] + iv [8 Bytes] をnonceとし, このnonceとkeyを使ってPoly1305のOne Time Keyを生成する.
次にChacha20を使って暗号化(使用するnonceとkeyはさっきと同じ)しciphertextを得る.
ciphertextが得られたらmac_dataを組み立てていく.
最後にmac_dataをmsg, One Time KeyをkeyとしてPoly1305で認証タグを生成する.
???
実はRFCに問題がある. Pseudocode for the AEAD Construction
擬似コードの後にtest vectorがあり,そこでは mac_data となる部分が
AEAD Construction for Poly1305:
000 50 51 52 53 c0 c1 c2 c3 c4 c5 c6 c7 00 00 00 00 PQRS............
016 d3 1a 8d 34 64 8e 60 db 7b 86 af bc 53 ef 7e c2 ...4d.`.{...S.~.
032 a4 ad ed 51 29 6e 08 fe a9 e2 b5 a7 36 ee 62 d6 ...Q)n......6.b.
048 3d be a4 5e 8c a9 67 12 82 fa fb 69 da 92 72 8b =..^..g....i..r.
064 1a 71 de 0a 9e 06 0b 29 05 d6 a5 b6 7e cd 3b 36 .q.....)....~.;6
080 92 dd bd 7f 2d 77 8b 8c 98 03 ae e3 28 09 1b 58 ....-w......(..X
096 fa b3 24 e4 fa d6 75 94 55 85 80 8b 48 31 d7 bc ..$...u.U...H1..
112 3f f4 de f0 8e 4b 7a 9d e5 76 d2 65 86 ce c6 4b ?....Kz..v.e...K
128 61 16 00 00 00 00 00 00 00 00 00 00 00 00 00 00 a...............
144 0c 00 00 00 00 00 00 00 72 00 00 00 00 00 00 00 ........r.......
このようになっている.
末尾の num_to_4_le_bytes(aad.length) と num_to_4_le_bytes(ciphertext.length) だが, test vectorでは4バイトではなく8バイトのリトルエンディアンである.
どちらが正しいのかを確認するためにopensslのchacha20_aeadのソースを漁ったが見つからなかった.
というか書いてあった.
* The length of the additional data in octets (as a 64-bit
little-endian integer).
* The length of the ciphertext in octets (as a 64-bit little-
endian integer).
リトルエンディアンの8バイトが正しい.
まとめ
以下にコードを示した.
基本的にはRFCの擬似コードを元にしているので擬似コードを模倣すれば任意の言語でChacha20-Poly1305が実装可能である.
擬似コードを読み返すと結構穴があるので, 実装でわからないことがあればRFCを読むか筆者にmentionを飛ばしてくれれば解決できると思う.
実際のコード
Gistで公開している.
ファイルごとに各節で表示したかったのだが..
ファイルは上から順に
- aead_enc.py : chacha20, poly1305を使用してAEADを生成
- calc.py : 主にchacha20で使用される計算の関数群
- chacha20.py : Chacha20の実装
- poly1305.py : Poly1305の実装
- test.py : テストコード, RFCのtest vectorをクリア済
- utils.py : utils
使用したモジュールはstructとbinasciiiのみ.
追記
こちら(Golangで暗号化されたsocket通信をする)にGolangを使ってChacha20-Poly1305を再再実装した記事を書きました.
