Schneier on Security
A blog covering security and security technology.
« DHS Has a Blog |
| Carrot-Bomb Art Project Bombs in Sweden »
June 16, 2009
Ever Better Cryptanalytic Results Against SHA-1
The SHA family (which, I suppose, should really be called the MD4 family) of cryptographic hash functions has been under attack for a long time. In 2005, we saw the first cryptanalysis of SHA-1 that was faster than brute force: collisions in 269 hash operations, later improved to 263 operations. A great result, but not devastating. But remember the great truism of cryptanalysis: attacks always get better, they never get worse. Last week, devastating got a whole lot closer. A new attack can, at least in theory, find collisions in 252 hash operations -- well within the realm of computational possibility. Assuming the cryptanalysis is correct, we should expect to see an actual SHA-1 collision within the year.
Note that this is a collision attack, not a pre-image attack. Most uses of hash functions don't care about collision attacks. But if yours does, switch to SHA-2 immediately. (This has more information on this, written for the 269 attack.)
This is why NIST is administering a SHA-3 competition for a new hash standard. And whatever algorithm is chosen, it will look nothing like anything in the SHA family (which is why I think it should be called the Advanced Hash Standard, or AHS).
Posted on June 16, 2009 at 12:21 PM
• 50 Comments
To receive these entries once a month by e-mail, sign up for the Crypto-Gram Newsletter.
"which is why I think it should be called the Advanced Hash Standard, or AHS"
Hmm how long before people start trying to pronounce it as a word...
Advanced Standard for Hashing = "ASH". Slightly less problematic w.r.t. pronunciation. :)
"Most uses of hash functions don't care about collision attacks"
One use can be enough.. MD5 collisions caused rogue CA certificate, and now, most CA-s use SHA-1
> Advanced Standard for Hashing = "ASH".
Which is how my colleagues in Canada pronounce "hash" anyway.
How about a new Hash Algorithm Measure = HAM
I vote for PGH (Pretty Good Hash)
AHS would probably sound like "æs" -- that'd be interesting.
How about Schneier's Hash Algorithm – SHA?
Erik: I didn't know that "Canadian" is the new Euphemism for "French".
Or, alternatively: Canadians -- the poor man's French.
It sounds like this is close to impacting code signing with hashes.
SHA2 or Public key signing works. I can already hear developers grumbling about their users having to change code verification procedures.
What else could they do? A very kludgy stop-gap answer might be to verify against both MD5 and SHA1. It's ugly, frought with procedural problems, not to mention all those grumbly developers and users. But at the heart of it, I'm not sure if an attacker could find a collision that worked for both.
@Erik that would be in Montreal. :)
@naive: yeah come on now, I pronounce it "hash", never heard "ash" before.
how about JAHA: Just Another Hash Algorithm
SNASH - SHASH's not an SHA Hash.
To me, this 2^52 complexity is wrong in this paper. The autors are assuming that they can do full message modification AND boomerang attack as the same time. This is impossible because of the lack of freedom degrees. In fact, even without using the boomerang trick, the 2^57 complexity just with message modifications is very optimistic.
Moreover, when claiming such a provocative complexity, I guess an experiment on a reduced-round version is a minimum. I don't say that reaching a 2^52 attack one day is impossible, but with the current cryptanalysis knowledge we are still far away.
Finally, I would say that before disseminating this information, we should wait to see if the claims are proven right.
I guess Bruce's point with AHS was to make it sound like it's in the same generation with AES. So how about ADS (D for digest)?
@Erik: Which is how my colleagues in Canada pronounce "hash" anyway.
Oly annah, you ave a point. Ow is it that I aven't noticed this before...
Srsly - I always "h" my "hashes".
"Advanced Digital Hash Digest" ... if you can pay attention for a name that long.
What's the latest on the SHA-3 competition? Is Skein still holding up?
Since SHA stands for Secure Hash Algorithm that seems like a reasonable thing to stick with. Once the "Advanced Hash Algorithm" gets broken, will we have the "Super Advanced Hash Algorithm" and then the "Most Super Advanced Hash Algorithm Turbo Edition"?
HASH - "Highly Advanced Standard for Hashing."
@ Chris S,
I was beging to regret making my comment at the top of the page and then I saw your ADHD and smiled again 8)
With regards the French and their "colonial cousins" in Canada a thought for you.
French speaking women are often regarded as being more attractive than those speaking languages derived from Old German.
Possibly this is due to French being spoken more from the front of the mouth and old German from the throat.
The effect of speaking from the front of the mouth being to make the cheek bones look more defined and thus apear higher.
I concur. Using "advanced", "high speed" or "new" in the name of an IT related standard is just asking for trouble, as the only thing certain in IT is that everything becomes obsolete one day
Windows NT (New Technology) is a good example
Reminds me of a cartoon called Le Chat who said "Le hash du hasish est aspiree, ca fait plus d'effet" - Roughly "The h of hashish is pronounced (inhaled), it gives a better effect.".
My French wife always complains about the hair conditioner in the car and uses an air-dryer after a shower. The joys of speaking more than one language.
I like the name ASH. Somehow the words "boomstick" and "s-mart" need to be incorporated. Not sure how just yet.
> Finally, I would say that before disseminating
> this information, we should wait to see if the claims
> are proven right.
How do you suppose one has the claims proven to be correct if you don't disseminate the information to discerning consumers?
Yes, yes, yes. The word "Advanced" is only meaningful if we consider the time period that it was "Advanced" in. In 20 years, the "Advanced Hash Standard" will sound more than a bit ironic.
I think it's probably wiser to name the function after the math and skip all the "super", "hyper", "awesome" and "uber" modifiers that just turn embarrassing as advancement lunges forward.
One application of SHA1 is the Git SCM.
Really breaking SHA1 might allow an attacker to replace a patch in, eg, the Linux kernel repositories. If that would happen in one of the important vendor trees, or even Linus' tree, this might have devastating effects. There are more checkpoints, but as people "trust" the SHA1 hashes, they might simply go for the HEAD hash.
The possible breaking of SHA1 and its effects on the security of code repositories have already been discussed in 2006 by the Linux kernel developers here:
They do seem to have the means ready for a bulk move of old repositories to SHA256.
@Winter The attacks that would matter to Git are preimage attacks, specifically, second preimage attacks, where you are trying to collide with an existing hash, given that you know the contents. As far as I know, no one has any second preimage attacks against SHA1 yet.
Collision attacks would only really work well if you managed to get an un-audited binary blob into someone else's repository. Perhaps this is another good reason to try and keep binary blobs out of the kernel?
I think those who manage the repositories ask themselves regularly whether they are paranoid enough for their job.
So even the remotest possibility of the equivalent of the chosen-prefix attack used to create rogue certificates will get them anxious. It might indeed speed up the banning of binary blobs from the repositories, if there are any left.
Put the year of conception into the name. That way, it sounds modern when it comes out, and gradually sounds more and more like it should be replaced as time goes on.
MD2009 would be a welcome replacement for MD2008, let alone MD1972.
Collision attacks by offering patches to git repositories are indeed inefficient as patches are well studied and git will show whatever changes. In general, if you can trust your own repository, hash collision vectors are not worth the effort. However, "easy" collisions would allow undetected replacements in repositories stored on compromised servers.
Suppose, it would become possible to construct a SHA-1collision file to an existing text file.
A theoretical attack using SHA1 hash collisions on the Linux kernel git repositories of a linux vendor (Red Hat, SuSE, Debian) could work after compromising their servers.
Replace a little changed kernel file in the repository with one having the same SHA-1 hash in the git repository. The file will stay put because git does not replace an existing file with the same hash.
Downstream of the vendor, people who clone from the repository will start to receive the compromised file without noticing a difference.
Difficulties: File lengths are encoded in the git tags and included in the SHA1 hashes. And obviously, constructing collisions with functional C files is non-trivial. And much more.
But in the end, on a rooted server, nothing is safe anyhow.
@Winter: "Replace a little changed kernel file in the repository with one having the same SHA-1 hash in the git repository."
Note that this requires you to be able to seriously influence both documents that you intend to create the collision for.
I.e. you need two valid C source files that have the same hash value instead of two random documents. I am unaware whether a successful "collision" automatically implies that the attack is extensible to (partly) meaningful content for the colliding documents.
If it is, you could put comments into the source files that are ultimately responsible for making the hash sums match up, but that is rather noticeable by even casual observers of the submitted patch.
E.g., the two well-publicised Postscript-documents with identical MD5 values can easily be flagged as "highly suspect" if you take a look at their sources.
(In fact, both contain both documents along with an if-statement to switch between the two for output and some random gibberish to match the MD5 sums.)
If you need one completely "innocent" source file and you need a "malicious" replacemant, you have to execute a preimage-attack, not a collision.
I obviously should have written "preimage-attack", not collision.
wasn't ASH the android on Alien?
No homicidal killer robots for me thanks!
What will you do when "AHS" gets broken ?
Call it "SuperAHS", "SuperDuperAHS" ....
Why not just give these things numbers -- What's wrong with HS-2009 .. that's a lot more informative than the worthless adjectives piled on by vain cytologists.
Giving something the name "Advanced" will never stand the test of time. Although you could just say AHS stands for 'Antiquated Hashing Standard' if it's broken.
MASH-Massively Advanced Super Hash
or we could delve into the food world...
BBQ or Brunswick Stew
goulash -- can't be beet :-)
(I guess it's time to eat, since I'm thinking so much about food)
hmm.. considering that the standards body is holding a competition for Secure Hashing Alghorithm - 3, one would assume that decision was already made!
DUH - Dynamic Uber Hash :-)
SHA - Schneier's Awesome Hash
Study the history of MD5, very telling. 1991 published, 1996 flaws showing up. Grr, simple 10 year rule, 2006, MD5 in bad trouble. PGP weakness was MD5. Heck, even PGP limit of 1024 for early designs, has been kicked hard for serious stuff.
The old 10-15 year rule, the NSA lead on crypto applies roughly. I would expect the NSA to be able to screw with the SHA class, you would hope so, it is their family of "games."
OpenBSD 4.5 just went from MD5 to SHA-256, for signing on package parts. I sure wish they used skein AND SHA-512. More goodies are coming for OpenBSD 4.6, thank you, things are getting complex and "hot," these days. Just having another hash, is not the extra security that many hope for.
Quality of implementation is really a PITA. Lots of things go unsaid, typical business world today,
Thankfully, skein has an excellent design for hashes. Without going into details/reasons, Skein, too good to be allowed to be its best in a typical distributed form?
Some words *not* to use when naming your hash function (or any software for that matter):
I dropped MD5 and SHA-1 ages ago, but this still makes me real uneasy. I've been hoping the switch to SHA-2 (256) would buy me at least a decade before I had to pull out my hair again, but who knows, they seem to be making a decent bit of progress against SHA-2 as well
with, certainly, more progress to come.
"I concur. Using "advanced", "high speed" or "new" in the name of an IT related standard is just asking for trouble"
I agree. Call it "Secure Hash Improvement" (Tentatively So)... however I'm not sure the acronym would be that appealing.
Why not ADHS? Advanced Digest Hash System? :-)
> MD2009 would be a welcome replacement for
> MD2008, let alone MD1972.
But none would be as good as MD2020? :)
only when backed up by another security layer: Winchester 1894 :)
DUH - Dynamic Uber Hash yeah right
DASH - Digest Algorithm (for Speedy|for Secure|Standard for) Hashing
Bruce, et. al:
What's the state of SHA-1 cryptanalysis? I've recently read about German fellow who claims to have "cracked" the entire set of passwords up to six characters, that were hashed with SHA-1, in less than 1 hour. And did it renting time on a commercially-available computer cluster.
obviously cracking 6-character passwords isn't a reasonable metric for determining security. But does this say anything about collision attacks in 2^53 rounds? Has that been been reduced? And has there been any recent development on pre-image attacks?
Schneier.com is a personal website. Opinions expressed are not necessarily those of BT.