[Cfrg] Re: [saag] Bad day at the hash function factory

[James Hughes <James_Hughes at StorageTek.com>]

I am actually sorry to continue to beat this, but this is an important 
issue. Comments at the end please.

First, to clarify the discussion, I want to present some definitions. 
From
	http://www.wordiq.com/definition/Cryptographic_hash_function

1. Collision resistance is that it is to hard to find H(m1)=H(m2) for 
_any_ messages m1 and m2.

2. Second preimage resistance is that given h_1=H(m_1) it is hard to 
find m_2 such that h_1=H(m_2). This is for digital signatures.

3. Preimage resistance is that given h determine any message m_2, 
h=H(m_2). This is for password files.

If you have Collision resistance then you have 2nd preimage resistance. 
If you have 2nd preimage resistance preimage resistance.

The attack that Xiaoyun Wang, Xuejia Lai (& Dengguo Feng, Hongbo Yu) 
performed (portions of which were not presented) was that they spend 
about one and one half hours on a workstation to find an example of a 
class of messages (m_1) that are not 2nd pre-image resistant. Then once 
they have done that, then they can find multiple 2nd pre-image (m_2) 
from this message every 15 minutes.

So "MD5 is collision resistant" has fallen by existence proof and a 
demonstration that there are some messages that are not 2nd preimage 
resistant has also occurred (although this has not been analyzed to a 
great extent).

On Aug 23, 2004, at 8:32 PM, Stephen Kent wrote:
> At 8:59 PM -0400 8/19/04, james hughes wrote:
> >One comment and two discussion points.
> >
> >Can we withdraw the MD5 RFC as obsolete?
> >
> >On Aug 19, 2004, at 12:23 PM, David A. McGrew wrote:
> >>>WHAT'S SAFE?
> >>>First, anything that's already been signed is definitely safe.  If 
> you
> >>>stop using MD5 today, nothing you signed already puts you at risk.
> >
> >I sign a document (in the clear) which says "... pay me $100.00 ...
> >" and now I can create a document that to  "... pay me $10,000 ... "
> >with a collision. Just because the original is old, why are old
> >these documents safe?
>
> because you would have to generate a collision with a fixed value,
> the old has, and the techniques presented do not do that. They find a
> collision for MD5 based on the ability to create both messages from
> scratch. This is fundamentally different, in the same way that
> "birthday paradox" attacks have always been different from fixed
> message attacks.

Yes, but...

What you are saying is that even though MD5 is not collision resistant 
and it has been demonstrated that there is a class of messages that are 
not 2nd preimage resistant, that this class of messages is small small 
enough that _any_ message is not a member of this class even though the 
specific characteristics of this class has not been determined.

I could argue that saying that "nothing you signed already puts you at 
risk" is being hopeful. It really depends on the numbers of messages 
that have been signed and the percentage of this class. If billions of 
messages have been signed, are _all_ of them safe? Aren't we talking 
about probabilities? If we are talking about [unknown] probabilities, 
isn't this statement false in a rigorous logical [legal] sense (even 
though it may turn out to be true from a practical sense)? I am 
quibbling with your words "definitely" and "nothing" as being too 
absolute given the factual information that is out there.

I would suggest better wording of this statement would be
> [...] anything that's already been signed has a high probability of 
> being safe.  If you stop using MD5 today, there is a high probability 
> that nothing [previously] you signed already puts you at risk.

Even then, this begs the issue of trusting the timestamp.

Comments here...




Thanks!

jim
_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg