クリプト野郎なので解説します。とりあえず速報なのであとでもう少し書くかもしれません。結論から言うと(少なくとも現時点で観測される情報の範囲では)脆弱性じゃないので安心して。
これは何
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_hash
とmessage_block
の組を見つけること、を指す。
“can result infinite set of collisions"と言っているのは、このattackの性質を満たす(input_hash
, message_block
)について、input_hash
を得られるような文字列を得たあとは、その後任意の回数message_block
をくっつけることで衝突となる文字列が好きなだけ得られますよ、ということ。例えばs0
がinput_hash
を与える文字列、m
がmessage_block
ならs0 + m
、s0 + m + m
、s0 + m + m + m
、…として任意の数の衝突が得られます、といっている。
最初読んだときは第二原像攻撃の定義と同じだと思っていたが第二原像攻撃の特殊なケースと見るのが正しそう。
と思ったがことはそう簡単ではないらしい
(メモ:ここは全文書いたあとに追記した)
あっ、ひどい見逃しをしてた。確かにこの手法単独だと攻撃可能性はほぼ無い。というのも、SHA-256 の実際のハッシュを得る際にはブロックのパディングを行うのだが、そのパディングに長さが含まれるのだ。……ハッシュを合わせるために約 2^64 ビットの追加データを与えるのはちょっと。
— Tsukasa #01 [要出典] (@a4lg) 2017年6月29日
SHA-2の擬似コードにあるように実際のハッシュを計算するときにはpre-processingの段階でパディングのあとにメッセージの長さを付与する。結果としてs0
とs0 + m
(またはその後任意の回数連結したもの)は長さが異なるので、パディングの前までは一致する中間状態を作り出すことができても、パディング+メッセージ長のブロックで違った値にハッシュ化されてしまうため、これだけでは衝突にならない。
proof.pyは何をやってるの
- 15行目: SHA256の初期化ベクタを書き換えている
- sha256.py 27行目 の値が SHA-256のinitialization vector (疑似コードの中のh0〜h7)と一致していることに注意
- 16行目: 入力としてmessage blockを与えている
- 17行目: その結果の出力
「確かに与えられた性質を示す文字列がありますよ」ということを示しているだけ。
実際にこういう初期化ベクタとメッセージの組を探すのはどうしてるの
(こっからちょっと理解が怪しい)
SATソルバを使った解法がStackExchangeで公開されていた。GitHubのREADMEを読む限りSATソルバじゃない方法で解いたらしいけどその手法は説明されておらず。