Cryptographic key length

Key length is an important issue in cryptography. Since most cryptographic schemes are based on publicly specified algorithms, the difficulty of obtaining the key usually determines the security of the system. Though attackers often attempt methods of obtaining keys such as compromising the server on which they are stored, the difficulty of obtaining the key through mathematical means is crucially influenced by the size of the key.

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 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 2ⁿ possible keys. This number grows rapidly as n increases, and doubles when n in incremented by 1. However, this must be weighed against the fact that by Moore's law, 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.

Needless to say, a key length of 40 bits offers little protection today even against a casual attacker. Thus the Advanced Encryption Standard published in 2001 uses a key size of (at least) 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 to be sufficient for the forseeable future for symmetric algortihms like AES.

Public key cryptosystems depend on the computational infeasibility of certain problems such as integer factorization. Since the best factoring algorithms are much more efficient than brute force search, correspondingly longer keys are necessary for public key ciphers. As of 2002, a key length of 1024 bits is generally considered necessary for the RSA encryption algorithm. The knowledgeable and cautious use 2048.

References Note: please note that old references on this subject should not be relied upon, as they represent attempts to predict the future in a field that is constantly changing

• Blaze, Matt; Diffie, Whitfield; Rivest, Ronald L.; et. al. "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security". January 1996

External links

• A discussion on the importance of key length (pdf file) (http://www.giac.org/practical/gsec/Lorraine_Williams_GSEC.pdf)