Key Length and Public Key Commands

32,767. For almost two years, that was how many different keys of a given type and size a computer running Debian Linux could make, where there should have been more than anyone could ever count. In May 2006 a Debian maintainer, trying to quiet the warnings from a tool that checks programs for memory mistakes, commented out a couple of lines in Debian's copy of OpenSSL, the free encryption program whose code many other programs use to make keys. One of those lines fed fresh randomness into every key OpenSSL made. It sat in a file called md_rand.c, and it read:

MD_Update(&m,buf,j);

The changed package shipped in September 2006. From then on, the only unpredictable thing left in a new key was the process ID, the number the computer gives each running program, which on those systems ran from 1 to 32,767. Every key OpenSSL made on Debian, and on Ubuntu, which is built from it, came out of that short list, including the keys servers used to prove who they were, the keys people used to sign in to servers, and more. The fault was found by Luciano Bello, and Debian announced it on May 13, 2008.

An adversary guessing keys at random has to try, on average, half of all the possible keys before hitting the right one. Work out that number for Debian's broken generator.

Half of 32,767 is about 16,400 guesses, which one computer could get through in a day, even making every candidate key from scratch. In fact nobody needed to guess at all, since all 32,767 keys of each kind could be generated once and kept in a list. The figure below sets that beside the key sizes encryption normally uses, measured in bits. One more bit means twice as many keys.

DES, the standard before AES, used 56-bit keys. In 1998 the Electronic Frontier Foundation, a digital rights group, spent less than 250,000 dollars on a machine to search them. Its custom chips did nothing but test DES keys, about 88 billion a second in all. At that rate the full keyspace of $2^{56}$ keys takes about nine and a half days, and the average search, half of it, a little under five.

In July 1998 the machine found the key to a DES contest message in 56 hours. AES replaced DES as the U.S. government's standard in 2001.

The online bookstore uses two kinds of key. Its backups are protected by AES with a 256-bit key, and scouts send it offers encrypted with its RSA public key, which is 4096 bits long. Is the RSA key 16 times as strong as the AES key, since 4096 is 16 times 256?

It isn't, and the comparison means nothing. The two algorithms use their keys in completely different ways. An RSA key has to be very long for its security, because the mathematics behind RSA can be attacked with methods much faster than trying keys, while the best known attack on AES is close to trying every key. Length says something only between keys of one algorithm, such as two AES keys of different sizes.

A longer key has a cost. Decrypting an offer with the 4096-bit key takes the owner's computer noticeably more work than a shorter RSA key would, and the gap grows with every doubling. That is fine for a few offers a week and would matter for a site handling thousands of connections a second. The right length also changes over time, as computers get faster.

RSA is one of the common asymmetric algorithms; elliptic curve cryptography, or ECC, is another, and it reaches the same security as RSA with much shorter keys, one more reason length means nothing across algorithms. Both are behind the digital signatures and the certificates that secure websites. The bookstore made its key pair and uses it with OpenSSL, whose Debian copy had been broken and is long since fixed.

The first command below makes the bookstore's RSA key pair, 4096 bits long, and saves it as shop-key.pem. The second copies one half into shop-pub.pem, for the scouts' page. The third encrypts a scout's short offer with that half. The fourth decrypts the offer with the other half, which never leaves the owner's computer.

openssl genrsa -out shop-key.pem 4096
openssl rsa -pubout -in shop-key.pem -outform PEM -out shop-pub.pem
openssl pkeyutl -encrypt -inkey shop-pub.pem -pubin -in offer.txt -out offer.enc
openssl pkeyutl -decrypt -inkey shop-key.pem -in offer.enc -out offer.txt

RSA can encrypt only a small amount of data directly, a few hundred bytes with this key, which suits a short note with a price in it. For anything longer, programs encrypt the file with a random AES key and use RSA to encrypt just that key. The collector's inventory in the house-sale case, far longer than a few hundred bytes, would have been sent that second way.

Debian's fixed OpenSSL package stopped new weak keys from being made but could not repair the old ones. A companion update for SSH replaced servers' own keys and refused known weak ones, and the rest had to be found by hand. Every key OpenSSL had generated on an affected system since September 2006 had to be treated as compromised, thrown away, and replaced, the same rule that applies to a stolen private key, and administrators spent the following weeks finding them on servers they had set up as much as twenty months before.