Subject: Re: [Cfrg] [saag] Further MD5 breaks: Creating a rogue CA certificate

From: RJ Atkinson <[email-masked]>
Date: Mon, 05 Jan 2009 08:26:52 -0500

On  5 Jan 2009, at 04:57, der Mouse wrote:
> What I, as an amateur, take away from it is approximately "MD5 is
> showing more and more cracks and nobody should use it for anything  
> that
> needs to withstand a malicious adversary".

Within the CA world, many folks here seem to agree.

However, the usage in CAs is rather different from
some other modes of operation (e.g. Keyed-Hash, HMAC-Hash).

So far, there are no known attacks on those other modes of operation.
[If someone knows of a refereed paper that's been published
on those latter topics, please share a citation here.]

> These may be the best openly published breaks of MD5 at the moment,

Mind, there are published "serious attacks" [using NIST's words
from their web site] against SHA-0 and SHA-1 also.   Timothy
Miller seemed to suggest in recent email that perhaps the PKIX WG
might enhance the CA structure to increase attack resistance in an
algorithm-independent way.

Now, may I suggest that folks please LOOK AT and possibly
REDUCE/EDIT the CC line as they reply to this thread going forward.
Items that are PKIX specific likely belong only on the PKIX
list.  Ditto for SMIME specific issues to the SMIME list.
That would leave only generic comments for the SAAG list.

Cheers,

Ran

_______________________________________________
Cfrg mailing list
[email-masked]
https://www.irtf.org/mailman/listinfo/cfrg

---

From: David McGrew <[email-masked]>
Date: Mon, 5 Jan 2009 10:15:26 -0800

Hi Ran,

> on those latter topics, please share a citation here.]

I'm not sure what you mean by keyed-hash, but here are some attacks  
that might be relevant.

[1] B. Preneel and P. van Oorschot, “MD-x MAC and building fast MACs  
from hash
functions,” Advances in Cryptology – Crypto 95 Proceedings, Lecture  
Notes in Computer
Science Vol. 963, D. Coppersmith ed., Springer-Verlag, 1995.

[2] B. Preneel and P. van Oorschot, “On the security of two MAC  
algorithms,” Advances
in Cryptology – Eurocrypt 96 Proceedings, Lecture Notes in Computer  
Science Vol. ??,
U. Maurer ed., Springer-Verlag, 1996.

RFC 2385 uses the method broken in Section 4.2 of [1].

HMAC seems to be secure given some reasonable assumptions about the  
hash functions (namely, that the underlying hash has a compression  
function that is a PRF - no collision resistance is required); see http://eprint.iacr.org/2006/043

> That would leave only generic comments for the SAAG list.

Done.

David

---

From: RJ Atkinson <[email-masked]>
Date: Mon, 05 Jan 2009 14:47:35 -0500

> function that is a PRF - no collision resistance is required); see http://eprint.iacr.org/2006/043

Thank you very much.
Pointers to the literature are very helpful.

One followup question, if I might, as a non-mathematician here.

Does the community agree on whether MD5, SHA-0, SHA-1, and/or SHA-2
meet the assumptions required by the HMAC proofs (e.g. your mention
above that the hash "is a PRF -- no collision resistance is
required") ???

I do continue to think that an Informational RFC that surveys
the use of hash functions -- as used by IETF protocols -- citing
the literature (as above) and comparing hash functions and modes
would be most helpful.  While RFC-4270 was good as far as it went,
it did not fully explain what the results meant relative to the
modes and algorithms that IETF specifications use -- and of course
time moves on and that RFC is now 3 years old.  :-)

Thanks again,

Ran
[email-masked]