WorldsFirstSha2Vulnerabilityについて

github.com

クリプト野郎なので解説します。とりあえず速報なのであとでもう少し書くかもしれません。結論から言うと(少なくとも現時点で観測される情報の範囲では)脆弱性じゃないので安心して。

これは何

SHA256でFree-start collision attackができました、というもの。

Free-start collision attackとは

SHA-1、SHA-2などのハッシュ関数Merkle–Damgård構造 という構造を持つハッシュ関数で、2つの固定長の入力を受け取る関数を連続して適用することで最終的なハッシュ値を構築します。このときの最初の関数に渡るのが初期化ベクタ(IV)と最初のメッセージブロックで、以後はこの関数の結果と次のメッセージブロックが引数となって最後のメッセージブロックまで処理します。(該当のWikipediaページの図がわかりやすい)

これが現実的な攻撃に発展するためには、Free-start collisionで与えている初期化ベクタと同じ値の内部状態を得るような入力を与える必要があり、そのような入力を得る攻撃自体が衝突を見つけるのと同じオーダーの計算量が必要なので現時点で見えている情報では現実的な攻撃ではない。

Circular hash attackとは

内部状態がinput_hashであるとき、あるmessage_blockを与えることで出力がinput_hashと一致するようなinput_hashmessage_blockの組を見つけること、を指す。

“can result infinite set of collisions"と言っているのは、このattackの性質を満たす(input_hash, message_block)について、input_hashを得られるような文字列を得たあとは、その後任意の回数message_blockをくっつけることで衝突となる文字列が好きなだけ得られますよ、ということ。例えばs0input_hashを与える文字列、mmessage_blockならs0 + ms0 + m + ms0 + m + m + m、…として任意の数の衝突が得られます、といっている。

最初読んだときは第二原像攻撃の定義と同じだと思っていたが第二原像攻撃の特殊なケースと見るのが正しそう。

と思ったがことはそう簡単ではないらしい

(メモ:ここは全文書いたあとに追記した)

SHA-2の擬似コードにあるように実際のハッシュを計算するときにはpre-processingの段階でパディングのあとにメッセージの長さを付与する。結果としてs0s0 + m(またはその後任意の回数連結したもの)は長さが異なるので、パディングの前までは一致する中間状態を作り出すことができても、パディング+メッセージ長のブロックで違った値にハッシュ化されてしまうため、これだけでは衝突にならない。

proof.pyは何をやってるの

  • 15行目: SHA256の初期化ベクタを書き換えている
  • 16行目: 入力としてmessage blockを与えている
  • 17行目: その結果の出力

「確かに与えられた性質を示す文字列がありますよ」ということを示しているだけ。

実際にこういう初期化ベクタとメッセージの組を探すのはどうしてるの

(こっからちょっと理解が怪しい)

SATソルバを使った解法がStackExchangeで公開されていた。GitHubのREADMEを読む限りSATソルバじゃない方法で解いたらしいけどその手法は説明されておらず。

参考

crypto.stackexchange.com

crypto.stackexchange.com