Academics Improve SHA-1 Collision Attack, Make It Actually Dangerous (zdnet.com) 69
An anonymous reader writes: "Attacks on the SHA-1 hashing algorithm just got a lot more dangerous last week with the discovery of the first-ever 'chosen-prefix collision attack,' a more practical version of the SHA-1 collision attack first carried out by Google two years ago," reports ZDNet. Google's original research allowed attackers to force duplicates for specific files, but this process was often at random. A new SHA-1 collision attack variation (a chosen-prefix attack) detailed last week allows attackers to choose what SHA-1-signed files or data streams they want to forge on demand, making SHA-1 an attack that is now practical in the real world, albeit at a price tag of $100,000 per collision.
Re: (Score:3)
They base the cost on what you would pay a premium server host like AWS for enough CPU time
You could cut the cost by a factor of 10 by using GPGPU.
You could cut by another factor of 10 by using FPGAs.
For a serious effort, ASICs would be perfect for the bit shifts and rotations needed by SHA-1. NRE would be about $1M, but after that, less than $100 per crack in power consumption.
Does anyone still use SHA-1? It was deprecated back in 2005.
Re: good use of 100k (Score:4, Insightful)
Does anyone still use SHA-1? It was deprecated back in 2005.
Yes.
Even though I've been writing into security and crypto policies for around a decade that SHA-1 should be considered insecure, there is a lot of software out there using it without a way to change the crypto algorithm. Wherever we put that above rule into place, we've had to grandfather in or allow exceptions for numerous applications.
Yes, SHA-1 is very much still in use.
Re: (Score:2)
I keep saying - there needs to be a resource somewhere that software and developers can query.
Is MD5 safe? No.
Is SHA-1 safe? No.
And so on. Programmatically, on a simple table on a webpage, and so that people can subscribe to updates when something changes.
There is no reason in this day and age why we can't tag *algorithms* themselves as obsolete, and why libraries that incorporate them can't query such an API and issue deprecation warnings the second they are flagged as potentially insecure - either brea
Re: (Score:2)
Only issue I see with this is "safe (or unsafe) for what use"
Re: (Score:2)
I keep saying - there needs to be a resource somewhere that software and developers can query.
That resource exists in good companies and is called the crypto policy.
Because it isn't that simple. You need to keep use cases in mind. And yes, there are use cases for which MD5 is perfectly fine still.
And it isn't that simple because there is a lot more to consider about crypto than just an algorithm. AES-128 or AES-256? (spoiler: makes almost difference for most purposes) Which mode? Take care of your IVs. Except where the mode uses a nonce instead. And let's talk about key management, certificates and
Re: good use of 100k (Score:2)
2) Yes FPGAs and ASICs potentially could do better, but no: research in that direction has failed.
Re: (Score:2)
that could have fed poor people
Goody-goody comment whose only goal is to make you feel virtuous. Talk is cheap - so stop feeling virtuous and do something to feed the poor, beyond publishing inane comments to make you feel virtuous.
Re: (Score:2)
Criminals show are trying to hack into your systems don't care about feeding poor people. They will more than happily fork out $100k in the use of this technology is going to put more money into their pockets.
So, yes, this is an excellent use of $100k in order to prove that this can be done. While it may feed poor people, it will also ensure that many more people don't go poor because some bank somewhere decided to use SHA-1 thinking it was secure enough, and now your bank account is empty and your house
I've gotta bad feeling about Academics (Score:1)
They always seem to be up to nefarious machinations.
Re: I Am Disappoint (Score:3)
If the can is kicked far enough it may not matter. No algorithm is likely to be impervious forever anyway.
Re: (Score:3)
No algorithm is likely to be impervious forever anyway.
Nope, there are provably secure algorithms, it's just that all proven ones are slow for practical use. All you need is 512 bits of hash length.
To find a collision via the birthday attack, you'd need to store approximately one bit per nucleon in the visible universe. Brute-forcing is obviously out of question (heat death and that stuff). Quantum computers won't help, too -- even if they can be extended indefinitely without decoherence (which is highly doubtful), the lower bound for a quantum algorithm is
Re: XOR OTP would like to have a word with you... (Score:2)
You've very much handwaved key distribution.
Re: (Score:2)
No, he very much correctly pointed out that key distribution across an insecure channel is always going to be insecure.
Do you really think the government can't instantly crack Diffie-Hellman?
Re: (Score:2)
Do you really think the government can't instantly crack Diffie-Hellman?
Considering that the U.S. government has deprecated RSA for new government contracts requiring cryptography, but not Diffie-Hellman, I would surmise they cannot.
Remember that bit strength exponentry is not linear. 256 bits is not twice as strong as 128-bit, it's the square of 128 bits. 129 bits is twice as large as 128 bits. 256 bits is ((2)^128)^2).
I tried to show it in terms of powers of two, but /.'s retarded lameness filter wouldn't allow it. You'll have to use your imagination.
Re:I Am Disappoint (Score:5, Informative)
My disappointment is that having realized that SHA has a significant weakness, they chose to simply multiply it with SHA-256. They are knowingly kicking the can down the road. It is only a question of time and computing power before SHA-256 is as worthless as SHA-1 is today.
The SHA-2 family of hashes, including SHA-256, is not closely related to SHA-1. There's no reason to think that a break of SHA-1 means anything about SHA-256.
But, just in case, the SHA-3 family has already been selected and standardized, and it takes a very different approach from any of the previous algorithms.
Re: (Score:2)
They are knowingly kicking the can down the road. It is only a question of time and computing power before SHA-256 is as worthless as SHA-1 is today.
If you kick the can past the end of the Universe, that is far enough.
SHA-256 is not going to be cracked before the sun goes out.
But if you really want to be sure, use a 512 bit digest, and you should be good till the last black hole evaporates.
Black hole evaporation [wikipedia.org].
Re: (Score:2)
The problem here is gonna be Git (Score:5, Insightful)
People are going to be obsessing over TLS and dedicated crypto format problems that are already mostly fixed, but the real problem is that Git uses SHA-1 for everything, not just signatures but any kind of unique commit identification. You can't just recompute all those hashes, and if there's a migration plan it can't be very far along. And a Git commit is a long-lived object, so you have plenty of time to find your collision.
Like the software supply chain wasn't already enough of a problem...
Re: The problem here is gonna be Git (Score:2, Informative)
https://github.com/git/git/blob/master/Documentation/technical/hash-function-transition.txt
Re: (Score:1)
Re:The problem here is gonna be Git (Score:5, Informative)
Linus Torvalds didn't see it as a big problem in the previous collision demonstration. Summary here: https://www.theregister.co.uk/... [theregister.co.uk] (it links to the mailing list).
Just producing a collision with an existing git object is not enough. It also needs to have valid git headers and be compileable. And if you succeed in that, git, during a fetch/pull, will not overwrite a commit that already exists with the same hash. The attacker would need to corrupt all cloned repositories as well.
Re: (Score:2)
P.S. I misremembered what I read in the mailing list discussion. Here is a discussion on Git's behavior. I think (not sure) that later Git versions were hardened.
https://stackoverflow.com/ques... [stackoverflow.com]
Re: (Score:2)
People usually think stuff like that will be hard to do. It's usually not actually hard in practice.
And what if you clone my already corrupted repo, and rely on checking out a specific hash? What if you trust a signature that's on a commit in the repo you got fr
Re: (Score:2)
It also needs to have valid git headers and be compileable.
That was a good reason why the previous weakening wasn't an immediate problem. It could produce 2 files with the same hash, but it couldn't modify a given file to have an arbitrary hash. The colliding file was highly unlikely to resemble source code.
This is MUCH closer to an attack where you modify the source as desired, and stick an arbitrary comment in at the bottom that makes the SHA1 come out the same as the original version. Of course, the compiler doesn't care what is in the comment.
git is the least of your worries (Score:2)
most of the problems are with Certificate authorities
who signs the software and connections that you run on 90% of the worlds machines ?
people who depend on CA's and think TLS 1.3 is going to save them... look to your jurisdiction, the law is going to catch up...
Re: (Score:2)
Public CAs switched to SHA256 a long time ago. There are almost no SHA-1 certs in the wild any more. That's what I mean whn
Re: (Score:2)
Grr. That's what I mean when I say dedidicated crypto formats are mostly going to be OK.
Re: (Score:2)
Git is in a transition to a more secure hash function (sha-2-256), but for now it has replaced plain SHA-1 by a hardened SHA-1 using the sha1collisiondetection library (https://github.com/cr-marcstevens/sha1collisiondetection).
Our hardened SHA-1 (https://github.com/cr-marcstevens/sha1collisiondetection) directly protects against all S
Re: (Score:2)
That blog post seems to indicate that GItHUB is using an ad-hoc detection method to deal with related attacks (and presumably it'll work against this one too). GitHub isn't Git. Are you saying that mainline Git does the same thing?
Re: (Score:1)
Re: (Score:2)
+1 Informative. Thanks, Marc.
Re: (Score:2)
As I said to the first of the three people who seem to be confused about this, you can't just recompute the hashes in a repo and be done with it, because things outside of that repo, including not only other unconverted Git repos but various tools completely unrelated to Git, are still going to be using the old SHA-1 hashes to refer to items in the repository. Furthermore, PGP signatures inside of your repository would also be referring to the old SHA-1 hashes, and you would not be able to recreate all of t
BitTorrent is the most common use of SHA1 (Score:2)
BitTorrent uses SHA-1 to validate the integrity of each chunk of downloaded data.
If finding chosen SHA-1 collisions becomes cheap, then it becomes possible for a malicious peer to inject malware into data it uploads, while still having it be recognised by downloader as valid according to the .torrent file. We're still a long way from there, but that's the risk.
mod parent up [nt] (Score:1)
Re: (Score:2)
Meh. Just download from IRC.
I'm realhashbreaker, here is my take (Score:5, Insightful)
1. Our SHAttered research (CRYPTO2017) demonstrated the first, and still only, SHA-1 collision. It is directly based on my 2^61-cost attack in EUROCRYPT2013. Besides other improvements SHAttered used GPUs at higher cost (2^64.7) but at much greater effectivity, making it practical.
2. This research is only an improvement for a more difficult and costlier collision attack for 'chosen-prefix collisions'. The first chosen-prefix collision attack on SHA-1, see my EUROCRYPT2013 paper, costs 2^77 SHA-1 calls which they improve to 2^66.9 SHA-1 calls in theory, it has not been executed yet.
3. This new research paper directly recycles almost the entire SHAttered collision attack, except, as is usual, it modifies the first and last few steps to turn the 'identical-prefix collision' into a 'chosen-prefix collison' and uses an improved strategy for the sequence of 'near-collision attacks'.
4. Using similar analysis in previous papers on the cost of SHA-1 collision attacks, their attack would cost 2^2.2 more than SHAttered, so 2^2.2 x $110K = about $500K.
5. Their claim of less than $100K is based on as-of-yet undisclosed improvements, and has not stand up to peer review yet. I am very sceptical that they can claim a cost lower than the SHAttered attack on which they rely on (see below). Historically, there have been quite a few erroneous claims of new low complexities to break SHA-1, and these have not stand up to academic peer-review.
Re: (Score:2)
Doesn't matter.
All of that is academic. SHA-1 is broken, and getting more broken, that's all we need to know. As soon as it costs $numbered_amount to break a hash, it's useless and needs to be retired. Quite what that amount is is really just trivia - that cost will drop dramatically on optimisation, dramatically over time, and can be subsumed by anyone with an interest in breaking the hash with sufficient amount of equipment already (though it might "cost" $500k to break the hash, if you have a $1bn wor
Re: (Score:2)
Your putting dollar values on breaking ability is hilarious and pointless.
A low end IBM 1620 cost $700,000 in today's money, but a $5 SOC has way more memory and power
Re: I'm realhashbreaker, here is my take (Score:2)
What I'm saying here is that we already showed a $110k sha1 attack in 2015, and that this claim of $100k is actually not substantiated. Moreover, their current attack directly recycles the $110k and does *more* work, so in any metric it should always cost more than our attack.
Lastly, there is your point of cost effectiveness. This we already showed is optimized using GPUs. GPUs provide the most com
Re: (Score:2)
the prices of compute power in the cloud vary hugely by market forces.
your $110K of GPU, whatever the hell that means, will be my cell phone soon enough