Re: Humble Contribution

From: Foo Bar (foobar965_at_hotmail.com)
Date: 01/25/04 

Date: Sun, 25 Jan 2004 13:32:32 GMT

jcduque@lycos-dot-com.no-spam.invalid (jcduque) writes:

> > Paul Rubinwrote:
> Kristian Gjøsteen <kristiag+news@math.ntnu.no> writes:
> > But this is not a weakness in a hash function. Surely, the goal of
> a
> > hash function is to be collision resistant, not to be a good MAC?
> Or?
> >
> A good hash function's output also has to not tell you anything about
> the preimage. But as Paul Crowley explains, the message extension
> attack means that given H(X) you can construct H(Y) where X is a
> prefix of Y.[/quote:fce3f464a5]
>
> Paul Crowley is wrong in saying:
> > MD-strengthening is an important part of collision resistance, but
> it
> > does nothing to prevent message extension attacks. There's nothing
> to
> > stop MD-style padding appearing in the middle of a message.
> I quote here Schneier's Applied Cryptography:
>
> > The pre-image should contain some kind of binary representation
> > of the length of the entire message. This technique overcomes a
> > potential security problem resulting from messages with different
> lengths
> > possibly hashing to the same value. This technique is sometimes
> called
> > MD-strengthening.
> >
>
> It is clear that MD-strengthening makes a hash function immune to
> message extension attacks.

No. Think again. MD-strengthening helps collision resistance but does
not protect against message extension attacks. MD-strengthening only
guarantees that different messages are different _before_ invoking the
compression function. Message extension attacks are possible since the
whole state of the hash function is output as hash value.

The potential problem Schneier talks about is the following: Consider a
MD5-like hash function that pads with zero-bits to the first block
boundary (and applies no MD-strengthening). What do the two messsages
"1" and "10" look like after padding? What about their hash values?

Rubin and Crowley are both right. I can explain it in more detail if you
want.

/FB 

-- 
Foo Bar (foobar965@hotmail.com)