Why some cryptographic keys are much smaller than others

If you connect to CloudFlare's web site using HTTPS the connection will be secured using one of the many encryption schemes supported by SSL/TLS. When I connect using Chrome I get an RC4_128 connection (with a 128-bit key) which used the ECDHE_RSA key exchange mechanism (with a 2,048-bit key) to set the connection up.

If you're not familiar with the cryptographic protocols involved you might be wondering why one part uses a 128-bit key and another a 2,048-bit key. And you'd be forgiven for wondering why a large key wasn't used throughout and whether a 128-bit key is weaker than a 2,048-bit key. This blog post will explain why a 128-bit symmetric key is, in fact, a bit more secure than a 2,048-bit asymmetric key; you have to look at both the type of encryption being used (symmetric or asymmetric) and the key length to understand the strength of the encryption.

My connection above used a symmetric cipher (RC4_128) with a 128-bitkey and an asymmetric cipher (ECDHE_RSA) with a 2,048-bit key.

You might also have seen other key lengths in use. For example, when I connect to the British Government portal gov.uk I get a TLS connection that uses AES_256_CBC (with a 256-bit key) set up using RSA with a 2,048-bit key. It's not uncommon to see RSA with a 1,024-bit key as well.

To understand these key lengths it's necessary to understand a little about the actual encryption schemes they are used with.

The RC4_128 and AES_256_CBC schemes mentioned above are symmetric cryptographic schemes. Symmetric simply means that the same key is used to encipher and decipher the encrypted web traffic. In one case, a 128-bit key is used, in another a 256-bit key.

Symmetric cryptography is the oldest form there is. When children use a Caesar Cipher (shifting each letter in the alphabet some fixed number of places) they are performing symmetric cryptography. In that case, the key is the number of places to shift letters and there are 26 possible keys (which is roughly like saying the Caesar Cipher has a roughly 5-bit key).

Here's a Caesar Shift with a key of 7 (each letter is moved up in the alphabet 7 places):

ISTHE BESTT HATCO RPORA LBOBB YSHAF TOECA NDOON SHORT NOTIC E PZAOL ILZAA OHAJV YWVYH SIVII FZOHM AVLJH UKVVU ZOVYA UVAPJ L

There are lots of ways to break the Caesar Cipher, but one way is to try out all 26 possible keys. That's really not that hard since there are only 26 possible solutions:

PZAOL ILZAA OHAJV YWVYH SIVII FZOHM AVLJH UKVVU ZOVYA UVAPJ L
----- ----- ----- ----- ----- ----- ----- ----- ----- ----- -

0: PZAOL ILZAA OHAJV YWVYH SIVII FZOHM AVLJH UKVVU ZOVYA UVAPJ L 1: OYZNK HKYZZ NGZIU XVUXG RHUHH EYNGL ZUKIG TJUUT YNUXZ TUZOI K 2: NXYMJ GJXYY MFYHT WUTWF QGTGG DXMFK YTJHF SITTS XMTWY STYNH J 3: MWXLI FIWXX LEXGS VTSVE PFSFF CWLEJ XSIGE RHSSR WLSVX RSXMG I 4: LVWKH EHVWW KDWFR USRUD OEREE BVKDI WRHFD QGRRQ VKRUW QRWLF H 5: KUVJG DGUVV JCVEQ TRQTC NDQDD AUJCH VQGEC PFQQP UJQTV PQVKE G 6: JTUIF CFTUU IBUDP SQPSB MCPCC ZTIBG UPFDB OEPPO TIPSU OPUJD F 7: ISTHE BESTT HATCO RPORA LBOBB YSHAF TOECA NDOON SHORT NOTIC E 8: HRSGD ADRSS GZSBN QONQZ KANAA XRGZE SNDBZ MCNNM RGNQS MNSHB D 9: GQRFC ZCQRR FYRAM PNMPY JZMZZ WQFYD RMCAY LBMML QFMPR LMRGA C 10: FPQEB YBPQQ EXQZL OMLOX IYLYY VPEXC QLBZX KALLK PELOQ KLQFZ B 11: EOPDA XAOPP DWPYK NLKNW HXKXX UODWB PKAYW JZKKJ ODKNP JKPEY A 12: DNOCZ WZNOO CVOXJ MKJMV GWJWW TNCVA OJZXV IYJJI NCJMO IJODX Z 13: CMNBY VYMNN BUNWI LJILU FVIVV SMBUZ NIYWU HXIIH MBILN HINCW Y 14: BLMAX UXLMM ATMVH KIHKT EUHUU RLATY MHXVT GWHHG LAHKM GHMBV X 15: AKLZW TWKLL ZSLUG JHGJS DTGTT QKZSX LGWUS FVGGF KZGJL FGLAU W 16: ZJKYV SVJKK YRKTF IGFIR CSFSS PJYRW KFVTR EUFFE JYFIK EFKZT V 17: YIJXU RUIJJ XQJSE HFEHQ BRERR OIXQV JEUSQ DTEED IXEHJ DEJYS U 18: XHIWT QTHII WPIRD GEDGP AQDQQ NHWPU IDTRP CSDDC HWDGI CDIXR T 19: WGHVS PSGHH VOHQC FDCFO ZPCPP MGVOT HCSQO BRCCB GVCFH BCHWQ S 20: VFGUR ORFGG UNGPB ECBEN YOBOO LFUNS GBRPN AQBBA FUBEG ABGVP R 21: UEFTQ NQEFF TMFOA DBADM XNANN KETMR FAQOM ZPAAZ ETADF ZAFUO Q 22: TDESP MPDEE SLENZ CAZCL WMZMM JDSLQ EZPNL YOZZY DSZCE YZETN P 23: SCDRO LOCDD RKDMY BZYBK VLYLL ICRKP DYOMK XNYYX CRYBD XYDSM O 24: RBCQN KNBCC QJCLX AYXAJ UKXKK HBQJO CXNLJ WMXXW BQXAC WXCRL N 25: QABPM JMABB PIBKW ZXWZI TJWJJ GAPIN BWMKI VLWWV APWZB VWBQK M

The goal of modern symmetric cryptography is to make this sort of'trying out all the possible keys' the only approach to breaking a symmetric cipher. Algorithms like RC4 and AES scramble data based on a key. The key itself is, ideally, randomly chosen from the set of all possible keys.

On a side note, there are now serious problems with RC4 and as better replacements come along (such as ciphersuites based on AES) CloudFlare will update the ciphersuites it uses to provide the best level of protection.

That said the basic idea is that the only way to break into a connection secured with a symmetric cipher is to try out all the keys. Which brings us to 128-bit and 256-bit keys.

A 128-bit key means there are 340,282,366,920,938,463,463,374,607,431,768,211,456 possible keys to try. A 256-bit key has the square of that many keys to try: a hugenumber.

To put that in context imagine trying to test all the keys for a 128-bit AES encryption using the special AES instructions added to the latest Intel microprocessors. These instructions are designed to be very fast and according to Intel's own data decrypting a block of AES encrypted data would take 5.6 cycles on Intel i7 Processor with 4 cores.

Put another way, that processor could try out one key on one block of data in about 1.7 nanoseconds. At that speed it would take it about 1.3 * 10^12 * the age of the universe to check all the keys (you'd probably only have to check half before finding the right one so divide that incredibly long time by two).

Since personal computers became available roughly 1 billion of them have been sold. Imagine that they all had the same top-of-the-line processor and were used to attack a 128-bit key. You'd manage to get the time down to 660 * the age of the universe.

Image (c) BBC TV

So, breaking 128-bit keys by brute force just isn't practical. And breaking 256-bit is even less possible. So, for symmetric ciphers, keys of these lengths make sense.

But that's not the case for asymmetric cryptography.

Asymmetric cryptography works by having two different keys, one for encryption and one for decryption. It's also often called 'public key cryptography' because it's possible to make one key public (allowing someone to encrypt a message) while keeping the other private (only the holder of the private key can decrypt the message encrypted with its related public key).

In order to have these special properties the public and private keys are related by some mathematical process. Aside: in the symmetric examples there's only one key and it's just any value of the right number of bits. This randomness of a symmetric key means it can be relatively short as we saw.

For example, in the popular RSA scheme used with SSL/TLS the public and private keys consist in part of the product of two large prime numbers. Making an RSA key starts with picking two random prime numbers. The security of RSA relies (in part) on the fact that it's easy to choose two random prime numbers, but it's very hard to discover what they are when just given the product of them.

Suppose there are two prime numbers picked at random called p0 and p1. Part of the RSA public (and private) key is called the modulus and it is just p0*p1. If an attacker can decompose (or factor) the modulus into p0 and p1 they can break RSA because they can work out the private key. Mathematicians believe that it is very hard to factor a product of two primes and the security of web transactions relies, in part, on that belief.

Typical RSA key sizes are 1,024 or 2,048 or 4,096 bits. That number is the number of bits in the modulus. For each there will be a pair of primes of roughly 512 bits or 1,024 bits or 2,048 bits depending on the key size picked. Those primes are chosen by some random process (highlighting once again the importance of random number generators).

But we still haven't answered the question of why these key sizes are so large. Just as in the symmetric key case, attacks on say 2,048-bit RSA are based on trying out all keys of a certain size, but unlike the symmetric key scheme not every 2,048-bit number is an RSA key (because it has to be the product of two primes).

So, although the key size is larger there are actually fewer possible RSA keys for any given number of bits that there are for the same symmetric key size. That's because there are only so many prime numbers of that size and below. The RSA scheme can only use pairs of prime numbers, whereas the symmetric schemes can use any number at all of the same size.

This diagram (called an Ulam Spiral) shows the numbers from 1 to 40,000 as black or white dots. The black dots are the primes

Image from Wikipedia

If you used a 256-bit RSA key (roughly consisting of two 128-bit prime numbers multiplied together) you'd quickly find that your encryption had been broken by someone using a fast home PC. There are only so many 128-bit prime numbers and there are fast ways of attacking the factorization problem (such as the General Number Field Sieve that actually make breaking RSA keys a little easier than trying out every single key).

Any time there's a pattern in a cryptographic key it represents a chink in the crytography's armor. For example, in a perfect world, people would pick completely random passwords. Because they don't there are patterns in the passwords and they can be guessed or broken without trying out every possible password.

RSA keys have a distinctive pattern: they are the product of two prime numbers. That provides the chink; today that chink is best exploited by the General Number Field Sieve. In the symmetric key case there are no such patterns: the keys are just large randomly-chosen numbers. (Of course, if you don't pick your symmetric key randomly you might actually be helping an attacker find a way to break your encrypted messages.)

A few years ago the 512-bit RSA key used to sign software for TIcalculators was broken by an individual using a PC that ran for 73 days using the open source msieve and ggnfs prorgrams.

So, asymmetric keys have to be much larger than symmetric keys because there are less of them for a given number of bits, and because there are patterns within the keys themselves.

The ECRYPT II recommendations on key length say that a 128-bit symmetric key provides the same strength of protection as a 3,248-bit asymmetric key. And that those key lengths provide long term protection of data encrypted with them.

The length of time a key is good for is also important. Over time computers get faster and techniques for breaking encryption schemes (particuarly techniques for breaking asymmetric encryption) get better. That 512-bit key used for TI calculators probably looked pretty safe when it was first chosen. And in 1999 a key of that length took a supercomputer to break.

We keep an eye on these reports when choosing ciphers and key lengths to secure our and our customers' communications.

Because of the importance of protecting our customers' communications CloudFlare has also opted to roll out forward secrecy for our SSL/TLS connections. That means that the public/private keys used for connections are generated freshly each time. That prevents bulk attacks where a single public/private key (such as the one used in simple RSA-based certificates) is broken revealing all of the symmetric keys used to secure HTTPS for a web site.

Returning to the HTTPS connection I made to CloudFlare at the start, the key negotiation was done using ECDHE_RSA. That's the ephemeral version of the Diffie-Hellman key exchange mechanism that uses elliptic curves and RSA for authentication. That's quite amouthful. It breaks down like this:

1. The public/private key pair used to this connection was ephemeral: it was only created for this connection. That's what gives 'forward secrecy'.

2. The actual public-key encryption scheme used was Elliptic Curve Diffie-Hellman. Elliptic Curve Cryptography uses a different branch of mathematics than RSA. Looking at the ECRYPT II report shows that a 128-bit symmetric key is as strong as a 3,248-bit asymmetric key; to get the equivalent strength from an Elliptic Curve Cryptographic scheme requires a key with 256-bits.

3. So, Google Chrome set up an ephemeral 256-bit Elliptic Curve Diffie Hellman public/private key pair and used it to agree on a 128-bit symmetric key for the rest of the communication.

4. To prove that the web site really was www.cloudflare.com the 2,048-bit RSA key was used along with the web site's certificate.

So, three different key lengths were used: 128-bit (with RC4), 256-bit (with ECDHE) and 2,048-bit (with RSA). All three key lengths provide similar levels of security.