Key size
In cryptography, key size or key length refers to the number of bits in a key used by a cryptographic algorithm (such as a cipher).
Key length defines the upper-bound on an algorithm's security (i.e. a logarithmic measure of the fastest known attack against an algorithm), because the security of all algorithms can be violated by brute-force attacks. Ideally, the lower-bound on an algorithm's security is by design equal to the key length (that is, the algorithm's design does not detract from the degree of security inherent in the key length).
Most
Significance
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 and/or would take too much memory to execute.
Key size and encryption system
Encryption systems are often grouped into families. Common families include symmetric systems (e.g.
The actual degree of security achieved over time varies, as more computational power and more powerful mathematical analytic methods become available. For this reason, cryptologists tend to look at indicators that an algorithm or key length shows signs of potential vulnerability, to move to longer key sizes or more difficult algorithms. For example, as of May 2007[update], a 1039-bit integer was factored with the special number field sieve using 400 computers over 11 months.[2] The factored number was of a special form; the special number field sieve cannot be used on RSA keys. The computation is roughly equivalent to breaking a 700 bit RSA key. However, this might be an advance warning that 1024 bit RSA keys used in secure online commerce should be deprecated, since they may become breakable in the foreseeable future. Cryptography professor Arjen Lenstra observed that "Last time, it took nine years for us to generalize from a special to a nonspecial, hard-to-factor number" and when asked whether 1024-bit RSA keys are dead, said: "The answer to that question is an unqualified yes."[3]
The 2015 Logjam attack revealed additional dangers in using Diffie-Hellman key exchange when only one or a few common 1024-bit or smaller prime moduli are in use. This practice, somewhat common at the time, allows large amounts of communications to be compromised at the expense of attacking a small number of primes.[4][5]
Brute-force attack
This section needs additional citations for verification. (August 2012) |
Even if a symmetric cipher is currently unbreakable by exploiting structural weaknesses in its algorithm, it may be possible to run through the entire space of keys in what is known as a brute-force attack. Because longer symmetric keys require exponentially more work to brute force search, a sufficiently long symmetric key makes this line of attack impractical.
With a key of length n bits, there are 2n possible keys. This number grows very rapidly as n increases. The large number of operations (2128) required to try all possible 128-bit keys is widely considered
Symmetric algorithm key lengths
IBM's Lucifer cipher was selected in 1974 as the base for what would become the Data Encryption Standard. Lucifer's key length was reduced from 128 bits to 56 bits, which the NSA and NIST argued was sufficient for non-governmental protection at the time. The NSA has major computing resources and a large budget; some cryptographers including Whitfield Diffie and Martin Hellman complained that this made the cipher so weak that NSA computers would be able to break a DES key in a day through brute force parallel computing. The NSA disputed this, claiming that brute-forcing DES would take them "something like 91 years".[7]
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 or government.[8][9] The book Cracking DES (O'Reilly and Associates) tells of the successful ability in 1998 to break 56-bit DES by a brute-force attack mounted by a cyber civil rights group with limited resources; see EFF DES cracker. Even before that demonstration, 56 bits was considered insufficient length for symmetric algorithm keys for general use. Because of this, DES was replaced in most security applications by Triple DES, which has 112 bits of security when using 168-bit keys (triple key).[1]
The
In 2003, the U.S. National Institute for Standards and Technology, NIST proposed phasing out 80-bit keys by 2015. At 2005, 80-bit keys were allowed only until 2010.[11]
Since 2015, NIST guidance says that "the use of keys that provide less than 112 bits of
Asymmetric algorithm key lengths
The effectiveness of
Since 2015, NIST recommends a minimum of 2048-bit keys for
1024-bit RSA keys are equivalent in strength to 80-bit symmetric keys, 2048-bit RSA keys to 112-bit symmetric keys, 3072-bit RSA keys to 128-bit symmetric keys, and 15360-bit RSA keys to 256-bit symmetric keys.
The Finite Field
Elliptic-curve cryptography (ECC) is an alternative set of asymmetric algorithms that is equivalently secure with shorter keys, requiring only approximately twice the bits as the equivalent symmetric algorithm. A 256-bit Elliptic-curve Diffie–Hellman (ECDH) key has approximately the same safety factor as a 128-bit AES key.[12] A message encrypted with an elliptic key algorithm using a 109-bit long key was broken in 2004.[17]
The NSA previously recommended 256-bit ECC for protecting classified information up to the SECRET level, and 384-bit for TOP SECRET;[10] In 2015 it announced plans to transition to quantum-resistant algorithms by 2024, and until then recommends 384-bit for all classified information.[18]
Effect of quantum computing attacks on key strength
The two best known quantum computing attacks are based on Shor's algorithm and Grover's algorithm. Of the two, Shor's offers the greater risk to current security systems.
Derivatives of Shor's algorithm are widely conjectured to be effective against all mainstream public-key algorithms including
Mainstream symmetric ciphers (such as
In a 2016 Quantum Computing FAQ, the NSA affirmed:
"A sufficiently large quantum computer, if built, would be capable of undermining all widely-deployed public key algorithms used for key establishment and digital signatures. [...] It is generally accepted that quantum computing techniques are much less effective against symmetric algorithms than against current widely used public key algorithms. While public key cryptography requires changes in the fundamental design to protect against a potential future quantum computer, symmetric key algorithms are believed to be secure provided a sufficiently large key size is used. [...] The public-key algorithms (
[Elliptic-curve Diffie–Hellman] ECDH, and [Elliptic Curve Digital Signature Algorithm] ECDSA) are all vulnerable to attack by a sufficiently large quantum computer. [...] While a number of interesting quantum resistant public key algorithms have been proposed external to NSA, nothing has been standardized by NIST, and NSA is not specifying any commercial quantum resistant standards at this time. NSA expects that NIST will play a leading role in the effort to develop a widely accepted, standardized set of quantum resistant algorithms. [...] Given the level of interest in the cryptographic community, we hope that there will be quantum resistant algorithms widely available in the next decade. [...] The AES-256 and SHA-384 algorithms are symmetric, and believed to be safe from attack by a large quantum computer."[20]
In a 2022 press release, the NSA notified:
"A cryptanalytically-relevant quantum computer (CRQC) would have the potential to break public-key systems (sometimes referred to as asymmetric cryptography) that are used today. Given foreign pursuits in quantum computing, now is the time to plan, prepare and budget for a transition to [quantum-resistant] QR algorithms to assure sustained protection of [National Security Systems] NSS and related assets in the event a CRQC becomes an achievable reality."[21]
Since September 2022, the NSA has been transitioning from the Commercial National Security Algorithm Suite (now referred to as CNSA 1.0), originally launched in January 2016, to the Commercial National Security Algorithm Suite 2.0 (CNSA 2.0), both summarized below:[22][b]
CNSA 2.0
Algorithm | Function | Parameters |
---|---|---|
Advanced Encryption Standard (AES) | Symmetric block cipher for information protection | 256-bit keys |
CRYSTALS-Kyber | Asymmetric algorithm for key establishment | Level V |
CRYSTALS-Dilithium | Asymmetric algorithm for digital signatures | Level V |
Secure Hash Algorithm (SHA) | Algorithm for computing a condensed representation of information | SHA-384 or SHA-512 |
Leighton-Micali Signature (LMS) | Asymmetric algorithm for digitally signing firmware and software | All parameters approved. SHA256/192 recommended. |
Xtended Merkle Signature Scheme (XMSS) | Asymmetric algorithm for digitally signing firmware and software | All parameters approved |
CNSA 1.0
Algorithm | Function | Parameters |
---|---|---|
Advanced Encryption Standard (AES) | Symmetric block cipher for information protection | 256-bit keys |
Elliptic Curve Diffie-Hellman (ECDH) Key Exchange | Asymmetric algorithm for key establishment | Curve P-384 |
Elliptic Curve Digital Signature Algorithm (ECDSA) | Asymmetric algorithm for digital signatures | Curve P-384 |
Secure Hash Algorithm (SHA) | Algorithm for computing a condensed representation of information | SHA-384 |
Diffie-Hellman (DH) Key Exchange | Asymmetric algorithm for key establishment | Minimum 3072-bit modulus |
[Rivest-Shamir-Adleman] RSA | Asymmetric algorithm for key establishment | Minimum 3072-bit modulus |
[Rivest-Shamir-Adleman] RSA | Asymmetric algorithm for digital signatures | Minimum 3072-bit modulus |
See also
Notes
- ^ See the discussion on the relationship between key lengths and quantum computing attacks at the bottom of this page for more information.
- ^ See the complete tables and the transition timeline at Commercial National Security Algorithm Suite article.
References
- ^ a b c Barker, Elaine; Roginsky, Allen (March 2019). "Transitions: Recommendation for Transitioning the Use of Cryptographic Algorithms and Key Lengths, NIST SP-800-131A Rev 2" (PDF). Nvlpubs.nist.gov. Retrieved 2023-02-11.
- ^ "Researcher: RSA 1024-bit Encryption not Enough". PC World. 2007-05-23. Retrieved 2016-09-24.
- ^ Cheng, Jacqui (2007-05-23). "Researchers: 307-digit key crack endangers 1024-bit RSA". Ars Technica. Retrieved 2016-09-24.
- ^ "Weak Diffie-Hellman and the Logjam Attack". weakdh.org. 2015-05-20.
- ^ Adrian, David; Bhargavan, Karthikeyan; Durumeric, Zakir; Gaudry, Pierrick; Green, Matthew; Halderman, J. Alex; Heninger, Nadia; Springall, Drew; Thomé, Emmanuel; Valenta, Luke; VanderSloot, Benjamin; Wustrow, Eric; Zanella-Béguelin, Santiago; Zimmermann, Paul (October 2015). Imperfect Forward Secrecy: How Diffie-Hellman Fails in Practice (PDF). 22nd ACM Conference on Computer and Communications Security (CCS '15). Denver, CO. Archived (PDF) from the original on 2022-10-10.
- ^ "How secure is AES against brute force attacks?". EE Times. Retrieved 2016-09-24.
- ^ "DES Stanford-NBS-NSA meeting recording & transcript". Toad.com. Archived from the original on 2012-05-03. Retrieved 2016-09-24.
- Fortify. Retrieved 2011-10-14.
- ^ Strong Cryptography The Global Tide of Change, Cato Institute Briefing Paper no. 51, Arnold G. Reinhold, 1999
- ^ a b c "NSA Suite B Cryptography". National Security Agency. 2009-01-15. Archived from the original on 2009-02-07. Retrieved 2016-09-24.
- ^ Barker, Elaine; Barker, William; Burr, William; Polk, William; Smid, Miles (2005-08-01). "Recommendation for Key Management – Part 1: General" (PDF). NIST Special Publication. (PDF) from the original on 2016-12-13. Retrieved 2019-01-08.
- ^ (PDF) from the original on 2015-02-26. Retrieved 2017-11-24.
- ^ "A Cost-Based Security Analysis of Symmetric and Asymmetric Key Lengths". RSA Laboratories. Archived from the original on 2017-01-13. Retrieved 2016-09-24.
- (PDF) from the original on 2020-05-09.
- ^ Kaliski, Burt (2003-05-06). "TWIRL and RSA Key Size". RSA Laboratories. Archived from the original on 2017-04-17. Retrieved 2017-11-24.
- ^ Zimmermann, Paul (2020-02-28). "Factorization of RSA-250". Cado-nfs-discuss. Archived from the original on 2020-02-28. Retrieved 2020-07-12.
- ^ "Certicom Announces Elliptic Curve Cryptography Challenge Winner". BlackBerry Limited. 2004-04-27. Archived from the original on 2016-09-27. Retrieved 2016-09-24.
- ^ "Commercial National Security Algorithm Suite". National Security Agency. 2015-08-09. Archived from the original on 2022-02-18. Retrieved 2020-07-12.
- ^ Bennett C.H., Bernstein E., Brassard G., Vazirani U., The strengths and weaknesses of quantum computation. SIAM Journal on Computing 26(5): 1510-1523 (1997).
- ^ "Commercial National Security Algorithm Suite and Quantum Computing FAQ" (PDF). National Security Agency. 2016-01-01. p. 6-8. Retrieved 2024-04-21.
- ^ "NSA Releases Future Quantum-Resistant (QR) Algorithm Requirements for National Security Systems". National Security Agency. 2022-09-07. Retrieved 2024-04-14.
- ^ "Announcing the Commercial National Security Algorithm Suite 2.0, U/OO/194427-22, PP-22-1338, Ver. 1.0" (PDF). media.defense.gov. National Security Agency. September 2022. Table IV: CNSA 2.0 algorithms, p. 9.; Table V: CNSA 1.0 algorithms, p. 10. Retrieved 2024-04-14.
Further reading
- Recommendation for Key Management — Part 1: general, NIST Special Publication 800-57. March, 2007
- 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