«前の日記(2006-05-14 (日)) 最新 次の日記(2006-05-21 (日))»  

まちゅダイアリー


2006-05-16 (火)

独自MACの危険性

「はてなの認証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点は肝心の本の名前を間違えていたという…。 失礼しました。

Tags: security
本日のツッコミ(全2件) [ツッコミを入れる]
kazuho (2006-05-19 (金) 03:57)

わかりやすくて、すばらしいと思います。<br><br>> 入力データが512ビットに満たない場合は、パディングが入ります<br><br>重箱の隅をつつくようで申し訳ないですが、パディングは常に入ります。

まちゅ (2006-05-19 (金) 16:01)

うわっ。本当ですね。<br>やはり思い込みで書くべきじゃないですね(苦笑)<br>ご指摘ありがとうございます。