本記事は 暗号学一人アドベントカレンダー 第8日目(相当)の記事です。
この内容も2回に分けます。今回はSHA-3のコンテストに残らなかったBLAKE)とそこで使われているHAIFA Constructionの話をします。
Merkle-Damgård構造の何がマズいか
先の記事でも触れたように、MD5, SHA-1, SHA-2はすべて共通してMerkle-Damgård構造を用いたハッシュ関数でした。1979年に発表されて以来長らくハッシュ関数に使われてきたこの構造ですが、いくつかの問題があることが明らかになってきました：
- 長いメッセージに対する第二原像攻撃が理論値よりも少ない計算量で可能である。Kelsey and Schneier, 2004によるとn-bitのハッシュにおける2kブロックのメッセージに対して第二原像攻撃が\(k \times 2^{\frac{n}{2}+1} + 2^{n-k+1}\)の計算量（理論値は\(2^{\frac{n}{2}}\)）。
- 一つの衝突が見つかれば複数の衝突をもっと少ない計算量で見つけることができる。
- 伸長攻撃に弱い。H(X)とlen(x)が既知のとき、H(pad(X) || Y)を計算できる、という性質。CTFなどでの出題例が多い最もよく知られている性質。
SHA-3の選択においては、これらの弱点を回避するためMerkle-Damgård構造でないハッシュ関数がいくつも提案されました。そのうち、今回はHAIFA構造を使ったBLAKE、次回は実際に選定されたスポンジ構造を用いたKeccakを見ていきます。
HAIFA構造
Merkle-Damgård構造では \( C_{MD} : \{0,1\}^{m_c} \times \{0,1\}^n \to \{0,1\}^{m_c} \) （m_cは次の圧縮関数にchainする値の長さ、nは圧縮関数のブロック長。だいたいの場合m_c = m）という形式の圧縮関数を使うのに対し、HAIFA構造では \( C_{HAIFA} : \{0,1\}^{m_c} \times \{0,1\}^n \times \{0,1\}^b \times \{0,1\}^s \to \{0,1\}^{m_c} \)という形の関数を使い、\(h_i = C(h_{i-1}, M_i, \#bits, salt) \) として途中状態を計算します。違いとしては、「今までハッシュ化したビット数」をハッシュ化の過程で含めることと、saltを付与することです。
ハッシュ化するには、「paddingを付与（この際にメッセージ長と最終出力の長さが含まれる）」→「初期値\(IV_m = C(IV, m, 0, 0)\)を計算する」→「saltと初期値を使ってCを繰り返し計算する」（新たなメッセージがpaddingの後ろに付く場合には#bitsを0として計算する）→「必要な長さに切り詰める」という手順を取ります。
ここで、今までハッシュしたbit数が関数に含まれることでいくつかの攻撃が無効化できます。まず、圧縮関数の不動点を利用した攻撃が困難になります。C(h, M, #bits, salt)の不動点を見つけたところで、それを複数回利用することは#bitsの値が変わってしまうためできません。
また、paddingの後ろにメッセージが新たに付く場合は#bitsを0として計算し直すため、伸長攻撃も成立しなくなります。
BLAKE
SHA-3公募の最終候補になったBLAKE（リンクはドキュメント）は圧縮関数としてストリーム暗号のChaChaを使ったHAIFA構造のハッシュ関数です。
BLAKE-256を例に取ると、8ワードのchain value h、16ワードのメッセージブロックm、4ワードのsalt sと2ワードのカウンターを使って\(h' = C(h, m, t, s)\)*1として計算します。この圧縮関数ではChaChaの1/4ラウンド（にメッセージmの加算が追加され、bitwise rotationの向きが逆になったもの）を「h, t, sから作った4x4ワードの初期値の行列」の列と対角線上の要素に対して適用していきます。
現在では改良版であるBLAKE2のほうがよく使われるようです。Argon2は内部でBLAKE2を使っています。
続けて次回がSHA-3に採用されたKeccakとスポンジ構造の予定です。
*1:ドキュメントではh, m, s, tと書いているが、HAIFA論文に出てくる順番と揃えるため順序の入れ替えをした
