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.

How long before we get

[Anonymous Coward]

...the magical SHA-24M?

Re:How long before we get

[bruno.fatia]

At least a couple years, after that chinese guy figures how to break the new ones too.

Re:How long before we get

[whitehatlurker]

It would be a Marvel if that hash were to be cracked.

Leadtime for security: Is it too late?

[G4from128k]

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?

[bhima]

The general consensus among the experts in cryptology is that a competition is far more effective than other methods of designing algorithms. Presumably the 3 years is a function of how long the world can wait as compared to how the experts need to crack it. The thing that makes me wonder is why they waited so long to begin it.

Characterizing this process as a "serial security-by-obscurity strategy" is completely wrong because due to the very nature of the competition the algorithm is known from the start.

Re:Leadtime for security: Is it too late?

[suv4x4]

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?

[cperciva]

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

Competitions like this and the AES competition aren't about inventing new cipher designs; they're about taking the state of the art and creating a standard. The ideas underlying Rijndael are essentially the same as those in Square, which was published back in 1997; while nearly all of the ciphers submitted to the AES competition were "new", the ideas behind them had been studied long before the competition started.

Of course, no competition will ever be able to anticipate future developments: If people had been paying attention to non-constant table lookup timing leaks (as Bernstein and Osvik/Shamir/Tromer demonstrate) it is unlikely that Rijndael would have won the competition. But unless we want to wait until cryptography is a dead field, with no new research being performed, this will occur whenever there is a new standard, and regardless of how long the process is which constructs that standard.

Re:Leadtime for security: Is it too late?

[duffbeer703]

Its not like everyone is starting from a blank slate on the first day of the contest. It's basically a call for the math geeks who design this stuff to polish up whatever they are working on.

Re:Leadtime for security: Is it too late?

[Sublmnl]

A professor once told me..."Knowledge is an infinite resource; we tap it when needed." Much the same as, "Necessity is the mother of invention."

It's difficult enough to figure out an encryption model that will be secure for the next few years, let alone to work out an encryption model for 50 years from now.

Immediacy and viability will be plenty to create encryption that is, "good enough for now." If you desire stronger encryption you might fair better asking hackers to break the current code.

Re:Leadtime for security: Is it too late?

[evilviper]

This is what a hash is by design: obscurity.

Not unless "obscurity" has been entirely redefined, recently.

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.

A (mathematically) good algorithm can stand up to such scrutiny. a "determined group" wouldn't make it any weaker. They can only (potentially) expose weaknesses in the algorithm, that allow it to be circumented faster than brute-force alone.

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

No, it isn't.

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

[PDAllen]

Hash insecurity is nothing like as much of an issue as cipher insecurity.

If I use a hash algorithm now, and I am confident that it's secure enough that no-one's going to find a useful collision within a month, then I can happily distribute my data for a couple of weeks, then I maybe need to find another hash algorithm, and the eventual recipients of my data can check their data against the hash I produce and be confident they got the right stuff; the possibility of an attacker coming along a few weeks later with some malware with an identical hash isn't an issue, because I'm no longer using the old hash as a certificate.

Whereas if I want to send secrets around, then I probably don't want anyone to be able to read them for a long time, so my cipher has to be much more secure against being broken.

Re:Leadtime for security: Is it too late?

[Beryllium Sphere(tm)]

>This is what a hash is by design: obscurity.

"Security through obscurity" means trying to depend on indefensible secrets. The classic example from 19th century crypto theory is that it's stupid to try to keep your crypto algorithm secret, so you should keep keys secret instead.

Security through obscurity leads to worldwide breaks when it fails.

The existing secure hashes have nothing obscure about them. The algorithms are published and open for review. The fact that they're vulnerable to brute force is not being hidden and is the same problem that all the workhorse encryption algorithms have.

"Security through obscurity" would be trying to hide the fact that there's a work factor reduction attack and hoping that nobody rediscovered it.

Re:Leadtime for security: Is it too late?

[bahstud1]

The thing is, this has been in motion since august 2005, when the proof of concept was announced @ the annual crypto con in Santa Barbara, Ca. Since then, NIST has hosted 2 HASH workshops and has entertained ideas from all kinds of experts.

There is nothing new going on....

Re:Leadtime for security: Is it too late?

[Fahrenheit 450]

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.

Re:Leadtime for security: Is it too late?

[mrmeval]

sha1sum sha224sum sha256sum sha384sum sha512sum

I have those on my system.

Re:Leadtime for security: Is it too late?

[Plutonite]

If that's correct, I wouldnt consider it much of a threat at all. It is scientifically correct for NIST to seek a hash that, in principle, is random enough to be brute-force-equal in terms of no. of attempts required, but practically it will make little difference.

There should be no password entry scheme in the world, in whatever application, that allows this number of attempts without delaying the attacker for years using various methods. But why did you say that

"find a collision to a known string" is different than the problem here? Aren't we talking about the input strings? If so, will it not take approx 2^63 attempts to find a string producing the same hash whatever the input?

Re:Leadtime for security: Is it too late?

[Fahrenheit 450]

"find a collision to a known string" is different than the problem here? Aren't we talking about the input strings?

No. There are a number of different properties that a cryptographic hash function should have. The first is what is referred to as collision resistance. That is, given a hash function H, the probability of finding any two strings x and y (x <> y) such that H(x) = H(y) should not be significantly greater than that of an ideal hash function (i.e. 2^-(|H(x)|/2)). The second (what the the GP was referring to) is one-wayness or non-invertability. With that the problem is, given H and input x, find an input y (x <> y) such that H(x) = H(y). The probability of this happening are not to be significantly greater than 2^-|H(x)|.

There are others, of course that have come to light of late, multi-collision resistance (i.e. finding k collisions should take k times as long as finding one collision -- most hash functions today only require log(k) times the amount of work), preservation of random oracle indistinguishability, length extension attack resistance, and so on. But the first two listed have always been of paramount importance.

Re:Leadtime for security: Is it too late?

[suv4x4]

You know, it's not considered cool anymore to just jump in random posts, split them in sentences and just say "no, it isn't" to every piece without adding anything of substance.

But.. you'll catch up. Eventually.

Re:Leadtime for security: Is it too late?

[evilviper]

You know, it's not considered cool anymore to just jump in random posts, split them in sentences and just say "no, it isn't" to every piece without adding anything of substance.

It is when the original has no substance to begin with...

Assertions are a perfectly valid response to other assertions.

Re:Leadtime for security: Is it too late?

[Omnifarious]

I'm sorry, there are purposes to which hash functions are put to in which even a 'stage 1' (by your nomenclature) break creates serious weaknesses. Basically it creates a situation in which any document of any kind that Alice creates and Bob signs can have a malicious substitute also created by Alice that Bob will have apparently signed.

The biggest example of this in modern usage is a Certificate Authority or PGP key signature. I would call both of those pretty important.

The required abilities of cryptographic hash functions are all important.

It IS true that there still are some uses of a hash function is good for even if it isn't resistant to the creation of two messages that collide. But I don't think going around analyzing all protocols to see which ones the hash function is still good for is a worthwhile pursuit, mostly because I think the time needed for a serious analysis is much greater than most people are willing to spend. It's much better to just create a new hash function which does have collision resistance and use that instead.

Re:Leadtime for security: Is it too late?

[mstahl]

As with pretty much any cryptographic system, the exact details of how the system works are usually well known by attackers and can still be extremely difficult to exploit. On the other hand, DES became "easily" breakable despite the U.S. government's decision to keep the exact details of the algorithm a secret. The way we're usually creating new algorithms today is to, for one, start with a problem whose complexity increases exponentially with problem size, then as computing power increases just increase the size of the problem. Everybody talks about SHA-1 like it's broken completely just because someone can do it 2000 times faster than brute force guesswork. Starting near 2^256, 2^256/2000 is still remarkably close to 2^256. Fudging slightly (it was an estimate after all) and saying a method is 2048 times faster, that's still only 2^11th, and it will still take 2^245 guesses or so on average. SHA-1 isn't obscure at all; the method by which hashes are generated is freely available to anyone who wants to know. It's still a bitch and a half to break.

Re:Leadtime for security: Is it too late?

[Calyth]

I couldn't agree more. Crypto hash are esigned to be preimage, second-preimage and collosion resistant. There is probably some limit on how secure the algorithm is based on how many bits the generated hash is; however it isn't security through obscurity.

Re:Leadtime for security: Is it too late?

[MrNaz]

Unfortunately there are more than 10'000'000 potential hackers trying to break me.

Darl McBride, is that you?

Re:Leadtime for security: Is it too late?

[PDAllen]

Yes - but that's still not an issue: if I send you an encrypted message using your public key, together with a signature (using a hash) to prove it's from me, then that's all fine. Now suppose that my enemy intercepts the message, and tries to find hash collisions to send you misinformation supposedly from me. Either the signature was encoded with the message (in which case it'll use a hash of the plain text) or it wasn't (in which case it generally uses a hash of the encrypted text).
In the first place, my enemy is stuffed unless he can break your cipher, in which case the crypto system's fairly useless anyway.
In the second place, my enemy can go looking for hash collisions. Let's assume a worst case: the hash is so badly broken that my enemy can quickly find a hash collision with a message that's almost entirely his choice: he can choose all but say 20 bytes of the message, maybe his algorithm is so good he can put the 20 bytes all over the message to look like spelling errors, and it still has the same hash as my encrypted message. Looks good for my enemy - except that his message will still _decrypt_ as garbage to you unless he can break your cipher, because although he can encrypt his message using your public key, when he is forced to change some bytes to make the hash work the decryption of the altered message will be very different, and he is still stuffed.

ROT-7

[Chapter80]

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

Re:ROT-7

[somersault]

What about a scheme based on ternary operators - ROT-6.5? 4 times and you're back to where you started, but anyone who is expecting ROT-13 will give up after the first try!

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:Schneier Proposed this in 2005

[Anonymous Coward]

Yeah, and it probably takes a year or two for a project like this to be fully thought-out, organized, blessed by the appropriate governmental approval agencies, &c, &c, &c. It's entirely possible that the origins of this contest were with Schneier's suggestion.

Re:Schneier Proposed this in 2005

[Anonymous Coward]

Yeah, but other people actually did something about it. The first workshop was in 2005.

Re:Schneier Proposed this in 2005

[Fahrenheit 450]

Yeah. 80% of the crypto world called for one too, they're just not as loud.

The thing is these kinds of contests take money and time to get running and (at least initially) NIST didn't have the resources to get a competition going. So what they did is organize a hash workshop for Halloween 2005, and had a second one last August following the Crypto conference where initial planning for the contest took place (a work shop that Schneier didn't bother to attend -- I guess he had yet another book to sell).

Good News

[Ckwop]

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.

Re:Good News

[steelfood]

Hashes are more important than ciphers. But hashes can only be secured so far. Beyond that, the return is minimal. All hash algorithms will eventually be cracked. It's the nature of hashing that the signature is not necessarily unique. Otherwise, it'd be called compression rather than hashing. The goal is to find an algorithm that will produce unique results under the most common conditions, and be least likely to produce the same result for two messages with purely algorithmic differences.

On the other hand, a good cipher can potentially be technologically unbreakable. So everyone is trying to find this holy grail (especially because once quantum computing comes along, today's strongest ciphers will amount to nothing) because it is theoretically possible, while for hash algorithms, this holy grail by definition doesn't exist, so researchers will only put enough time and effort to get to the next level of security when the previous level is threatened.

Re:Good News

[Paul Crowley]

This doesn't make any sense to me at all. Studied as theoretical objects, hash functions are "keyed" just as ciphers are. Just like ciphers, they are strong only against an attacker with limited computing power, not against an infinitely powerful adversary. Just like ciphers, we have no way of proving them secure, but through crypatanalysis we gain confidence in them.

And quantum computing has nothing to do with it; there are algorithms that are believed to be strong even in the face of quantum computing, and for symmetric primitives like block ciphers and hash functions, quantum computing is not a big problem.

Re:Good News

[mattpalmer1086]

Hashes aren't "more important" than ciphers. They're used for different things - apples and oranges.

"All hash algorithms will eventually be cracked". What do you mean by "cracked"? How broken does it need to be for it to be "cracked"? Enough that the US government could do it, that a crime ring could do it, that spotty teenages in their bedrooms can do it?

"On the other hand, a good cipher can potentially be technologically unbreakable". The only unbreakable cipher is the one-time pad. We already know that - and even those can be broken if they aren't used carefully. Other ciphers may be more or less resistant to attack than, say, a hash algorithm. More ciphers have been broken (in a practical, exploitable sense) than hash algorithms.

"once quantum computing comes along, today's strongest ciphers will amount to nothing". Not really. Only ciphers that depend on things that quantum computers can solve easily, such as the factorisation problem. So RSA would be useless, but elliptic curve cryptography might be fine. All the standard block ciphers like AES, 3DES and other wouldn't be affected at all, as they don't use the kind of maths that QCs are good at doing.

"for hash algorithms, this holy grail by definition doesn't exist, so researchers will only put enough time and effort to get to the next level of security when the previous level is threatened." There is no difference here between ciphers and hash algorithms (except that more ciphers have been broken than hash algorithms, so more work on ciphers has been done). Now it's time to do some work on hashes is all.

Re:Good News

[Omnifarious]

I have heard, but don't have a source, that elliptic curve is broken by quantum computing as well. I did a bunch of research when doing the initial design of CAKE because I figure that quantum computing will be a solved engineering problem at some point.

Re:Generic hashing is impractical

[petermgreen]

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

[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

[lordtagoh]

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)

Hash functions in common protocols

[Srin Tuar]

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

[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:Hash functions in common protocols

[Srin Tuar]

That doesnt seem to be the case.

Looking at the RFC for TLS:

http://www.ietf.org/rfc/rfc2246.txt
It seems sha-1 and md5 are the only options for hashes in 1.0.

Not to mention that the vast majority of existing implemtations would not be interoperable, even if it is technically possible to update the protocol to support newer hash algorithms. (there are asn.1 id's allocated, but the fixed sized buffers for the output of various hash functions may be different, etc, so protocol changes seem mandatory)

Re:Hash functions in common protocols

[Kjella]

Typically, they send some sort of algorithm list, choose the best algorithm they both have, and then use a hash to make sure the algorithm list was transferred successfully (so you can't downgrade security by doing a man-in-the-middle on the algorithm list). So basicly replacing SHA1 starts the day one "better than SHA1" client connects to a "better than SHA1" server, without any backward compatibility issues.

Re:Hash functions in common protocols

[Bert64]

But if you consider the length of time between AES encryption being available for SSL/TLS use, and microsoft actually supporting it (i believe they still don't) it's going to be years before these new hashing algorithms appear in microsoft products.

Re:Hash functions in common protocols

[Marillion]

While I agree that TLS and SSL and the like are flexible, the real barrier is not the specification but how long it take for a critical mass of adoption to make a revised specification useful.

Re:Hash functions in common protocols

[durdur]

My understanding is that, due to the way TLS/SSL works, the weaknesses in SHA-1 do not really affect TLS transport-layer security. Hash-based digital signatures are used to validate certificates, though, so the possibility of forging a cert indirectly weakens TLS.

Re:Hash functions in common protocols

[Srin Tuar]

My understanding is that, due to the way TLS/SSL works, the weaknesses in SHA-1 do not really affect TLS transport-layer security.

very true.

but when NIST says not to use it, your hands are tied one way or the other.

They have long turned a blind eye to MD5, because sha-1 was also present. But now its looking like the protocol itself will have to change, since both hashes used are now considered unacceptable :(

Re:Hash functions in common protocols

[ATucker]

Definitely not true at all.

The TLS key derivation function is hard coded to use SHA-1 and MD5 and there is no way in TLS to specify requiring or denying specific key lengths, asymmetric algorithms or hash functions in the certs for client or server authentication.

This paper from Bellovin and Rescorla covers the issues with TLS, SMIME and IPSEC:
http://www.cs.columbia.edu/~smb/papers/new-hash.pd f

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.

How about SHA-512?

[ngunton]

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?

Re:How about SHA-512?

[delt0r]

I beleive SHA-256/512 are fine. Also IIRC SHA-256 is a truncuted SHA-512 so there is little point using SHA-256 unless you have tight mesage size constraints. Also remember that SHA-1 is "broken" is a abstract type of way. In terms of real security its not really "broken" in the wild. Its just a little weaker than we hoped.

Re:How about SHA-512?

[tomstdenis]

No, SHA-224 is truncated SHA-256 and SHA-384 is a truncated SHA-512.

SHA-256 and SHA-512 are different hash functions (same basic design though). On 32-bit boxes SHA-256 is faster, and on 64-bit boxes SHA-512 is faster.

There is no point in 224 or 384, but they're there just for completeness (e.g. to comply with some specs that don't allow the arbitrary truncatage of a hash).

Tom

Re:How about SHA-512?

[delt0r]

My bad. Thanks for the correction.

Re:How about SHA-512?

[tomstdenis]

No worries. Common mixup if you're not waist deep in it all day (most customers don't quite know what SHA-512 is or why they can't pair it up with AES-512 hehehehe).

Tom

Re:How about SHA-512?

[iabervon]

SHA-512 and SHA-256 are essential the "SHA-2" family, with different details (leading to different output lengths). The SHA-1 flaw doesn't apply to them (which is why NIST is saying to move to SHA-256 from SHA-1 (-512 is a tad excessive if you weren't previously worried about length with 160 bits, and are leaving SHA-1 due to algorithm weakness).

Also, many uses for a secure hash are still safe with SHA-1 as far as has been published; the only issue presently is that people could prepare pairs of colliding documents with less effort than should be required, although this raises the concern that there are techniques for doing other things to SHA-1 hashes which haven't been published (or discovered) yet.

Multiple Hash Functions

[RAMMS EIN]

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

[rbarreira]

Doesn't work very well. Read this:

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

Re:Multiple Hash Functions

[finkployd]

In a nutshell, stacking hash functions makes it worse.

Finkployd

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:Multiple Hash Functions

[bfields]

You could take that as a warning against feeding the output of hash functions to each other in series; the OP however was asking about calculating hashes in parallel, and concatenating the output of the different hash functions. Seems to me that that's trivially at least as strong as the strongest of the individual components, but whether it's likely to be worse or better than a single hash of comparable output size sounds like a crapshoot.

Re:Multiple Hash Functions

[grumbel]

I don't think he wants to stack them, but instead simply concat them:

md5sum foo -> 4f1cbee4972934c3beccc902f18242a7
sha1sum foo -> 3c92a387f898a31d2e8af31caff27c0f8f7a5a3a
md5sha1sum foo -> 4f1cbee4972934c3beccc902f18242a73c92a387f898a31d2e 8af31caff27c0f8f7a5a3a

That should definitely not weaken anything, it will require some more CPU and storage, but thats it.

Re:Multiple Hash Functions

[PDAllen]

It would almost certainly be much harder, but it would mean your hash overheads would triple (bandwidth and processing), and that is very important for hash codes.

Re:Multiple Hash Functions

[rbarreira]

Read the link properly, that's not what it says or talks about.

Re:Multiple Hash Functions

[RAMMS EIN]

``That should definitely not weaken anything, it will require some more CPU and storage, but thats it.''

First of all, you're looking at quite a bit more CPU. At least with the hash functions I've implemented, as well as with MD5 and SHA-1, the time needed to compute the hash depends on the amount of data processed, not really on the size of the hash (some hash functions actually run quicker if you compute larger hashes). If you want to use three different hash functions, rather than one that is triple the size, you will need about three times as much time.

Secondly, as the post linked to earlier explains, multiple hashes together _are_ weaker than one large hash. The reason is that, once you've found a collision in a single hash function, it's easy to generate more of them. The example it gives is for 160-bit hash functions. It takes 2^80 attempts to brute-force a collision in such a function. Now, you might think it takes 2^80 * 2^80, i.e. 2^160 attempts to brute-force a message that collides in both of them (which would be the case for a single 320-bit hash function), but it doesn't. The reason is that it only takes you 2^80 * 80 attempts to get 2^80 colliding messages for the first 160-bit hash function...which gives you enough of them to brute-force a collision in the second. 2^80 * 80 is obviously a lot less that 2^80 * 2^80...

Re:Multiple Hash Functions

[bfields]

OK, (reading to the end this time!) so the point as I understand it is that existing hashes have the property that it's much easier than it should be to find n-way collisions (even when finding ordinary 2-way collisions is hard), and that makes it easier than it should be to turn a collision in one of the concatenated hashes to a collision on the concatenation, by generating an n-way collision for n large enough that it contains collisions on the other hash(es). So while the result is stronger than any of the individual hashes, it's dramatically less than it should be given the additional bits.

Re:Multiple Hash Functions

[v4vijayakumar]

... H(x) = SHA1(x) || RIPEMD160(x) ... ?!

How strong are the following hashing functions?

H(x) = SHA1(SHA1(x))
H(x) = RIPEMD160(RIPEMD160(x))
H(x) = SHA1(RIPEMD160(x))
H(x) = RIPEMD160(SHA1(x))

How frustrating!

[Paul Crowley]

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

Re:Generic hashing is impractical

[simm1701]

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

One Word....

[tomstdenis]

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

Re:One Word....

[G-Licious!]

Amen!

And many, many thanks for your public domain implementation. :)

Re:One Word....

[delt0r]

I assume it could be entered as a contender?

Re:One Word....

[tomstdenis]

I definitely hope so. I certainly don't look forward to the deluge of non-mathematical FROGHASH style [or HPC] submissions which IMHO are a total f'ing waste of time.

I'd say if you can't prove the branch of your primitive then you need a REALLY COMPELLING reason to submit it. Otherwise, be gone!

Tom

Re:One Word....

[tomstdenis]

You're welcome.

Glad to be of service.

Tom

Re:One Word....

[Paul Crowley]

Whirlpool is pretty slow. What do you think of Radiogatun?

Re:One Word....

[tomstdenis]

Whirlpool is slower than SHA ... but SHA is insecure so it's a meaningless comparison. memcpy() is faster than AES-CTR!!! :-)

Never heard of Radiogatun. To be honest i'm not really into crypto as much as I used to be. The whole debacle with the LT projects threw me off. I'd much rather play a Sonata on my piano than read a dry boring paper about cryptography. :-)

Tom

Re:One Word....

[Fahrenheit 450]

Of course it's also slower than SHA-256 and SHA-512 which have no reported weaknesses, so ... not no meaningless.

Re:One Word....

[tomstdenis]

Presumably this is because people lost faith in the UFN approach. If that's the case, comparing new designs to the faster, but generally accepted as insecure designs, is not wise nor prudent.

I'm not saying WHIRLPOOL is perfect, but it's definitely a step in the right direction. Maybe this contest will spur a faster hash which is also as mathematically sound.

Tom

What about multi-hashing?

[jcr]

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

Re:What about multi-hashing?

[jcr]

Please s/has/hash/ in the message above. I guess my finger-memory to type "has" is pretty strong.

-jcr

Re:What about multi-hashing?

[madcow_bg]

Dunno about cryptographers, but Gentoo uses that already. Just see:
* portage-2.1.1.tar.bz2 MD5
* portage-2.1.1.tar.bz2 RMD160
* portage-2.1.1.tar.bz2 SHA1
* portage-2.1.1.tar.bz2 SHA256
* portage-2.1.1.tar.bz2 size

By the way, this is not a bad solution, since it uses industrial standards. The problem is that if you can't use this solution: i.e. want to store the hash of a password to check, you can't use this method, as brute forcing will still wield the same result.

Re:What about multi-hashing?

[pipatron]

The chance of a different message generating the same hash basically only depends on the number of bits used in the hash. Sure, a combination of hash functions would give more bits. However, I strongly suspect that the combination of two hash functions to create one final hash would always be worse in that respect than a carefully designed hash function with the same number of bits.

No hashing algorithm can care for more than 2^bits number of different documents.

Re:What about multi-hashing?

[sethawoolley]

sourcemage.org supports any hashes supported by gnupg. In addition, it supports upstream author and package maintainer gnupg directly and lets you apply trust configuration values to the validation engine. I wrote that part of the package manager some time ago.

Gentoo's been behind the times with package management for a long while now.

Re:Generic hashing is impractical

[simm1701]

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

FYI

[trifish]

This "news" is several months old.

Oh well I know, it's Slashdot.

Re:FYI

[Fahrenheit 450]

No, it's not. The draft requirements and evaluation criteria were announced just yesterday.
Unless you live in a place where January 23, 2007 is several months ago....

Re:FYI

[trifish]

Wrong. If you read the first line of the summary, it says: "NIST is preparing for a competition to augment and revise the current Secure Hash Standard." THAT is several months old news.

Re:FYI

[Fahrenheit 450]

Yes, I can see how a line containing some of the background of the story would change the fact that yesterday's publication of the draft requirements for the hash candidates actually occurred yesterday and not several months ago.

Re:FYI

[trifish]

You're a bit slow. Anyway "yesterday's publication of the draft requirements for the hash candidates" is still part of the preparations for the contest. They just elicit comments on the submission requirements. The contest has not begun. And now the point: The preparations began MONTHS ago. Got it now?

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.

Wrong

[trifish]

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

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

Re:Wrong

[trifish]

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

The keyword is "yet". The only thing that "protects" SHA-2 from the attacks are a bunch of extra rotations. If you think NIST and NSA are going to rely on that as a strong form or protection, you're a bit naive.

Re:Generic hashing is impractical

[PDAllen]

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.

Some suggestions

[UnknowingFool]

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

[evilviper]

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.

Re:Perfect Solution...

[Anonymous Coward]

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.

You're a horrible person.

If you really knew autistic children you'd know that nothing smells like 5 green triangles to them. Four, at most.

Re:Perfect Solution...

[T5]

The problem with your idea is that you're post smells like 5 green triangles too! As do a lot of other posts on /. Like this one.

Re:Perfect Solution...

[dumbunny]

The NSA could probably break this system in a few months. They would just detain the public autistic twin down in Gitmo and brute-force him into admitting that the MB file does, indeed, "smell like 5 green triangles." Since the US has relaxed its cryptography export restrictions, they could send him to any number of secret, overseas detention centers as well.

Re:Moo...

[tomstdenis]

This is why we have editors...

I don't know what's scarrier, my loose grasp of formal language, or that I'm the author of two comp.sci text books :-(

hehehehe

Whatever, I do what I want!

Tom

Think of it as synchronization.

[Kadin2048]

As other people have pointed out, I'm not necessarily sure that these competitions really result in a whole lot of new development work per se. Rather, they serve as encouragement to researchers in the field, to take whatever they've been working on for the past few years, tidy it up and make it publishable, and submit it as a candidate for standardization.

The research into new functions progresses more or less on its own in the academic world most of the time. These competitions basically seek to tap into what's going on there, and re-synchronize the commercial/governmental world with whatever the state-of-the-art is in academic cryptography.

Re:Moo...

[swillden]

...or whatever sound that Elk make ;-)

They make a variety of sounds, most of them surprisingly high and squeaky for such large animals.

Competitions change the community

[Paul Crowley]

I disagree. The AES competition really galvanized the research community and resulted in some exciting innovations in cryptography - eg the application of bitslicing to the construction of ordinary primitives a la Serpent - and cryptanalsysis - eg Lucks's "saturation attack". And we're seeing similar effects with the eSTREAM competition, which in turn results from the way that all the stream ciphers proposed for NESSIE were broken.

Not obscurity

[sacrilicious]

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.

Your point about the impossibility of producing unique M-byte hashes for every N-byte message (where N>M) is of course mathematically correct. But instead of thinking of hashes as working via obscurity, think of the function of the ideal hash to be: the impossibility of finding data with a matching hash without so radically changing the input data that the change is obvious to anyone who sees it. For example, if someone can produce a page of text that has the same hash value as garbage, or as a video of a monkey, the value of the hash function is not diminished. Whereas if someone can produce two license agreements that differ only in the phrases "I accept the following terms" and "I do *not* accept the following terms", the hash function is considered broken.

A hash function seeks to re-map a mathematical space in such a way that previously "adjacent" places in the input space are far apart in the output space. An ideal hash function would do this

• (a) uniformly: for all points in the space; and
• (b) unpredictably: H(A)-H(B) != H(A+X)-H(B+X); (so for example, by this criteria a simple checksum is not a good hash)

Re:Not obscurity

[petermgreen]

For example, if someone can produce a page of text that has the same hash value as garbage, or as a video of a monkey, the value of the hash function is not diminished.
due to the block based nature of many hash algorithms and the nature of many file formats, for many applications if someone can find ANY two inputs that give the same hash you are in shit, this is what has essentially happened with MD5 and is dangerously close (read: isn't known to have been done yet but someone with the NSAs rescources could almost certainly do it) with SHA1

The ideal hash is a hash where it is virtually impossible to find a collision now or in the forseeable future. Since every hash is vulnerable to the birthday attack we set that as our "perfect hash of a given length" and consider any reduction in the break time from that to be breakage of the hash.

Re:Not obscurity

[sacrilicious]

due to the block based nature of many hash algorithms and the nature of many file formats, for many applications if someone can find ANY two inputs that give the same hash you are in shit

Could you explain this a bit more fully?

Re:Not obscurity

[petermgreen]

with md5 and sha you essentially run the process on a block of data at a time using the results from one block as a set of "starting values" when doing the next block.

you choose a format (pdf is a good one) where you can easilly build conditionals into the document structure.

then you prepare a header which is a whole number of blocks in size and run it through your md5 calculator.

Then you run your collision searcher telling it what starting values you want to find a collision for. This then produces two blocks of random data which when added to the end of the headers give the same MD5.

then you prepare the rest of your document which is really two different documents with a conditional to check something in the random blocks and display one or the other. you add this to the end.

the result is two pdfs with contents of your choice which have the same md5.

Re:Not obscurity

[MrNaz]

Right, in theory, wrong in practice (I think).

Even telling your collision searcher that the hash you want to look for can be for a document of any length and with any content as long as it starts with a capital "A" will be very hard. Mathematically, it will be (assuming you are using monobye ASCII) 256 times harder than just finding a random data block. Finding a similar hash that starts with "As" will be 256^2 harder than finding a random data block. In short, the more specific you need the data to be, the harder finding a hash that matches that will be.

The idea of a hash is that appending data to an existing data block radically changes the resulting hash. One cannot simply start with a given data block and append data to it to find a hash, the resulting linear equation will be monstrously difficult to solve and far outside of current computing capacity.

In theory, given any data block, there should be a 128bit string that can be appended to it to generate the the same MD4 as the block would give without it. Finding the right string to append to say a 1mb file is, even with the deprecated MD4, outside the resources of any known computing facility including the Lawrence Livermore monster.

Re:Not obscurity

[petermgreen]

i belive there is a working example out there of the technique i just mentioned for MD5 and SHA1 operates on the same basic principles so it should be possible there as well given enough computing power to find a SHA1 collision (which right now is in the realm of possible but hard).

As i said MD5, SHA1 and thier ilk all work in blocks, you take a set of starting values (eqivilent to hashing the previous blocks in your file) and a block of data and you get a new block out the end (there is also a little preprocessing to deal with files that are not a whole number of blocks in length but that doesn't really concern us here)

The result of this is it is no harder to find a collision for two files starting with your header block and following it with a block of random junk than it is to find two blocks that collide when placed at the start of the file.

and if your two files start with the header block followed by one of your colliding blocks followed by the same data those two files will also collide since the starting values for subsequent blocks will be the same.

Re:Not obscurity

[MrNaz]

Wow, I thought block collisions ended back when they killed MD2.

Thanks for the clarification.

Re:Not obscurity

[petermgreen]

that shouldn't be too big a deal

assuming the padding step is some form of preprocessing that only affects the last block you just do your collision finding on a version of sha1 with the padding step removed, then you add the trailers complete with the correct padding for the length of prefix+random block+trailer

Re:Not obscurity

[sacrilicious]

Ah, I see. Quite clever! Thank you for the excellent explanation.

My feeling is that this technique doesn't sufficiently qualify a hash as broken, since anyone who digitally signs a doc and either remembers the gist of it or keeps a copy for themselves can require the folks using this technique to produce their copy of the doc for discovery... and of course it would never stand up to technical scrutiny, the monkeying would be obvious.

Not mathematically advantageous, but still useful.

[Kadin2048]

I was wondering the same thing, and apparently so were a few other people besides. There's another discussion of it further up in the thread, and the quote which seems to be the final answer doesn't seem to be too hot on the idea. Here it is (quoting here from another source):

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

What this means to me is both 'yes,' and 'no.' Yes, using multiple hash algorithms protects against the failure of one algorithm. It avoids putting all your eggs in one basket. However, using multiple algorithms doesn't, in itself, offer any greater security than just using a single algorithm and a longer hash, assuming the algorithm is good. (By 'good,' I mean that it doesn't offer any ways of finding collisions that are significantly faster than brute force.)

Mathematically, using multiple algorithms may not offer much of an advantage, but practically, where you may by necessity have to work with algorithms that have flaws (because you have to pick from algorithms that are well-agreed-upon standards), or that may be discovered to have flaws in the future, it seems like a good way to hedge one's bets. Aside from the added complexity, there doesn't seem to be any compelling reasons not to do it, if time and computational power allow.

Well...

[Jugalator]

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.

Re:Generic hashing is impractical

[petermgreen]

Sure, it might take a while, but it would be possible.
sure but with a decent hash algorithm the sun would most likely go red giant before you finished so its a non-issue.

Re:You clearly don't know what a crytographic hash

[roguegramma]

You meant to say "maximum amount of work" is needed.

I'm not sure whether a "broken hash" which e.g. maps blocks of 512 bits to 256 bits isn't better than a bijective hash which maps a 256 bit space to a 256 bit space, because bijectiveness is a property which can probably be exploited just as well as non-bijectiveness (= hash collisions).

already alternatives exist

[Anonymous Coward]

Right?

I mean, I have one program called "HashCalc" http://www.slavasoft.com.nyud.net:8090/hashcalc/in dex.htm
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...

Re:already alternatives exist

[Paul Crowley]

Not hash functions at all: ADLER32, CRC32 (collisions trivial to make)
Broken: MD2, MD4, MD5, SHA-1, PANAMA
Suspect after recent attacks, vulnerable to generic MD attacks: TIGER, RIPEMD-160
Very, very slow: SHA-2

Re:already alternatives exist

[owlstead]

MD2, MD4 and MD5 as well as Panama are broken. Tiger seems to be an old hash function that has at least 16 rounds broken. ADLER32 and CRC32 are not *secure* hash functions, just checksums. RIPEMD-160 is also quite old, and simply said, the number of bits (160 obviously) only provide a maximum of 80 bits protection. So, with SHA-1 under attack, your HashCalc "only" provides the SHA-2 family of secure hashes. An inclusion of WHIRLPOOL would have been nice. I put only between "" because there are not many true and tried hash algorithms out there that are up to the task. Actually, that is one of the main gripes of Bruce Schneider with the current state of cryptography.

CRC32 is fine for detecting errors in downloads, but it doesn't provide a way to test for genuinity. If that is all you need, CRC32 is fine.

Re:Generic hashing is impractical

[Anpheus]

I would have thought that brute force no longer implied 2^X attempts as the 'standard' for brute force. Wikipedia gives a lovely equation (hope it's accurate!,) such that if we want a 50% chance of finding a collision, we let H be the number of possible values in the hash, and let n(P) be a function representing the number of values that must be tested for a desired probability of collision P. n(P) = 1.1174sqrt(H). Applying that to a 160-bit value gives us 'only' 1,350,853,710,837,386,639,816,681 values. That's a phenomenal result (1.35x10^24) because it is drastically lower than 2^160 (1.46x10^48.) And the neat thing about the birthday attack is that as we increase P, n'(P) decreases. (dn/dP)

Oh look, moron mods are out in full force.

[Anonymous Coward]

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.

SASH-1280?

[kirils]

Why don't we try using SASH-1280 for a while? http://kirils.org/sash-1280-1.0.pdf

Yeah, I did write that myself, but it doesn't for granted mean it's insecure, does it?

Re:Perhaps you would better understand

[gardyloo]

It is in Amsterdam

      How appropriate for a conversation about HASH.

Re:Generic hashing is impractical

[MrNaz]

Even applying that math, you still have non-trivial time requirements. Assuming you can test for collisions at a rate of 10^12 attempts / second (that's a thousand billion attempts per second, a rate that would requre a very large grid or supercomputer) you still have to wait in the order of magnitude of 10^12 seconds. I.e., about 31,700 years.

In reality, collision testing would not be able to be done anywhere near that fast, I'd guess the assumption of 10^12 attempts / second is about 1,000 times faster than anyone could do it. Anyone with real world experience in finding hash collisions feel free to chime in right about now.

A non-tiny data block (anything over say over 100kb) would require a huge amount of processing power and memory bandwidth in order to find a collision with a similar sized data block. Lets go back to our 10^12 cracking grid. To find a 100kb data block with a given hash at that rate would require the computer to have 100kb*10^12 transferred from memory to the CPU every second and then hashed. That's 100,000,000,000,000kb, or 100petabytes between CPU and memory every second plus whatever CPU power is required to perform 10^12 hashes on that data. While clever use of the hardware and lots of L2 cache could perhaps keep this off the main memory bus, it's still a phenomenally difficult task for any CPU.

Take these figures, and assume that it is now 2,000 times easier. These figures still put the time at finding a collission outside of the average lifespan of a person. Now factor in the fact that not just *any* collision will do, we need one that's about the right size and has at least a certain *part* that looks like something useful. I.e., a random data block is not a useful substitution for a PDF of an important doc, the recipient will notice if they receive random data instead of something readable. The practicality of any attack given these real world constraints goes down by an order of magnitude or two.

In short, SHA-1 is still safe. There is no realistically exploitable attack vector, at least not in the public domain as yet. That being said, I am a paranoiac. In the DB file stores that I am in charge of I keep both MD5 and SHA-1 hashes in the metadata table, and have been recommending this for years.

Adi Shamir's Discrete Logarithm Hash Function...

[iamcf13]

...is provably collision-resistant.

http://senderek.de/SDLH/

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

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

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 or Shor's Algorithm).

Case closed.

I see an opportunity for a dead Sun proposal

[XPulga]

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*

Re:Generic hashing is impractical

[jd]

My understanding is that you are correct. The correlation is, I believe, along several different dimensions and not just a trivial one. The trivial case is that if you change some given number of bits in a message, over some distribution, then the changed bits in the hashed value should not be predictable in either number or distribution. The next-most trivial case is that if you add some new data to the end of a message, then the changed bits in the hashed value should also be unpredictable in number or distribution.

In addition to those two cases, what else can we say? Well, we can say that a cryptographically strong hash is a many-to-one mapping, where the set of cases that map to the same hash value should follow a random distribution AND where the set of differences between the aliases of any two hash values should also follow a random distribution.

(By random, I mean that the deltas aren't constant, cyclic, polynomial or otherwise predictable. You can't use any subset in order to predict any other subset. I also mean that for an infinite number of deltas, all possible delta values will occur with a frequency equal to the probability of that delta. In this case, you would want a flat probability, so all delta values will occur equally.)

Another way of saying all of this is to say that finding the aliases for a given input should be an NP-complete problem - the only way to find them is to look.

Anything else? Well, since most of this is extremely hard to test for, there needs to be a few tests that are more practical. The first would be that the hashing function should be in its simplest form. There should be no way of reducing it - for all inputs or for selected subsets of inputs. The second would be that the hashing function is non-differentiable (otherwise related inputs will produce related outputs). The third is that the function should be sensitive to initial conditions (for much the same reason). The fourth is that for any random selection of inputs where the pool of inputs is statistically significant, a standard statistical test for randomness should yield unimaginably high confidence limits that the distribution is indeed random. The chances of it not being random - ie: the chances of you finding an alias algorithmically and not herustically - should be no better than finding the alias by chance alone. (So, even if the hash could be broken, the chances of you finding the flaw are no better than of you finding the alias in the first place.)

I'm sure there are a million other tests that could be applied, but these are the more "obvious" ones that spring to mind. People can turn anything into cryptographic hashes (FFTs and even cellular automata have been used) - my guess is that chaotic systems might be another area of interest, provided you could guarantee the input was always in a chaotic region, as chaotic systems are only that way for specific conditions and can become periodic or stable outside of those limits, which is exactly what you don't want.

Using the existing hash functions securely.

[Ruptor]

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.

And who would you trust...

[Paul Crowley]

And who would you trust to generate the shared N that everybody uses? Whoever knows p and q will trivially be able to break the hash function every way you can.

Other serious problems with this hash function are (1) The output is much too long (2) it's far too regular to substitute for a random oracle where one is needed, and (3) it's much, much too slow.

It's cool - and the proof is cool - but it's not a serious contender for normal applications.

Re:And who would you trust...

[iamcf13]

And who would you trust to generate the shared N that everybody uses? Whoever knows p and q will trivially be able to break the hash function every way you can.

Write your own bignum package and run it on an un-networked computer. I did just that not long ago in 100% C code (Visual C++) using only a small __asm function to read the Pentium CPU cycle counter and the CString 'datatype'.

FWIW, it generated 2 1024(+) bit 100% provable prime numbers that could be multiplied together into a modulus in under 10 minutes on a friend's 2.8 GHz Windows PC.

Other serious problems with this hash function are (1) The output is much too long (2) it's far too regular to substitute for a random oracle where one is needed, and (3) it's much, much too slow.

Concerning (1), SHA-512 is the largest secure fixed-length hash around that I know of, has only 256 bits of security. What if you need more?

I'm not a cryptographer but I know how RSA works. Please explain (2) in detail, I am curious.

As for (3), that's the only downside to SDLH, even with using Montgomery exponentiation to speed up the calculations. If you want/need fundamentaly perfect security with factoring the modulus as the only problem, barring coercion or eavesdropping, then SDLH is for you.

It's cool - and the proof is cool - but it's not a serious contender for normal applications.

SDLH can only be broken by throwing fast and/or exotic hardware or more efficient integer factorization algorithms at it. Can the same be said of the successor to SHA-512 when/if it gets broken? Remember how the NSA tweaked DES to frustrate differential cryptanalysis before other people 'rediscovered' it?

Same thing happened with RSA -- some government guy in England's version of the NSA discovered it a few years before the 'RSA' guys 'rediscovered' it.

Re:And who would you trust...

[Paul Crowley]

And who would you trust to generate the shared N that everybody uses?

Write your own bignum package and run it on an un-networked computer.

For some applications, everybody has to share the same hash function. If the hash function is SDLH, then whoever generated N can break the application. By contrast, Rijmen has no special advantage in breaking WHIRLPOOL-based applications.

I did just that not long ago in 100% C code (Visual C++) using only a small __asm function to read the Pentium CPU cycle counter and the CString 'datatype'. FWIW, it generated 2 1024(+) bit 100% provable prime numbers that could be multiplied together into a modulus in under 10 minutes on a friend's 2.8 GHz Windows PC.

Good for you - this sort of code is fun to write and good programming practice, and the math behind provable primes is cool. Bear in mind, though, that there's no problem with Rabin-Miller-based prime generation in pratice - the probability of a false positive from RM is much less than the probability of a false positive due to a hardware glitch.

Concerning (1), SHA-512 is the largest secure fixed-length hash around that I know of, has only 256 bits of security. What if you need more?

The problem is that SDLH requires many more bits of output from the same level of security.

SHA-512 has 512 bits of output and the best attack currently known requires 2^256 work - vastly, vastly more than we could ever imagine doing in the next century. By contrast, an SDLH based on RSA-200 would have 663 bits of output, but it's been demonstrated that we can break a modulus that size today. To be as confident of the security as we are of SHA-256, the output of SDLH would have to be thousands of bits long - that would be really quite impractical for many protocols.

By the way, you really don't need more than 256 bits of security. Remember what Bruce Schneier says about the stake in the ground.

I'm not a cryptographer but I know how RSA works.

I am a cryptographer, and you may be surprised about how much there is to learn about how RSA works. The random oracle model is at the heart of the proofs of security for protocols based on RSA. The proof is there to show that the only way to break the protocol is to find an efficient way to solve the RSA problem. The proof says "OK, supposing we had a random oracle, accessible to all parties including the attacker, and it returns random fixed-length outputs given arbitrary-length inputs. Could you break it then?" For practical protocols, we substitute a hash function for the random oracle. When we do that, we're making an assumption that the hash function has basically no interesting structure at all that could be useful to an attacker. It's pretty clear that the output of SDLH has lots of structure - the only property we can really be confident of is that it's collision-resistant, and that's not nearly enough.

To put it another way, strong cryptography is a mixture of mathematics and muddle. If RSA is providing the mathematics, the hash function provides the muddle. A hash function based on a mathematical problem doesn't provide enough muddle to use here.

Sorry I haven't gone into more detail here. The random oracle model is quite hard to explain briefly - you should read Bellare and Rogaway's "Random Oracles Are Practical" if you want to discuss this further.

SDLH can only be broken by throwing fast and/or exotic hardware or more efficient integer factorization algorithms at it. Can the same be said of the successor to SHA-512 when/if it gets broken? Remember how the NSA tweaked DES to frustrate differential cryptanalysis before other people 'rediscovered' it?

Indeed, and it turns out that DES is surprisingly strong for its keysize, even though it was designed in the dark ages - brute force is still the most

Re:And who would you trust...

[iamcf13]

A hash function based on a mathematical problem doesn't provide enough muddle to use here.

How about the Blum Blum Shub Sequence Generator? (see 6.3.2 in RFC 1750)

It apparantly can be used for cryptographic tasks but has the same factoring 'flaw' and size issues as SDLH. Your thoughts if any about this?

Thanks for your long reply to my earlier post, it was very informative. :)

Re:And who would you trust...

[Paul Crowley]

Yeah, there are ways of doing without the muddle for that problem, and indeed there are entire protocols that can be proven secure without the random oracle model. However most practical protocols still rely on the RH (which allows better hardness assumptions), and for that muddle is unavoidable because we don't have a way of defining what it means to be "like a random oracle", and indeed there are some proofs that this goal is unattainable.

Really, if you're worried about eg AES being broken you're worrying about the wrong security issues. That isn't where our problems lie.

Re:Generic hashing is impractical

[simm1701]

Correct me if I'm wrong but isn't that a just binomial expansion approximation?

Not a different hash strategy...

[Junta]

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.

Now that is a funny requirement...

[chancycat]

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.