Key Length and Security ---------------------------------- by Bruce Schneier Founder and CTO Counterpane Internet Security, Inc. schneier@counterpane.com http://www.counterpane.com Copyright (c) 1999 by Bruce Schneier Despite what everyone else tries to tell you, cryptographic key length has almost nothing to do with security. A short key means bad security, but a long key does not mean good security. The lock on the front door of your house has a series of pins. Each of the pins has multiple possible positions. When someone inserts a key into the lock, the pins are each moved to specific positions. If the positions dictated by the key are the ones that the lock needs to open, it does. Otherwise, it doesn't. Most normal locks have four pins, each of which can be in one of ten different positions. That means that there are 10,000 possible keys. A burglar with a very large key ring can try every possible key, one after the other, and eventually he will get in. He had better be patient, because if you assume fifteen seconds to try a key, it will take him an average of 21 hours to find the correct key -- and that doesn't include bathroom or meal breaks. One day a salesman knocks on your door, and offers to sell you a new lock. His lock has six pins with twelve positions each. A burglar, he tells you, will have to try different keys for 259 days-non-stop-before he will be able to open your door. Do you feel more secure with this lock? Probably not. No burglar would ever stand at your doorstep for 21 hours, anyway. He's more likely to pick the lock, kick the door down, break a window, or just hide in the bushes until you saunter up the front walk. A lock with more pins and positions won't make your house more secure, because the specific attack it makes more difficult -- trying every possible key -- isn't one you're particularly worried about. As long as there are enough pins to make that attack infeasible, you don't have to worry about it. The same is true for cryptographic keys. If they are long enough, don't worry about it. And how long is "long enough" is more complicated than a simple number; it depends on the application and the amount of entropy in the keys. Let's start at the beginning. A cryptographic key is a secret value that modifies an encryption algorithm. If Alice and Bob share a key, they can use the algorithm to communicate securely. If Eve, an eavesdropper, does not know the key, she cannot read Alice's or Bob's messages. She is forced to try and "break" the algorithm; that is, try to learn the key from just the ciphertext. One obvious thing she can do is try every possible key, like the hypothetical burglar from the beginning of this essay. If the key is n bits long, then there are 2^n possible keys. So, if the key is 40 bits long, there are about a trillion possible keys. This would be impossibly boring for a burglar, but computers excel at impossibly boring tasks. On the average, a computer would have to try about half the possible keys before finding the correct one, so a computer capable of trying a billion keys per second would take 18 minutes to find the correct 40-bit key. The DES-breaking machine Deep Crack tried 90 billion keys per second; it could find a 56-bit DES key in an average of 4.5 days. The distributed Internet keysearch project, distributed.net (which included Deep Crack), was testing 250 billion keys per second at its peak. All of this scales linearly. In 1996, a group of cryptographers (including myself) researched the various technologies one could use to build brute-force cryptanalytic machines, and recommended a minimal key length of 90 bits to provide security through 2016. Triple-DES has a 112-bit key, and most modern algorithms have at least a 128-bit key. Even a machine a billion times as fast as Deep Crack would take 10^15 years to try all 2^112 keys and recover the plaintext. Even assuming that Moore's law holds true for the next few hundred years, this will be secure for a long time. So, what else is there to worry about? Why can't we just zillion-bit keys and be secure until the end of time? To answer this I need to explain about entropy. Entropy is a measure of uncertainty. The more uncertain something is, the more entropy there is in that thing. For example, if a random person from the general population is either male or female, the variable "gender" has one bit of entropy. If a random person prefers one of the four Beatles, and each is equally likely, that corresponds to two bits of entropy. The sex of someone on a men's Olympic swimming team has no entropy; everyone is male. The entropy of the Beatles-preference at a John Lennon fan-club meeting has much less than two bits, because it is more likely that a random person will prefer John. The more certainty in the variable, the less the entropy. The same is true for cryptographic keys. Just because an algorithm accepts 128-bit keys does not mean it has 128 bits of entropy in the key. Or, more exactly, the best way to break a given implementation of a 128-bit encryption algorithm might not be to try every possible key. The first worry is the quality of the encryption algorithm. All of the calculations above assumed that the algorithms took the keys they were given and used them perfectly. If there are flaws in the algorithm, this reduces the entropy in the keys. For example, the A5/1 algorithm, used in European GSM cellphones, has a 64-bit key, but can be broken in the time required to brute force a 40-bit key. This means that even though the algorithm is given a cryptographic key with 64 bits of entropy, it only makes use of 40 bits of entropy in the key. You might as well use an algorithm that effectively uses a 40-bit key. This problem is why the AES process is taking so long. The U.S. government wants to replace DES (which has a 56-bit key) with a new algorithm that accepts keys up to 256 bits. Right now there are five semi-finalists for the standard, but do any actually deliver the 256 bits of entropy it claims to? This is also why products that advertise thousand-bit keys are hard to take seriously; they don't understand how keys and entropy work. The second worry is the source of the keys. All the key-length calculations I just made assume that each key has maximum entropy when it is generated. In other words, I assumed that each key is equally likely. This just isn't true. Many keys are generated from passwords or passphrases. A system that accepts 10-character ASCII passwords might require 80 bits to represent, but has much less than 80 bits of entropy. High-order ASCII bytes won't appear at all, and passwords that are real words (or close to real words) are much more likely than random character strings. I've seen entropy estimates of standard English at 1.3 bits per character; passwords probably have less than 4 bits of entropy per character. This means that a 6-character passphrase is about the same as a 32-bit key, and if you want a 128-bit key you are going to need a 98-character English passphrase. You see, a brute-force password cracking engine isn't going to try every possible key in order. It's going to try the most likely ones first, and then try the rest in some likelihood order. It will try common passwords like "password" and "1234," then the entire English dictionary, and then varied capitalitlization and extra numbers, and so on. L0phtcrack is a password-cracking program that does this; on a Pentium Pro 200 it can test a 200-entry password file against an 8 Megabyte dictionary of popular passwords in under a minute. Testing the entire 26-character alphabet space takes 26 hours, and the 36-character alphanumeric space takes about 250 hours. This is why it is laughable when companies like Microsoft tout 128-bit encryption and then base the key on the password. (This describes pretty much all of Windows NT security.) The algorithms they use might accept a 128-bit key, but the entropy in the password is far, far less. In fact, it doesn't matter how good the cryptography is or what the key length is; weak passwords will break this system. Some have dealt with this problem by requiring stronger and stronger passwords, but that is no longer effective. Over the past several decades, Moore's law has made it possible to brute-force larger and larger entropy keys. At the same time, there is a maximum to the entropy that the average computer user (or even the above-average computer user) is willing to remember. You can't expect him to memorize a 32-character random hexadecimal string, but that's what has to happen if he is to memorize a 128-bit key. These two numbers have crossed; password crackers can now break anything that you can reasonably expect a user to memorize. Good passwords are difficult to memorize, he will complain, but this difficulty is precisely why they are considered good. Randomly generated keys aren't necessarily better, because now the random number generator must produce keys with maximum entropy. A flaw in the random number generator is what broke the encryption in Netscape version 1.1. While the random number generator was used to generate 128-bit keys, the maximum entropy was around 20 bits. So the algorithm was no better than if it had a 20-bit key. Solutions exist, but they require engineering tradeoffs. Biometrics can generate better passwords, less because there is a lot of entropy in -- for example -- a fingerprint (my guess is that it is equivalent to about a 60-bit key), and more because there is no such thing as a bad fingerprint in the same way that there is a bad password. Smart cards offer a convenient way to carry about a high-entropy key, but have the restrictions associated with a physical device. And for some communications systems, public-key protocols can generate high-entropy secrets using nothing but public information. On-line verification of passwords, which prevents off-line dictionary attacks, also works in some circumstances. This is a big deal. I see complex PKI systems where the private key is protected with a password. Almost every hard-disk encryption product bases its security on a user-remembered key. Almost all the security of Windows NT collapses because it is all built on user-remembered passwords. Even PGP falls apart if the user chooses a bad passphrase. It doesn't matter what the algorithms are or how large the keys they use; user-remembered secrets are not secure. A Note on Public-Key Algorithms This essay talks about symmetric algorithms (block and stream ciphers), which take arbitrary bit strings as keys. Public-key systems, which have mathematical keys such as the product of two large primes, are different. There are still brute-force attacks against public key systems, but they involve solving mathematical problems such as factoring. The group that just factored a 512-bit RSA key said that the calculation took about 2% the effort of a 56-bit keysearch. Estimates of future security for RSA keys are much harder, because you have to take into account advances in factoring mathematics as well as advances in computer speed and networking. Conservative estimates indicate that 1028-bit keys are good enough for the next few years, and 2048-bit keys should be good enough for ten or so years. But since no one even knows if factoring is "hard," it is certainly possible that a brilliant mathematician may come along and make even these key lengths insecure. RSA keys have, of course, much too much entropy to memorize. They are either encrypted with a passphrase and stored on the hard drive, or stored on a token such as a smart card. Sometimes they're even left out in the clear. Key length paper: http://www.counterpane.com/keylength.html