独自MACの危険性

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

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

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

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

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

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

• 入力データは一定サイズで分割 (ブロック化) される。
• 分割されたブロックごとにハッシュ値 (内部状態) を計算する。そのハッシュ値と次のブロックを組み合わせて、次のハッシュ値を生成する。

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

第三者による MAC の偽造

hyuki さんが指摘されたハッシュ関数が「iterativeな性質を持つ」ことが落とし穴。 「ある値」と「秘密鍵＋ある値」のハッシュ値が入手できれば、秘密鍵を知らなくても 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点は肝心の本の名前を間違えていたという…。 失礼しました。