まちゅダイアリー

独自MACの危険性

2006-05-16

「はてなの認証API」について、秘密鍵とハッシュ関数を組み合わせる手法によっては、セキュリティホールが発生する可能性があるという kazuho さんの指摘や、ハッシュ関数がiterativeな性質を持つ限り、この危険性からは免れませんという hyuki さんの指摘がようやく理解できた(遅すぎ?)。 忘れないように、図を書いて整理しておこう。

正当なユーザによる MAC の生成

まずは正当なユーザによる署名データ (MAC) の生成から。 署名データは、「秘密鍵 (共有鍵)」と「パラメータ」を連結した文字列のハッシュ値になる。 秘密鍵を知らないとハッシュ値は生成できないから、ハッシュ値が署名データ (MAC) になる…という考え方。

ハッシュの仕組みは下の図の通り。 結城さんの暗号技術大全入門 P.177 の図を元に、少し簡略化している。

MACの生成

緑色の枠は第三者が入手可能な情報を表している。 赤とグレーは正当な利用者(とはてなの認証サーバ)しか知らない情報を表している。

ここでのポイントは2つ。

一見すると秘密鍵を知らない人が MAC を偽造することはできないように見える。 でも、実は落とし穴がある。

第三者による MAC の偽造

hyuki さんが指摘されたハッシュ関数が「iterativeな性質を持つ」ことが落とし穴。 「ある値」と「秘密鍵+ある値」のハッシュ値が入手できれば、秘密鍵を知らなくても MAC を作ることができる。 仕組みは下図の通り。

MACの偽造

ハッシュ値と内部状態は同じものなので、元のメッセージの後ろに新しいメッセージを追加することで、それに対応するハッシュ値も生成できてしまう。 結果として、第三者が独自のメッセージ (図中のメッセージ (2)) とそれに対応する MAC (図中のMAC(2)) のペアを入手できることになる。 もちろん、正当なユーザの秘密鍵は不要。

秘密鍵とハッシュ関数で MAC を実現したい場合は、 RFC に書かれている HMAC を使うのが無難かつ確実ってことか。

追記 (2006/05/18)

結城さんから2点ほどツッコミをいただきました。 ありがとうございます。

入力データはパディングされるので、そのことに言及したほうがよいです。「追加データ」を作るときにちょっと工夫が必要になる程度ですが。

図に書くと複雑になりそうだったので省略していました。

~~入力データが512ビットに満たない場合は、~~パディングが入ります(暗号技術入門の178ページ)。(2006/05/19 追記: パディングは常に入るそうです。RFC1312の3.1節にも「このパディングは常に実行される」とありました) 追加データを作る時は、「秘密鍵+パラメータ+パディング+追加データ」になります。 Kazuhoさんのエントリで挙げられていた例(下記引用)でも、パディングが含まれていますね。

[秘密鍵]api_key[API_KEY]appendDATA\x80\0\0\0…\0\0\x02\x08cert[任意の cert 値]

もう1点は肝心の本の名前を間違えていたという…。 失礼しました。