A Competition To Replace SHA-1 159
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 (Score:5, Informative)
How long before we get (Score:3, Funny)
Re: (Score:2)
Leadtime for security: Is it too late? (Score:3, Insightful)
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: (Score:3, Interesting)
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? (Score:5, Insightful)
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: (Score:2)
Not unless "obscurity" has been entirely redefined, recently.
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.
Re: (Score:2)
But.. you'll catch up. Eventually.
Re: (Score:2)
It is when the original has no substance to begin with...
Assertions are a perfectly valid response to other assertions.
Re: (Score:3, Informative)
"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
Not obscurity (Score:2)
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
Re: (Score:2)
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
Re: (Score:2)
Could you explain this a bit more fully?
Re: (Score:2)
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 blo
Re: (Score:2)
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.
Re: (Score:2)
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 prepr
Re: (Score:2)
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: (Score:2)
I have those on my system.
Re: (Score:2)
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
Re: (Score:3, Informative)
Re:Leadtime for security: Is it too late? (Score:4, Informative)
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: (Score:2)
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 cryptog
Re: (Score:2)
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
Re:Leadtime for security: Is it too late? (Score:4, Interesting)
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 (Score:2, Funny)
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: (Score:2)
Schneier Proposed this in 2005 (Score:5, Informative)
Re: (Score:3, Informative)
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 (Score:4, Interesting)
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: (Score:2)
On the other hand
Re: (Score:2)
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,
Re: (Score:2)
"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 t
Re: (Score:2)
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 [cakem.net] because I figure that quantum computing will be a solved engineering problem at some point.
Hash functions in common protocols (Score:4, Interesting)
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 (Score:4, Informative)
Re: (Score:2)
That doesnt seem to be the case.
Looking at the RFC for TLS:
http://www.ietf.org/rfc/rfc2246.txt [ietf.org]
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: (Score:2)
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
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
How about SHA-512? (Score:4, Interesting)
Re: (Score:2)
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 d
Re: (Score:3, Informative)
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: (Score:2)
Tom
Multiple Hash Functions (Score:2, Informative)
Re:Multiple Hash Functions (Score:5, Informative)
http://www.mail-archive.com/cryptography@metzdowd
Re:Multiple Hash Functions (Score:4, Informative)
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: (Score:2, Informative)
Re: (Score:2)
Re: (Score:2)
Re: (Score:3, Informative)
md5sum foo -> 4f1cbee4972934c3beccc902f18242a7
sha1sum foo -> 3c92a387f898a31d2e8af31caff27c0f8f7a5a3a
md5sha1sum foo -> 4f1cbee4972934c3beccc902f18242a73c92a387f898a31d2
That should definitely not weaken anything, it will require some more CPU and storage, but thats it.
Re: (Score:2)
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 s
How frustrating! (Score:3, Interesting)
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!"
Think of it as synchronization. (Score:2)
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
Competitions change the community (Score:2)
One Word.... (Score:5, Interesting)
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: (Score:2)
Re: (Score:2)
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: (Score:2)
Re: (Score:2)
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
Re: (Score:2)
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: (Score:2)
Glad to be of service.
Tom
Re: (Score:2)
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
Re: (Score:3, Funny)
They make a variety of sounds, most of them surprisingly high and squeaky for such large animals.
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
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.
Not mathematically advantageous, but still useful. (Score:3, Interesting)
FYI (Score:2, Offtopic)
Oh well I know, it's Slashdot.
Re: (Score:2)
Unless you live in a place where January 23, 2007 is several months ago....
Re: (Score:2)
Re: (Score:2)
Re: (Score:2)
Wrong (Score: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 (Score:4, Informative)
As for the Chinese attacks, they haven't shown any real applicability to SHA-2 as of yet.
Re: (Score:2)
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.
Some suggestions (Score:2)
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... (Score:4, Funny)
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: (Score:3, Funny)
Well... (Score:2)
Adi Shamir's Discrete Logarithm Hash Function... (Score:3, Interesting)
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.
And who would you trust... (Score:2)
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: (Score:2)
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 minu
I see an opportunity for a dead Sun proposal (Score:2)
Now that is a funny requirement... (Score:2)
"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: (Score:2)
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 tel
Re:Generic hashing is impractical (Score:4, Insightful)
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 (Score:4, Informative)
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: (Score:2, Informative)
Re: (Score:2)
Re: (Score:2)
sure but with a decent hash algorithm the sun would most likely go red giant before you finished so its a non-issue.
Re:Generic hashing is impractical (Score:4, Informative)
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: (Score:2)
Re:Generic hashing is impractical (Score:5, Informative)
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: (Score:3, Informative)
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 doe
Re: (Score:2, Informative)
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 numb
Not a different hash strategy... (Score:2)
Re: (Score:2)
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: (Score:2)
Re: (Score:2)
How appropriate for a conversation about HASH.