A Competition To Replace SHA-1

SHA who? writes "In light of recent attacks on SHA-1, NIST is preparing for a competition to augment and revise the current Secure Hash Standard. The public competition will be run much like the development process for the Advance Encryption Standard, and is expected to take 3 years. As a first step, NIST is publishing draft minimum acceptability requirements, submission requirements, and evaluation criteria for candidate algorithms, and requests public comment by April 27, 2007. NIST has ordered Federal agencies to stop using SHA-1 and instead to use the SHA-2 family of hash functions."

Comments

Draft location

[ErGalvao]

The draft can be found (in PDF) here.

Schneier Proposed this in 2005

[RAMMS EIN]

Schneier proposed such a competition in March 2005: http://www.schneier.com/crypto-gram-0503.html#1

Re:Generic hashing is impractical

[RAMMS EIN]

``Maybe secure hashing needs to store a mixture of the low level and the high level details but in a context specific way - the face picture example should also store the detailed iris pattern as well as an overall face picture, both should match to allow this person through. It might be easy to find someone who looks like me, but the specific portion cannot be modified without surgery.''

The idea is that, in a good hash function, each input bit affects all the output bits more or less equally. This is especially true of cryptographic hashes, and for a good reason. The stronger the correlations between input and output, the weaker the hash function.

Re:Generic hashing is impractical

[delt0r]

You clearly don't know what a crytographic hash is about. And this is not what is ment by collisions resitant. What it means is that there is minum amount of work needed to produce a collision.

There are a number of different type of collisions as well. Lets assume we have a 256-bit hash. There is the kind of colision where you just find *any* 2 strings that produce the same hash, which should require on avarage 2**128 "operations". A harder task is given a string and its hash find another string with the same hash. For a secure hash 256-bit hash function this will require on avarage 2**256 "operations".

There are other properties that are important as well. Its a well established idea. Hashes are very very usefull and are used for a lot more that file verification and we know what properties they need. We are just not very good at producing very good hashes yet.

Re:Hash functions in common protocols

[cpuh0g]

Most modern protocols and standards are designed to be agile. Basically, this means that they don't mandate any one particular algorithm, but rather are designed such that alternatives can be used. Otherwise, many specs would be woefully out-of-date every few years as computing power and cryptographic algorithms advance. The 3 examples you give above are all considered "agile", read the specs and note that they use algorithm identifiers and allow for a wide variety of different algorithms to be used, none of the above are strictly bound to use SHA-1 or MD5.

Re:Multiple Hash Functions

[rbarreira]

Doesn't work very well. Read this:

http://www.mail-archive.com/cryptography@metzdowd. com/msg02611.html

Re:Generic hashing is impractical

[simm1701]

2000 times quicker than brute force (where brute force is average time 2^159 attempts) means the algorithm is not as secure as it used to be thought.

This has demonstrated a cryptographic weakness, there could quite well be more, look at the research over the years on weakening md5, therefore moving to different algorithm would be advisable.

Its doesn't mean that you are going to be able to find a collision in non trivial time, but it did lower the bar. Lowering it enough that people wanting high grade protection should switch to a more secure algorithm.

Context specific data has no place in a hash, it would only weaken it.

Re:Multiple Hash Functions

[RAMMS EIN]

Thanks. The post you linked to precisely answers both my questions. I'll restate the questions and copy the answers from the post for /.ers' convenience.

1) Would multiple hash functions be harder to fool (i.e. make the system think you got the original, but it's actually a forgery) than one hash function that generated as many bits?

No. In fact, the multiple hash functions perform worse:

``Joux then extended this argument to point out that attempts to increase
the security of hash functions by concatenating the outputs of two
independent functions don't actually increase their theoretical security.
For example, defining H(x) = SHA1(x) || RIPEMD160(x) still gives you only
about 160 bits of strength, not 320 as you might have hoped. The reason
is because you can find a 2^80 multicollision in SHA1 using only 80*2^80
work at most, by the previous paragraph. And among all of these 2^80
values you have a good chance that two of them will collide in RIPEMD160.
So that is the total work to find a collision in the construction.''

2) Does using multiple hash functions protect you against the case where one of them gets broken?

Basically, yes. Just note that your total security is no better than the security of the best hash function (as explained in point 1).

Re:Leadtime for security: Is it too late?

[Kjella]

Let's start with the facts: SHA1 is cryptographically "broken" in the sense there's a "better than brute force" attack which takes about 2^63 operations instead of 2^80 of finding a colliding pair of two random strings.

It's not a practical attack because 2^63 is still a huge number.
It's not a "find a collision to a known string" attack which would be stage 2.
It's not a "find a collision to a known string by appending to a fixed string" attack which would be stage 3.
It is a sratch in the armor which creates doubt if there are more powerful attacks, nothing more.

There are strong alternatives like SHA-512 and Whirlpool (AES-based) which it is possible to use today, if you're paranoid more is better. Is it urgent? Not really, even a practical stage 1 and 2 attack would just be "stuff breaks, files corrupt, migrate away". The only one with really nasty consequences is stage three with code injection attacks in software and such.

Re:Wrong

[Fahrenheit 450]

Again you are wrong (and somewhat right about the incorrect title at the same time, iI suppose). The point of this workshop is to revise and amend FIPS 180-2. Now, while the SHA-2 line of hashes are laid out in FIPS 180-2, it is not the case that SHA-2 and the like will be thrown out. They meet the requirements laid out in the call, and frankly NIST would be insane to not make it one of the workshop's submissions. It may very well fall out that the SHA-2 is just fine and indeed the best candidate submission.

As for the Chinese attacks, they haven't shown any real applicability to SHA-2 as of yet.