Main Page | See live article | Alphabetical index

Cryptographic key length

Key length is an important issue in cryptography. Since most cryptographic schemes are based on publicly known algorithms, the difficulty of obtaining the key is related to the mathematical security of the system, provided that there is no known analytic attack, ie, a 'structural weakness' in the algorithm. A key should therefore be large enough that a "brute force" attack is infeasible. It must be kept in mind that even if the system is mathematically secure, attackers might attempt to obtain keys through theft (eg, dumpster diving or burglary), pressure against humans (eg, extortion or threats against those with access to the keys), compromising the computers on which keys are stored, etc.

Shannon's work on information theory showed that for achieving perfect secrecy, it is necessary for the key length to be at least as large as that of the message to be transmitted. In light of this, modern cryptography has discarded the notion of perfect secrecy as a requirement for encryption and instead focuses on computational security. Under this definition, the computational requirements of breaking a cipher must be infeasible for an attacker.

Even if a cipher is unbreakable by exploiting structural weaknesses in the algorithm, it may be possible to run through the entire space of keys in what is known as a brute force attack. Therefore, the length of the key must be enough to be resistant to this form of attack.

A key of length n (bits) means that there are 2n possible keys. This number grows rapidly as n increases, and doubles when n in incremented by 1. This is comforting to those using ciphers. However, any comfort is seriously reduced by considering Moore's law, which predicts (successfully since it was first stated) that computing power available to the attacker doubles roughly every 18 months!

When the Data Encryption Standard was introduced in 1977, a key length of 56 bits was thought to be sufficient (though there was speculation that the NSA has deliberately reduced the key size from the original value of 112 bits (in IBM's Lucifer cypher) or 64 bits (in one of the versions of what was adopted as DES)). However, in the late 90s, it became clear that DES could be cracked in a few days' time-frame with custom-built hardware such as could be purchased by a large corporation. The book Cracking DES (O'Reilly and Associates) tells of the successful attempt to break DES by brute force attack mounted by a cyber civil rights group. Clearly 56 bits is insufficient length for symmetric algorithm keys; more technically and financially capable organizations were surely able to do the same long before the attack described in the book.

Needless to say, a key length of 40 bits offers little protection today even against a casual attacker with very inexpensive computing resources. Thus the Advanced Encryption Standard published in 2001 uses a key size of (at minimum) 128 bits. It also can use keys up to 256 bits (a specification requirement for submissions to the AES contest). 128 bits is currently thought, by informed observers, to be sufficient for the forseeable future for symmetric algorithms of AES's quality.

The effectiveness of public key cryptosystems depends on the intracability (computational and theoretical) of certain mathematical problems such as integer factorization. Since acceptable keys for these algorithms must have particular mathematical properties (eg, relations between large prime numbers), not any key may be used. To make a brute force search infeasible against such keys, there must as always be sufficient numbers of possible keys. That implies that asymmetric algorithm keys must be longer for equivalent resistance to such attacks than symmetric algorithm keys (eg, DES, IDEA, or AES). As of 2002, a key length of 1024 bits is generally considered necessary for the RSA encryption algorithm. The knowledgeable and cautious use 2048.

One of the asymmetric algorithm types, elliptic curve algorithms, appear to be secure with shorter keys than other asymmetric key algorithms. It has been suggested that their keys need be, in the most favorable cases, no longer than symmetric key algorithms. However, a message encrypted with an elliptic key algorithm and using a 109 bit long key has been broken by brute force. Elliptic curve algorithms are relatively recent, and until more theoretical work has been done, it appears that they require somewhat longer keys for security against brute force search than do good symmetric key algorithms.

References

Note: please note that non-current references on this subject should not be relied upon, as they represent attempts to predict the future in a field that is rapidly changing. 'Secure' key length estimates from only a few years ago have been made obsolete by increased cost/effectiveness of computers, or by theoretical advances (eg, in factoring theory).

External links