SHA-3に選出されたKaccakのスポンジ関数方式

大学の講義で暗号論をかじったくらいの知識で解説してみる。

SHA-3コンペで選出されたKaccakは、旧来の構造とは異なるスポンジ関数という考え方で構築されている。

古い設計のハッシュ関数は、入力圧縮関数、内部状態バッファ、撹拌関数で構成されていた。（丸めやパディングのような雑多な処理は略す）
入力圧縮関数は、撹拌関数の呼び出し回数を減らすため、また前処理として大きな入力ブロックを内部状態サイズ以下に不可逆に縮めるために使われ、
可能な限り撹拌関数の対象となる内部状態サイズ＝必要レジスタ数を小さくして、その分撹拌関数一回あたりの複雑性を高めることで安全性を担保しようとした。

http://sponge.noekeon.org/
一方スポンジ関数方式では、大きな内部状態＝スポンジを用い、複雑な圧縮関数を不要にする。入力は単に、内部状態の一部（例えばKeccakでは1600bit中の1024bit）にXORするような方法で行われる。最後に出力圧縮関数を使う場合もあるが、keccakのように単純な切り出しで十分と考えられているようだ。
この場合、バッファサイズの大きさが増えるが、撹拌関数の複雑性・計算量を無理に増やす必要はないようだ。
非線形な圧縮関数を用いず、撹拌関数と内部状態の余裕分に安全性を担保してもらう形になる。

昔はハードウェアレジスタがとても高価だったため、内部状態を小さくすることは至上命題だったかもしれない。
現在では、ASICや高速な一次キャッシュが十分安価になっているので、内部状態を小さくする利点よりも、高速かつ単純な撹拌関数を利用する利点の方が勝ったということと思われる。非線形性をワード内rotとワード置換のみで実現している点などが評価されたか。

メリット

内部状態の大きさはが出力可能なハッシュサイズを決定するので、内部状態のサイズを切り詰めていた旧来の方式では、内部状態のサイズ自体を変更しなければならず、圧縮・撹拌関数の計算式が出力サイズによって異なった。SHA-256とSHA-512は内部が違う上、計算コストが急激に増えた。

スポンジ関数方式なら将来必要になった時に、同じ撹拌関数を用いて、入出力するブロックサイズを任意に変更できる。例えばkaccakなら仕様上1024bitまでのブロックサイズでそのまま利用でき、出力ビット数もブロックサイズ以上にできる。実質的に計算量は変わらず、原理的には安全性の検証をブロックサイズ毎に行う必要が無く、単純に算出できるものと思われる。
またkeccakは5x5xWord長という可変サイズの内部状態に対してほぼ同じ関数を使える。（rijndaelからAESの256bitブロック固定のように最終的に64bitword固定で規格化されると思うけど。）

もうひとつ利点があり、撹拌関数を都度取り出すことでストリーム暗号に仕立てることが、ほぼ同じ実装だけでIO増加以外の性能劣化なしに可能になる。出力ブロックに対して内部状態が十分大きいなら、内部状態の全体の逆算は困難で、安全である可能性が高い。
独立した暗号化と鍵精製関数を使うよりも、スポンジ関数にsalt+パスワード＋padを入力し、残りは入力ブロックの替りにカウンタを入れて出力ブロックをCTRモード暗号として扱う、といった単純な実装で安全に利用できる可能性がある。SHA-3で規格化されることは無いだろうが、ハッシュと暗号化を統合できるかもしれない。

デメリット
素人に思いつくのはせいぜい必要レジスタ数で実装コストが増えることくらいか。
構造が単純な分懐石も検証もしやすいかもしれない。一般に非線形置換・rotで十分安全と考えられているようなので、単純に性能を犠牲にラウンド数を増やされるかも、程度に思う。

トレードオフ
撹拌関数のラウンド数の他、スポンジ関数の内部状態レジスタにどの程度余裕をもたせるか（一回に出し入れする入出力サイズと、手を加えない残り自由度。図のrとc）で性能が変わる。
余裕を減らしてブロックサイズを大きくすれば計算速度は早くなるが、衝突が発生しやすくなる。（内部状態を推定・制御しやすくなる）

ブロックサイズ1024bit＋576bitで1600bitのバッファ、出力サイズ576bitで、2^-288の衝突耐性がデフォルトのようだ
http://keccak.noekeon.org/tune.html
ブロックを減らせば第二原像の算出可能性が下がるが、撹拌関数の呼び出しが増えるのでrに反比例して性能が下がる。

SHA-3規格化時点でこれも数通りに固定されると思うしそれを使えば安全だろうけれど、自由度が大きいぶん、実装が下手なパラメータを許容するとかやらかしそう。