Slashdot Mirror
SHA-1 Broken
Nanolith writes "From Bruce Schneier's weblog: 'SHA-1 has been broken. Not a reduced-round version. Not a simplified version. The real thing. The research team of Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu (mostly from Shandong University in China) have been quietly circulating a paper announcing their results...'" Note, though, that Schneier also writes "The paper isn't generally available yet. At this point I can't tell if the attack is real, but the paper looks good and this is a reputable research team."
And I just got done upgrading from MD5.
For those interested, here is the actual detailed/lengthy FIPS PUB 180-1 from NIST, as typical, Wikipedia has a nice summary, and the W3 Folks have a short snippet ...
I'm not sure if this post is news or what, but for more info, click here:
http://www.itl.nist.gov/fipspubs/fip180-1.htm
A lot of companies and products use SHA1 in some form or another. Does this mean that we can arrest and imprison these "researchers" if they ever step foot in America?
Time to change the VPN policies
... to SHA-2!
If you don't switch to the newest, latest hashing algorithm, you will die horribly when your corrupted emacs RPM performs malicious code!!! Everyone, delete everything and log off of the Internets now!!! We're all gonna die!!! HELP!!!
"Anyone who attempts to generate random numbers by deterministic means is living in a state of sin." -- John von Neumann
Same group of people that found the MD5 Hash Collision. Self references and the MD5 paper.
Steal This Sig
SHA-1 Hash Algorithm and Source Code.
Creative Demolition
Is it time to update bittorrent?
How hard is it going to be for people to provide garbage data with correct SHA-1 hashes to screw up downloads?
Rats would be more funny if they could fart.
The Hashing Function Lounge also lists Cellhash, Parallel FFT-Hash , RIPEMD-128, RIPEMD-160, Subhash and Tiger as (so far) unbroken.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
One collision in 2**69 operations... that's quite minimal...
Sure, for signatures, it means that you can't trust the algorithm 100% anymore.
But for storing passwords, and other operations where collisions are not important, it doesn't matter much, even if there's another password that can generate the same hash, you still need to brute-force it.
Doest not affect HMAC. So it does not affect IPSEC and WEP.
RTFA.
I'm not a cryptographer, just a nerdy engineer, but let me explain my rationale: a hash algorithm takes an arbitrary message and generates a fixed-length signature that has a high probability (10**50 or better for most modern algorithms) of being the original.
Let's assume that your hash algorithm generates a 128-bit hash. Anyone who knows anything about probability can see that is the original message is greater than 128 bits, there MUST be more than one message that will generate the same hash. For long messages, there may be thousands or millions of messages out of a filed of 10**50 (or better) that have the same hash, although many of them will be meaningless garbage.
So SHA-1 has been broken by a group of cryptographers/mathematicians. Does this really mean that they can generate can alter any message in a way that will generate the same hash as the original, thus fooling the math that we use to validate content? No Way! I read Bruce Scheier's Cryptogram every month and he often makes the same argument.
So yes, this means that from a long-term systems security standpoint, we should all move to stronger hashes. Does it mean that SHA-1-based transactions are inherently secure right now?
I think not!
Well, for starters, there's:
SHA-256
SHA-384
SHA-512
The numbers refer to the bit length of the generated hash. SHA-1 uses only a 160 bit length, called a message digest. But then, you'd know all that if you would have rtfa.
--I wish there was some way to automatically append a line of text to messages posted on slashdot.
Well, no. Not exactly. SHA-1 is supposed to be a one-way function, meaning that you can't just reverse the operation. So you can't just "crack" it like solving an equation.
I'm not sure if you are talking about retrieving the original file from the hash, but if you are, then you don't understand what hash functions are for. In this case, there are an infinite number of combinations of bytes that have the same SHA-1 hash. The goal is to find one that has the same hash value, regardless of whether it is actually the same file. SHA-1 is not a cipher.
www.timcoleman.com is a total waste of your time. Never go there.
If this definite break is confirmed, I think we will need to conclude that the entire family is suspect for any genuinely important purpose.
There are a bunch of hashing algorithms on the Hashing Function Lounge that are listed as having no known attacks. At present, the most widespread is Whirlpool. I think it likely that one of these will replace SHA as the hashing function of choice in major cryptographic areas.
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
No, that would be one application of a hash (and not a very good one, because someone wanting to mess with it enroute could just re-hash the doctored version and pass on the new hash. What you discribe could be a way to check for accidental errors, though.). A hash is a function that given data gives a smaller amount of data. This smaller amount of data is then also called the hash of the origonal data. A good hash function has the property that if you know the hash for a file, you shouldn't be able to come up with another file that has the same hash without a prohibitive amount of work. A hash function is broken if this property stops holding.
This post written under Gentoo-linux with an SCO IP license.
Finding a single collision after a huge search isn't the same as being able to generate a collision on demand, which is what the SHA-1 breakage apparently purports to be.
Bruce sits at his desk, reading over the encrypted e-mail sent to him about breaking SHA-1, when a loud scream echoes from his office
I JUST SENT OUT MY NEWSLETTER THIS MORNING!
Slackware, what else when it must be secure, stable, and easy?
OTOH, this attack indicates that other types of attacks may be found sooner than was previously thought. So it is still a good idea to move away from SHA-1 in the medium to long term. Though it's not entirely clear what you should move to. And it is not certain that more attacks will be found soon.
main(c,r){for(r=32;r;) printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
Some attacker would have to be REALLY dedicated to use this vulnerability to harm you, and they would still require hideous amounts of processor time to mount an effective attack. Digests are a quick and easy way to verify that some message or file is correct. If the hash is signed as well, then you can verify the sender, too. When you download something like a Linux ISO, there is often another file on the server containing the hashes of the files, so you can verify that everything downloaded correctly. If you want to make sure that nobody other than a trusted person modified the files, then that trusted person could encrypt the digest with their private key, allowing anybody with their public key to verify that everything's correct.
A person can, with a broken hash, create another ISO file, perhaps with malicious code inserted, that has the same digest, meaning you can no longer trust the signed digest. Let's say that this vulnerability reduces the average time needed to find a collision from 2^48 tries via the Birthday paradox (If this isn't a 96-bit hash, then I really need to get more sleep) to 2^32 tries. That's over 65,000 times faster, but you know why I'm not worried? That's still over 4,000,000,000 ISO files that the attacker would have to try before hitting on one that's got the wanted characteristics and the correct digest to boot, and if it requires equivalent memory usage to its time usage, then I'd expect it to use at least 48 gigabytes of memory to store all of the previous attempted hashes. If it takes 15 seconds to compute one digest, then you're looking at a mere 2,000 processor years to find a vulnerability, compared to the much more comfortable 130,000,000 processor years that it would have required using the brute force method.
Feel better now? If I really got mixed up, and was wrong about the size, then just multiply all the listed times by 2^32, and wake me in 8 trillion AD.
"Anyone who attempts to generate random numbers by deterministic means is living in a state of sin." -- John von Neumann
thank god ROT-13 will never be cracked.
Check this article: Federal agencies have been put on notice that National Institute of Standards and Technology officials plan to phase out a widely used cryptographic hash function known as SHA-1 in favor of larger and stronger hash functions such as SHA-256 and SHA-512.
Had to happen, didn't it?
No algorithm is all-powerful - it only withstands attacks for so long.
No, it didn't. In fact, this is the most important problem in CS. The theory is that there are certainly problems where checking a solution is easy (2 and 3 are unique factors of 6 because it's easy to see that 2*3 == 6) but where the only possible way to find the solution given the answer is to compute the solution for every possible answer.
It's not been proven whether hashing is this type of problem (whether it's NP-complete). Moreover, it's never been proven that there isn't a solution for problems we think are NP.
What's more, it *has* been proven that once we find a solution to an NP-complete problem we'll instantly have solutions for *every* NP-complete problem.
sha1 and md5 are generally considered so weak that they should only be used to combat error or accidents, not fraud.
:(
Not true. SHA-1 is the hashing algorithm of practically all common security standards. It's found in SSL/TLS, X.509, PGP (the protocol, not the program, so that means GPG also!), S/MIME, etc. In other words... everything. Replacing this is going to suck.
I noticed using ROT-2 gave what looked like a kinda-close decryption of ROT-13. So I started trying ROT-3, then ROT-4, I got as far as ROT-12 before I got bored and gave up, but it was showing great promise!
Education is a better safeguard of liberty than a standing army.
Edward Everett (1794 - 1865)
if I understand correctly, SHA-1 is a similiar algorithm to MD5, which is commonly used to uniquely identify files
/etc/passwd and /bin/ls files have the same MD5 hash. The value in MD5 and other such hashes is that the probability of that happening is so remote that as a first approximation, comparing hashes is just as good as comparing files.
You do not quite understand correctly. MD5 and SHA-1 are hashing algorithms, and as such it is expected (and accepted) that there are collisions. That is, you might find that your
That is, you can either keep a backup copy of your filesystem to compare against or you can keep a list of hashes, and mathematically, all this "break" has demonstrated is that the chances are 1:590295810358705651712 not 1:1208925819614629174706176 of a collision. In other words, don't lose sleep.
Now, for secure cryptographic signatures, the implications are much more unpleasant. It's not the end of the world, but this is that big red light that says: switch to SHA-512 (or something equally secure) ASAP!
The article says that 2**69 hash operations are needed to find a collision. If you have a SuperHashOMatic that can do 1 Billion hashing operations per second, thats still an average time of about 18700 years.
In order for the time to be something to be concerned about (~10 years), you would need a machine capable of doing 1.87e12 hashing operations per second. Thats 1.87 TRILLION hashing operations per second.
Ah, but what about distributed computing?
Let's assume that there are 1 billion desktop computers working on this project. Then they must be able to do 1870 hashing operations per second. This is a ridiculously large number for today's implementations (mine gets 100 per second, most could do about twice that).
So is it bad? Somewhat. Further breaks could make it worse.
We should move away from SHA-1. But this isn't not the end of the world.
Note that what cryptographers consider a "break" is not necessarily the same as what users consider a break. (Neither is more strict, they are just different criteria for different people).
In this case, the researchers from Shandong University (supposedly) reduced the work required to find a collision from 2**80 to 2**69; this is a major cryptographic result. It is major because SHA-1, as a "cryptographically strong hash", is not supposed to have any attacks better then random. A factor of 2**11 reduction shows SHA-1 to be very far from ideal; and since lots of clever people have tried to show this, the research team should be proud.
Does this mean the bad-guy-of-your-choice can now start forging digital contracts? Not yet - there is no guarantee that the collision will be meaningful (as least their earlier papers didn't show that result). For a forgery to be useful, the forger needs to make the fake message say something useful - may be change the $1 to $1 million, or change the name, or something. A collision at a random place (or a non-sensical string) is essentially useless as a forgery (there may be some interested DOS attacks, but I am talking about outright forgery which is the point of the hash functions).
And lastly, 2**69 (roughly 10**21) is still a big number! Assume that some clever people wrote a super-duper hand-optimized code that does a whole SHA-1 in a micro-second on a late model 4 Ghz PC, that is 10**6 hashes/sec. A grad-student using all the PC's on a campus, say ten thousand, that's another 10**4. This would take 10**11 seconds (or roughly 20K years). Note that for SHA-0, their break is 2**39 operations, which *is* practical - it would take the grad student only a minute, or a single PC a week.
This break is yet *practical* for *most* people. (Would I still use SHA-1? Not in new application, and I make sure that existing applications get changed over eventually.)
Lest I be accused of ignoring the big boys, the equation changes for them. If a Three Letter Agency is willing to invest a lot of money and design some cool chips that has awsome parallelism and everything, then each break may take only a week. For example, assume these chips has a bunch of pipes that can do a hash every nano-second (or 10**9 hash/second). Further, say there are 100 of these pipes per chip, 100 chips per board, 100 board per rack (or 10**6 pipes/rack). Each rack can then do 10**15 hash/sec, With such a magical rack, it would take 10**6 seconds (or just under two weeks) to find a collision. This would cost Some Real Dollars, but is it within the budget of some three letter agency? You bet. Hack, I would be willing to sell you one for under a billion dollar US. On the other hand, for that kind of money, cryptanalysis takes on different textures - why spend a billion to crack SHA-1 when you can buy the right wet-ware unit for a million?
That's nothing. ROT-26 offers the best encryption as of yet!
I can't read your post, it seems to be encrypted in that new ROT-26 scheme.
Video Production Support
Relax... it still takes 2^69 tries. That is 590,295,810,358,705,651,712 hash operations. To brute force sha-1 it takes 2**80. This is only 2**11 times faster then a brute force attack... thats 2048 times faster. Its significant but it's not that big of a deal. It is no more significant then if someone with a 2000 node cluster tried to brute force your hash (which is completely feasible...especially for large government agencies like the NSA). In other words, if you were capable of performing 1 trillion (1,000,000,000,000) hash operations per second, it'd still take nearly 19 years for a collision to be found. I assume the NSA can knock that number down to under 24 hours, but thats expected of them. For anyone else in the world, assuming your not being followed by the NSA... and god help you if you are... sha-1 will still be fine and the entire internet security infastructure will not need to be redesigned.
Regards,
Steve
What someone really ought to do is use ROT-7.5 twice to decrypt ROT-13.
Si la vida me da palo, yo la voy a soportar Si la vida me da palo, yo la voy a espabilar
both papers were (IIRC) generate two datasets X and Y with the same hash Z
the next step up is to, for any data X and hash Z determine a Y which does not equal X which has hash Z. THe ultimate breakage is when you can, for any data X with hash Z and arbitrary data Y generate M which has the property of Y+M has a hash of Z. At this point you can substitute a conrolled and malicious piece of data which can substitute for X.
Snowden and Manning are heroes.
For example, if my password is "foobar", then the server does not store "8843d7f92416211de9ebb963ff4ce28125932878" as the hash, but perhaps the hash of "foobarDKTUHRAOHL" or "19747e26b86ee7939c046c0171a991926f0e01ae". The salt value "DKTUHRAOHL" is stored on the server and never revealed to anyone. So, even if somebody knows the hash value "19747...e01ae", they cannot come up with another string of characters that hashes to the same value, because even if they could, the value they enter in an attempt to hack my account is appended with "DKTUHRAOHL", rendering (almost certainly) a different hash value.
Now, if they know the salt value, the problem becomes equivalent to finding a string ending with "DKTUHRAOHL" that hashes to "19747...e01ae." However, if someone has gained access to a properly secured server's salt values, you have a large problem on your hands indeed.
(This is not meant as a comment on the security of HMAC-SHA-1.)
In general, we can say that there are infinitely fewer hashes than there are possible data objects you may wish to hash, and therefore there are infinitely many collisions. We can also say that for an N bit hash, at least one collision must occur over a range of (2^N)+1 values for the initial data object.
However, if the collisions occur on a totally cyclic basis, it doesn't matter if there's only ever one within that range. You know where it is, without the bother of looking.
Therefore, the strength of a hash can be measured as a function of two properties:
Bit operations have tended to be used, because they're fast and they allow some control over these two parameters. Other than that, there is no particular merit in using them.
Cellular automata can produce some excellent one-way functions. Their behaviour can also be far harder to predict, if the algorithm is good. However, they are computationally very expensive and getting a usefully strong algorithm is much harder than with bit manipulations.
Transforms are not generally considered one-way, because 99.9% of the time they are only useful because they are two-way. I've not really looked into how transform operations are used in hashes, but they presumably have some strengths.
(Transforms in cryptography, where you want to go from one domain to another and then back again, would make sense. They would also be useful for encryption modes, for generating the new encryption key for the next block.)
It's a small world and it smells funny; I'd buy another if it wasn't for the money; Take back what I paid (SoM)
I read on one site - in answer to the question "What's the big deal - is 2**69 really all that bad?"
That's 2**11 less operations. Let's say breaking this (2**69 ops) takes the NSA a week. If it had been 2**80, it would have taken 2048 weeks, or 39 years. If it would have taken the NSA (or whomever) a year to break SHA-1 before, it could be broken in 4 hours.
My guess would be it would still take a lot longer than a week - but would now be in the realm of possibility, whereas before it would have been in the lifetime(s) range. However, this is totally a wild-assed-guess, based on the assumption that it was expected to take 100+ years before this to crack.
This sig donated to Pater. Long live
What you have to figure is that with any hash thats shorter than the max amount of data, then the possibility of collisions will occur;
figure that if you could represent every possible combination in 128 bits, you would never need to have 129 bits of data.
Because this is not true all hashes will have collisions. However the chances of multiple hashes all having collisions with altered data is 'pretty damn slim'. So therefore the best solution, most likely in the future, and presently is to authenticate messages, identification (ala ssl certificates**) and binaries with multiple hashs known to be reasonably strong. One doesnt need to be a cryptologist to realize that using something like md5, sha256 and like ripemd160, the chances of collision in all 3 hashes are quite slim, and within the range of acceptable risk.
I think ROT-65536 would work even better, especially for Unicode.
Beware: In C++, your friends can see your privates!
MD5 was 'broken' in 1995 by Hans Dobbertin who discovered compressor function collisions. It was almost another 10 years before the compressor function collisions were turned into an attack which produced hash collisions.
So there is a serious security problem here but it does not mean that everything that uses SHA-1 is now vulnerable. There are many applications where MD5 is completely adequate. If you have a really good reason to do so and a really good understanding of the security requirements and risks you can use even something like MD2.
Today paul Kocher complained that Microsoft was using MD5 in its anti-spyware to identify known bad software. This is not actually a major problem, much worse would be using MD5 to identify known good software to keep, that is when a collision would bite. For known bad programs well i don't want any variant of the program to run...
But if you are writing an entirely new application then use SHA-256 or SHA-512, more rounds, more bits.
Meanwhile we need to research some new hash functions pronto.
Looking for an Information Security student project suggestion?
Try http://dotcrimeManifesto.com/
That is nothing. This post has been encrypted with an unbreakable one-time-pad! TWICE!
For password hashes this attack shouldn't be a problem, if it is as described in the article. The attack does only one thing: allows an attacker to generate two streams of data which hash to the same value. This is a problem for digital signatures, because somebody can sign one data stream, then distribute another with the same signature. So the signature doesn't guarantee the data has not been modified
Even for signatures, it depends on the application. There are two types of collision resistance:
- Weak collision resistance: Given x, I cannot coumpute y s.t. H(x)=H(y)
- Strong collision resistance: I cannot compute arbitrary x,y s.t. H(x)=H(y)
Usually collision results show that a hash algorithm is not strong resistant.
So if I want to create random data (a nonce) and sign it there is a problem, I can create x,y with the same signature. However if I want to sign something specific, say an email, then I have to break weak resistance, random x,y won't do since x is unlikely to be the email I wrote.
I guess I missed posting this before the bulk of the posts, but maybe it'll help someone.
First: MD* SHA-* etc - they are all basically the SAME algorithm! The are just minor modifications of the same exact thing, so a break in one is a break in all.
Second: Tons and tons of people ask: can't we merge two hashes together and get a stronger one? Yes you can that's EXACTLY what MD* and HA-* DO! They are a combination of different hashes! That's how they work.
So if you really did have a good combo of hashes then just give them a name and use them as a hash - don't bother just plain merging existing ones.
Also, merging say MD5 and SHA-1 is pointless - they are both based on the same hashing code! You are gaining nothing by merging them.
-Ariel
I hope they get it fixed soon.
As others have pointed out, I can create 2 documents, X and Y, have a target sign one, then substitute the other. His digital signature will be valid for both. Great - it takes only 2^69 attempts to get a collision - I'm sure the chances that the X and Y found will both be valid English documents, one of which I could convince a target to sign, the other allowing me to scam him out of enough money to make the whole ordeal worthwhile.
However, people keep copies of what they sign. Even if I did find a collision, and even if both documents were valid English text, the guy could say "I didn't sign Y - look, my signature is valid for X - he scammed me". Great.
The more likely scenario is someone signing their own document, then claiming it was fraudulent. They could create their own X and Y, sign X that somehow involves another party, then claim they actually signed Y and this other party was the scammer. But they still have to find X and Y in 2^69 steps such that both make logical sense in the English language - no simple task.
This is cool in a theoretical sense, but in a practical sense, its like saying you don't need a million monkeys on a million typewriters typing for a million years to generate Shakespeare; it'll only take 999,999 monkeys on 999,999 typewriters...
Or, to go back to the theoretical world: with processor speeds doubling every 1.5 years, and this team shaving 11 factors of 2 off of the break time, the lifetime of SHA-1 just shortened by about 16.5 years. Not quite the end of the world as we know it.
Step 1: Break SHA-1
Step 2: ?
Step 3: Profit!
At least they gave the algorithm. If their synopsis is indicative of the paper, they illustrate that SHA-1 has collisions, and collisions can be discovered through the awesomely sophisticated technique of brute force. Pardon me while I dust off my bomb shelter.
Let's wait for the actual paper. If it takes more CPU power to force a collision within a year than the whole of what IBM sells in that year, I think that the hash is doing its job...
I am no longer wasting my time with slashdot