Why did browsers deprecate 1024-bit RSA, but retain SHA-1?

Question

I was reading Mozilla's security blog Phasing out Certificates with 1024-bit RSA Keys. Effectively, some browsers are deprecating 1024-bit RSA for CAs and Subordinate CAs because the certificate must withstand attack for 10 to 30 years.

As far as I know, 1024-bit RSA provides about 80-bits of security due to advances in integer factorization and the number field sieve. 80-bits of security is out of reach of most attackers.

SHA-1 provides about 61-bits of security due to Marc Steven's HashClash. 61-bits of security is well within the reach of many attackers, especially when compute time is so inexpensive on Amazon's EC2 or OpenStack's Nova.

Two real life attacks on crypto I am aware are (1) Texas Instruments signing key, which factored a 512-bit key; and (2) Flame, which exploited collisions on weak/wounded signing algorithms. From TI, we know the attacker will attempt to factor a key with 60 or so bits of security. And from Flame we know the attacker will attack the digest function when its effective security is around 60 bits or so.

Why did browsers deprecate CAs and Subordinate CAs with 1024-bit RSA, but retain SHA-1?

Answer 1

Breaking a CA SHA1 signature would not get you anywhere: you could just recreate a public certificate with the same signature as a legitimate one, but the public key of the legitimate certificate would still be used to verify certificates, because it is stored in browsers.

To successfully forge a certificate you need to break one of:

• an RSA private key of the chain
• a checksum of an intermediate authority
• the checksum of the SSL/TLS certificate

The checksums do not necessarily have to use the same algorithm of the root CA: a root CA hashed with SHA1 may be used to sign TLS certificate hashed with SHA256.

Answer 2

Since cipher suites with forward secrecy aren't universally used the RSA key on an end entity certificate needs to remain secure for as long as the content of the communications needs to remain secure. The hash function on the other hand only needs to be secure at the time the certificate is validated.

Furthermore for a hash function we must distinguish between security against different types of attack (unlike with RSA where it's pretty much either factored or not factored, there is no in-between). The easiest attack to pull off against a hash function is a simple collision attack but it's also the least useful. The most useful attack against a hash function would be a preimage attack with flexible prefix and suffix but noone has achived that even for MD5. In between are collision attacks with distinct chosen prefix and common chosen suffix. These can be combined with a CA that has poor issuance policies to construct a bogus certificate but it's certainly not an easy task.

Nevertheless for intermediate and end entity certificates the major browsers are pushing a phaseout of SHA1. For root certificates the digest algorithm is basically irrelevent. Since the client already has the root cert in it's store, it doesn't need to get it from an untrusted source.