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

Tags: , , , ,

Posted on June 16, 2009 at 12:21 PM • 50 Comments

Comments

Clive Robinson • June 16, 2009 1:05 PM

@ Bruce,

“which is why I think it should be called the Advanced Hash Standard, or AHS”

AHS…

Hmm how long before people start trying to pronounce it as a word…

Ben • June 16, 2009 1:21 PM

“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

Erik • June 16, 2009 1:23 PM

Advanced Standard for Hashing = “ASH”.

Which is how my colleagues in Canada pronounce “hash” anyway.

naive • June 16, 2009 3:20 PM

Erik: I didn’t know that “Canadian” is the new Euphemism for “French”.

Or, alternatively: Canadians — the poor man’s French.

anonymous canuck • June 16, 2009 3:30 PM

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

Petey B • June 16, 2009 3:32 PM

@naive: yeah come on now, I pronounce it “hash”, never heard “ash” before.

how about JAHA: Just Another Hash Algorithm

Thomas Peyrin • June 16, 2009 4:25 PM

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.

Thomas.

mpj • June 16, 2009 4:26 PM

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)?

Chris S • June 16, 2009 4:29 PM

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

Chris S • June 16, 2009 4:31 PM

“Advanced Digital Hash Digest” … if you can pay attention for a name that long.

Jack • June 16, 2009 5:53 PM

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”?

Clive Robinson • June 16, 2009 6:18 PM

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

Liam O • June 16, 2009 7:55 PM

@Jack

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

Franglais • June 16, 2009 9:44 PM

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.

Pat Cahalan • June 16, 2009 10:59 PM

@ Thomas

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?

Daniel Guinan • June 16, 2009 11:28 PM

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.

Winter • June 17, 2009 1:22 AM

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:
http://kerneltrap.org/mailarchive/git/2006/8/27/211001/thread#mid-211001

They do seem to have the means ready for a bulk move of old repositories to SHA256.

Winter

Brian • June 17, 2009 1:35 AM

@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?

Winter • June 17, 2009 3:01 AM

@Brian

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.

Winter

Schmoo • June 17, 2009 4:48 AM

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.

Winter • June 17, 2009 5:15 AM

@Brian,

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

Paeniteo • June 17, 2009 6:13 AM

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

Winter • June 17, 2009 6:38 AM

@Paeniteo

I obviously should have written “preimage-attack”, not collision.

Winter

bf skinner • June 17, 2009 7:33 AM

wasn’t ASH the android on Alien?

No homicidal killer robots for me thanks!

sooth sayer • June 17, 2009 7:39 AM

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.

Jamie • June 17, 2009 9:04 AM

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.

aikimark • June 17, 2009 12:12 PM

Hash-by-Schneier (HBS)?
Bruce-Approved-Secure-Hash (BASH)?
Cryptic-Advanced-Secure-Hash (CASH)?

or we could delve into the food world…
Delicious
BBQ or Brunswick Stew
goulash — can’t be beet 🙂

(I guess it’s time to eat, since I’m thinking so much about food)

havvok • June 17, 2009 12:58 PM

@sooth sayer
hmm.. considering that the standards body is holding a competition for Secure Hashing Alghorithm – 3, one would assume that decision was already made!

PackagedBlue • June 17, 2009 11:34 PM

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?

Shane • June 18, 2009 10:47 AM

Some words not to use when naming your hash function (or any software for that matter):

Secure
Advanced
Unbreakable
Invincible
Dependable
Modern
Standard
Foolproof
New
Cutting-edge
Breakthrough
(et al)

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

http://eprint.iacr.org/2008/270.pdf

with, certainly, more progress to come.

TNT • June 18, 2009 2:13 PM

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

Something other than anonymous • June 18, 2009 9:45 PM

MD2009 would be a welcome replacement for
MD2008, let alone MD1972.

But none would be as good as MD2020? 🙂

Rob Johnson • December 21, 2011 3:38 PM

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?

Thanks

Leave a comment

Login

Allowed HTML <a href="URL"> • <em> <cite> <i> • <strong> <b> • <sub> <sup> • <ul> <ol> <li> • <blockquote> <pre> Markdown Extra syntax via https://michelf.ca/projects/php-markdown/extra/

Sidebar photo of Bruce Schneier by Joe MacInnis.