Kazuho@Cybozu Labs

　というのは、同じハッシュ値をもつ "[ゴミデータ][任意の１バイト]" と "[別のゴミデータ][特定の１バイト]" という２つの異なるデータを用意できれば、攻撃が可能だからです。

　たとえば、今回のようなケースでは、仮に秘密鍵が後置されていたとしても、

のハッシュ値を選択平文攻撃で取得できれば、同じハッシュ値をもつ、

というリクエストを生成できるということになります^注2。

　MD5 については、パソコンで１分以内に衝突を発見できるレベルにあるそうです。SHA-1 については、現在のところ衝突は知られていないものの、

It has been speculated that finding a collision for SHA-1 is within reach of massive distributed Internet search.
(SHA hash functions - Wikipedia, the free encyclopedia)

という状況にあるようです^注3。

　いずれにせよ、結論が「HMAC を使うべき」^注4である点は、変わりません。

9:05 追記:　ぼけていて申し訳ないですが、上の話はオレオレ HMAC に限った話ではなくって、ハッシュ関数一般の話ですね。冗長でゴミデータを埋め込めるようなデータ形式の場合は、コリジョンを起こすブロックの先頭または末尾のキャラクタの差を利用して、同一のハッシュ値だが異なる意味をもつ複数種の文書を作成することができる、ということでしょうか。

注1: 衝突の発生するデータの分布が特殊でないことを仮定しています。まともなハッシュ関数なら、この仮定は満たされるんじゃないでしょうか
注2: ハッシュ値計算の際にパラメータ間にセパレータが入る場合についても、「特定の１バイト」をそのセパレータにしてしまえば良いので、評価は同等です
注3: 約 1/128 の確率で最初の衝突が公知になった瞬間に、上の攻撃が可能になります (9:17 追記: IV の問題があるので実際の確率はより低いでしょうか。上の例においては 1/300 くらい？)
注4: HMAC は使用するハッシュ関数の強衝突耐性に依存していないため、安全性が高いということ