Deploying a New Hash Algorithm

| Comments (4) | TrackBacks (56) |
Steve Bellovin and I have a new paper up (submitted to the NIST Hash Function Workshop):
Deploying a New Hash Algorithm
Steve Bellovin and Eric Rescorla

As a result of recent discoveries, the strength of hash functions such as MD5 and SHA-1 have been called into question. Regardless of whether or not it is necessary to move away from those now, it is clear that it will be necessary to do so in the not-too-distant future. This poses a number of challenges, especially for certificate-based protocols. We analyze S/MIME, TLS, and IPsec. All three require protocol or implementation changes. We explain the necessary changes, show how the conversion can be done, and list what measures should be taken immediately.

PDF, PS.

UPDATE: Fixed link to PS file. Thanks to Jens Kubieziel for pointing this out.

56 TrackBacks

Listed below are links to blogs that reference this entry: Deploying a New Hash Algorithm.

TrackBack URL for this entry: http://www.educatedguesswork.org/cgi-bin/mt/mt-tb.cgi/339

Schneier is blogging like crazy, but there's so much news to blog about. Xiaoyun Wang, one of the team of Chinese cryptographers that successfully broke SHA-0 and SHA-1, along with Andrew Yao and Frances Yao, announced new results against SHA-1 yesterd... Read More

TITLE: State of the Hash: the end of SHA-1 URL: http://blogs.3sharp.com/Blog/deving/archive/2005/08/19/929.aspx IP: 64.65.179.146 BLOG NAME: (e)Mail Insecurity DATE: 08/19/2005 12:46:51 PM Read More

TITLE: State of the Hash: the end of SHA-1? URL: http://blogs.3sharp.com/Blog/deving/archive/0001/01/01/929.aspx IP: 64.65.179.146 BLOG NAME: (e)Mail Insecurity DATE: 08/19/2005 12:51:04 PM Read More

TITLE: syllable URL: http://www.syllable.org/search.php?query=%22%3E%3C/strong%3Estrategy%20%3Ca%20href=http://www.emistry.com/poker-strategy-epoll%2Ehtml%3Epoker%3C/a%3E%3Ch3%3EMisc.%20Weight%20loss%3C/h3%3Echeap::%3Ca%20href=http://discount.emistry.com/%3Ephentermine%3Ca/%3 IP: 80.58.42.42 BLOG NAME: syllable DATE: 09/20/2005 04:23:09 PM Read More

forex trading from forex trading on October 13, 2005 5:38 PM

forex trading Biggs had been smoke-dried by Munsther to rinse her whereas to Cheruscan. But Sherman's emotionless was choir-sing Read More

Mother rape incest from Rape hentai free video previews on November 6, 2005 6:19 AM

Free lesbian incest video Rape brutal incest Grannys having gang bangs Moms fuck daughters galleries Read More

cyclobenzaprine Read More

lipitor cost Read More

hummer sales Read More

buy mircette Read More

asian girls from JRB Technology on December 12, 2005 9:28 AM

thanks Read More

Bd sister tgp from Underskirt pictures on December 19, 2005 7:03 PM

Free american porn movies Sex italian movie free Gay sex sample videos Samples videos of sex with animals Read More

balloon bouquets from balloon bouquets on December 30, 2005 11:26 PM

Toryize landlady relative stirrings blue orchid the white stripes http://www.planyourhome.net/blue-orchid-the-white-stripes.html Read More

Acne Treatment from Acne Treatment on January 12, 2006 6:45 PM

Acne Treatment Read More

buy phentermine from buy phentermine on January 25, 2006 7:09 PM

buy phentermine Read More

buy tramadol from buy tramadol on January 25, 2006 7:15 PM

buy tramadol Read More

buy xanax Read More

Credit Repair from Credit Repair on January 27, 2006 6:04 AM

Credit Repair Read More

phentermine buy from phentermine buy on January 30, 2006 5:57 PM

phentermine buy Read More

buy xanax online from buy xanax online on January 30, 2006 5:57 PM

buy xanax online Read More

college loan from college loan on February 1, 2006 9:23 PM

college loan Read More

Car Hire Read More

Closet and Room Organizer from Closet and Room Organizer on February 5, 2006 6:25 AM

Closet and Room Organizer Read More

buy tramadol cod from buy tramadol cod on February 7, 2006 8:57 AM

... Read More

kelly blue book Read More

priceline Read More

Lesbi Joy Read More

install ceiling fan Read More

Retirement Planning from Retirement Planning on February 20, 2006 8:41 AM

Retirement Planning Read More

Closet and room organizer from Closet and room organizer on February 21, 2006 7:32 AM

Closet and room organizer Read More

free hot pics from porn collection online on February 26, 2006 4:01 AM

more great pics Read More

Cheap Ticket Read More

4 Comments

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

Leave a comment