Slashdot Mirror
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."
The draft can be found (in PDF) here.
Er Galvão Abbott - IT Consultant and Developer
...the magical SHA-24M?
Schneier proposed such a competition in March 2005: http://www.schneier.com/crypto-gram-0503.html#1
Please correct me if I got my facts wrong.
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.
``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.
Please correct me if I got my facts wrong.
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.
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.
If information wants to be free, why does my internet connection cost so much?
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.
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?
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
Someday, I'll have a real sig.
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
$_="Slashdotter";$syn="OTT";s;..;;;sub _{print shift||$_};s!ash!Perl !;s=$syn=ack=i;tr+LLEd+BLAH+;_"Just Another ";_
Doesn't work very well. Read this:
. com/msg02611.html
http://www.mail-archive.com/cryptography@metzdowd
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
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.
$_="Slashdotter";$syn="OTT";s;..;;;sub _{print shift||$_};s!ash!Perl !;s=$syn=ack=i;tr+LLEd+BLAH+;_"Just Another ";_
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).
Please correct me if I got my facts wrong.
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.
Live today, because you never know what tomorrow brings
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.
Slashdot gets worse every day... Pipedot: News for nerds, without the corporate slant
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.
-30-
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.
-30-