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."

Draft location

The draft can be found (in PDF) here [nist.gov].

How long before we get

...the magical SHA-24M?

Leadtime for security: Is it too late?

The security of a given hash/encryption would seem to be a function of how much effort has gone into breaking it. Lots of algorithms can look good on paper, but until people really tear into the math and code, it's true level of unbreakability is undecidable. A 3 year competition is not likely to bring enough IQ, theorems, malevolence, or brute CPU cycles to bear against any candidate.

The point is that any attempt to quickly create a new algorithm is likely to create an insecure one. Shouldn't we be trying to create candidate algorithms for the year 2050 to give the algorithms time to withstand attack? Or do we plan to keep creating new algorithms as a serial security-by-obscurity strategy.

Re:Leadtime for security: Is it too late?

Shouldn't we be trying to create candidate algorithms for the year 2050 to give the algorithms time to withstand attack? Or do we plan to keep creating new algorithms as a serial security-by-obscurity strategy.

This is what a hash is by design: obscurity. For mathematical reasons alone, you can't have a unique hash for your megabyte message crammed in (say) 256 bytes. Or 512, or 1024 bytes.

And with a public algorithm spec, it's all about whether there's a determined group to turn it inside-out and make it easy to crack.

That said, the ability to hack SHA/MD5 given the time and tools, doesn't make hashes useless. A hash by itself can be useless, but coupled with a good procedure that incorporates it, it can raise the security level just enough so it's not reachable by 99.99999...% of the potential hackers out there that will try to break you.

Security is just an endless race on both sides, and will always be.

Re:Leadtime for security: Is it too late?

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:Leadtime for security: Is it too late?

That's great. Except for one thing...
Hashes are used all over the place in cryptography. That digital signature you generated? You didn't sign the message, you signed a hash of the message. That key you just exchanged? There was likely a hash involved in that process. Hashes are one of the basic building blocks of cryptographic protocols and systems, and while the recent weaknesses aren't too much to worry about yet as they aren't really practical or directly applicable, their presence is troubling.

And far more interesting (to me at least) are the attacks like Joux's multicollisions and Kelsey and Kohno's Hash Herding/Nostradamus attacks.

ROT-7

Rot-7. Everyone's doing ROT-13. I'm going to suggest Rot-7.

Think about it. You walk into a video store and you see Rot-13 and right next to it you see Rot-7 --which one you gonna spring for?

Not 13. Seven. Seven Little monkeys sitting on a fence...

Schneier Proposed this in 2005

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

Good News

The amount of research done in to hash functions is nothing like the amount that goes in to ciphers. I'm not really sure why this is the case because hashes are much more important than ciphers. Hashes are used in MACs to protect the integrity and authenticity of a message.

Ask yourself this, is it more important that somebody can read your SSH connection or that somebody can hijack the channel? The reasons for wanting a good hash function suddenly become very clear.

It's true that hashes are becoming less important as a result of AEAD modes. But they have uses far beyond MACs and it's good to see a competition from NIST to stoke research in to those primitives.

Simon.

Hash functions in common protocols

Does anyone know whether or not common protocols and formats such as TLS, ssh, X.509 certs, etc are being updated to use newer hash functions?

Its easy to change parts of a self-contained system, such as password hashes, but common protocols require interoperability and standards compliance.

This is actually fairly interesting situation, where NIST certification and platform interoperability may actually be at odds with each other.
   

Re:Hash functions in common protocols

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.

How about SHA-512?

Anybody know if SHA-512 is mathematically vulnerable to the same kind of attack as SHA-1 (only presumably requiring more computing power)? Or is it really a different kind of beast?

Multiple Hash Functions

I always wonder about what would happen if we used multiple hash functions together. E.g. you provide an SHA-1 hash, an MD5 hash, and an RMD-160 hash, all for the same message. Would that 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? What about weaknesses in the individual hash functions; would you be worse off because a flaw in any one of your hash functions affects you, or better off, because you have more hash functions that need to be fooled?

By the way, IIRC, OpenBSD and NetBSD include multiple hashes per archive in their ports trees, but use only one for verification.

Re:Multiple Hash Functions

Doesn't work very well. Read this:

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

Re:Multiple Hash Functions

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).

How frustrating!

The unfortunate thing is that in order to win this competition, the hash function submitted will have to be pretty conservative - very much like the SHA-512 family. There isn't time to analyze anything really new and have enough confidence in its security to bless it as the new standard for ever on. But if these attacks (and especially the recent attacks on the whole Merkle-Damgard structure) show us anything, it is that the old way turns out not to be the best way to build hash functions, and that more innovative ideas (eg Daemen et al's "belt and mill" proposal RADIOGATUN) should be the way forward.

What we need is for NIST to pull the rug under everyone near the end, and say "thanks for putting huge amounts of energy and hard work into designing and attacking all these hash functions, now you can all make new proposals based on what we've all learned and we'll start over again!"

One Word....

WHIRLPOOL.

It's a balanced design, an SPN to boot.

The big problem with the SHA's [and their elk] is that they're all UFN [unbalanced feistel networks], in particular they're source heavy. Which means the the branch/diffusion is minimal (e.g. it's possible to make inputs collide and cancel out differences).

SPN [substitution permutation networks] like WHIRLPOOL are balanced in their branch/diffusion.

Best of all, WHIRLPOOL is already out there. just a sign the paper!

Tom

What about multi-hashing?

So, I haven't studied this matter at all, but it seems to me that if you use more than one has algorithm on the same message, the chances of a different message generating the same has from both algorithms should be vanishingly small. Any cryptographers here care to fill me in?

-jcr

FYI

This "news" is several months old.

Oh well I know, it's Slashdot.

Wrong

TF title is wrong. It says: "A Competition To Replace SHA-1". But, it's to replace the whole SHA family, which includes both SHA-1 and SHA-2.

SHA-2 includes SHA-256 and SHA-512. Why the whole SHA family? Because its design is not very trustworthy anymore since the "Chinese" attacks in 2005.

Re:Wrong

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.

Some suggestions

Can we make a real competition and call it Hashing Idol where every week another function gets voted out? Or they could compete in a head to head. Two functions enter ring. One function leaves.
...
Have I been watching too much TV?

Perfect Solution...

I have a perfect solution to the hashing problem, for verifying the data integrity between two points...

You simply have to find autistic twins. The one at the source looks through the MB file, then writes a hash, explaining that it "smells like 5 green triangles". If the twin at the destination agrees, you know you have a match.

It's nearly impossible, even to brute-force this method... I mean, you need to covertly aquire a sample of their DNA, and wait several years for the clone to mature.

Of course, this method's weakness is that it doesn't scale-up effectively. There are only so many autistic twins out there, and human cloning technology is still quite expensive.

Well...

My expert advice is that now that we've seen what happened to the SHA-1 family, I think they should just skip the inevitable upcoming round of exploits for the SHA-2 family and go straight for a new SHA-3 family.

already alternatives exist

Right?

I mean, I have one program called "HashCalc" http://www.slavasoft.com.nyud.net:8090/hashcalc/in dex.htm [nyud.net]
Which includes:
Support of 12 well-known and documented hash and checksum algorithms: MD2, MD4, MD5, SHA-1, SHA-2( 256, 384, 512), RIPEMD-160, PANAMA, TIGER, ADLER32, CRC32.

I don't even know HALF of those. I knew of SHA1, but not of SHA256 384 or 512. Let alone Panama, Tiger, Adler32.

Not sure how "Secure" these other hashes or checksums are. The longer the string of characters, the more secure?

I still see sites offer up a CRC32 to check on your downloads...

Adi Shamir's Discrete Logarithm Hash Function...

...is provably collision-resistant.

http://senderek.de/SDLH/ [senderek.de]

'Proof' by Ron 'RSA' Rivest...

http://diswww.mit.edu/bloom-picayune/crypto/13190 [mit.edu]

SDLH is simple and secure to any number of bits of security desired once set up properly.

Factoring the modulus in SDLH is the only way to break it.

For that you need a state of the art number factoring algorithm (currently General Number Field Sieve [wikipedia.org] or Shor's Algorithm [wikipedia.org]).

Case closed.

I see an opportunity for a dead Sun proposal

Sun will propose an encryption scheme, it will be rejected, and Sun will release an open source alpha version of it, written in slow and unusable form, then make a press release about how their rejected product will replace something that isn't an encryption scheme at all *cough* Fortress *cough*

Using the existing hash functions securely.

You can still use the existing hash functions securely. According to my own analysis, SHA0 requires 108 rounds to be secure and SHA1 requires 104 rounds. Of course SHA0/SHA1 provides only 80-bit security and MD4/MD5 only 64-bit security, so you are better off using the 128-bit secure SHA2-256 or the 256-bit secure SHA2-512, but you have to use 96 rounds for the SHA2-256 to be secure and 104 rounds for the SHA2-512 to be secure. The point is that you are perfectly safe if you hash every block with any of the SHA functions or with MD5 twice. For the MD4 to be secure you have to hash each block three times. Whirlpool also needs 12 rounds to be secure, 10 is not enough.

Now that is a funny requirement...

From the official requirements PDF:

"A.3 The algorithm must support
224, 256, 384, and 512-bit message
digests, and must support a maximum
message length of at least 264 bits."

Someone either forgot the ^ carat, or thinks the world can get by on nine bytes of data at a time.

Re:Generic hashing is impractical

When you digest a message and obtain a hash it is obvious that there will be collisions.
It is obvious that there will be many possible inputs that produce the same output.

however the actual chance of encountering two inputs that hash to the same value by accident is vanishingly small.

with SHA1 even finding two inputs that hash to the same value deliberately is very hard and finding a second input to match an existing output is considered virtually impossible.

If I show you some pictures of people can you tell which one is me? Would you let me on a plane with just a grainy picture?
that is a very different situation because two photos of you will be far from identical. Secure hash functions are only usefull in the case where things are supposed to be identical (two copies of the same file for example).

Re:Generic hashing is impractical

No you can't very easily modify it - thats the point.

You can exhaustively search for a collision, but the time requirement is very much non trivial.

Feel free to prove me wrong - unless you have a huge botnet or a supercomputer available I dont give you much chance of finding a collision that way for md5 let alone SHA-1

Re:Generic hashing is impractical

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:Generic hashing is impractical

``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

Collision always exist,

what u don't want is an easy way to locate them!

Know that there is a collision is a normal thing,
be able to fabricate Hundred of them in a couple of minute
(It's NOT possible now with SHA1, but it's becoming just a bit easier..)

So better start now to replace it so if even more serius
problems are founded we will be in a good shiny new boat!
(It will probably also be sunked but we buy time in this way)

Re:Generic hashing is impractical

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:Generic hashing is impractical

I think that you are missing the point of a hash.

A hash is a signature of the file, its designed to give a good confidence that a given file that you have been supplied matches the one that you think has been supplied.

The theory being that being able to create a file that is of the same length as the orignal, is not corrupt (eg a zip file still unzips, an executable still runs, a pdf still displays) and is different from the original but still hash should be infeasable (not impossible, most cryptography doesn't look for impossible, not practical within a given time frame is sufficient for most needs)

Another use of hashes is on data storage systems, especailly with backup systems, where two files with the same hash and length are treated as the same file (so no need to write it to tape twice) this way you only have to sort the list of hashs and look for matches, rathering than having to diff every file against every other one.

Personally I think I'd rather binary diff matches hashes just to be safe - but thats time intensive. The chances of two files each having the same size and SHA-256 hash and being different is less than the chance of your sotrage device being destoryed (meteroite, fire, flood, plane) before you are able to back up either file

Re:Generic hashing is impractical

Sure there must be collisions, but that's not the point.

The point is that you can verify that data is correct with a good amount of confidence, from a relatively small hash code. So I can download a lot of data through, say, bittorrent, and despite the fact that I don't necessarily trust the people I actually download from, I can verify that the hash is right and therefore I am confident that the data I receive is what the original seeder put out: no-one's decided to play games and (say) sneak their CC number grabber into the data.

So what you want is an algorithm which is reasonably easy to run, which SHA-1 is, but where it is not easy to find a collision. For example, if my hash code was simply to give the total byte sum modulo 1000, then while it would almost certainly catch accidental errors in data, it would be very easy for an attacker to stick in his CC number grabber to your data then fiddle the byte sum back to where it should be.

Your idea pretty clearly shows you have no idea of what hashes are used for: there is no point preserving the data structure, it takes a lot of extra space and gives virtually no security. For example, SHA-1 produces a 20 byte hash. I can put something that size up on my personal website without getting huge bandwidth charges even if millions of people want to download it - and then I can distribute my 1GB zipfile by way of people I don't necessarily trust (but who have more bandwidth than I) and still the eventual recipients can be confident that what they receive is what I sent out. If I include the virtual FAT table of this zipfile, my hash size goes up by about 500,000 percent (literally), and so do my bandwidth charges. And I get virtually no extra security, because all that an attacker has to do above finding an SHA-1 collision is ensure that the change doesn't affect the FAT table: i.e. he replaces some suitable virtual file of mine with one of his, keeps the name and size the same and he's done.

Oh look, moron mods are out in full force.

Its not a troll morons, its the truth. Rijndael was THE LEAST SECURE algorithm that made the finals. It uses the same fundamental concepts as serpent, but takes shortcuts for speed. Serpent was the most conservative cipher in the contest, and twofish the most flexible. Either of them would have made sense. Rijndael was just fast on 686 class hardware (and not even much faster than twofish), and should not have been chosen to be AES. If you don't know shit about crypto, then don't mod posts about it.

Re:Perhaps you would better understand

It is in Amsterdam

      How appropriate for a conversation about HASH.

Not a different hash strategy...

Just different application. For example, if your application needs hashes, use two hashes. One hash of a byte-sized fixed field that gives you the 'hints' you desire, and because it is a fixed byte-size, it reduces the problemspace, and another hash that is considered in the context of the fixed field hints. The hashing algorithm need not change to do what you want.