本記事は 暗号学一人アドベントカレンダー 10日目(相当)の記事です。
本来ならば今日終わってるハズなのですが半分以上を残す結果になってしまいました…。期待していた方がいたなら大変申し訳ありませんでした。残りの内容は次の3〜4週間を目安で執筆・公開していきます。
これは何
『プロフェッショナルSSL/TLS』の第4章に出てきた「MicrosoftのMD5のコードサイニング証明書乗っ取れた」話に対する対策、また、SHAttered*1の後にGitHubが「衝突が発生するようなことがあったら検知できるよ」と言ってたアレの仕組みです。基本的には該当の論文の解説記事です。MD5やSHA-1への攻撃手法に共通する特徴があるため、それを逆手にとって「あるハッシュが攻撃によって生成されたものかどうか」を判定する、ということをやろうとしています。弱いハッシュ方式は互換性維持のために使われ続けるので、せめて攻撃があったことの検知を可能にすることでセキュリティをマシにしようとしています。
(スライドは @nunnunさん による読書会の該当章の部分。10ページ目、32-36ページ目のFlameの項が関係ある)
攻撃の背景
6日目の記事で書いている内容と重なるところで、本論文の要約がわかりやすかったのでまとめ。
- Near-collision attack
- 誕生日攻撃で特定の形式を持つ δIHV_b を探し、その後Near-collision attackで δIHV_b を0にして衝突にするような「選択プレフィクス衝突攻撃」(Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities)に応用される
手法の概要
MD5やSHA-1の攻撃で知られている手法がNear-collision attackを使うことに依存しているため、Near-collision attackで使われるような特徴を持つδB/δIHVがハッシュ関数の計算過程で検出されれば「このハッシュ値は攻撃に使われた可能性がある」ということがわかります(Algorithm 2-1)。以下がその手順を書き下したものです:
- k <- (0 ... N-1) ブロック目について、
- メッセージのkブロック目が処理される前の値をIHV_kと置く
- WS_0 = IHV_k とし、中間状態 WS_1 ... WS_(S-1) (Sは圧縮関数の中のステップ数)を計算する
- 攻撃が可能であると知られているδB, ステップi, δWS_iについて、
実際に使われるMD5とSHA-1での既知の値は論文末尾の付録に記されています。
もちろんこれによって誤って攻撃であると検出されることも有りえます。もし攻撃されていなかったと仮定するならば IHV'_(k+1) は圧縮関数を適切に経た値のハズで、つまり1つの知られているδB/δWS_iに対して2-L (Lは圧縮関数の確率でこれが検出されるため、合計C個の組み合わせに対して試みた場合は \(C \times 2^{-L} \) の確率で偽陽性を得ます。MD5の場合、1つのδB/δWS_iの組み合わせが例外的に2-Lよりも遥かに高い(2-48、L=128)ためこれだけは特別扱いして処理をする必要があります(2.3)。SHA-1の場合は(本論文時点では)このような特別なケースは知られていません。
実装
こちらにてオープンソースになっています。