Slashdot Mirror
More on Newly Broken SHA-1
AnonymousStudent writes "Details are out about the reported broken SHA-1 hash function. The findings are that SHA-1 is not collision free and can be broken in 2^69 attempts instead of 2^80. This is about 2000 times faster. With todays computing power and Moores Law, a SHA-1 hash does not last too long. Using a modified DES Cracker, for the small sum of up to $38M, SHA-1 can be broken in 56 hours, with current computing power. In 18 months, the cost should go down by half. Jon Callas, PGP's CTO, put it best: 'It's time to walk, but not run, to the fire exits. You don't see smoke, but the fire alarms have gone off.' As Schneier suggests, 'It's time for us all to migrate away from SHA-1.' Alternatives include SHA-256 and SHA-512."
2^69 = 590295810358705651712
2^80 = 1208925819614629174706176
2^80 / 2 ^ 69 = 2^11, which = 2048.
Yep. 2000 times faster.
The new SHA-1 break only affects very carefully constructed messages. This means that it is completely useless for an attacker impersonating an existing message, unless that message was purposely constructed to be attackable. The attack is only useful if the attacker creates both messages, and the attacker can choose the exact format of both messages.
- Sam Ruby
The findings are that SHA-1 is not collision free and can be broken in 2^69 attempts instead of 2^80.
Well, doh - it's a hash you silly, there will always be collisions.
Anyway, it's nothing to panic about really. The ammount of computer power needed to crack it is still massive. Unless you're investigated by the NSA, SHA-1 will be fine for quite a while.
It simply means that it is possible to find a collision without a brute-force scan of O(2^80) messages. Instead, because of weaknesses in the algorithm, it is only necessary to scan O(2^69) times.
They already exist. RIPEMD-160 is tried and tested and seems secure, or at the more experimental stage there's Whirlpool.
I am trolling
Using a modified DES Cracker, for the small sum of up to $38M, SHA-1 can be broken in 56 hours, with current computing power.
Is that assuming that that the collision will be found on the last (or in this case, 590,295,810,358,705,651,712nd time) try?
Because statistically it's just as likely you will find a collision on the first try as you are on the last try.
Yes, but say someone creates a document (such as a contract) for you to digitally sign.
If they're prepared to spend a realistic level of time on it they could create two of them that hash to the same thing, with a small but effective change to the second.
You sign the first with SHA-1, but your signature also matches on the second, putting you in a weak position when you try and claim "I didn't sign _that_!"
The time/money requirements to do this aren't really practical yet, but they will be soon.
As the sub says, time to start shifting off SHA-1.
Remember kids, it's all fun and games until someone commits wholesale galactic genocide.
Well, it all depends. Catastrophe didn't happen with DES because there was an early warning and noone used it for serious stuff by that time. With SHA-1 however, the warning came a little later and the shift will be a bit more painful as a lot of things are using it, although not impossible and not a catastrophe neither.
It takes a man to suffer ignorance and smile
Be yourself no matter what they say
The attack has nothing to do with trying to discover contents based on the hash, it has to do with generating intentional collisions.
Attacks on hashes have absolutely nothing to do with discovering any kind of content, they have to do with the reliability of digital signatures, key exchange, data integrity, authentication etc.
As for any kind of cryptography being sufficient...no, not really. Consider CSS...the encryption used on DVDs is no longer considered any kind of barrier to access.
Similarly publicly visible hashes in password files on Unix systems haven't been considered secure for over 10 years, due to the simplicity and success rate of dictionary attacks (plus more recently, brute force is becoming increasingly easy).
The concern is not so much that the method described in this break is feasible on today's hardware, or even that this method will get cheaper and cheaper as hardware gets faster. The BIG concern is that this method provides insight in to the SHA-1 in general, and will be used by others to come up with more efficient breaks or more egregious flaws.
http://netlab.fe.up.pt/~ei01024/sha-1/
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
Creating pseudo-random numbers that hash to the same value != making any arbitrary document hash to the same value.
It's tragic. Laugh.
As far as anybody knows, no. If such a technique were known, this article wouldn't be very big news. Before this technique, the best way anybody knew of to generate two pieces of data with the same SHA-1 hash was to just try a ton of random data until you found two pieces with the same hash.
Mod down posts with a "Free Mac Mini/iPod" sig, they're spam!
SHA-2 in 256 and 512 bit flavors isn't the only alternative folks. Among other nifty hashes, there's whirlpool: Linux 2.6 kernel crypto API entry for whirlpool and a page with whirlpool details.
http://tinyurl.com/4ny52
... does not mean what you think it means. Look it up.
All crypto algorithms age, and even if the news of SHA-1's death is somewhat dramaticised by people who make their living from security work, it's important to see _all_ crypto algorithms as temporary shims.
That is why anyone developing new protocols and products that rely on security should use SASL, which abstracts the crypto layers in such a way that it's easy to change them over time.
SASL is an IETF standard and there are open source implementations like Cyrus.
Sig for sale or rent. One previous user. Inquire within.
An idea: This could be a good thing. If there was a one-one relationship, then that would mean theoretically there could be an inverse function to "expand" the hash. Given that there are going to be collisions, this may give us (if only a little) more confidence that hashes are not reversible.
Apologies, $80k per problem.
It is because given any string, I can produce another string with the same hash faster.
No, that would be a pre-image attack. This is a collision attack. To perform it, the attacker needs to be able to choose both strings.
Note to ACs: I usually delete AC replies without reading them. If you want to talk to me, log in.
is to speak of averages. So, it is likely that 56 hours is the time to search half the keyspace on such a machine, as over a large number of uses, that will be the average time required per use.
I forget what 8 was for.
It might not be that much harder to generate a collision like this:
- I, John Smith, agree to sell my coin collection to Fred Jones for $10. -- JonesCo internal business form bma p3 rjphta,-9p.u2#H50982u.yha,cp. hxasnip
and- I, John Smith, agree to sell my nubile teenage daughter to Fred Jones for $10. JonesCo internal business form BUEQXBBX2 jma93#9g5xbaida htuEXOAhkra1255,y
And if cryptographers are finding stronger and stronger attacks against SHA1, it's foolish to assume the attacks won't get any stronger.Find free books.
In computational science and cryptography it is common to use notation O(n^x), but it doesn't mean the same thing as Big-Oh notation, it just means 'order-of-magnitude'. Its usually clear from the context what is meant: big-oh notation describes the asymptotic behaviour as a function of input size. In this context, the input size is the length of the hash and that is fixed.
Hmm...but SHA is a hashing (i.e. one way) algorithm, and Blowfish is an encryption (i.e. bidirectional) algorithm. (For more on this, see the page you actually linked to.)
So you don't use SHA-1 as an encryption algorithm for stuff like SSH, etc., because, well, you can't. Well, you can encrypt, but good luck decrypting :-)
But you might use SHA-1 to generate crypto keys from plaintext data (e.g. passwords) for use by an encryption algorithm. So 'switching to Blowfish' won't help - you need to switch to a different hashing algorithm (assuming you consider this recent discovery to be a concern for such usage of SHA-1).
Or, and this is a good one, you could do that. For any message that I create, and sign for SHA-1, it's now possible that I created another duplicate message, and that I could, at any point in the future, say "Oh no, I didn't sign _that_!"
So, there are two lessons to be learned.
1. Don't trust SHA1 as part of an algorithm for signing a document that someone else gave you. Actually, this is not so much of a risk, because any reasonable signature algorithm signs more than just a straight hash of the document.
2. Don't trust any document signed by someone else with an algorithm using SHA1, if they created that document themselves; they might have a way to repudiate that signature, leaving you out in the cold. This one is actually more dangerous.
The findings are that SHA-1 is not collision free
What, is that new? That already follows from the fact that there are only N possible hashes, and M possible messages, and NM. In other words, if you have an 8-bit hash (256 values) for a, say, 1K message, then you must get a lot of collisions.
If it takes only three days or so to find a collision, what does that mean practically? Almost nothing. Because the collision that you would find is most likely meaningless. The modification that you'd like to apply to the message (while sticking with the same, given hash) is likely to be something very specific, for example, change $1000 to $10.000. And that, unfortunately, is not easy. This vulnerability can't be easily exploited at this point.
But even saying that "if the algorithm has one vulnerability, then it's likely to have others" is totally illogical - unless a whole class of vulnerabilities has been pointed out.
It's not even time to 'walk to the door' because the fire alarm has gone off, as someone said later down in the comments. Instead, it's time to read the Chinese paper, produce more truthful descriptions of how much of a problem we are going to get with this (does it lead to more severe vulnerabilities), and start working on better hashing algorithms.
Not true. The use of that is creating one legitimate document and apply a certification to it, with the authority of a trusted certifier (who would have verified it, because it is legitimate).
The is that as soon as you try to place specific content in the message, it becomes *much* harder to find a collision that meets your requirements (especially if there are length requirements too).
Now.... Let me bring up one possible use of these issues. If you store passwords as SHA hashes, and if someone can get a list of hashes, then they can find colliding passwords.
LedgerSMB: Open source Accounting/ERP
There are, however, 2^296 messages that are 37 bytes in length, which means that for any 37-byte message, there are by necessity 255 other 37-byte messages that yield the exact same hashes. Sure, most (all?) of the others will be binary gibberish, but there are nonetheless 255 colliding messages for any given 37-byte message.
And that's just for 37-byte messages. If you send a 1 KiB message, there are 2^7904, or around 10^2379 colliding messages.
Bit Torrents use SHA-1, I believe. If the MPAA wants to spend the money, I suppose they could start corrupting downloads now by inserting torrents that pass the SHA-1 hash, but do not actually contain valid data.
as soon as you try to place specific content in the message, it becomes *much* harder to find a collision
It's pretty easy to put a whole lot of garbage data in a document. Changing this data wouldn't affect how the document looks, but would of course affect the hash. With this to modify, you could create a collision with the ease mentioned in the article.
If you store passwords as SHA hashes, and if someone can get a list of hashes, then they can find colliding passwords.
No, they can't. You can create a hash collision with a known piece of data, not with a known hash. You would have to know the original password (from which of course the hash is easily computable) to create a password with a colliding hash.