Subject: Re: [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

---

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: Jeffrey Hutzelman <[email-masked]>
Date: Mon, 05 Jan 2009 18:19:24 -0500

--On Thursday, January 01, 2009 05:01:33 AM +0100 Philipp Guehring 
<[email-masked]> wrote:

>> It should be noted, though, that yanking the trust anchors is not
>> enough. You really should change the relying party to not recognize
>> this algorithm. Otherwise, it's perfectly valid for a CA whose
>> certificate is signed with SHA1 to sign an intermediate CA certificate
>> with MD5 (although they usually don't do that, I hope)
>
> I also thought so, but then I realized that if we invalidate MD5
> completely, then we would also invalidate root certificates that are MD5
> self-signed, which isn't a security issue. So that would give lots of
> unnecessary false-positives.

Except that the validation process doesn't actually need to check the 
signature on a "root certificate", because that signature is not part of 
the chain.

> I would like to propose the following idea:
>
> We should define a date for expiring MD5 in certificate chains for the
> Internet. I would suggest the 1. June 2009, which is 6 months from now.

Hahahahaha!

If we all agreed, today, that this is the right approach, and the browser 
vendors all agreed with us, and they all managed to have updated versions 
available, by, say, next week...

It would be after June before anyone even had the new software.

If we're going to propose that browser vendors make a software change, it 
should not be to remove MD5 support; it should be to allow configuration of 
which signature algorithms are supported, just as they allow configuration 
of which TLS ciphersuites are supported.

It certainly should _not_ be to generate a warning every time an MD5 
signature is used.  All that will do is train users to click away security 
warnings without reading them, which they are already quite good at.

-- Jeff