First Successful Collision Attack On the SHA-1 Hashing Algorithm (google.com) 87
Artem Tashkinov writes: Researchers from Dutch and Singapore universities have successfully carried out an initial attack on the SHA-1 hashing algorithm by finding a collision at the SHA1 compression function. They describe their work in the paper "Freestart collision for full SHA-1". The work paves the way for full SHA-1 collision attacks, and the researchers estimate that such attacks will become reality at the end of 2015. They also created a dedicated web site humorously called The SHAppening.
Perhaps the call to deprecate the SHA-1 standard in 2017 in major web browsers seems belated and this event has to be accelerated.
Perhaps the call to deprecate the SHA-1 standard in 2017 in major web browsers seems belated and this event has to be accelerated.
You can't just string a hash together (Score:1, Funny)
Sorry, this isn't that serious. You can't just walk up to a geisha 1 day and in fits and starts
handle all the encoding black-hattery of some random pasha 1 character per line. Seriously, duh
All this won't flip anyone's ricksha 1 morning. Another thing: SSL's still safe. At best it's a
1-time (or... maybe 2) opportunity to replace someone's kasha 1 grain at a time. But probably 1
Re: (Score:2, Funny)
LOL, I successfully trolled a mod. :)
That's going to keep me smiling all day!
Deliberately Incoherent Ramblings (Score:3, Funny)
LOL, I successfully trolled a mod. :)
That's going to keep me smiling all day!
And here I thought you were just smoking crack.
Wordplay -- there's fun in the whooshing sound (Score:2)
It's ok. I realize wordplay makes a -->hash<-- out of many people's thought processes, and they can't do something as simple as moderate well in that kind of state. Not offended at all; there's no -->collision<-- between my feelings and clueless moderation of my posts. It strikes me as sad when other people's posts are similarly abused by moderators who can't -->look up<-- long enough to see what's being said, but hey, that's slashdot, where anyone can moderate for any reason, or no reaso
Re: (Score:2)
You just need to add a linked list, so collisions are resolvable.
Not to worry. :)
Re: (Score:2)
I don't think you really 'trolled' a mod... you were just downmodded for making a pointless comment.
Re: (Score:2)
The thing is, one person's "pointless" is another person's "I get it."
Get it?
SHAshank RedempSHA (Score:1)
I don't know; every man has his breaking point.
Re: (Score:1)
I won't be all that surprised... (Score:2)
... if one day it gets out that this was discovered a long time again by certain intelligence agencies.
Re:I won't be all that surprised... (Score:5, Interesting)
People have been attacking SHA-1 since 2005.
https://en.wikipedia.org/wiki/... [wikipedia.org]
No need for any conspiracy since people were warned about potential weaknesses in SHA-1 for a decade.
Re: (Score:2)
People have been attacking SHA-1 since 2005.
https://en.wikipedia.org/wiki/... [wikipedia.org]
No need for any conspiracy since people were warned about potential weaknesses in SHA-1 for a decade.
There's also no need for any conspiracy when staying ahead of such things (with their nearly unlimited resources and no concern for profit) is part of the reason why such agencies exist...
Re:I won't be all that surprised... (Score:4, Insightful)
People have been attacking SHA-1 since 2005.
https://en.wikipedia.org/wiki/ [wikipedia.org]...
No need for any conspiracy since people were warned about potential weaknesses in SHA-1 for a decade.
It's also important to point out that this is a free-start collision, where the attacker gets to choose the initial values, something that isn't possible with full SHA-1. This makes the attack much, much easier than an attack on full SHA-1. It took nearly a decade to go from the first free-start collision on MD5 to an actual attack, and MD5 was a much weaker function than SHA-1. Their estimate of "end of the year" may be a bit optimistic.
Re: (Score:2)
... if one day it gets out that this was discovered a long time again by certain intelligence agencies.
Well, wasn't that what happened with Dual_EC_DRBG?
Re:I won't be all that surprised... (Score:4, Informative)
Not really. People at Microsoft Research showed it to be broken years before it became a scandal. No one bothered to listen.
Re: (Score:2)
Not really. People at Microsoft Research showed it to be broken years before it became a scandal. No one bothered to listen.
This is one major reason I prefer full public disclosure with functioning reference exploits. Those seem much harder to ignore.
Re: (Score:2)
Not really. People at Microsoft Research showed it to be broken years before it became a scandal. No one bothered to listen.
I didn't know that. Got a link?
Re: (Score:2)
Re: (Score:2)
Here you go [arstechnica.com] the article states that MSFT Research gave a paper on it being vulnerable in 07.
Thanks pal!
Re:I won't be all that surprised... (Score:5, Interesting)
Well, wasn't that what happened with Dual_EC_DRBG?
We can never know for sure, but empirically, I really don't think Dual_EC_DRBG ever pinged on NSA's --- or any other state intel actor's --- radar. At least not before EC vulnerabilities became public knowledge. Its use by default in the RSA BSafe toolkit meant that products using that toolklit would be vulnerable. And YES, that was a rich prize. BSafe may have been part of a program to seed a backdoor towards, say, a particular target state or industry.
BUT... there is for me an irreconcilable problem with that theory. I ran an ISP in those crazy early days when administrators were faced with a choice of whether to 'drop in' a BSafe object library under license (prove USA blahdy-blah) or compile the SSLeay/OpenSSL source, which was by no means as smooth and functional as it is today. But even pre-2000 it was obvious that the whole world was going the OpenSSL open source route as soon as it was stable.
Given that OpenSSL's populary was increasing by leaps and bounds... and yet, the OpenSSL FIPS Object Module v2.0 had a bug that prevented Dual_EC_DRBG from being used [marc.info]. *IF* the back door was being actively exploited by some state actor, they would have noticed this right away and it would have been a trivial matter (and top priority) for some helpful volunteer to emerge from the shadows and toss in a fix for it. Maybe even a soft-sell for epileptic curves. But this did not happen. Ergo, circumstances more closely resemble a situation in which NOBODY, including NSA, cared.
Remember that intel agencies are padded with the same bloviating internal memos as any organization, and love to take 'credit' for a thing to show their prowess whether or not the thing is actively being used. Maybe a good part of Snowden's trove are empty boasts.
Re: (Score:2)
Nice catch! I can't believe you read all that, but nice catch!
Gwaarsh. y'know yer reely smart when you make fun of that readin' stuff.
Becha think Twitter raisin' the 140 character limit is the end of the world!
Speling chekker gonna suck u in
Re: (Score:2)
computational power of seizures
Makes a fine RNG
what about git? (Score:5, Funny)
Re:what about git? (Score:4, Interesting)
Har har.
But seriously, as I recall git doesn't use SHA 1 for security, but just as a really good hashing algorithm.
Re: (Score:2)
With a SHA1 collision you can rewrite a repositorty's history.
Re:what about git? (Score:4, Insightful)
No. That's second preimage attack. Collision is if you can chose multiple versions to map to the same hash.
Re: (Score:2)
Well, yes. Then let's say one could introduce a new (chosen) commit that one could secretly amend after the fact. I guess preimage attacks is the logical next step, though.
Re: (Score:1)
If you can somehow make a security-flaw inducing subtle change that ALSO hashes to the same SHA1 key, there's a three letter agency or two that would like to meet your acquaintance.
Re: (Score:2)
Comments. You might have heard of 'em.
Re: (Score:1)
Only simpletons comment code. It's called job security.
Re: (Score:2)
Yes - so it means that you can rewrite history: by producing an alternative set of commits that match the hashes. They may be junk, but they are an alternative history. 2nd preimage means that you can choose what the alternative commits are: so that you can choose a plausible alternative history.
Re: (Score:3)
No, the difference between 2nd preimage and collision is that for your hash function HASH, you have for 2nd preimage sth, and HASH(sth) given, and want to get sth2 so that HASH(sth) == HASH(sth2). sth2 is choseable by you, either completely, or only in parts. Sometimes you only have HASH(sth), but you never can modify sth.
Now for collision, you only have HASH given, as function, but you can chose both sth and sth2, either completely, or in parts.
This means you never can rewrite history with git, if you only
Re: (Score:2)
Oops. Very true. I had done a little brain fart there.
Re:what about git? (Score:5, Insightful)
Not quite.
This is not yet a full attack on SHA-1.
It cannot - yet - be used to generate a collision for any known hash.
It is an indication that you should move away from sha-1 as fast as you can.
Re: (Score:2)
Why can't git be updated to just use another algorithm? I guess that would be a much better solution than just moving to something else.
Re:what about git? (Score:5, Informative)
Why can't git be updated to just use another algorithm?
First off, Linus on the topic of SHA1 safety: (SO link, as the git mailing list links are flaky on me today) [stackoverflow.com]
The problem is that git uses the SHA1 hash *extensively* for "permanent" identification of things. There's a host of existing usage out there which would need to be updated/converted, and any conversion of an existing repository would completely invalidate any crosslinks/references using the SHA1 format. Also, because git allows shortened hashes to be used for identification, there's no way you can use the length of the hash to tell the difference between two hash formats for a "mixed" repository.
That said, it's not really a big deal. Even if you can manufacture a hash collision, there really isn't a good way to use it to attack a (remote) git repository. Even if you could create a file with the same SHA1 hash as a typical file in a git repository, it's highly unlikely to be anything approximating something that's in an appropriate format. The colliding file will be line noise, rather than a compile-able C++ file, for example.
Moreover, git is set up to use the *previous* version of a file in case two files have the same SHA1 has. So you can create a SHA1 collision of an existing file ... which is then ignored by git in favor of the other file. The only way around that is if you have admin access to the remote git repository, or can somehow contrive to get your malicious file accepted to the repository prior to the file you're trying to collide with. (In which case, where are you getting the SHA1 you're targeting from?)
Even then, if someone has a "clean" copy of the file you're colliding with, makes a modification to that and re-commits, your malicious file will be overwritten wholesale by the new version of the non-malicious file (as git commits encode full file changes, rather than file deltas, so the new SHA1 will be encoded as the new version of the old SHA1).
You might be able to promote a divergence in the code tree due to the different files, but given that everyone in git has a full version of the repository on their disk, it would soon become apparent that something "funky" is going on in the commit history.
In short, even if you can make deliberate collisions with SHA1, that doesn't change the usefulness (and safety) of SHA1 for git, just like rot13 being a poor encryption doesn't mean you need to use PGP to encode your usenet joke punchlines.
(BTW,. I'm guessing the GP post is supposed to be a joke)
Re: (Score:2)
even if you can manufacture a hash collision, there really isn't a good way to use it to attack a (remote) git repository.
If you have $150k to drop on creating a hash-collision, you can afford someone to hack the remote system. Most systems are not properly secured.
Even then, if someone has a "clean" copy of the file you're colliding with, makes a modification to that and re-commits, your malicious file will be overwritten wholesale by the new version of the non-malicious file
Same could be said about the malicious file.
Re:what about git? (Score:5, Funny)
I guess Perl projects using git are in trouble.
Re: (Score:3)
Given the state of the art in Perl golf, the colliding file might be condensed implementation of a complete proof to Fermat's Conjecture, or a DNA codemap to cure cancer.
Or another stupid "JAPH". [wikipedia.org]
Re: (Score:2)
TL;DR an SHA1 hash collision is only good for password cracking.
Re: (Score:2)
Why can't git be updated to just use another algorithm?
First off, Linus on the topic of SHA1 safety: (SO link, as the git mailing list links are flaky on me today) [stackoverflow.com]
The Linus' comment is somewhat outdated.
For the first type of collision - the inadvertent kind - a check was added to the git very long time ago. It will not let you commit, if there is a hash collision. The time-stamp is also part of the commit, and as such, the workaround is to simply wait one second and try to commit again.
Re: (Score:1)
There are limits on what it means to break SHA. Your encryption key should look like random gibberish, so if I find other random gibberish that hashes to the same key, then my key looks like your key as far as the SHA hash is concerned. Git hashes the actual content of the commit, so if you find random gibberish that hashes to the same thing as my real commit, you can replace my commit with your gibberish. The real challenge here is that in order for this to not be immediately obvious, you can't use ran
Re: (Score:1)
Can you expand on this?
Surely, yes, finding an MD5 collision would be easier to do than finding a SHA1 collision, but finding a collision that is valid for both at the same time would be orders of magnitude harder than finding a SHA1 collision alone?
IN ADDITION, not sha1 of md5 (Score:3)
GP said IN ADDITION to, not "as the input of".
Not
hash = sha1(md5))
which would be weaker. Rather:
hash1 =sha1(plaintext) , hash2 =md5(plaintext)
Adding (not embedding) an additional hash is strictly stronger.
Of course it would be just as easy to add sha256 rather than to add md5. You could then deprecate the sha1 and after a while stop using it at all.
Re:what about git? (Score:5, Interesting)
Immerman's point is essentially right. Here is a more thorough opinion.
Git does not use SHA1 for cryptographic purposes. The use of SHA1 for cryptographic purpose is what should be deprecated. If major git repositories start calculating SHA256 hashes too, and keep an eye out for in the wild collisions, it will probably be ok. Git does not need to be attack resistant like TLS does. In any case, it is worth rejigging the code so that the hash is done via a plugin and can be migrated, if this isn't already done. I haven't read the git source and am not sure, but it would be easy to get it done before it becomes a problem for git. I use md5sum for a lot of applications which don't require security sufficient for cryptographic purposes. Cryptography is the Formula 1 of computation, and just like most vehicles don't need to compete against an F1 car, many of the trickle-down uses of cryptographic hashes will be fine for a while. Git only has an issue if two versions of files in the same repo produce the same hash. In practice that means two compilable source files, rather than arbitrary meaningful input. That makes cracking much harder since you have a language recognition problem bolted onto the frontend of your hash, so most potentially colliding inputs will be excluded by this (if one colliding file is a C file, and the other is bad French poetry, it is clear which is intended -- cryptographic purposes cannot rely upon such applications of commonsense recognition). Do not worry about Git.
As an exercise, try and write two valid Python3 files between 10 and 30 lines long importing only sys, re and glob, such that they have identical md5sum outputs. By reducing the input space for a hash, you can make collisions less likely. What is important about this attack is that there is a round trip forward through the hash, and then backwards to a different input. By looking at the information discarded by the nonlinear parts of the hashing algorithm (that is, the non-reversible steps) you can start to make meaningful sense of what the hash is doing. Interestingly, if you produce a language specification which permits fewer valid inputs than the number of possible hash outputs, it is in principle possible that no collisions will occur. Indeed it would be a good exercise for a beginning cryptanalyst to try and construct a language such that valid inputs were guaranteed to get different md5sum outputs.
Re: (Score:2)
Interestingly, if you produce a language specification which permits fewer valid inputs than the number of possible hash outputs, it is in principle possible that no collisions will occur.
Yes, and knowing each possible valid input would allow you to build a rainbow table to decode each hash back to its original value (and not just to a value that will give you the same hash).
Indeed it would be a good exercise for a beginning cryptanalyst to try and construct a language such that valid inputs were guaranteed to get different md5sum outputs.
Only because they would, shortly thereafter, learn that hashes are, in fact, meant to not be reversible. Guaranteeing a 1-to-1 mapping (e.g. no collisions) makes them reversible, negating the point of the hash.
Re: (Score:2)
The entropy in hashes must be less than the entropy in the data or it isn't a hash. That means that a hash requires that there be collisions by definition. A good hash will minimize those but there will always be a risk.
When writing a program that requires a hash, I find it useful to gut the hash function so that if I'm using sha256, I set all the bytes except for one to zero so I see what happens with collisions and can test that functionality. It is amazing how many bugs I've found in protocol implemen
Re: (Score:1)
Tim, thanks for elaborating on my point; you gave much more detail than I thought was necessary, but I may not have given enough.
Re: (Score:2)
Re: (Score:1)
- The attacker kind of collision because somebody broke (or brute-forced) SHA1.
This one is clearly a _lot_ more likely than the inadvertent kind, but by definition it's always a "remote" repository. If the attacker had access to the local repository, he'd have much easier ways to screw you up.
So in this case, the collision is entirely a non-issue: you'll get a "bad" repository that is different from what the attacker intended, but since you'll never actually use his colliding object, it's _literally_ no different from the attacker just not having found a collision at all, but just using the object you already had (ie it's 100% equivalent to the "trivial" collision of the identical file generating the same SHA1).
Re: (Score:1)
combine them? (Score:4, Interesting)
One thing that always bothered me with announcements like 'MD5 is dead because we can forge collisions' is that what are the chances that the forgery would pass *both* MD5 and SHA1 ?
Say you have a string S and a forged S' so that S != S' and MD5(S) = MD5(S') and let's say you can create S' easily regardless of S. That's the definition of a hash collision and a proof that the algorithm can't be trusted anymore. Surely, the odds that it also satisfies SHA1(S) = SHA1(S') are close enough to impossible, no?
If that's the case, then sign your certs, code, etc with concat(MD5(S),SHA1(S)) instead of just one broken hash. Yes, two broken hashes are indeed protecting you.
Re: (Score:3)
Re:combine them? (Score:4, Informative)
Apparently, concatenation isn't as effective as it could be. It will be at least as strong as either MD5 or SHA1, and while it seems that you'd get a 288 bit hash, it's about as strong as if you had 174 bits.
It's probably easier to make a 288 bit hash from the start.
Discussion page: http://crypto.stackexchange.co... [stackexchange.com]
Re: (Score:2)
a step further - instead of md5, add a good hash (Score:2)
Of course it would be just as easy to add sha256 rather than to add md5. You could then deprecate the sha1 and after a while stop using it at all. If you keep the two hashes separate rather than concatenating them, you can deprecate a weaker one every ten years or so, as as needed. Instead of:
if matches (candidate, md5hash)
You'd use:
if matches (candidate, @undeprecated_hashes)
Re: (Score:2)
One thing that always bothered me with announcements like 'MD5 is dead because we can forge collisions' is that what are the chances that the forgery would pass *both* MD5 and SHA1 ?
The increased difficulty of finding a collision is derived by storing two separate hashes not diversifying algorithms.
For example one could just as easily perturb a plaintext in a publicly known deterministic way then rerun very same hash algorithm again for similar effect. If you assume both algorithms are no longer sufficiently collision resistant for your needs then switching it up makes no practical difference.
Re: (Score:2)
Based on all the published benchmarks I could find, the amount of time it takes to compute the MD5 + SHA1 hashes is approximately the same if not greater than what it takes to compute the SHA256. Why bother to compute a hash with two "broken" algorithms when you can spend less time using an unbroken one?
Here's the results of running a benchmark test using openssl speed on my i5 laptop:
Doing md5 41943040 times on 16 size blocks: 41943040 md5's in 17.67s
Doing sha1 41943040 times on 16 size blocks: 41943040 sh
Re: (Score:2)
The goal of combining isn't to save time, it's because it's what's available. Let's say you have an embedded device, and it can do SHA1 and MD5 already in hardwa
Re: (Score:2)
the issue in using one hash is still present though. One day if SHA256 is broken, you will be back to the same problem.
Suppose a (near?) future where SHA256 is widely deployed and just got broken: full collision on demand. That future also means that SHA1 is even more trivially broken and MD5 even more so.
My point is that it would harder to conjure S' so that S != S' AND MD5(S) = MD5(S') AND SHA1(S) = SHA1(S') than it would be to have S != S' AND SHA256(S) = SHA256(S')
For that matter, string 3 of those hash
I SHA-T in my pants when I read this (Score:1)
Weak attack (Score:2)
It is called a freestart collision.
A freestart collision is one where the attacker gets to choose the initialization vector. In maybe all practical applications, it doesn't happen as it is fixed by the standard.
Unlike MD5, it is still impossible to get two different files that have the same standard SHA-1 checksum.
And even true collision attacks are quite limited. For many applications (like cracking passwords), what you need is a preimage attack, and neither MD5 nor SHA-1 have one.
Re:Weak attack (Score:4, Informative)
Unlike MD5, it is still impossible to get two different files that have the same standard SHA-1 checksum.
False. As long as there are potentially more bits in the input than there are in the output (read: the input can be longer than the resulting hash), any hashing algorithm will have collisions. It is the difficulty in generating these collisions that makes the algorithm strong or weak; and they are quite easy to generate for MD5.
Re: (Score:1)
While true, the issue is one of ease of generating a (meaningful) input that matches the hash. That is, given a hash, one cannot instantly provide a plain text to generate it. (this can only be done today with rainbow tables -- i.e. try everything until there's a match, which is far from "quick".) Nor can one start with a given plaintext and alter it while not altering the hash. (an example of such exists for MD5, thus it's "broken", however, in reality, it is merely "week" as it's very difficult to do. No
Re: (Score:2)
While true, the issue is one of ease of generating a (meaningful) input that matches the hash. That is, given a hash, one cannot instantly provide a plain text to generate it.
Why, yes, that's what my second sentence said.
Wake me when someone preimage-attacks SHA-1 (Score:2)
The original Xbox and I have some unfinished business.
Back to the future (Score:1)
It's gotten to the point that, in order to encrypt anything safely for a few years, I have to invent a time machine and steal the technology from the future. And kill the inventor, so that he doesn't independently discover it in the original time stream.
We just got vendors to stop using MD5 and SSL 3.0 about a year ago.
Re: (Score:2)