by Marc Stevens (CWI)
An international team of cryptanalysts from CWI, Inria and NTU Singapore broke the core of the SHA-1 internet security standard in October 2015. They projected that breaking SHA-1 is much cheaper and can be achieved earlier than international security experts expected, which gained a lot of attention in the media. The team urged the industry to retract the standard earlier than planned. Their results ensured that an industry ballot to extend the issuance of SHA-1 certificates was withdrawn.
SHA-1 is a cryptographic algorithm to securely compute message fingerprints, which was designed by the NSA in 1995. It became an industry standard that is commonly used for digital signatures, which secure credit card transactions, electronic banking and software distribution. It is fundamental to internet security - for HTTPS (SSL/TLS) security, for example.
Google Chrome users receive a warning when a certificate is signed with a SHA-1 based signature issued after 2015.
Picture: Marc Stevens.
SHA-1 is a ‘hash function’. It generates from input, such as text or code, a short string of letters and numbers (a hash), which serves as a digital fingerprint for that message. Even a small change in the input, such as changing one letter in a message, will generate a very different and unpredictable output. When two different messages lead to the same hash, this is called a collision. Such collisions allow forgeries of digital signatures – a catastrophe for banking transactions, secure e-mails, and software downloads.
The industry standard was already theoretically broken in 2005 [1] but for a long time it remained difficult to make a practical attack. However, the researchers combined advanced mathematical methods by using graphics cards for their computations to speed up the computations and make the attack much more cost effective.
In September, a joint effort by CWI, Inria and NTU Singapore – also known as ‘the SHAppening’ [L2] – led to a successful ‘freestart collision attack’ on SHA-1, breaking the full inner layer of SHA-1. In early autumn, 2015, the researchers then estimated that it would cost only $US75,000 - 120,000 to rent Amazon EC2 cloud over a few months and conduct a full SHA-1 collision [2]. This indicated that collisions were already within the resources of criminal syndicates, almost two years earlier than previously expected [3], and one year before SHA-1 would be marked as unsafe in modern internet browsers in January 2017, in favour of its secure successor SHA-2.
The team therefore recommended that SHA-1 based signatures should be marked as unsafe much sooner. In particular, they strongly urged against a proposal to extend issuance of SHA-1 certificates with another year in the CA/Browser Forum, for which the voting was scheduled briefly after the announcement. The proposed extension was not just because some companies were not ready yet, but also because millions of users with old software, mostly from developing countries, would not be able to access some websites anymore. However, owing to the demonstrated insecurity, the proposal for extension was withdrawn by Symantec before the meeting. Also the upcoming TLS 1.3 standard deprecated SHA-1 as a consequence of this team’s results. Mozilla, Google and Microsoft also adopted their planning regarding SHA-1.
“Although this is not yet a full attack, the current attack is not the usual minor dent in a security algorithm, making it more vulnerable in the distant future,” says Ronald Cramer, head of CWI’s Cryptology group [L1]. The research team adds: “As SHA-1 underpins more than 28 percent of existing digital certificates, the results of real-world forgeries could be catastrophic. We hope the industry has learned from the events with SHA-1’s predecessor MD5 and in this case will retract SHA-1 before examples of signature forgeries appear in the near future.”
The research team consisted of Marc Stevens (CWI), Pierre Karpman (Inria and NTU Singapore) and Thomas Peyrin (NTU Singapore). The research was partially funded by the Netherlands Organisation for Scientific Research Veni Grant 2014, the Direction Générale de l'Armement, and the Singapore National Research Foundation Fellowships 2012. The results have been presented at the 35th Annual IACR EUROCRYPT 2016 conference.
This text was written by Annette Kik
Links:
[L1] https://www.cwi.nl/research-groups/Cryptology
[L2] https://sites.google.com/site/itstheshappening/
References:
[1] X. Wang, Y. L. Yin, H. Yu: “Finding Collisions in the Full SHA-1”, CRYPTO 2005, LNCS, vol. 3621, pp. 17-36, Springer, 2005. http://link.springer.com/chapter/10.1007%2F11535218_2
[2] M. Stevens, P. Karpman, T. Peyrin: “Freestart collision for full SHA-1”, EUROCRYPT 2016, LNCS, vol. 9665, pp. 459-483, Springer, 2016, http://link.springer.com/chapter/10.1007%2F978-3-662-49890-3_18
[3] M. Stevens: “New collision attacks on SHA-1 based on optimal joint local-collision analysis”, EUROCRYPT 2013, LNCS, vol. 7881, pp. 245-261, Springer, 2013. http://link.springer.com/chapter/10.1007%2F978-3-642-38348-9_15
Please contact:
Marc Stevens, CWI, The Netherlands
