Previously, we advised that the SSL industry must move to the SHA-2 hashing algorithm for certificate signatures. We thought it would be helpful to provide the reasoning behind the position.
In the context of SSL, the purpose of a hashing algorithm is to reduce a message (e.g., a certificate) to a reasonable size for use with a digital signature algorithm. The hash value, or message digest, is then signed to allow an end-user to validate the certificate and ensure it was issued by a trusted certification authority (CA). In the past, we used MD5 for hashing; we are now primarily using SHA-1 while beginning the transition to SHA-2, and have SHA-3 available for the future.
Hash attacks are described as follows, in increasing order of difficulty for an attacker:
- Collision – A collision attack occurs when it is possible to find two different messages that hash to the same value. A collision attack against a CA happens at the time of certificate issuance. In a past attack against MD5, the attacker was able to produce a pair of colliding messages, one of which represented the contents of a benign end-entity certificate, and the other of which formed the contents of a malicious CA certificate. Once the end-entity certificate was signed by the CA, the attacker reused the digital signature to produce a fraudulent CA certificate. The attacker then used their CA certificate to issue fraudulent end-entity certificates for any domain. Collision attacks can be mitigated by putting entropy into the certificate, which makes it difficult for the attacker to guess the exact content of the certificate that will be signed by the CA. Entropy is typically found in the certificate serial number or in the validity periods. SHA-1 is known to have weaknesses in collision resistance.
- Second-preimage – In a second-preimage attack, a second message can be found that hashes to the same value as a given message. This allows the attacker to create fraudulent certificates at any time, not just at the time of certificate issuance. SHA-1 is currently resistant to second-preimage attacks.
- Preimage – A preimage attack is against the one-way property of a hash function. In a preimage attack, a message can be determined that hashes to a given value. This could allow a password attack, where the attacker can determine a password based on the hash of the password found in a database. SHA-1 is currently resistant to preimage attacks.
Attacks against hash functions are measured against the length of time required to perform a brute-force attack, in which messages are selected at random and hashed until a collision or preimage is found. Thanks to the birthday paradox, the time required to find a collision by brute force is approximately 2ⁿᐟ², where n is the bit length of the hash. To find a preimage or second-preimage by brute force, approximately 2n messages must be hashed. Thus, a hash function is weakened if a collision can be found in less time than that needed to compute 2ⁿᐟ² hashes, or if a preimage or second-preimage can be found in less time than would be needed to compute 2n hashes. For common hashes the bit length is: MD5 (128 bits), SHA-1 (160 bits) and SHA-2 (224, 256, 384, or 512 bits).
The time required to perform a brute-force attack keeps getting shorter due to increases in available computing power (see Moore’s Law). As such, increases in hash function lengths are necessary to maintain an acceptable margin of security. In the past, an attack threshold of 2⁶⁴ operations was considered acceptable for some uses, but NIST recommendations now set the bar at 2⁸⁰, and this will soon move up to 2¹¹².
Using the formula 2ⁿᐟ², we can see that a brute-force attack against SHA-1 would require 2⁸⁰ computations. Unfortunately, security researchers have discovered an attack strategy that requires only 2⁶¹ computations. This would make the time required to perform an attack below current standards. In fact, Bruce Schneier has estimated that the cost of a performing SHA-1 collision attack will be within the range of organized crime by 2018 and for a university project by 2021.
The bottom line is SHA-1’s collision resistance is weak and the cost of an attack is dropping; as such, SHA-1 must be replaced with SHA-2.
Certificate owners are encouraged to test and deploy certificates signed with SHA-2. If your application does not support SHA-2, please inform your product vendor and your CA.
