A SHA-1 freestart collision has occurred


Ars article: http://arstechnica.com/security/2015/10/sha1-crypto-algorithm-securing-internet-could-break-by-years-end/

With the IV 50 6b 01 78 ff 6d 18 90 20 22 91 fd 3a de 38 71 b2 c6 65 ea, this message:

9d 44 38 28 a5 ea 3d f0 86 ea a0 fa 77 83 a7 36 33 24 48 4d af 70 2a aa a3 da b6 79 d8 a6 9e 2d 54 38 20 ed a7 ff fb 52 d3 ff 49 3f c3 ff 55 1e fb ff d9 7f 55 fe ee f2 08 5a f3 12 08 86 88 a9

has a SHA-1 hash of f0 20 48 6f 07 1b f1 10 53 54 7a 86 f4 a7 15 3b 3c 95 0f 4b.

With the IV 50 6b 01 78 ff 6d 18 91 a0 22 91 fd 3a de 38 71 b2 c6 65 ea, this message:

3f 44 38 38 81 ea 3d ec a0 ea a0 ee 51 83 a7 2c 33 24 48 5d ab 70 2a b6 6f da b6 6d d4 a6 9e 2f 94 38 20 fd 13 ff fb 4e ef ff 49 3b 7f ff 55 04 db ff d9 6f 71 fe ee ee e4 5a f3 06 04 86 88 ab

has a SHA-1 hash of f0 20 48 6f 07 1b f1 10 53 54 7a 86 f4 a7 15 3b 3c 95 0f 4b.


The researchers estimate that computing a real collision - one without different IVs - would cost between $75,000 and $120,000 on Amazon EC2 over a few months. This is within the resources of organized crime today.


If you are having trouble recognizing how this is a problem, check your browser’s CA store for a subordinate certificate authority from “MD5 Collisions, Inc.” issued by Equifax.

10 Likes

Hi, good information. With this there can be two assumptions, if there is an SHA1 Certificate in the chain
then the chain can be compromised within few months or only be “worth” 75.000$ of insurance.
So two month at maximum is unacceptable and event 75.000$ should be feasible for phishing .

CONCLUSION: SHA1 is no longer acceptable at any chain position of the certificate trust chain.

Note that the “MD5 collisions inc” attack required a “distinct chosen prefix” collision attack which was substantially more expensive than a plain collision attack. It also required bad CA practices.

As far as I know, the complexity of SHA-1 collisions is still around 260. For details see Marc Stevens’ HashClash. He is one of the researchers who found collisions on MD5, and he predicted the Flame attack by writing the paper on the prefix collision attack on the compression function (years in advance).

Nothing has really changed as far as complexity goes. 260 is well within the reach of many adversaries (and not just organized crime or government). To put it in perspective, RSA-1024 moduli, with a complexity of 280, is outside the reach of most adversaries. Browsers and other user agents sunsetted RSA-1024 years ago.

The thing that apparently changed is the rig they used to find the collision. They used low cost, commodity playstations or GPUs. So the cost appears to have dropped, and not the complexity of the attack.

For security i think not the complexity is the most relevant part but the cost.
For that reason if you want strong security it does not stay with algorithm but
you also need to take care about physical security so that an sneak in is not
cheaper/easier than attack on the math.
The problem with certificate is that through serial, embedded image and other
information you have sufficient “random” for the attack on one side. And with
more than one million certificates around > 2^20 the chance get higher that you
find an collision for some certificates.

And the fun is: Any signature of a signing CA which is still operational/valid could be used, not just from the list of currently valid certificates. So a SHA-1 certificate which was issued 2006 for a year or two by a CA that is still valid, could still be attacked.

Edit: However, an attacker has to focus on a specific Signing CA and its signed SHA’s as he has to fill that CA’s CN/OU/O/C values into the ‘Issuer’ field prior to attempting the collision. So, in the end, the less certificates a CA has issued, the smaller is the attack vector. This favors higher-class CAs like EVs.

Edit 2: Of course, it should be more the Certificate Key Authority Identifier field that has to match the later Signing CA, but you get the idea.

Even more Critical are OLD SHA/MD5 CA certifikate.
They could be used to sign an certificate valid for time stamping.
And then create some signed objectes that are trusted.