Malicious SHA-1

Malicious SHA-1: systems using “custom” versions of SHA-1 may include backdoors exploitable by the designers. Such custom versions of cryptographic standards are typically found in proprietary systems as a way to personalize the cryptography for a given customer, while retaining the security guarantees of the original algorithm.

SHA-1

SHA-1 is a NIST standard designed by NSA in 1995 and used everywhere: in TLS, SSH, IPsec, etc. as part of encryption, signature, message authentication, or key derivation schemes.

SHA-1 produces 160-bit hash values. Therefore a generic attack requires approximately 2⁸⁰ evaluations of SHA-1 to find a collision, as per the birthday paradox. Such a “birthday attack” works on any reasonable hash function regardless of its strength. Cryptographers thus say that a hash function is “broken” if one finds an attack substantially faster than the birthday attack.

According to this definition, SHA-1 is broken, since public research described collision attacks more than a thousand times faster than the birthday attack. However,

• the actual complexity of collision attacks on SHA-1 is unclear, but seems to be greater than 2⁶⁰
• an actual collision for the original SHA-1 has yet to be published (found?)

The known collision attacks are differential attacks. These introduce differences in the first message block—SHA-1 processes message by compressing iteratively blocks of 512 bits—and control the propagation of the differences thereby injected in SHA-1’s internal state in order to “correct” the disturbances thanks to a second message block and thus finally obtain a collision, thanks to an internal state now free of any difference.

Backdooring

To construct malicious SHA-1 versions, we had to find

1. a differential characteristic of high enough probability (that is, a pattern of differences propagation that leads to a collision)
2. a method to efficiently find messages and constants following this characteristic

To find a differential characteristic, we build on previous research and sought a characteristic by linearization that minimizes the cost of construction a malicious version of SHA-1.