Next steps for hash functions

| Comments (15) | TrackBacks (146) |
The recent rumored results on SHA-1 aren't a catastrophe, but we need to start planning for the future. (warning, slightly heavy sledding ahead).

The bad news is that there is no standard function that is guaranteed to be more secure. In particular, we can't really be confident that SHA-256 is going to be stronger.

Here's one thing that probablywon't work:
Concatenation The obvious thing to do is to take a SHA-1 and an MD5 and concatenate them on the theory that this makes things harder. Unfortunately, Joux's CRYPTO 2004 paper on multicollisions suggests that this doesn't make things anywhere near as much harder as you would expect.

Here are a few alternatives that might work:

  • Randomized hashing The whole reason why this attack works is that the attacker knows the exact message you're going to hash. If you prefix the message with a random value, this effectively defeats the attack. So, when you sign a message you would sign H(random || message) instead of H(message) [0]. In particular, CAs should immediately start using unpredictable serial numbers. [1]
  • A non-MDx-based hash function All of the major standard hash functions ultimately derive from MD4. It's possible to design hash functions based on block ciphers (see Tom Shrimpton's slides) for an overview. Unfortunately, as I understand it you can't prove security for these constructions in a realistic model of the underlying algorithm. However, there's some hope that you would have to make a pretty serious dent in that block cipher in order to break the hash.
Strangely enough, it's actually easier to specify a new hash function than it is to move to randomized hashing. At the end of the day, we'll probably want to do both because randomized hashing provides protection against this kind of attack in general, regardless of the status of the hash function.

[0] My intuition is that you'll want to pad out the random IV to an input block length, even if the IV is less than a block length, rather than just concatenating the values directly. However, you'd need to ask a real hash function here.

[1] It's easy to make these monotonically increasing. Just use Counter || random

146 TrackBacks

Listed below are links to blogs that reference this entry: Next steps for hash functions.

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

SHA-1 Broken from Sergey Simakov blog on February 20, 2005 10:56 PM

TITLE: SHA-1 Broken URL: http://geekswithblogs.net/ssimakov/archive/0001/01/01/23142.aspx IP: 216.26.145.168 BLOG NAME: Sergey Simakov blog DATE: 02/20/2005 10:56:55 PM Read More

blood pressure from Blood Pressure on April 13, 2005 9:03 AM

TITLE: blood pressure URL: http://bp.xmix.net/ IP: 80.227.56.42 BLOG NAME: Blood Pressure DATE: 04/13/2005 09:03:31 AM Read More

beastiality from animal sex on May 19, 2005 8:07 PM

dogs doing girls dogs doing girls dog fuck dog fuck animalsex animalsex Read More

beastiality from animal sex on May 20, 2005 10:58 PM

TITLE: beastiality URL: http://pencile.artshost.com/1/ IP: 68.250.108.146 BLOG NAME: animal sex DATE: 05/20/2005 10:58:06 PM Read More

comparison levitra viagra how to recognise levitra buy cheap levitra online anti impotence levitra levitra product which is better viagra cialis or levitra levitra info information on drug called levitra tachyphylaxis levitra levitra versus cialis levi... Read More

jeep cherokee discussion 1999 jeep cherokee grand cherokee whining noise cherokee women piper cherokee jeep cherokee used parts 1827 cherokee constitution cherokee removal cherokee indians of missouri photos of cherokee indians jeep cherokee grille gua... Read More

womens health Read More

The most important thing Read More

viagra I had rather believe all the fables in the Legend, and the Talmud, and the Alcoran, than that this universal frame is without a mind. And Read More

Discount Cruise and Vacation from Discount Cruise and Vacation on September 7, 2005 8:18 PM

mhgcu@trstrjs.net Read More

gothic literature buddhist literature hatchet literature circle literature censored critical analysis of scientific literature romantic period in literature revolutionary war literature unit point of view in literature encourage students to dramatize l... Read More

NY party seeks to remove member Read More

All I want to say Read More

FUNNY PICTURE - FUNNY JOKE Read More

CHEAP TICKET from CHEAP TICKET on October 1, 2005 11:33 AM

CHEAP TICKET Read More

Next steps for hash fu... Read More

ORLANDO HOTEL from ORLANDO HOTEL on October 8, 2005 11:48 AM

ORLANDO HOTEL Read More

Cheap Pharmacy Online from Cheap Pharmacy Online on October 8, 2005 4:02 PM

Mexican aid convoy heads into US Read More

CANCUN MEXICO HOTEL - CANCUN MEXICO VACATION from CANCUN MEXICO HOTEL - CANCUN MEXICO VACATION on October 9, 2005 6:47 PM

CANCUN MEXICO HOTEL - CANCUN MEXICO VACATION Read More

Captain Stabbin from Captain Stabbin on October 13, 2005 3:05 PM

Quite nice Read More

Boys First Time from Boys First Time on October 13, 2005 5:49 PM

Judge Orders Berger to Pay $50,000 Fine Read More

GOOGLE ADSENSE TIP from GOOGLE ADSENSE TIP on October 16, 2005 9:28 PM

GOOGLE ADSENSE TIP Read More

True mom son sex stories from Daddies girl getting fucked on November 3, 2005 2:02 PM

Adult cartoonsfree thumbnails Gay download video free Mom and dad fuck vids Mature free sex film Read More

Final Fantasy XI from Final Fantasy XI on November 5, 2005 4:20 AM

Final Fantasy XI Read More

health insurance is a greatblog Read More

some nice babes from babes posing outdoor on November 13, 2005 10:20 AM

xxxx fresh links Read More

xxx posing outdoor from hot amateur babes on November 14, 2005 2:26 PM

nice and hot Read More

spyware and spyware list Read More

romantic vacation from romantic vacation on November 28, 2005 7:52 PM

romantic vacation Read More

Next steps for hash fu... Read More

cheap vacation from cheap vacation on November 29, 2005 6:21 AM

cheap vacation Read More

cruise vacation from cruise vacation on November 29, 2005 6:26 AM

cruise vacation Read More

vacation discount from vacation discount on November 29, 2005 11:24 AM

vacation discount Read More

vacation planning from vacation planning on November 29, 2005 12:34 PM

vacation planning Read More

Fruit Baskets Read More

used jeep parts Read More

ethereal music from Karl Justafsson on December 8, 2005 12:56 PM

Next steps for hash fu... Read More

Next steps for hash fu... Read More

gold digger mp3 from Ruediger Horstemke (?) on December 22, 2005 9:49 AM

Next steps for hash fu... Read More

rules for poker Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

mp32 from Hatzialexiou Manolis on December 27, 2005 1:32 AM

Next steps for hash fu... Read More

scorpions mp3 from Anni Ca Soderovist on December 27, 2005 1:52 PM

Next steps for hash fu... Read More

Payday Loan Read More

TITLE: hoodia URL: http://www.20mbweb.com/Health/hoodia/ IP: 84.253.137.122 BLOG NAME: hoodia DATE: 01/17/2006 05:30:44 AM Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

cryptopsy-mp3 from Jeanett Ishksson on January 27, 2006 9:35 PM

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

hellsing-music-videos from Marcus Fredriksson on January 28, 2006 3:06 AM

Next steps for hash fu... Read More

hellsing-music-videos from Marcus Fredriksson on January 28, 2006 3:06 AM

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

dragostea-din-tei-mp3 from Anneliesk Schlechtleiner on January 28, 2006 7:11 PM

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

i-music from Kerstin Soedler on January 29, 2006 2:55 AM

Next steps for hash fu... Read More

i-music from Kerstin Soedler on January 29, 2006 2:55 AM

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

john-fogerty-mp3 from Reinhard Andrian on January 29, 2006 6:32 PM

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

dr-no-music from Carloline Eliasson on January 30, 2006 4:18 PM

Next steps for hash fu... Read More

dr-no-music from Carloline Eliasson on January 30, 2006 4:18 PM

Next steps for hash fu... Read More

dr-no-music from Carloline Eliasson on January 30, 2006 4:18 PM

Next steps for hash fu... Read More

music-of-cuba from Ilse Schallert on January 30, 2006 5:56 PM

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

dead-man-music from Felicia Stromborn on February 2, 2006 10:17 PM

Next steps for hash fu... Read More

camelot-music from Benjamin Lysgoard on February 3, 2006 1:23 AM

Next steps for hash fu... Read More

Next steps for hash fu... Read More

Next steps for hash fu... Read More

poker casino585 from poker casino585 on February 9, 2006 11:51 AM

poker casino poker 993 Read More

party poker party poker online poker online poker Read More

free ringtones free ringtones poker online poker online Read More

free pissing sex movies from free pissing sex movies on February 22, 2006 2:47 PM

TITLE: free pissing sex movies URL: http://free-pissing-sex-movies.join-4free.info IP: 195.42.160.19 BLOG NAME: free pissing sex movies DATE: 02/22/2006 02:47:42 PM Read More

denver real estate from denver real estate on February 23, 2006 1:01 PM

denver real estate seattle real estate seattle real estate oro valley real estate ... Read More

15 Comments

Have any weaknesses been found in RIPEMD-160 yet?

Could Whirlpool be a solution?

Let me amplify the randomized hashing concept. The point is, this attack can only be mounted by the one who created the message to be signed. They could in principle create two versions, such that a signature on one would also be a signature on the other.

Now, in almost all cases, the person creating the signature is the person who creates the message to be signed. Randomized hashing is irrelevant there.

The point of randomized hashing is for cases where one party prepares the message to be signed, and another party signs it. And the main example of that is cryptographic certificates like those used in secure web pages. The person applying for the certificate creates most of the data in the format he wants it to appear. The issuer (typically Verisign) then validates that data and signs it if it is OK. So most of the data is provided by the requestor.

One thing that the signer adds is a serial number, which goes at the front. If the serial number is predictable, the requestor knows the exact certificate format and he can apply the attack. But if the serial number is unguessable and random, the attack won't work.

That's the point of randomized hashing - to thwart attacks where one party supplies another with data to be signed. But this is an unusual circumstance and so this fix only applies in a few narrow cases.

I haven't thought this through very far, but wouldn't adding a random element onto the front of the message possibly make it easier to forge a message under a sig? Say you have:

(random,msg,sig) where the random element is just some random collection of bits, and the sig applies to (random,msg). One of the key defenses against forged sigs is that the msg allegedly signed is in fact something meaningful, no? So if you make part of that message random junk, can't you essentially hide entropy in that random part? ie, keep same signature, make up msg2 which has different contents, now just find random# such that (random2,msg2,sig) is valid. The key here is that we're less restrained in the contents of msg2, because we have ultimate freedom in choosing random2.

cypherpunk:
yes this is mostly correct, though to my mind this is the important attack model.

that said, randomized techniques provide security in other threat models as well: first, if both parties sign the same message with different randomizers. second, if the relying party provides a contribution to the randomizer.

RIPE-MD160 is very similar in spirit to MD5, RIPEMD, Haval, SHA0, and SHA1, all of which have now fallen to the same group of researchers. So, maybe their (still basically unpublished) techniques won't work on RIPE-MD160, but I'd hate to bet on that. My money is on RIPE-MD160 as the next target for them.

SHA256 is different in structure from SHA0/SHA1, but it still depends on the same kind of operations--mixing bitwise logical operations, rotations, and addition, and expecting a lot of the diffusion in the function to come from carry bits. There are some important differences--the large-scale unbalanced Feistel structure of SHA256 is pretty different from that of MD4/MD5/SHA0/SHA1/Haval-*, and the internal functions do a better job of using linear mixing operations to mix together different bit positions--but it's hard to have a huge amount of confidence in it until we can see the techniques of Wang et al.

Whirlpool is completely different, and it's the fallback I'd recommend at first glance. It's designed by Vincent Rijmen, who helped design AES, and it's very similar to AES conceptually. Other hash functions not closely related to MD5 and SHA1 are Tiger and GOSTHASH, but I'm not crazy about either of them for a variety of reasons.

--John Kelsey

So John, any comments on when NIST is going to get off its duff and extend the DSS so we can use something other than SHA-1? Wouldn't you agree that it's time for such an enhancement, which has been promised for years?

It's definitely important, and the break of SHA1 definitely adds some urgency. I'm not sure about the timetable, though--it's one of the ten or so things my boss is working on right now. I know she's been getting reqests to get this out for awhile now....

--John

Adding some randomness may help, depending on the attack. Having the CA put some unpredictable bits in the value it finally signs from the user seems like a reasonable thing to do, for example. But this doesn't address the far more common case where I sign a message of my own creation offline and you validate it offline. And it works only for some hash function attacks--for example, a pure differential attack (where I don't care about the bit values, just the differences) won't be affected by this. Now, it looks like the Wang attack is using knowledge of the bits, but since they haven't published their techniques, it's hard to be sure.

--John Kelsey

John:

Yes, the case where you sign something and I verify it is common, but what's NOT common is to be using that in a nonrepudiation style application rather than a data origin authentication style application.
In SSL client auth, for instance, the client can plausibly deny the message contents without denying the signature because the message contents themselves are protected by a MAC, not a signature.

Craig has a point--randomizing signatures increases their security against chosen message attack, at the cost of reducing their security against known message ("second preimage") attack.

For example, suppose that I randomize the IV in a SHA1-style hash function before hashing and signing. (various randomized-prefix schemes are equivalent to this.) Since such hash functions typically compute a permutation on the IV for any fixed input, the random IV effectively controls the hash output, making any attacker's choice of messages no better than random choices. Hence the best attack will be the standard birthday attack.

However, if I want to attack a particular message, I can now hash that message with different IVs, do the same with a message of my choice, and do the standard birthday attack. "Second preimage" attacks thus become no more difficult than existential collision attacks.

Of course, if the hash size is large enough that birthday attacks are infeasible, then neither of these attacks are a problem. (And 160 bits may well be large enough--for now, at least--that this can be said of SHA1.) But it's worth remembering that randomization reduces everything to a birthday attack in both directions, making the birthday attack threshold critical for all collision-intractability-related uses of the hash function.

Dan,

As I understand your point, you're saying that given a message M, and a randomized hash H(r,M) it's easier to find another value M' so that H(r,M) = H(r',M'). I agree with that.

However, it seems to me that that's not the security environment in which a second preimage attack is likely to be useful. In that situation, you have a signed message, i.e. a triplet of (M,r,S(H(r,M)). The attacker needs to create a new pair M',r' such that H(r',M')=H(r,M). He doesn't get to mount the birthday attack because he needs to produce the same fixed hash value. Have I missed something?

No, you haven't missed anything--I just wasn't thinking clearly (as I realized--too late--when I woke up this morning). My apologies.

However, the Handbook of Applied Cryptography points out an obvious problem with randomly chosen IVs: you can trivially find collisions by deleting leading blocks from the message. (Clever formatting rules might help prevent this one, though.)

Right. Randomizing the IV is the wrong way to randomize. (r,H(r,x)) seems a better choice -- i.e., to prepend the random value to the message to be hashed.

There is a lot of theoretical work on these kind of constructions, under the name "universal one-way hash function" (UOWHF). (Dan Simon knows this, but some other readers might not, so I thought I'd mention it for the benefit of any onlookers.)

David... Glad to get your input.

If r is a full input block long (or you pad it out to the block length as in HMAC), then aren't you effectively randomizing the IV? Do you think one should deliberately choose an r that is smaller than the block length?

Leave a comment