Anatomy of a change – Google announces it will double its SSL key sizes

Google just announced that its HTTPS web pages will be ditching 1024-bit RSA keys in favour of 2048 bits.

“Pah,” I hear you say. “I have one or two questions about that – three questions, in fact.”

1. How is this newsworthy when many other web properties have already made the switch to 2048 bits? (Kim “Big Fella” Dotcom’s mega.co.nz, for example.)
2. Why switch if 1024 bits is much bigger than the largest RSA key yet known to have been cracked, at 768 bits?
3. Why the fuss about 1024 bits anyway, if just 128 bits is considered more than enough for other encryption algorithms, such as AES?

Let’s start at the end: why thousands of bits of RSA key but only hundreds for AES?

An n-bit symmetric key gives 2ⁿ different possible keys to choose from.

If we assume there is no algorithmic shortcut, we have to try all 2ⁿ of them to be certain of cracking the key.

For obvious reasons, this is called a brute force attack.

A cryptographic attack that requires an equivalent effort to brute-forcing n bits of symmetric cipher key is said to have a security strength of n.

According to the US National Institute of Standards and Technology (NIST), security strengths of 112 and above are considered OK until the end of 2030. Security strengths below 112 are already considered deprecated, a word that means “used with disapproval.”

From the end of 2013, they’ll move from “deprecated” to “disallowed”, at least if you follow NIST’s playbook. So, you have until the end of the year to get all your cryptosystems up to a security strength of 112 or more.

AES uses keys of 128, 192 or 256 bits in length, so AES implicitly meets this condition.

But RSA encryption is a public/private key cipher, meaning you have one key to lock and another key to unlock.

You make the locking key public, so that anyone can encrypt messages and send them to you; you keep the corresponding unlocking key private, rather obviously, so that only you can decrypt them.

Technically and algorithmically, a 128-bit RSA key isn’t anything like a 128-bit AES key. It’s actually a 128-bit number n that is constructed by multiplying together p and q, two randomly-chosen 64-bit prime numbers. To crack such a key requires you to factorise n back into p and q.

This sort of factorisation is computationally complex, but it doesn’t take 2¹²⁸ tries to guarantee a result.

→ Straight off the bat, we know that the largest possible factor of n is √n, and √(2¹²⁸) is 2⁶⁴. So that cuts the maximum number of tries to 2⁶⁴. And neither factor can be even, since then it wouldn’t be a prime factor, which instantly halves the maximum number of tries to 2⁶³. Clearly, the cost of factoring n-bit prime products is well below 2ⁿ.

If fact, an 128-bit RSA key would be absurdly weak by modern standards. In practice, a 1024-bit RSA key is only considered equivalent to an 80-bit symmetric key, and thus has a security strength of 80.

So the fuss about 1024-bit RSA keys is that they too, like AES or similar keys below 112 bits, will become “disallowed” at the end of the year.

Now we come to the second question: why the jump from 1024 to 2048 bit keys?

In 2014, symmetric keys will need to go from a minimum of 80 bits to a minimum of 112 bits; in 2031, they’ll go from 112 to 128 bits. Those are key-size increases of 40% and about 15% respectively.

But in 2014, RSA key sizes are required to grow by 100% (1024 to 2048 bits), and in 2031 by 50% (2048 to 3072 bits). Why the discrepancy in the scale-up?

The reason is that the complexity of a brute-force attack against a symmetric key grows exponentially with the number of key bits, so each additional key bit multiplies the strength by a constant factor of 2.

But each additional key bit in an RSA key multiplies the strength by an ever-decreasing amount, so you need a bigger jump in key size for the same increase in resilience to brute force attack.

And finally, the first question: is this a big deal only because Google has announced it?

It shouldn’t be a big deal for anyone to make an announcement like this. Indeed, it should be expected and unexceptional, as Google itself explains.

In theory, you should easily be able to change website certificates as a matter of routine, not least because they expire and need refreshing anyway. Everyone’s software should automatically adapt.

But SSL certificates don’t usually stand alone, or else anyone could mint a certificate that claimed to be from sophos.com, or microsoft.com, or anywhere they liked.

So SSL certificates are themselves generally signed by other people who vouch for you – firstly by one or more intermediaries (which might be security teams in your own company) and finally by a root certifier. This creates a so-called “chain of trust,” topped out by a root certificate that is automatically trusted by software on your computer, such as your browser or the operating system itself.

The list of root certificates is often rather long – perhaps alarmingly long when you think about the power and authority it conveys.

Of course, root certificates themselves aren’t immune from expiry, or from compromise, or from needing key-size updates. So software that uses its own list of trusted roots must provide a way to update that list, for changes neccesitated both by routine (e.g. expiry) and emergency (e.g. a hack of the certificate authority’s network).

Note that Google will be changing its root certificate size to 2048 bits as well, so that all the certificates in its chain of trust are 2048 bits.

So Google is warning all of us, in good time, in case any of us have software (or, more challengingly, firmware burned into devices like games consoles, phones, and printers) that rely on hard-wired lists of root certificates.

If you have software that relies inflexibly on hard-wired SSL trust lists, take this as a good time to change the way your code works.

As Google points out, firmly but fairly, in its FAQ:

The only way to do this correctly is to build software that understands that Roots can change, and can adapt to that.

Google does have some self-interest here, as it doesn’t want potential customers being put off by certificate warnings as as result of this change. On the other hand, those certificate warnings shouldn’t really happen, so Google is acting in the interest of the whole ecosystem by highlighting these issues.

The takeaways?

• Build SSL certificate flexibility into your software.
• Switch to 2048-bit RSA keys before the end of 2013.

For the greater good of all!