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

["Hughes, James P" <HugheJP at LOUISVILLE.STORTEK.COM>]

Thanks Steve [Kent] and sorry about confusing the quotes. As you correctly
noted, I was was trying to comment on the absolutes in David's statement.  

Thanks Phillip [Hallam-Baker] about the fundamental differences in MD5 and
HMAC algorithm and generally agree, but would add that MD5 and SHA are
diffent "sized" algorithms and 128 vs 160 or 256 bits is not an
inconsequential difference and should be considered when discussing what
kinds of HMAC is recommmended. (Similar to the TDES vs AES discussions.)

Thanks Steve [Bellovin] for the "ad on" statement. I would like to agree and
even suggest that it goes without saying that you may want future new
applications of HMAC to pass over MD5 (for SHA-x where x>0) if they have the
option. 

Thanks! I thought this was a very civil conversation!

Jim




-----Original Message-----
From: Stephen Kent <kent at bbn.com>
To: Hughes, James P <HugheJP at LOUISVILLE.STORTEK.COM>
CC: saag at mit.edu <saag at mit.edu>; cfrg at ietf.org <cfrg at ietf.org>
Sent: Wed Aug 25 10:56:09 2004
Subject: Re: [saag] Bad day at the hash function factory

Jim,

>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'm looking at the text of my message that you copied  above and I 
don't see the words "definitely" or "nothing" in what I said, only in 
what David said :-)

But, I concede your point that IF the signed messages of interest 
have a prefix that falls into the class noted, then there could be a 
problem. I didn't attend Crypto, but the examples were shown for 
messages that were 1024 bits long, and the prefix was 512 bits. If 
the length is a critical feature of the attack capability, that would 
limit the set of vulnerable messages.

>
>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.

Time stamp? The usual concern re time stamping is compromise of a 
private key and being able to distinguish what was signed before 
detection of the compromise, vs. afterwards. In this context, a 
secure time stamp would help IF it used a different hash algorithm. 
In the current Internet context, most of the persistent, signed 
objects are X.509 certificates, and the syntax of these certs does 
not accommodate time stamps from other parties.


Steve

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