Key size
|
|
In cryptography, the key size (alternatively key length) is a measure of the number of possible keys which can be used in a cipher. Because modern cryptography uses binary keys, the length is usually specified in bits. The length of a key is critical in determining the susceptibility of a cipher to exhaustive search attacks.
| Contents |
Significance
Keys are used to control the operation of a cipher so that only the correct key can convert encrypted text (ciphertext) to plaintext. Many ciphers are based on publicly known algorithms or are open source, and so it is only the difficulty of obtaining the key that determines security of the system, provided that there is no analytic attack (ie, a 'structural weakness' in the algorithms or protocols used), and assuming that the key is not otherwise available (such as via theft, extortion, or compromise of computer systems). The widely accepted notion that the security of the system should depend on the key alone has been explicitly formulated by Auguste Kerckhoffs (in the 1880s) and Claude Shannon (in the 1940s); the statements are known as Kerckhoffs' law and Shannon's Maxim respectively.
A key should therefore be large enough that a brute force attack (possible against any encryption algorithm) is infeasible – i.e, would take too long to execute. Shannon's work on information theory showed that to achieve 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, and the practical difficulty of managing such long keys, modern cryptographic practice 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 an encrypted text must be infeasible for an attacker.
The preferred numbers commonly used as key sizes (in bits) are powers of two, potentially multiplied with a small odd integer.
Brute force attack
Main article: Brute force attack
Even if a cipher is unbreakable by exploiting structural weaknesses in the algorithm, it is possible to run through the entire space of keys in what is known as a brute force attack. Since longer keys require more work to brute force search, a long enough key will require more work than is feasible. Thus, length of the key is important in resisting this type of attack.
A key of length n (bits) means that there are 2n possible keys. This number grows extremely rapidly as n increases. Moore's law suggests that computing power doubles roughly every 18 months, but even this doubling effect leaves the key lengths currently considered acceptable well out of reach. Large numbers like the 2128 operations required to try all possible 128-bit keys will be out of reach for all of mankind's conventional computing power for the forseeable future.
Symmetric algorithm key lengths
US Government export policy has long restricted the 'strength' of cryptography which can be sent out of the country. For many years the limit was 40 bits. Today, a key length of 40 bits offers little protection against even a casual attacker with a single PC. The restrictions have not been removed (it is still illegal to export some cryptographic products), but the limit was effectively raised to 128-bit key lengths in 1999/2000.
When the Data Encryption Standard cipher was released in 1977, a key length of 56 bits was thought to be sufficient (though there was speculation at the time that the NSA has deliberately reduced the key size from the original value of 112 bits, in IBM's Lucifer cipher, or 64 bits, in one of the versions of what was adopted as DES) so as to limit the 'strength' of encryption available to non-US users. The NSA has major computing resources and a large budget; some thought that 56 bits was NSA-breakable in the late '70s. However, by 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 56-bit DES by a brute force attack mounted by a cyber civil rights group with limited resources; see EFF DES cracker. 56 bits is now considered insufficient length for symmetric algorithm keys, and may have been for some time. More technically and financially capable organizations were surely able to do the same long before the effort described in the book. Distributed.net and its volunteers broke a 64-bit RC5 key in several years, using about seventy thousand (mostly home) computers.
The NSA's Skipjack algorithm used in its Fortezza program employs 80 bit keys.
DES has been replaced in many applications by triple DES or 3DES, which has 112-bit keys.
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 many observers, to be sufficient for the foreseeable future for symmetric algorithms of AES's quality. The U.S. Government requires 192 or 256-bit AES keys for TOP SECRET data.
As of 2003, the U.S. National Institute for Standards and Technology, NIST, is proposing that 80-bit keys be phased out by 2015.
Asymmetric algorithm key lengths
The effectiveness of public key cryptosystems depends on the intractability (computational and theoretical) of certain mathematical problems such as integer factorization. Since acceptable keys for these algorithms must have particular mathematical properties (e.g., be a product of two 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 was generally considered the minimum necessary for the RSA encryption algorithm.
As of 2003 RSA Security claims that 1024-bit RSA keys are equivalent in strength to 80-bit symmetric keys, 2048-bit RSA keys to 112-bit symmetric keys and 3072-bit RSA keys to 128-bit symmetric keys. RSA recommends that 1024-bit keys may be used until 2010 and that 2048-bit keys may be used until 2030. An RSA key length of 3072 bits should be use if security is required beyond 2030. Draft key management guidelines under consideration by NIST further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys.
One of the asymmetric algorithm types, elliptic curve cryptography, or ECC, appears to be secure with shorter keys than other asymmetric key algorithms. NIST guidelines suggest that their keys need be twice the length of equivalent strength symmetric key algorithms. So, for example, a 224-bit ECC key would have roughly the same strength as a 112-bit symmetric key. These estimates assume no major breakthrough in solving the underlying mathematical problem that ECC is based on. A message encrypted with an elliptic key algorithm using a 109-bit long key has been broken by brute force.
References
- Blaze, Matt; Diffie, Whitfield; Rivest, Ronald L.; et. al. "Minimal Key Lengths for Symmetric Ciphers to Provide Adequate Commercial Security". January 1996
- Arjen K. Lenstra, Eric R. Verheul: Selecting Cryptographic Key Sizes. J. Cryptology 14(4): 255-293 (2001) — Citeseer link (http://citeseer.ist.psu.edu/lenstra99selecting.html)
External links
- A recommended keylength calculator (http://www.keylength.com/)
- A discussion on the importance of key length (http://www.giac.org/practical/gsec/Lorraine_Williams_GSEC.pdf) (PDF file)
link; available in PDF, PostScript, and other formats)
- The FreeS/WAN project's discussion of key length (http://www.freeswan.org/freeswan_trees/freeswan-2.06/doc/politics.html#shortkeys)
- Burt Kaliski: TWIRL and RSA key sizes (http://www.rsasecurity.com/rsalabs/node.asp?id=2004) (May 2003)it:Dimensione chiave