MAC_k(x)=MD5(k,x) としたときに不味い理由.

Kazuho@Cybouzu Labs: Hash \neq MAC

Consider the "prepend-only" construction: MAC_k(x) = F(k, x) (i.e., the key k is prepended to the data x and the hash function - with the fixed IV - computed on the concatenated information). Because of the iterative structure of F it is easy to see that if one knows the value of MAC_k(x) where x contains an integral number of blocks, then one can compute the value of MAC_k on any extension y of x (i.e., any string y that contains x as a prefix) by just using the result of MAC_k(x) as an intermediate value of the chaining variable in the computation of MAC_k(y). This attacks needs no knowledge of or direct attack on the key k.
(Keying Hash Functions for Message Authentication, p.16)

MD5 の実装を見るに, y=x{0,1}^* に MAC がつけられるっていうのは嘘. ある程度は x の直後が限定され, y=x g(x) {0,1}^* という感じの関数 g が必要. 具体的なアタックは MD5(k,x,0...0,|k|+|x|,z) = MD5(MD5(k,x),z)MD5(k,x)を使って計算できると. Merkle-Damgård法によるハッシュ関数を使っているとパスワード前置式では駄目になるなぁ.