はじめに
実装して理解する暗号技術シリーズです。
ChaCha20-Poly1305 を理解したいので、Poly1305をやっていきます。ChaCha20は以前理解済みなので気になる方はそちらもみてね
仕様など
Poly1305 は RFC8439 ChaCha20 and Poly1305 for IETF Protocols で標準化されています。
元ネタは Daniel J. Bernstein , "The Poly1305-AES message-authentication code", 2005 の論文なんだけどそこで使われてるワンタイム認証関数である Poly1305 がコスト軽いので、暗号アルゴリズムをChaCha20、ワンタイム認証をPoly1305を使い、組み合わせていい感じのAEAD(Authenticated Encryption with Associated Data: 認証付き暗号)として使おう！となったのが先述のRFCです。
こいつの全体像を最終的には理解したいんだけど、まずは Poly1305 からやっていきます。
Poly1305 概要
ワンタイム認証のアルゴリズムで、もともとは Poly1305-AES でAESとセットで利用される想定でした。ワンタイム認証部分が早くて便利だったので、他のアルゴリズムとも組み合わされたりしています。有名なのはさっきも紹介した ChaCha20-Poly1305 など。
メッセージを突っ込むと(内部で秘密鍵と一緒に渡されて)対応する認証タグが吐かれる構造になっています。 検証者は、期待する認証タグと一致するかを調べれば改竄などが検出できる、という感じです。
詳細は先述の RFC8439 Section-2.5 あたりを見るのがわかりやすいんだけど、ほかにもわかりやすいのがあります！
Go の暗号周りの標準、準標準はめちゃめちゃ手が行き届いてることで有名で、もちろん Poly1305 も準標準で実装がある。便利だね〜
Go は構文が複雑でなく、コメントに元ネタへのリンクなども貼ってくれがち！アルゴリズムの学習にピッタリ！
https://cs.opensource.google/go/x/crypto/+/master:internal/poly1305/sum_generic.go
のっけにコメントがある
// Poly1305 [RFC 7539] is a relatively simple algorithm: the authentication tag // for a 64 bytes message is approximately // // s + m[0:16] * r⁴ + m[16:32] * r³ + m[32:48] * r² + m[48:64] * r mod 2¹³⁰ - 5 // // for some secret r and s. It can be computed sequentially like // // for len(msg) > 0: // h += read(msg, 16) // h *= r // h %= 2¹³⁰ - 5 // return h + s // // All the complexity is about doing performant constant-time math on numbers // larger than any available numeric type.
めっちゃ簡単やんけ！ようはメッセージを 16 bytes ごとにチャンクして、+=, *= して mod とる操作を各ブロック繰り返す、最後に s を加算する、これで出力されるのが認証タグや！と言っています。
これが可能なのは剰余演算は分配則が成り立つので、演算中逐一やっても最後にまとめてやっても等価だからですね。
この h + s (mod 2130 -5) をちょっと加工したら認証タグ！がベースの考えです。めっちゃ簡単
RFC の疑似コードをそのまま引用すると以下です
clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
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
clamp とかいう謎のビットマスクとる箇所ありますが、これは当時計算の効率化などを目的に入れたようです。 le_bytes_to_num はリトルエンディアンでバイト列を数値としてパースするだけです。
これをみると、さっきの流れでメッセージを 16 bytes ごとに読んで多項式の評価をしていって、最後に h + s して下位 16 bytes が認証タグになるんや！と言っています。
かんた〜ん
clamp 処理の意図、背景
疑似コードの clamp を思い出してください
clamp(r): r &= 0x0ffffffc0ffffffc0ffffffc0fffffff
特定位置にビットマスクをかけていそうです。RFCみると特に意図記載されてないですが、背景が気になります。
元の論文読むと演算の簡素化、高速化のため〜みたいな言及がされていました。 このマスクによってとりうる値の空間は狭まり 2106 まで下がってしまいます。が、十分広い空間だし演算が速い方がいいでしょ〜みたいなことが書かれていました。
なぜ高速化するのか？の理由についてはあまり説明されていなかったものの、いくつかの bit を落として空間を狭めているのでとりうる値の bit 長も狭まっているはずで、たとえば carry なんかの処理が減ってるのかもしれません。4byte 周期のマスクなのでそのあたり意味がありそうな気がしています。もうちょい調べてみます。
なぜ成立するか
ようは攻撃者が秘密情報である r を知らない状態で、ある別の m' の認証タグ T' を作りたいとき、それが計算量的安全であれば自前で認証タグをでっちあげるのが困難とかんがえてよいです。
元論文の証明を斜め読みした感じだと
あたりの性質を利用してランダムに r を選んだ時にそれが正しいものである確率は十分低いという主張をしてそうでした。条件を満たすケースは高々Nこくらいだから〜みたいな。
ここは元論文の Theorem 3.3. あたりが核心っぽいんですが、まだちゃんと読んでないので理解したら追記する予定
実装
いうて普通に疑似コードの内容を実装するだけ！以下実装で sum がおおよそ本体
package poly1305 import ( "encoding/binary" "math/big" ) const blockSize = 16 var p = new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 130), big.NewInt(5)) type MAC struct { r *big.Int s *big.Int } func New(r, s [16]byte) *MAC { m := &MAC{} rBytes := make([]byte, 16) copy(rBytes, r[:]) rBytes[3] &= 0x0f rBytes[4] &= 0xfc rBytes[7] &= 0x0f rBytes[8] &= 0xfc rBytes[11] &= 0x0f rBytes[12] &= 0xfc rBytes[15] &= 0x0f m.r = readLittleEndian(rBytes) m.s = readLittleEndian(s[:]) return m } func readLittleEndian(b []byte) *big.Int { result := new(big.Int) for i := 0; i < len(b); i += 8 { end := min(i+8, len(b)) chunk := make([]byte, 8) copy(chunk, b[i:end]) val := binary.LittleEndian.Uint64(chunk) shifted := new(big.Int).SetUint64(val) shifted.Lsh(shifted, uint(i*8)) result.Or(result, shifted) } return result } func writeLittleEndian(dst []byte, val *big.Int) { for i := 0; i < len(dst); i += 8 { v := new(big.Int).Rsh(val, uint(i*8)).Uint64() binary.LittleEndian.PutUint64(dst[i:i+8], v) } } func (h *MAC) Size() int { return 16 } func (m *MAC) Sum(msg []byte) []byte { a := big.NewInt(0) for i := 0; i < len(msg); i += blockSize { end := i + blockSize if end > len(msg) { end = len(msg) } block := msg[i:end] nBytes := make([]byte, len(block)+1) copy(nBytes, block) nBytes[len(block)] = 0x01 n := readLittleEndian(nBytes) a.Add(a, n) a.Mul(a, m.r) a.Mod(a, p) } a.Add(a, m.s) // 下位128ビットだけを取得 mask := new(big.Int).Sub(new(big.Int).Lsh(big.NewInt(1), 128), big.NewInt(1)) a.And(a, mask) result := make([]byte, 16) writeLittleEndian(result, a) return result }
テストとかも見たい方はこちらに全体があります！
感想
- Poly1305 やってる操作は大体理解した
- なぜ攻撃者が認証タグを偽装するのが困難なのか、についてはちゃんと証明読みたいな〜
- 材料は揃ったので、これで ChaCha20-Poly1305 やれるぞ
つぎは ChaCha20-Poly1305 をやり！ます！
