SHA-3・Keccakのスポンジ関数の利点のまとめ

Keccakをもう少しよく見てみた感想。スポンジ関数はなるほどよくできている。
以前のエントリ、 Keccak自体は「SHA-3に選出されたKaccakのスポンジ関数方式」http://causeless.seesaa.net/article/295263150.html
を参照。

前提として、ハッシュ関数の耐性の分類

強衝突耐性
ハッシュCについて、C=H(M1)=H(M2)となる異なる2つのメッセージM1とM2を推定できないこと。
言い換えると、秘密のメッセージM1のハッシュC1=H(M1)について、C1だけが与えられた時、H(M2)==C1になるようなメッセージM2を推定できないこと。

弱衝突耐性
メッセージM1が与えられた時、H(M1)＝C1＝H(M2)となるようなM1と異なるメッセージM2を推定できないこと。

第二原像困難性
秘密のメッセージM1のハッシュC1=H(M1)について、C1だけが与えられた時、C1=H(M)ないかなるメッセージMを推定出来ないこと。（MはM1と違っても良い）

第一原像困難性
秘密のメッセージM1のハッシュC1=H(M1)について、C1だけが与えられた時、M1が推定できないこと。

大まかには上から順に重要度、つまり破られた場合の深刻度が増していく。

衝突耐性を突破する手法のほとんどは、M1に対応するM2がごく稀なので、推定できるM2は不正なフォーマットや意味のない文字列になることが予想される。元データを秘匿する必要がなく、フォーマットが不正なデータを排除する機能がハッシュ関数の外部にある場合については直ちに問題はない。

MD5以前のように意味有る衝突を実現できた報告がある場合、すなわち任意のM2を生成できる衝突耐性突破法が見つかった場合完全性の証明につかえなくなる。例えば、SSL・PGPなどの電子署名に使うことができなくなる。
また、原像困難性が突破された場合には上に加えて、メッセージの秘匿にも使えなくなる。例えば、パスワードのハッシュ化保存に使うことができなくなる。これは完全なレインボーテーブルが生成可能であることに等しい。

Keccakの安全性トレードオフ
Keccakに使われているスポンジ関数は、内部状態を大きくして、その一部にXORでデータを入力、あるいは一部を切り出してハッシュを出力する。入出力毎にスポンジ関数で内部状態全体が撹拌される。

http://sponge.noekeon.org/

スポンジ関数方式では、撹拌一回あたりの入出力データ幅という簡単なパラメータの調整で、原像困難性・衝突耐性とパフォーマンスのトレードオフをかなり自由に選択できる。
一回あたりの入出力データ幅を増やすと、出力されない秘密の内部状態は相対的に小さくなるため、原像困難性が低下する一方、スポンジ関数の呼び出し回数が減るためパフォーマンスが向上する。

たとえば、64bit処理系に最適化された、1600bitの内部状態をもつスポンジ関数に512ビット幅で512bitのデータを入力し、512bitのハッシュ出力を得るとする。

http://keccak.noekeon.org/tune.html の式における、r=512、c=1088に相当する。

スポンジ関数1回の逆演算コストが十分安くなったと仮定しても、512bitのハッシュだけでは元のメッセージを得る事は困難だ。スポンジ関数の内部状態の残り1600-512=1088bitはハッシュに出力されず推定するしかないため、原像を特定するには残り1088bitを総当りするか、スポンジ関数アルゴリズムの根本的欠陥を探す必要がある。

スポンジ関数自体が安全で、一回分の逆算ですら困難な場合、スポンジ関数を繰り返し適用して、例えば二回よびだして1024bitのハッシュを得ることも安全に出来る。
衝突耐性が原像困難性を上回ることはないので、1088bitを超えて際限なく出力することは無意味だが、出力時にスポンジ関数を可変回数呼び出せるよう実装すれば、変更の際に追加のハードウェアやソフトウェアを必要としない。
また将来、原像困難性をさらに向上する必要があった場合、たとえば1472bit必要になっても、4倍の処理時間を許容すれば入出力幅を128bitに小さくするだけで対応できる。

実装の容易さ
Keccakは基本的に64bitハードウェアを前提に設計されていて、必要なレジスタ数は25と多いものの、x64なソフトウェアでも現実的な性能が望める。SHA-2のようにハッシュ長毎の複雑な関数バリエーションを個別に実装する必要もなく、専用ハードウェア・IPもそう簡単には陳腐化しないだろう。（うまく実装すれば64bit版の一部を使って32bit版にも対応可能のようだ）
AES-128、SHA-256のみ対応、といった不完全・部分的な実装が蔓延する危険性も防げるかもしれない。

スポンジ関数が十分強固である場合、ハードウェア実装コスト低減と将来的なパフォーマンス・安全性の調整が可能であるという点で、SHA-3は良い選択と言えそうだ。

スポンジ関数という根本は実に単純なアイデアで、実装や普及上の困難の大部分を解決してしまっている。暗号技術の面白さがよく分かる事例と思う。

---

タイトルから期待していたものと違う！という御指摘（汗）が有ったので追記してみる。
https://twitter.com/daidaiBANANA/status/264664673369092096

鍵生成とストリーム暗号への適用可能性
スポンジ関数方式では最後に圧縮関数を使う必要がないので、単純に切り出すだけで、（入力途中含め）いつでも好きなだけ出力を取り出せる。
スポンジ関数一回の逆算のコスト＝原像困難性が十分なら、ストリーム暗号とみなすことが出来る。

さらに、スポンジ関数がストリーム暗号として使えると、鍵生成関数も不要になる。
通常の暗号は別途に鍵生成関数を実装する必要がある。人間が入力するパスワードには偏りがあり、長さも暗号鍵、例えば256bitAESより短いことが多いため、そのままでは秘密鍵として不適切。通常はハッシュ関数を使って、なるべくランダムに分布する秘密鍵を作るので、暗号とハッシュ（鍵生成関数）の両方を実装する必要がある。

スポンジ関数をストリーム暗号として使う場合、鍵生成の代わりに通常のKeccak同様にパスワードをメッセージとして入力する。
その後、ブロックサイズ、例えば512bitのカウンタをスポンジ関数の一部にXORして、スポンジ関数出力512bitを暗号文とXORすることでCTRモード暗号として利用できる。 復号もカウンタの初期値を受け取って全く同様の方法で行えば良い。

概念的には http://sponge.noekeon.org/ 下の方の画像を参照

これらはスポンジ関数の入出力にごく簡単なロジックを追加するだけで実装できる。AESとSHA-2を両方実装するよりも、Keccak一つ実装するほうが実装面積が少なくてすみ、一旦ハードウェア実装してしまえば、スポンジ関数の計算量も何とかなりそう。ブロック暗号や鍵生成関数の利用法を間違える危険性も減る。

ただし、Keccakのスポンジ関数は高速化のため、AESなどの近代的な暗号と違って乱数表（S-BOX）を一切使っておらず、AESより弱い暗号かもしれない。
直感的にはハッシュ関数の原像困難性と暗号の復号困難性は同じなので安全と期待されるが、SHA-3コンペはあくまでもハッシュ関数部分の評価なので、Keccakの鍵生成・ストリーム暗号としての評価や規格が定まるのはまだ先と思われる。