(9) Non-Merkle-Damgård Hash part2: Sponge construction and SHA-3(Keccak)

本記事は 暗号学一人アドベントカレンダー 第9日目(相当)の記事です。

前回に引き続き、SHA-3公募で現れた新しい構造のハッシュ関数について、今回は実際にSHA-3に選ばれたKeccakとそれに用いられるスポンジ構造(リンクはPDF)の話です。

スポンジ構造

Keccakで用いられるスポンジ構造(sponge construction)は名前がその実態の一部を表しているという意味でとても直感的に理解できるのではないでしょうか。スポンジに入力を「吸収」(absorb)して内部状態を作り出し、そこから「搾出」(squeeze)することによって最終出力を得る、という動作をします。これだけ書いたらほんとにそんなことができるのかとなりますが、実態を見ると確かにその説明は非常に納得が行きます。

「スポンジ構造」は可変長の入力を受け取り、任意の長さの出力を得る関数を作る構造です。その内部では固定長の変換(transformation)もしくは置換(permutation)が使われます。この変換fの引数長bが内部状態の長さになります。内部状態はouter stateとinner stateにわけられ、それぞれの大きさをbitrate(rとおきます)とcapacity(cとおきます)と呼び、b = r + cが成立します。

吸収フェーズ(absorbing phase)ではパディングを行ったメッセージブロックをrビットずつにわけ、内部状態の先頭r bitのouter stateとXOR演算を行い、(outer state XOR message block) || inner stateのbバイトの文字列を変換fにかけます。これを文字列の終端まで行うのが吸収フェーズです。その後の搾出フェーズ(squeezing phase)では内部状態の最初のrビット(つまりouter state)が出力され、outer state || inner stateをfにかけたものが次の内部状態となり、必要な長さが得られるまでそれを繰り返します。

パディングについて

スポンジ構造で有効なパディングになるためには(式2.1)、パディング方式pad(M)が、2つの異なるメッセージM, M'に対して常に「M || pad(M)」と「M' || pad(M) || (0で埋められた任意の数のブロック)」が一致しないという結果を返す必要があります。直感的には「末尾に0だけの余計なブロックがつかない」という性質です。これを満たすようなパディング方式は2つ提示されています:

  • pad10* : Mの末尾に1を付加し、その後全体がブロック長の倍数になるまで0で埋める。
  • pad10*1 : Mの末尾に1を付加し、その後「0で埋めて最後に1を付加したもの」の全体がブロック長の倍数になるようにする。Keccakではこちらが使われています。

伸長攻撃ができない

伸長攻撃とはH(X)とlen(X)がわかっているとき、H(pad(X) || Y)が計算可能であるときに成立します。ここで、Merkle-Damgård構造ではH(X)は内部状態の構築が終わった値そのものが出力されているので、その後ろに適切なpaddingを施せばH(pad(X) || Y)は内部状態H(pad(X)) = H(X)で始めてYを順次圧縮関数にかけていくことで計算できてしまいます。

一方、スポンジ構造ではH(X)の計算後の内部状態にそのままYを連結してH(pad(X) || Y)を計算することができません。その理由は、H(X)を計算するためにはXを「吸収」しきったあとに一定の長さを得るまで「搾出」を続けないといけないためです。Xを「吸収」することによって得られる内部状態をH(X)から予想することは困難なので、結果としてH(X)の値を使ってH(pad(X) || Y)を計算することができなくなっています。

内部状態の衝突の困難性へのcapacityの大きさの影響

非常に簡略化した説明として、

  • inner stateの衝突を得る、つまり \(\widehat{absorb}(P) = \widehat{absorb}(Q)\) *1 なる相異なるP, Qの組を得られる確率は、fが理想的な変換である場合\(\frac{1}{2^c}\)
  • inner stateの衝突が得られた場合、\(\overline{absorb}(P) \oplus A = \overline{absorb}(Q) \oplus B\)となるようなA, Bを見つければinner stateだけでなくstate全体の衝突が得られる。

…という感じで(実際はもっと厳密な証明がある)、衝突のさせにくさはinner stateの大きさ=capacityに依存することがわかります。

Keccak

SHA-3では1600ビットの入力を受け取る置換が使われています。この変換は記述するだけでかなりしんどいので、実際に使われている置換関数Keccak-f/Keccak-pは実際のFIPS 202標準ドキュメント の3章をご参照ください…。SHA-3としては224/256/384/512ビットのdigestを出力する関数がそれぞれ定義されていますが、それぞれのスポンジ構造のcapacityはdigest長の2倍で定義されています。


ここで書いた他にもSHA-3には興味深い性質があり、Keccak TeamのWebサイトにはそれらがブログ形式で紹介されていますが今回まとめきれなかったのでアドベントカレンダー外で紹介するかもしれません。

*1:hat notationはinner stateを表し、bar notationはouter stateを表す