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.
What this means is that SHA-1 collision attacks can now be carried out with custom inputs, and they're not just accidental mishaps anymore, allowing attackers to target certain files to duplicate and forge.
The SHA-1 hashing function was theoretically broken in 2005; however, the first successful collision attack in the real world was carried out in 2017.
Two years ago, academics from Google and CWI produced two files that had the same SHA-1 hash, in the world's first ever SHA-1 collision attack -- known as "SHAttered."
Cryptographers predicted SHA-1 would be broken in a real-world scenario, but the SHAttered research came three years earlier than they expected, and also cost only $110,000 to execute using cloud-rented computing power, far less than what people thought it might cost.
But last week, a team of academics from France and Singapore has taken the SHAttered research one step further by demonstrating the first-ever SHA-1 "chosen-prefix" collision attack, in a new research paper titled "From Collisions to Chosen-Prefix Collisions - Application to Full SHA-1."
"Finding a practical collision attack breaks the hash function badly of course, but the actual damage that can be done with such a collision is somewhat limited as the attacker will have little to no control on the actual data that collides," Thomas Peyrin, one of the researchers told ZDNet via email over the weekend.
"A much more interesting attack is to find a so-called 'chosen-prefix collision,' where the attacker can freely choose the prefix for the two colliding messages. Such collisions change everything in terms of threat because you can now consider having collisions with meaningful data inside (like names or identities in a digital certificate, etc)."
(Score: -1, Offtopic) by Anonymous Coward on Monday May 13 2019, @11:51PM (4 children)
ترجمة كل شيء إلى اللغة العربية وتجربة في الله.
(Score: -1, Flamebait) by Anonymous Coward on Monday May 13 2019, @11:55PM (1 child)
Statistically speaking, that probably means "Death to infidels who break this code".
(Score: 3, Touché) by PartTimeZombie on Tuesday May 14 2019, @12:39AM
Statistically speaking, that probably says "Don't forget to pick up some hummus on the way home".
(Score: -1, Troll) by Anonymous Coward on Tuesday May 14 2019, @12:35AM
Not many of you lot can read Arabic, so I provide this translation:
"Allah------hahah-----ahahahah-ahahah------
Fuck------uckuckufck---uckcuck---uck
YOU!"
Peace be upon you.
Thank you, thank you very much.
(Score: 3, Informative) by Rosco P. Coltrane on Tuesday May 14 2019, @01:08AM
Google Translate seems to have broken your secret code:
"Translate everything into Arabic and experience in God"
Knowing Google Translate, that looks very much like a line from Shakespeare or something.
(Score: 4, Interesting) by bzipitidoo on Tuesday May 14 2019, @01:14AM (8 children)
Checking major projects such as the Linux kernel, Ubuntu Linux, Linux Mint, and Firefox, they're all using SHA-256 (256 bit SHA-2) or gpg signatures.
But I still see MD5 used a lot. It's only good for checking for transmission errors and such unintentional corruption, as it's a lot more broken than SHA-1.
There's a new family, SHA-3, published in 2015. I haven't seen it in use anywhere yet.
(Score: 0) by Anonymous Coward on Tuesday May 14 2019, @04:35AM (3 children)
And I bet a lot of people don't even check the MD5... The kind of people "There was an error on my computer! – What did the message say? – I have no idea because I didn't read it!"
(Score: 0) by Anonymous Coward on Tuesday May 14 2019, @05:50AM (2 children)
With all the crap they add to web browsers and web standards lately, wouldn't be to hard to add a "hash" attribute to the various tags or an X-Content-Hash header. Of course, this is becoming less of an issue with the push to have HTTPS on all websites.
(Score: 0) by Anonymous Coward on Tuesday May 14 2019, @06:14AM (1 child)
Subresource integrity is a thing, though.
https://developer.mozilla.org/en-US/docs/Web/Security/Subresource_Integrity [mozilla.org]
(Score: 0) by Anonymous Coward on Tuesday May 14 2019, @06:33PM
I am aware of that, but that attribute is only for script and link elements; it isn't generic and can't be used to verify other types of downloads.
(Score: 2) by driverless on Tuesday May 14 2019, @09:17AM (1 child)
You need to be able to read these papers with an ability to interpret what's really in there rather than taking the contents at face value. Chosen-prefix collisions are just an extension of standard collisions. In many cases where SHA-1 is used, e.g. in certs, this isn't possible, they have 64-bit (minimum) random serial numbers to deal with this. The paper also claims that you can "break TLS, IKE, and SSH", but this assumes either a near-real-time break of SHA-1 or a TLS implementation that's willing to wait several months between two parts of the TLS handshake, neither of which exist. So the impact is really mostly mitigated in common use cases, it's only if you're doing things like long-term signatures on data that you need to worry, and in that case you should have dropped SHA-1 long ago.
The reason why SHA-3 isn't used is that it has no currently-known advantages over SHA-2. It's also a lot slower than most other hash functions, including SHA-2 and also good alternatives like BLAKE2 if you really want a newer-than-SHA2 hash. So it has no real advantage over SHA-2 but is a whole lot slower, there's no incentive to use it.
(Score: 2) by bzipitidoo on Tuesday May 14 2019, @03:07PM
Ahh, the need for speed. Most people sing in the security choir, that security is more important than any other issue. Then they show they don't believe it by not practicing what they preach.
For example, if security is so important, why haven't chip makers moved faster to fix Spectre? They've nibbled at the edges, made it not as bad, but have not truly fixed it. They've whined that it will hurt the speed of their CPUs. However, manufacturers always complain that complying with regulations, fixing flaws, increasing safety, or whatever is overly burdensome, and then often it turns out not to have been as bad as they claimed. I would like Spectre fixed, but I have to concede that it takes a lot of clearly malicious code to exploit the flaw, and for unimportant uses and users, it may not be worth extraordinary efforts to solve. Most especially, I have not heard that anyone is willing to go all the way back to 25 year old CPUs that do not have speculative execution, and accept the massive performance hit, to be safe from Spectre.
If as you say SHA-3 has no advantage in security, then that's a double blow. Slower and no more secure.
(Score: 0) by Anonymous Coward on Tuesday May 14 2019, @07:51PM (1 child)
What about MD4+MD5?
One of the details left out in lots of these 'OMG IT'S BROKEN, UPGRADE!!!' scenarios is not just the practicality of attacks against a single checksum type, but attacks that work against multiple checksums plus a file length. If you have 2 checksums and a file length less than x(whatever the checksum(s) maximum value(s) with statistically unlikely collisions), you should in many cases be as secure as a 'stronger' checksum mechanism with less cycles used to arrive at that protection. If you can interleave the checksumming algorithms so they are both checksumming the same data at the same time you can increase performance even more. Given the ever increasing lengths of sha256/512/blake2/etc as well as the cpu time some of these hashing methods require, it is worth considering pairs based on file size, as well as a 'future hash' for each to help ensure authenticity well into the next decade or beyond, so that even if a website is hacked and some checksums can be faked, the integrity can be assured thanks to the intersection of checksums.
(Score: 0) by Anonymous Coward on Wednesday May 15 2019, @09:03AM
This is something I've been wondering myself. Would be interesting to hear the opinion of somebody qualified.
(Score: 2) by opinionated_science on Tuesday May 14 2019, @01:21AM
in the paper (I skimmed) they priced for a GTX 970 gpu on a cloud instance.
I wonder if there's a better estimate for the new V100 etc...
Better still, a distillation of the needed maths, so those of us that like to write code, can read the solution ;-)
(Score: 4, Interesting) by rob_on_earth on Tuesday May 14 2019, @10:02AM (3 children)
I never understood why we do not combine Hashes with file sizes.
My understanding of hash collisions was that to create a collision required vastly different sized files.
So why not just have a standard where we always give the number of bytes after the hash e.g.
68b329da9893e34099c7d8ad5cb9c940:56098
(Score: 0) by Anonymous Coward on Tuesday May 14 2019, @10:55AM
why use common sense to get rid of the problem if the alternative is to be payed forever to fix the stuff your friend on the other side of town keeps breaking?
(Score: 1, Informative) by Anonymous Coward on Tuesday May 14 2019, @01:09PM
Thinking like a non-mathematician will bite you in the ass when dealing with mathematicians. It's bad, m'kay? You are adding just some basic things to "fix" the hash but it's actually a really bad idea that doesn't work to fix collisions. It was shown already nicely for MD5. Same length file. Same hash. Different content.
https://www.mathstat.dal.ca/~selinger/md5collision/ [mathstat.dal.ca]
(Score: 0) by Anonymous Coward on Wednesday May 15 2019, @05:22AM
Hashes of constant length are desired.
(Score: 0) by Anonymous Coward on Tuesday May 14 2019, @11:25AM (1 child)
Before, Linus thought that this kind of attack is hard to use against Git as there are additional constraints:
https://marc.info/?l=git&m=148787047422954 [marc.info]
Does this new attack change anything, or not?..
(Score: 0) by Anonymous Coward on Tuesday May 14 2019, @04:06PM
Collision attacks, including this one, basically only are a problem for digital signatures. Now, git does use digital signatures, for example there are signed tags used for authentication.
So since SHA-1 collision attacks exist, the potential attack on a git repo is this: I can (possibly) construct two git commits with the same hash, with one being "good" and the other "evil". I get you to pull my "good" commit, so now your repository contains the colliding hash. If you then push a signed tag to the repository, at a later date I can publish another repo containing the "evil" commit with your valid signature on it.
Anyway, chosen-prefix collision attacks make dealing with formatting of the things you're hashing easier, so this will probably make it easier to construct colliding git objects.
In practice pulling off this sort of attack on a git repo is likely not worth the effort. Hardly anyone pushes signed tags and very few people verify signatures anyway. And there are much simpler attacks which are probably easier and more effective. For example, getting a maintainer to simply accept a bad patch (see: openssl), or take over maintanership of a popular but unmaintained package and publish malicious versions (see: event-stream), or simply compromise a mirror and replace source tarballs (see: unrealircd).