(10) Counter-Cryptanalysis

本記事は 暗号学一人アドベントカレンダー 10日目(相当)の記事です。

本来ならば今日終わってるハズなのですが半分以上を残す結果になってしまいました…。期待していた方がいたなら大変申し訳ありませんでした。残りの内容は次の3〜4週間を目安で執筆・公開していきます。

これは何

『プロフェッショナルSSL/TLS』の第4章に出てきた「MicrosoftMD5のコードサイニング証明書乗っ取れた」話に対する対策、また、SHAttered*1の後にGitHubが「衝突が発生するようなことがあったら検知できるよ」と言ってたアレの仕組みです。基本的には該当の論文の解説記事です。MD5SHA-1への攻撃手法に共通する特徴があるため、それを逆手にとって「あるハッシュが攻撃によって生成されたものかどうか」を判定する、ということをやろうとしています。弱いハッシュ方式は互換性維持のために使われ続けるので、せめて攻撃があったことの検知を可能にすることでセキュリティをマシにしようとしています。

speakerdeck.com

(スライドは @nunnunさん による読書会の該当章の部分。10ページ目、32-36ページ目のFlameの項が関係ある)

攻撃の背景

6日目の記事で書いている内容と重なるところで、本論文の要約がわかりやすかったのでまとめ。

  • Near-collision attack
    • Intermediate Hash Value(圧縮関数の受け取る中間値)のペア(IHV, IHV')
    • その2つの差分を δIHV と置く
    • 特定のメッセージブロックの差分を δB と表記。特徴は以下に定義
    • 圧縮関数を通したときに入力の差分 δIHV と δB がどのように伝搬するかのパス(differential path)を使って B + δB = B' になるような (B, B')を探す
      • 上記スライド13-14pの「衝突ブロック」というのがこの (B, B')
  • 誕生日攻撃で特定の形式を持つ δIHV_b を探し、その後Near-collision attackで δIHV_b を0にして衝突にするような「選択プレフィクス衝突攻撃」(Chosen-Prefix Collisions for MD5 and Colliding X.509 Certificates for Different Identities)に応用される

手法の概要

MD5SHA-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について、
      • M_k に δB を適用し M'_k を得る
      • WS_i に δWS_i を適用し WS'_i を得る
      • 逆順に計算を適用*2し、WS'(i-1) ... WS'0 を得る
      • i ... S-1 ステップ目*3を計算する
      • IHV'K = WS'0、IHV'(k+1) = WS'S
      • ここでIHV'(k+1) = IHV(k+1) ならば(M_k, M'_k)は「衝突ブロック」(near-collision block pair)なので攻撃に使われた可能性がある

実際に使われるMD5SHA-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の場合は(本論文時点では)このような特別なケースは知られていません。

実装

github.com

こちらにてオープンソースになっています。

*1:論文著者は同じ人

*2:圧縮関数の両方の入力がわかっていれば、各ステップを逆順に適用することは可能

*3:0-indexであることに注意