US kicks off secure hash competition
Gentlemen, choose your algorithms
Dozens of amateur and professional cryptographers signed up last week for the United States' first open competition to create a secure algorithm for generating hashes - the digital fingerprints widely used in a variety of security functions.
The contest, run by the National Institute of Standards and Technology (NIST), seeks to find a strong replacement for the current family of hash functions, some of which have been shown to be cryptographically weaker than originally thought. The agency expected at least 40 proposals to be submitted by the Friday 31 October deadline.
Hash algorithms are very important functions in computer security. The algorithms can reduce a large data file - such as a Word document or e-mail message - to a simple, if sometimes long, number that can be used to identify the data, in the same way that fingerprints are used to identify humans. A good hash function gives a completely different result if the original file is changed even slightly. A variety of encryption and security functions use hashes, from integrity checks to digital signatures.
"They are probably the most widely used and least talked about operations in cryptography," said William Burr, manager of the security technology group for NIST. "We expect it to be an interesting and useful exercise, and we hope to find out a lot more about hash functions."
There are a number of hash functions in current use. Two early algorithms - MD4 and MD5 - are the basis for the current family of government-certified hashing algorithms, known as the secure hashing algorithms (SHA), and including SHA-0, SHA-1, and SHA-2, the latter which actually consists of four functions depending on the number of bits desired in the resulting hash.
Yet researchers have found practical attacks against MD4 and SHA-0, demonstrating the ability to generate "collisions," ways of creating two data files that result in the same hash. By forcing a collision, an attacker could, for example, create a modified version of a contract that appears to match - according to the hash - the original digitally-signed document. While SHA-1 can still not be practically attacked, the length of time it takes to find a collision has theoretically shrunk considerably. Cryptographers originally thought that a computer that could perform an attack calculation one million times every second would find a SHA-1 collision only once in 38 billion years, but in 2005, researchers found a way to produce a collision once every 19 million years and then shortened that to once every 300,000 years.
While no significant attacks have been found against SHA-2, NIST is not waiting. A year ago, the agency called for submissions for a proposed new hashing standard, SHA-3. By Friday, the deadline for entries, the agency expected to see nearly 40 proposals - many from teams of professional cryptographers. The submissions will be judged by NIST for mathematical soundness, the perceived randomness of the hash values, the computational and memory efficiency of the hash calculation and the flexibility of the algorithm.
There are four documents
A and B originally
A, B -> A`, B`
A` and B` after engineer.
The ` docs look engineered, that's the tell tale, you start to distribute A` people know you are up to no good.
Sure there is a vector of attack, but you cannot really rely on hashing alone anyhow, it is just one of many checks to ensure the validity. I would be kind of worried about hunky dory being no one looks at the source code or generates their own compiled code, at that point why bother with engineering the hash, just payload in unchecked code.
Now if you can do A, B -> A, B` there is a problem.
Re: Is it really much of a problem?
I have two postscript files here, both can be printed, both have the same MD5 checksum. They say something completely different.
The fact that it is possible to engineer two documents with the same checksum is bad news for cryptography (as that web page says). The ability to engineer executables with the same checksum (or linux .rpm files or anything else that can be signed) is also bad news. If you can get inside then you can arrange to have something legitimate and all hunky-dory signed and distribute your malware through other channels. I'm sure you can remember the recent event where this possibility came uncomfortably close.
It's a serious problem.
Ohhh come on
the md5 attack shown from the link, doesn't actually use a simple natural hello.exe.
Both the hello.exe and the erase.exe are engineered together.
If only the erase.exe was engineered there would be a problem, but that is not the case.
So yeah there is a vector, but it would be a lot of odd things that would have to happen to create it.
And as to encryption :) Well I didn't want to make it too obvious, but if the author signs via his private key, and you use his public key to check. That is a better position to be in, as you really trusting the author, not the code. Combining all these methods is a good idea, add in encryption via your public key, and a quick check of the source code, and your security is on the up again.
As to documents saying one thing, with a character change or three (not) that is part of a good hashing algorithm for security anyhow, it should make a huge change in the resulting hash if only one character is changed, and they all currently exhibit that.
Collisions of course occur because the hash is smaller than the data it is representing, much smaller :). So, it is about permutations and length of hash more often than not..
These competitions are a good thing, but they are more about bringing on the field of security as a whole, than creating the next hashing star.