メモ

断片部 crypt

collision-resitantからじゃない. 元論文では, もっと弱い性質から示している.

HMAC-MD5というか, 元のハッシュ関数に衝突耐性が無い場合のHMACの安全性. HMACのRFCの邦訳を見つけたので, それだけ書いておく. http://www.ipa.go.jp/security/rfc/RFC2104JA.html

元論文の論法を使って\{F_k\}をMD5を使って構成した場合に, HMAC-MD5が暗号学的に証明可能安全性を持つかどうか分かんないというのが正直のところのような.

元論文の大雑把な説明.

MD5やSHA-1は, 1を内部に持っている. MD5やSHA-1は, 関数としては, 2のFを実装したものになる. Wangらがやっているのは, 2に対するアタックと見て良い.

  1. 元となるcompression function f:\{0,1\}^{b+l}\to\{0,1\}^lがcollision-resistant
  2. そこからMerkle-Damgard法*1で構成したハッシュ関数 F:\{0.1\}^{*}\to\{0,1\}^lもcollision-resistant. (fからFを構成する際に, IVが必要)
  3. このFのIVを秘密鍵と思って秘密にするという運用を考えると, 鍵付きハッシュ関数族 \{F_k\}になる. これはweakly collision-resistant.
    • \{F_k\}がweakly collision-resistantでないとすると, うんぬん.
  4. このFを使ったNMACは安全.
  5. この原理を応用すると, HMACも安全.

問題は2→3. 普通は「2を満たす→3を満たす」という論法になると.
しかし, 2と3を比べると, 3の方が弱い性質となる. それなので, 2を満たさなくても, 3を満たす場合がある. MD5から構成した鍵付きハッシュ関数族が3を満たすっていうのは, 共通前提? → まぁ共通前提扱いか. パッとみアタック無いし. んー, どの辺の性質を使うと示せるかな. second pre-image attackを防げるくらいで言えるか?

RFCには

注：この文書の執筆時点では、MD5 と SHA-1 が、最も広く使用されている暗号ハッシュ関数である。MD5 は、最近、衝突サーチ攻撃に対して弱いことが示された [Dobb]。この攻撃や他に現在知られている MD5 の欠点は、この文書にて指定されるような HMAC での MD5 の使用を妥協させるようなものではない（[Dobb] を見よ）。しかし、SHA-1 の方が暗号的に強固な関数であるようである。MD5 の優れた性能が重要なアプリケーションは、現在、その MD5 を HMAC で使用することを検討することが可能である。いずれにせよ、実装者と利用者は、これらの暗号ハッシュ関数に対する暗号解析の開発の可能性と、その結果として起こる基本となるハッシュ関数の置き換えの必要性について知っておく必要がある。（HMAC のセキュリティについてのさらなる情報については、6 章を参照のこと)

と書いてある. 誰か実験しないものかしらん.

*1:正確にはMerkle-Damg{\aa}rd法