生兵法は怪我の元 (ハッシュ関数と HMAC)

昨日の日記に書いた、「署名の生成に MD5 は危険だから HMAC を使った方がいい」という指摘が理解できないという話の続き。

「ある値」のハッシュ値が分かれば、「ある値＋α」のハッシュ値が分かるということか。これが本当なら、僕のハッシュ関数への理解が根本的に間違っていることになるなぁ…。 (もしくは、ハッシュ関数全般の危険性じゃなくて、MD5固有の話？)

これについて、 kazuho さんから貴重なツッコミを頂いた（ありがとうございます）。

秘密鍵とハッシュ関数を組み合わせる手法によっては、セキュリティホールが発生する可能性がある。このような穴がないことが証明されている組み合わせ手法が HMAC である、ということです。

「はてなの認証 API リリース」で書いた「はてな認証API」の方式（パラメータと秘密鍵を連結した値のハッシュ値を署名とする）では、ある条件を満たすと秘密鍵を知らなくても署名を偽造できる危険性があるということらしい （ただし、これは潜在的な危険性であって、「はてな認証API」の現状の実装では直接的な影響は無いとのこと）。 やっぱり、僕のハッシュ関数への理解が間違っていたみたい。 勉強になったなぁ…。

とりあえず整理

ちゃんと整理したいけど、時間が無いので箇条書きで。

• ハッシュ関数はメッセージの指紋を取るための仕組み
  • 衝突耐性（同じハッシュ値を持つ2つのメッセージを見つけることが困難）や一方向性（ハッシュ値から元の値を推測できない）を持つ
  • ハッシュ値は誰でも作ることができるので、それだけではメッセージ認証コード (MAC) に使えない
  • ハッシュ値は予測不可能性（あるメッセージからどのようなハッシュ値が生成されるかを予測できない）を持たないので、メッセージ認証に使うためには工夫が必要（←これを知らなかった）
• メッセージ認証コード (Message Authentication Code) は、あるメッセージを誰が生成したかを特定するためのもの
  • ハッシュ関数と秘密鍵 (secret key) を使ってメッセージ認証を実現するのが、 HMAC (Keyed-Hashing for Message Authentication)
  • ハッシュ関数と秘密鍵の組み合わせアルゴリズムによっては、秘密鍵を知らなくてもハッシュ値（メッセージ認証コード）を推測できる場合がある（←これも知らなかった）
  • 上記の危険性の例については、Kazuho@Cybozu Labs: Hash ≠ MACを参照。 Extension Attack という。
  • 秘密鍵を使ってメッセージ認証を実現したい場合は、独自方式ではなく HMAC を使うのがベター

関連リンク

• HMAC: Keyed-Hashing for Message Authentication … HMAC に関するRFC
• Keying Hash Functions for Message Authentication (PDF) … ハッシュを使った MAC の実現方法に関する論文（上記RFCの参考文献）