SoylentNews is people
SoylentNews
SecurityWeek has an interesting article today about the first real world SHA-1 collision attack.
Researchers at Google and Centrum Wiskunde & Informatica (CWI) in the Netherlands have managed to conduct the first real world collision attack against SHA-1, creating two documents with different content but identical hashes.
SHA-1 was introduced in 1995 and the first attacks against the cryptographic hash function were announced a decade later. Attacks improved over the years and, in 2015, researchers disclosed a method that lowered the cost of an SHA-1 collision to $75,000-$120,000 using Amazon's EC2 cloud over a period of a few months.
Despite steps taken by companies such as Google, Facebook, Microsoft and Mozilla to move away from SHA-1, the hash function is still widely used.
Google and CWI, which is the national research institute for mathematics and computer science in the Netherlands, have now managed to find a collision, demonstrating that these attacks have become increasingly practical. Their technique has been dubbed "SHA-1 shattered" or "SHAttered."
"We were able to find this collision by combining many special cryptanalytic techniques in complex ways and improving upon previous work. In total the computational effort spent is equivalent to 2 63.1 SHA-1 compressions and took approximately 6 500 CPU years and 100 GPU years," experts said in their paper.
While the task still required a large number of computations – nine quintillion (9,223,372,036,854,775,808) to be precise – the SHAttered attack is 100,000 times faster than a brute-force attack.
Google and CWI have announced the first publicly known SHA-1 collision at: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html The collision is based on a prefix attack and requires 5 orders of magnitude less work to find a collision, when compared to brute force. More information and the actual files are available here: https://security.googleblog.com/2017/02/announcing-first-sha1-collision.html and a detection tool here: https://github.com/cr-marcstevens/sha1collisiondetection
(Score: 0) by Anonymous Coward on Friday February 24 2017, @06:52AM
In practice yes that would work.
However by definition all of these systems should have collisions. Even the newer more secure ones. If not infinite compression is basically possible.
These systems as is however still have a place in finding 'easy' broken stuff. Such as transmission errors and disk corruption.
(Score: 2) by maxwell demon on Friday February 24 2017, @08:42AM
Well, the point of cryptographic hashes is not that there are not collisions, but that (a) the probability of accidental collision is low enough to be negligible, and (b) intentional collisions are hard enough to create that they are practically impossible.
The Tao of math: The numbers you can count are not the real numbers.
(Score: 0) by Anonymous Coward on Friday February 24 2017, @08:59AM
(minus the slight chance of parthenogenesis..which is really too slight to consider)
(Score: 3, Interesting) by ledow on Friday February 24 2017, @09:30AM
The probabilities multiply.
There's no common code between MD5 and SHA-1 so if one is a 1-in-2^128 and one is a 1-in-2^160 chance, then getting both is the product of those. You basically have a longer hash. The longer the hash, the hard to falsify data with the same hash.
Getting that double-collision, on a set of useful data (i.e. a malicious payload that matches an innocent file's hashes) is then harder too.
In fact, the more hash algorithms used, the longer the hash gets and the harder it becomes.
It may even be possible to design hashes where you CANNOT falsify them both simultaneously because of a certain well-chosen mathematical property of both hashes.
Infinite compression isn't possible, but it doesn't need to be. All you need to do is put every possible data configuration into one of 2^128 boxes. Which is what a hash does. And then finding a "malicious" file in the same box as a "known good" file that isn't complete nonsense, twaddle or invalid, and is malicious in precisely the way you need becomes an almost impossible task.
And the more boxes you categorise them into the harder it becomes.
Not only do you have to find one in the SHA-1 box numbered *whatever*, but it also has to be in the MD5 box numbered *whatever* (where whatever matches those hashes of the innocent data), and has to be craftably malicious too. Technically, for some hashes, it may not even be true that such a file exists that CAN be exploited, from all the possible files,within practical size limits, that happen to hash to those exact boxes.
But I guarantee that faking a file with a certain SHA-1, MD5, CRC32 and even, say, bit-parity is a lot harder than just faking a file with any subset of those requirements. Each one adds more constraints and locks down what's even possible.
It's like saying a virus could slip through the net, but only if it uses JMP instructions, and only an even number of them, and only to prime-numbered memory locations, and only executed on the second Thursday of each week. Sure, not "impossible", but each constraint you add makes a malicious attackers job THAT MUCH HARDER. And if the first stages requires 6000 years of CPU time, and the second another 3000 years of CPU time (because that's easier and we know how to break it better) then you're still vastly increasing the work - and cost - of breaking the hashes in any given time, and extending the life of all the contained algorithms.
(Score: 2) by Wootery on Monday February 27 2017, @01:44PM
There's no common code between MD5 and SHA-1 so if one is a 1-in-2^128 and one is a 1-in-2^160 chance, then getting both is the product of those. You basically have a longer hash. The longer the hash, the hard to falsify data with the same hash.
Getting that double-collision, on a set of useful data (i.e. a malicious payload that matches an innocent file's hashes) is then harder too.
In fact, the more hash algorithms used, the longer the hash gets and the harder it becomes.
I don't think you'd have to concatenate the hash strings: I think it would be enough to do something akin to a XOR, so long as every bit of every 'input hash' is significant.