Subject: RE: [Cfrg] Applications of target collisions: Pre or post-datingMD5-based RFC 3161 time-stamp tokens

From: "Hallam-Baker, Phillip" <[email-masked]>
Date: Thu, 26 Oct 2006 18:04:56 -0700

One thing that always concerns me in these issues is that it appears that some people look for the commercial CAs to take a lead in declaring algorithms obsolete.

This is a very bad assumption. While commercial CAs can and do take a lead in promoting support for stronger algorithms (we have had 2048 bit roots for over 5 years) it is not our function to  force people to upgrade applications by withdrawing support for crypto that may fall short of the absolute state of the art.

With the exception of the brute force attacks against DES (a product of the 70s) none of the recent theoretical advances in cryptology allow a practical attack against a real system. Even the DES attack is a pretty remote one.

Clearly these attacks are significant enough to say 'do not use these algorithms in new infrastructure you plan to use for the next 20 years. That is not the same as saying 'throw away anything that uses it'.

It's the same thing with my 1977 MGB. It does not have anti-lock brakes or airbags. I still drive it[1] even though I would never buy a new car that did not have those fitted.

[1] OK I will drive it after I have replaced the wiring.

> -----Original Message-----
> From: Weger, B.M.M. de [mailto:[email-masked]] 
> Sent: Thursday, October 26, 2006 3:21 PM
> To: Steven M. Bellovin; Alfonso De Gregorio
> Cc: [email-masked]; [email-masked]; [email-masked]; 
> [email-masked]
> Subject: RE: [Cfrg] Applications of target collisions: Pre or 
> post-datingMD5-based RFC 3161 time-stamp tokens
> 
> Hi Steven,
> 
> > So how close are we getting to first or second preimage attacks?
> 
> As far as we know, not one bit closer. 
> Best known attack on MD5 preimage resistance still is brute force. 
> 
> You may interpret our result as enlarging the applicability 
> of collision attacks. In that sense the gap to preimage 
> attacks has diminished. But we have no measure available to 
> tell by how much.
> 
> Grtz,
> Benne de Weger
> 
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www1.ietf.org/mailman/listinfo/cfrg
> 
> 

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

---

From: "Hal Finney" <[email-masked]>
Date: Fri, 27 Oct 2006 10:54:38 -0700

> This is a very bad assumption. While commercial CAs can and do take a lead in promoting support for stronger algorithms (we have had 2048 bit roots for over 5 years) it is not our function to  forc…

You are posting in a thread discussing new and powerful collision
attacks against MD5. Are you implying that CAs should not take a lead
in declaring MD5 obsolete, and should not withdraw support for issuing
certs using that algorithm?

> With the exception of the brute force attacks against DES (a product of the 70s) none of the recent theoretical advances in cryptology allow a practical attack against a real system. Even the DES a…

Do you consider the MD5 attacks impractical? Or are systems that use
them not real?

> Clearly these attacks are significant enough to say 'do not use these algorithms in new infrastructure you plan to use for the next 20 years. That is not the same as saying 'throw away anything tha…

So you'd support continuing to use MD5 even in the face of collision attacks?

The new attack is quite expensive to mount, but the authors mention
that the cost has come down. Simple MD5 collisions take only a few
minutes on an average PC, and code to generate them is widely
available. I am amazed that you would suggest that it is OK to
continue using it. If that is not your implication, I don't know why
you are posting such a comment in this thread.

Hal Finney

---

From: Paul Hoffman <[email-masked]>
Date: Fri, 27 Oct 2006 18:42:09 -0700

[[ Trimmed to CFRG ]]

At 10:54 AM -0700 10/27/06, Hal Finney wrote:
>>One thing that always concerns me in these issues is that it 
>>appears that some people look for the commercial CAs to take a lead 
>>in declaring algorithms obsolete.
>>
>>This is a very bad assumption. While commercial CAs can and do take 
>>a lead in promoting support for stronger algorithms (we have had 
>>2048 bit roots for over 5 years) it is not our function to  force 
>>people to upgrade applications by withdrawing support for crypto 
>>that may fall short of the absolute state of the art.
>

I cannot speak for what Phill was implying, and I am not often in 
agreement with him, but I am in agreement with what he says above. 
CAs have promoted support for stronger algorithms. It is not their 
function to force customers to do anything.

As to your point: CAs should not take a lead in declaring MD5 
obsolete because it is not. CAs should not withdraw support for 
issuing certs with MD5 if their customers want it unless someone can 
show that there is an attack that would affect their customers. MD5 
is not a good choice for new usage, and obviously not for usage where 
collision attacks are important. To date, no one has shown that 
collisions are important for what CAs do.

If the Stevens-Weger-Lenstra construction gets significantly better 
and becomes an attack, and if a CA does nothing to thwart the 
then-attack, they will hurt their customers. But it is easy to thwart 
(either add randomness to the lower-order bits of serial number in 
the PKIX certificate, or use a presumedly-better algorithm like 
SHA-1).

>Do you consider the MD5 attacks impractical? Or are systems that use

Again, not speaking for Phill, but for myself: no and yes. Being 
"real" doesn't make them in the least bit practical, of course.

It is generally agreed that second-preimage attacks would be more 
devastating for PKIX certificates than collision attacks. Yet no one 
has gotten bothered by the Kelsey-Schneier attack because it is 
impractical.

>So you'd support continuing to use MD5 even in the face of collision attacks?

Again, not speaking for Phill, but for myself: no, but I also would 
not suggest CAs "withdraw support" or even alert any of their 
customers.

>that the cost has come down.

First off, the authors go out of their way to say that this is not an 
"attack"; we all should probably follow their lead in that. Second, I 
don't see the part where they say that "the cost has come down". 
Given that the construction has only been implemented once, I'm not 
sure where it would come down from. It will go down in the future, 
but we have no idea how much.

>Simple MD5 collisions take only a few
>available.

Um, so? If those collisions can't be used in an attack, why is that 
fact relevant?

>I am amazed that you would suggest that it is OK to
>continue using it.

I hope two amazements in one day do not overwhelm you. :-)

--Paul Hoffman, Director
--VPN Consortium