3 min read

The SHA-1 Attack Further Emphasizes the Need for Crypto-Agility 

Picture of Edlyn Teske Edlyn Teske : 24. January 2020

CSG Crypto-Agility SHA-1 Attack
The SHA-1 Attack Further Emphasizes the Need for Crypto-Agility

The first practical chosen-prefix collision attack on SHA-1 was announced in January 2020 by researchers Gaëtan Leurent and Thomas Peyrin: “SHA-1 is a Shambles”.  

SHA-1 is a cryptographic hash function, mapping bitstrings of arbitrary finite length to strings of fixed length. Cryptographic hash functions are used for example in digital signatures, to improve efficiency and preserve data integrity.

One of the most significant applications of digital signatures is the certification of public keys in large networks.

SHA-1 collision attacks

A hash function H is a many-to-one function, and thus the existence of collisions, i.e., pairs of distinct inputs M and M’ with identical outputs H(M)= H(M’), is unavoidable.

In a cryptographic hash function, collisions should in theory be not significantly faster to find than in a brute force attack. Such a brute-force attack is based on the birthday paradox, and it would require expected 2^80 computations to produce a SHA-1 collision.

Of course, collisions should also be computationally infeasible to find in practice. SHA-1 has been broken in 2005 by a theoretical collision attack. This attack, by Wang, requires expected 2^69 calls to SHA-1’s compression function, which to this date is out of reach. 

In 2017, a practical collision attack on SHA-1 was reported, and the first known instance of a SHA-1 collision was provided. This computation required 2^64.7 operations (2^63.1 compression function calls), 6500 CPU years and 100 GPU years. Still, such a collision attack is hard to exploit in applications since the attacker has little control over M and M’.  

Chosen-prefix collisions 

More applicable is the so-called chosen-prefix collision attack. The problem of finding a chosen-prefix (CP) collision is: given two arbitrary message prefixes P and P’, compute two messages M and M’ such that H(P||M)= H(P’||M’), where || denotes concatenation. 

The prefixes may contain identifying information, for example, and thus a CP collision can be exploited for an impersonation attack in a public-key infrastructure:

An honest user Alice would create her public key kA and then have a certification authority (CA) sign H(ID-Alice|| kA), that is, the CA’s certificate assures that key kA is indeed Alice’s authentic key. Instead, a malicious user Bob may create kA and kB such that H(ID-Alice ||kA) = H(ID-Bob||kB), have the CA sign H(ID-Bob||kB), and then copy this CA-issued certificate to H(ID-Alice||kA). Now Bob can go on and sign subsequent documents in Alice’s name. Of course, this is highly simplified and more tweaks are needed to apply this idea to real-world protocols. 

In 2016, certain CP collisions in the underlying hash function were shown to break handshake protocols such as TLS, IKE, and SSH. These attacks (AKA the SLOTH attacks) were explicitly carried out against the hash function MD5, but they would have required 2^77 operations in the case of SHA-1, which is still considered impractical. 

Now, Leurent and Peyrin have implemented their CP collision attack on SHA-1 from Eurocrypt 2019 and created a specific instance of a CP collision for SHA-1, with a direct application for PGP/GnuPG security. Specifically, they chose the prefixes P and P’ to correspond to headers of two PGP identity certificates with different RSA keys, and created two public keys such that the corresponding PGP identify certificates have the same SHA-1 hash value.

This allows the attacker to impersonate its victim in the PGP Web of Trust. Due to the nature of the CP collision and the OpenPGP format, this CP collision can be used to target not just one but many victims.

Finding this CP collision took 2^63.4 computations and 107 GPU years (GTX 1060), at the GPU rental cost of $45K.

Implications

SHA-1 was designed in 1995 and was a NIST standard until formally deprecated in 2011. Commercial products that use cryptography from reputable vendors are likely to have phased out SHA-1 by now - but you might like to check! Legacy applications still may use or accept SHA-1 in certificates and signatures. Even if an application doesn’t offer SHA-1 hashing externally, an attacker could force it to downgrade if it supports SHA-1 internally. 

The work by Laurent and Peyrin is a timely reminder to audit the cryptography used within your organisation and check for SHA-1 (and other not-recommended configurations such as 1024-bit RSA). If you do find examples of SHA-1, then the applications have to be upgraded, to SHA-256 or SHA-3 etc. While this may be a disruptive exercise it could be an opportunity to future-proof your use of cryptography, by building a system where it is easy to switch between cryptographic algorithms.

One can never be complacent about the life-time of an algorithm – any cryptographic algorithm may have to be replaced over time. The increasing affordability of (classical) computing power makes theoretical attacks now practical. The rise of quantum computing will require quantum-resistant cryptographic algorithms. For protection against both incremental and new attacks on algorithms, organisations are well advised to be ‘crypto-agile’:

See our recommendations on how to architect a resilient infrastructure.

Read White Paper

References