The SHAppening: freestart collisions for SHA-1




This website contains latest news and background information regarding the SHA-1 freestart collision work from Marc Stevens (CWI, the Netherlands), Pierre Karpman (Inria, France and NTU Singapore) and Thomas Peyrin (NTU Singapore). 

You can find the latest version of our technical article here (currently under submission) and the corresponding press release here.

A freestart collision example for SHA-1

The following two input IV/message pairs give the same output value after applying the SHA-1 compression function:

   Input 1
 IV1 50 6b 01 78 ff 6d 18 90 20 22 91 fd 3a de 38 71 b2 c6 65 ea
 M1 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
 SHA1_compression_function (IV1,M1) f0 20 48 6f 07 1b f1 10 53 54 7a 86 f4 a7 15 3b 3c 95 0f 4b


   Input 2
 IV2 50 6b 01 78 ff 6d 18 91 a0 22 91 fd 3a de 38 71 b2 c6 65 ea
 M2 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
 SHA1_compression_function (IV2,M2) f0 20 48 6f 07 1b f1 10 53 54 7a 86 f4 a7 15 3b 3c 95 0f 4b

You can verify this freestart collision by yourself using this tester.

Kraken, our cheap GPU cluster

We have computed the SHA-1 freestart collision on Kraken, our 64-GPU cluster. More precisely Kraken is composed of 16 nodes, each node being made of simple, cheap and widely available hardware: 4 GTX-970 GPUs, 1 Haswell i5-4460 processor and 16GB of RAM.
 


Our recommendations

We recommend that SHA-1 based signatures should be marked as unsafe much sooner than prescribed by current international policy. Even though freestart collisions do not directly lead to actual collisions for SHA-1, in our case, the experimental data we obtained in the process enable significantly more accurate projections on the real-world cost of actual collisions for SHA-1, compared to previous projections. Concretely, we estimate the SHA-1 collision cost today (i.e., Fall 2015) between 75K$ and 120K$ renting Amazon EC2 cloud computing over a few months. By contrast, security expert Bruce Schneier previously projected (based on calculations from Jesse Walker) the SHA-1 collision cost to be ~173K$ by 2018. Note that he deems this to be within the resources of a criminal syndicate. Large corporations and governments may possess even greater resources and may not require Amazon EC2. Microsoft, Google and Mozilla have all announced that their respective browsers will stop accepting SHA-1 based SSL certificates by 2017 (and that SHA-1-based certificates should not be issued after 2015). In conclusion, our estimates imply SHA-1 collisions to be now (Fall 2015) within the resources of criminal syndicates, two years earlier than previously expected and one year before SHA-1 will be marked as unsafe in modern Internet browsers. This motivates our recommendations for industry standard SHA-1 to be retracted as soon as possible. With our new cost projections in mind, we strongly and urgently recommend against a recent proposal to extend the issuance of SHA-1 certificates with a year in the CAB/forum (discussion closes October 9 2015, vote closes October 16).

Background information on SHA-1

Here follows an overview of background information on the SHA-1 hash function industry standard.


On the recent proposal to extend issuance of SHA-1 certificates

On SHA-1 migration

On the cost of SHA-1 collisions

On SHA-1 freestart collisions and graphics cards

On MD5-based signature forgeries and the 2012 Flame malware

On MD5-based signature forgeries and the 2008 academic HTTPS break

Acknowledgements

Marc Stevens is supported by the Netherlands Organization for Scientific Research Veni Grant 2014.
Pierre Karpman and Thomas Peyrin are supported by the Singapore National Research Foundation Fellowship 2012 (NRF-NRFF2012-06).
Pierre Karpman is also supported by the Direction Générale de l'Armement.