Educated Guesswork

That is a good analysis. A couple of comments.

Does it make a difference if, when getting an "upgraded" certificate from SHA-1 to SHA-256, the same binary key material is used? So that the two certs could perhaps both be associated with the same signatures? Or is the signature linked unambiguously to a given cert in each of the protocols?

Section 4 is about S/MIME, but 4.3 is about DH? Is that the right place for it?

Section 4.4.3 assumes that everyone who might be in a position to influence a message is one of the communicants. But it could be a third party who has control over part of the message and wants to make a collision, not necessarily the recipient.

One other point on S/MIME: you advise warning on unverifiable signatures. Too many warnings are not always a good feature in a security product. If there are two signatures purportedly from the same signer, one with an unknown hash and one with a known one, I don't know that a warning is necessary. You got a good signature by a good key, that's what's immportant. And what about the case where one signature is by a known good hash (SHA-256) and one by a deprecated hash (MD5)? That just may mean that the sender didn't know that you were SHA-256 aware. Do you want to give a warning then? I don't think so.

Section 5.4 says, "The original rational for the dual hash construction was to provide security in the face of compromise of either hash. However, in practice, this has been undercut by the common heritage of SHA-1 and MD5." I think this is a little strong; in fact the current attacks cannot be used to find a common collision in these two hashes despite their similar structure. That would be a significant extension. It's a good idea to parameterize all the hashes in future versions of the protocol, but given that they were using a fixed algorithm the designers' purpose in using a dual hash construction has IMO been largely vindicated by the recent work. It does in fact provide security even in the face of a real compromise of one hash and a nearly practical compromise of the other.

Hal,

Thanks for the comments. A few quick replies.

Re: the same key. In the protocols we consider, the sig is either tied to the cert (S/MIME. though it's not cryptographically tied, just in the syntax, IIRC), or only one cert is allowed (SSL, IPsec).

S 4.3/DH. Yeah, this is S/MIME-specific stuff.

S 4.4.3: Good point. Though I tend to think this is a bit of an edge case, I agree it could be written more clearly.

Re: warnings. I agree, you could just succeed silently. My point was that if you threw an error then the dual-signature strategy wouldn't work but this could be phrased better.

Re: dual hashes. Well, note that a collision in SHA-1 wouldn't actually let you do anything useful in SSL AFAICT. I believe it would require a preimage. And if you can compute preimages in SHA-1, I would imagine that MD5 would be even more crippled. And, of course, this would let you forge certs....

Just as a nitpick, so long as the SHA1 collision attack stays above 2^{64} work, the Joux attack lets you find collisions on SHA1(m)||MD5(m) for about 64*cost(SHA1_collision)+2^{64} SHA1 compress calls.

--John

Hi,
the link to the PS-version is corrupt. It links to the PDF-version. Maybe you should change it.

Thanks
Jens