Key size
Encyclopedia
In cryptography
, key size or key length is the size measured in bit
s of the key
used in a cryptographic algorithm (such as a cipher
). An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits. The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force
), but it can be smaller. For example, Triple DES
has a key size of 168 bits but provides at most 112 bits of security, since an attack of complexity 2112 is known. This property of Triple DES is not a weakness provided 112 bits of security is sufficient for an application. Most symmetric-key algorithm
s in common use are designed to have security equal to their key length. No asymmetric-key algorithms with this property are known; elliptic curve cryptography
comes the closest with an effective security of roughly half its key length.
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 algorithm
s 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 (i.e., 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' principle
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 so called perfect secrecy, it is necessary for the key length to be at least as large as the message to be transmitted and only used once (this algorithm is called the One-time pad
). 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 which 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.
) and asymmetric systems (e.g. RSA); they may alternatively be grouped according to the central algorithm
used (e.g. elliptic curve cryptography
).
As each of these is of a different level of cryptographic complexity, it is usual to have different key sizes for the same level of security, depending upon the algorithm used. For example, the security available with a 1024-bit key using asymmetric RSA is considered approximately equal in security to an 80-bit key in a symmetric algorithm (Source: RSA Security
).
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 , a 1039 bit integer was factored with the special number field sieve
using 400 computers over 11 months. 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 advanced warning that 1024 bit RSA used in secure online commerce should be deprecated
, since they may become breakable in the near 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."
With a key of length n bits, there are 2n possible keys. This number grows very rapidly as n increases. Moore's law
suggests that computing power doubles roughly every 18 to 24 months, but even this doubling effect leaves the larger symmetric key lengths currently considered acceptably well out of reach. The large number of operations (2128) required to try all possible 128-bit keys is widely considered to be out of reach for conventional digital computing techniques for the foreseeable future. However, alternative forms of computing technology are anticipated which may have superior processing power than classical computers. If a suitably sized quantum computer
capable of running Grover's algorithm
reliably becomes available, it would reduce a 128-bit key down to 64-bit security, roughly a DES equivalent. This is one of the reasons why AES supports a 256-bit key length. See the discussion on the relationship between key lengths and quantum computing attacks at the bottom of this page for more information.
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 , but it became easier to gain authorization to export to certain countries in 1999/2000.
When the Data Encryption Standard
cipher was released in 1977, a key length of 56 bits
was thought to be sufficient. There was speculation at the time, however, 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
, which has 112 bits of security with 168-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 highly sensitive data.
In 2003 the U.S. National Institute for Standards and Technology, NIST, proposed that 80-bit keys should be phased out by 2015. As of 2005, 80-bit keys were allowed to be used only until 2010.
. These problems are time consuming to solve, but usually faster than trying all possible keys by brute force. Thus, asymmetric algorithm keys must be longer for equivalent resistance to attack than symmetric algorithm keys. As of 2002, a key length of 1024 bits was generally considered the minimum necessary for the RSA encryption algorithm.
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 claims that 1024-bit keys are likely to become crackable some time between 2006 and 2010 and that 2048-bit keys are sufficient until 2030. An RSA key length of 3072 bits should be used if security is required beyond 2030. NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys.
The Finite Field Diffie-Hellman algorithm has roughly the same key strength as RSA for the same key sizes. The work factor for breaking Diffie-Hellman is based on the discrete logarithm problem, which is related to the integer factorization problem on which RSA's strength is based. Thus, a 3072-bit Diffie-Hellman key has about the same strength as a 3072-bit RSA key.
One of the asymmetric algorithm types, elliptic curve cryptography
, or ECC, appears to be secure with shorter keys than those needed by other asymmetric key algorithms. NIST guidelines state that ECC keys should 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 breakthroughs in solving the underlying mathematical problems 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.
The NSA specifies that "Elliptic Curve Public Key Cryptography using the 256-bit prime modulus elliptic curve as specified in FIPS-186-2 and SHA-256 are appropriate for protecting classified information up to the SECRET level. Use of the 384-bit prime modulus elliptic curve and SHA-384 are necessary for the protection of TOP SECRET information."
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 RSA, Diffie-Hellman and elliptic curve cryptography
. According to Professor Gilles Brassard, an expert in quantum computing: "The time needed to factor an RSA integer is the same order as the time needed to use that same integer as modulus for a single RSA encryption. In other words, it takes no more time to break RSA on a quantum computer (up to a multiplicative constant) than to use it legitimately on a classical computer." The general consensus is that these public key algorithms are insecure at any key size if sufficiently large quantum computers capable of running Shor's algorithm become available. The implication of this attack is that all data encrypted using current standards based security systems such as the ubiquitous SSL
used to protect e-commerce and Internet banking and SSH
used to protect access to sensitive computing systems is at risk. Encrypted data protected using public-key algorithms can be archived and may be broken at a later time.
Mainstream symmetric ciphers (such as AES
or Twofish
) and collision resistant hash functions (such as SHA
) are widely conjectured to offer greater security against known quantum computing attacks. They are widely conjectured to be most vulnerable to Grover's algorithm
. Bennett, Bernstein, Brassard, and Vazirani proved in 1996 that a brute-force key search on a quantum computer cannot be faster than roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case. Thus in the presence of large quantum computers an n-bit key can provide at least n/2 bits of security. Quantum brute force is easily defeated by doubling the key length, which has little extra computational cost in ordinary use. This implies that at least a 160-bit symmetric key is required to achieve 80-bit security rating against a quantum computer.
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
, key size or key length is the size measured in bit
Bit
A bit is the basic unit of information in computing and telecommunications; it is the amount of information stored by a digital device or other physical system that exists in one of two possible distinct states...
s of the key
Key (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
used in a cryptographic algorithm (such as a cipher
Cipher
In cryptography, a cipher is an algorithm for performing encryption or decryption — a series of well-defined steps that can be followed as a procedure. An alternative, less common term is encipherment. In non-technical usage, a “cipher” is the same thing as a “code”; however, the concepts...
). An algorithm's key length is distinct from its cryptographic security, which is a logarithmic measure of the fastest known computational attack on the algorithm, also measured in bits. The security of an algorithm cannot exceed its key length (since any algorithm can be cracked by brute force
Brute force attack
In cryptography, a brute-force attack, or exhaustive key search, is a strategy that can, in theory, be used against any encrypted data. Such an attack might be utilized when it is not possible to take advantage of other weaknesses in an encryption system that would make the task easier...
), but it can be smaller. For example, Triple DES
Triple DES
In cryptography, Triple DES is the common name for the Triple Data Encryption Algorithm block cipher, which applies the Data Encryption Standard cipher algorithm three times to each data block....
has a key size of 168 bits but provides at most 112 bits of security, since an attack of complexity 2112 is known. This property of Triple DES is not a weakness provided 112 bits of security is sufficient for an application. Most symmetric-key algorithm
Symmetric-key algorithm
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both encryption of plaintext and decryption of ciphertext. The encryption key is trivially related to the decryption key, in that they may be identical or there is...
s in common use are designed to have security equal to their key length. No asymmetric-key algorithms with this property are known; elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
comes the closest with an effective security of roughly half its key length.
Significance
KeysKey (cryptography)
In cryptography, a key is a piece of information that determines the functional output of a cryptographic algorithm or cipher. Without a key, the algorithm would produce no useful result. In encryption, a key specifies the particular transformation of plaintext into ciphertext, or vice versa...
are used to control the operation of a cipher so that only the correct key can convert encrypted text (ciphertext
Ciphertext
In cryptography, ciphertext is the result of encryption performed on plaintext using an algorithm, called a cipher. Ciphertext is also known as encrypted or encoded information because it contains a form of the original plaintext that is unreadable by a human or computer without the proper cipher...
) to plaintext
Plaintext
In cryptography, plaintext is information a sender wishes to transmit to a receiver. Cleartext is often used as a synonym. Before the computer era, plaintext most commonly meant message text in the language of the communicating parties....
. Many ciphers are based on publicly known algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
s or are open source
Open source
The term open source describes practices in production and development that promote access to the end product's source materials. Some consider open source a philosophy, others consider it a pragmatic methodology...
, and so it is only the difficulty of obtaining the key that determines security of the system, provided that there is no analytic attack (i.e., 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
Auguste Kerckhoffs
Auguste Kerckhoffs was a Dutch linguist and cryptographer who was professor of languages at the École des Hautes Études Commerciales in Paris in the late 19th century....
(in the 1880s) and Claude Shannon (in the 1940s); the statements are known as Kerckhoffs' principle
Kerckhoffs' principle
In cryptography, Kerckhoffs's principle was stated by Auguste Kerckhoffs in the 19th century: A cryptosystem should be secure even if everything about the system, except the key, is public knowledge.Kerckhoffs's principle was reformulated by Claude Shannon as...
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
Information theory
Information theory is a branch of applied mathematics and electrical engineering involving the quantification of information. Information theory was developed by Claude E. Shannon to find fundamental limits on signal processing operations such as compressing data and on reliably storing and...
showed that to achieve so called perfect secrecy, it is necessary for the key length to be at least as large as the message to be transmitted and only used once (this algorithm is called the One-time pad
One-time pad
In cryptography, the one-time pad is a type of encryption, which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key of the same length as the plaintext, resulting...
). 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 which 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.
Key size and encryption system
Encryption systems are often grouped into families. Common families include symmetric systems (e.g. AESAdvanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
) and asymmetric systems (e.g. RSA); they may alternatively be grouped according to the central algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
used (e.g. elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
).
As each of these is of a different level of cryptographic complexity, it is usual to have different key sizes for the same level of security, depending upon the algorithm used. For example, the security available with a 1024-bit key using asymmetric RSA is considered approximately equal in security to an 80-bit key in a symmetric algorithm (Source: RSA Security
RSA Security
RSA, the security division of EMC Corporation, is headquartered in Bedford, Massachusetts, United States, and maintains offices in Australia, Ireland, Israel, the United Kingdom, Singapore, India, China, Hong Kong and Japan....
).
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 , a 1039 bit integer was factored with the special number field sieve
Special number field sieve
In number theory, a branch of mathematics, the special number field sieve is a special-purpose integer factorization algorithm. The general number field sieve was derived from it....
using 400 computers over 11 months. 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 advanced warning that 1024 bit RSA used in secure online commerce should be deprecated
Deprecation
In the process of authoring computer software, its standards or documentation, deprecation is a status applied to software features to indicate that they should be avoided, typically because they have been superseded...
, since they may become breakable in the near future. Cryptography professor Arjen Lenstra
Arjen Lenstra
Arjen Klaas Lenstra is a Dutch mathematician. He studied mathematics at the University of Amsterdam.He is currently a professor at the EPFL , in the Laboratory for Cryptologic Algorithms, and...
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."
Brute force attack
Even if a symmetric cipher is currently unbreakable by exploiting structural weaknesses in its algorithm, it is possible to run through the entire space of keys in what is known as a brute force attack. Since 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. Moore's law
Moore's Law
Moore's law describes a long-term trend in the history of computing hardware: the number of transistors that can be placed inexpensively on an integrated circuit doubles approximately every two years....
suggests that computing power doubles roughly every 18 to 24 months, but even this doubling effect leaves the larger symmetric key lengths currently considered acceptably well out of reach. The large number of operations (2128) required to try all possible 128-bit keys is widely considered to be out of reach for conventional digital computing techniques for the foreseeable future. However, alternative forms of computing technology are anticipated which may have superior processing power than classical computers. If a suitably sized quantum computer
Quantum computer
A quantum computer is a device for computation that makes direct use of quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. Quantum computers are different from traditional computers based on transistors...
capable of running Grover's algorithm
Grover's algorithm
Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....
reliably becomes available, it would reduce a 128-bit key down to 64-bit security, roughly a DES equivalent. This is one of the reasons why AES supports a 256-bit key length. See the discussion on the relationship between key lengths and quantum computing attacks at the bottom of this page for more information.
Symmetric algorithm key lengths
US Government export policy has long restricted the 'strength' of cryptographyExport of cryptography
The export of cryptography in the United States is the transfer from the United States to another country of devices and technology related to 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 , but it became easier to gain authorization to export to certain countries in 1999/2000.
When the Data Encryption Standard
Data Encryption Standard
The Data Encryption Standard is a block cipher that uses shared secret encryption. It was selected by the National Bureau of Standards as an official Federal Information Processing Standard for the United States in 1976 and which has subsequently enjoyed widespread use internationally. It is...
cipher was released in 1977, a key length of 56 bits
56-bit encryption
In computing, 56-bit encryption refers to a key size of fifty-six bits, or seven bytes, for symmetric encryption. While stronger than 40-bit encryption, this still represents a relatively low level of security in the context of a brute force attack....
was thought to be sufficient. There was speculation at the time, however, that the NSA
National Security Agency
The National Security Agency/Central Security Service is a cryptologic intelligence agency of the United States Department of Defense responsible for the collection and analysis of foreign communications and foreign signals intelligence, as well as protecting U.S...
has deliberately reduced the key size from the original value of 112 bits (in IBM's Lucifer cipher
Lucifer (cipher)
In cryptography, Lucifer was the name given to several of the earliest civilian block ciphers, developed by Horst Feistel and his colleagues at IBM. Lucifer was a direct precursor to the Data Encryption Standard...
) 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
EFF DES cracker
In cryptography, the EFF DES cracker is a machine built by the Electronic Frontier Foundation in 1998 to perform a brute force search of DES cipher's key space — that is, to decrypt an encrypted message by trying every possible key...
. 56 bits is now considered insufficient length for symmetric algorithm
Symmetric-key algorithm
Symmetric-key algorithms are a class of algorithms for cryptography that use trivially related, often identical, cryptographic keys for both encryption of plaintext and decryption of ciphertext. The encryption key is trivially related to the decryption key, in that they may be identical or there is...
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
Distributed.net
distributed.net is a worldwide distributed computing effort that is attempting to solve large scale problems using otherwise idle CPU or GPU time. It is officially recognized as a non-profit organization under U.S...
and its volunteers broke a 64-bit RC5 key in several years, using about seventy thousand (mostly home) computers.
The NSA's Skipjack
Skipjack (cipher)
In cryptography, Skipjack is a block cipher—an algorithm for encryption—developed by the U.S. National Security Agency . Initially classified, it was originally intended for use in the controversial Clipper chip...
algorithm used in its Fortezza
Fortezza
Fortezza is an information security system based on a PC Card security token. Each individual who is authorized to see protected information is issued a Fortezza card that stores private keys and other data needed to gain access...
program employs 80 bit keys.
DES has been replaced in many applications by Triple DES
Triple DES
In cryptography, Triple DES is the common name for the Triple Data Encryption Algorithm block cipher, which applies the Data Encryption Standard cipher algorithm three times to each data block....
, which has 112 bits of security with 168-bit keys.
The Advanced Encryption Standard
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
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 highly sensitive data.
In 2003 the U.S. National Institute for Standards and Technology, NIST, proposed that 80-bit keys should be phased out by 2015. As of 2005, 80-bit keys were allowed to be used only until 2010.
Asymmetric algorithm key lengths
The effectiveness of public key cryptosystems depends on the intractability (computational and theoretical) of certain mathematical problems such as integer factorizationInteger factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
. These problems are time consuming to solve, but usually faster than trying all possible keys by brute force. Thus, asymmetric algorithm keys must be longer for equivalent resistance to attack than symmetric algorithm keys. As of 2002, a key length of 1024 bits was generally considered the minimum necessary for the RSA encryption algorithm.
RSA Security
RSA Security
RSA, the security division of EMC Corporation, is headquartered in Bedford, Massachusetts, United States, and maintains offices in Australia, Ireland, Israel, the United Kingdom, Singapore, India, China, Hong Kong and Japan....
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 claims that 1024-bit keys are likely to become crackable some time between 2006 and 2010 and that 2048-bit keys are sufficient until 2030. An RSA key length of 3072 bits should be used if security is required beyond 2030. NIST key management guidelines further suggest that 15360-bit RSA keys are equivalent in strength to 256-bit symmetric keys.
The Finite Field Diffie-Hellman algorithm has roughly the same key strength as RSA for the same key sizes. The work factor for breaking Diffie-Hellman is based on the discrete logarithm problem, which is related to the integer factorization problem on which RSA's strength is based. Thus, a 3072-bit Diffie-Hellman key has about the same strength as a 3072-bit RSA key.
One of the asymmetric algorithm types, elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
, or ECC, appears to be secure with shorter keys than those needed by other asymmetric key algorithms. NIST guidelines state that ECC keys should 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 breakthroughs in solving the underlying mathematical problems 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.
The NSA specifies that "Elliptic Curve Public Key Cryptography using the 256-bit prime modulus elliptic curve as specified in FIPS-186-2 and SHA-256 are appropriate for protecting classified information up to the SECRET level. Use of the 384-bit prime modulus elliptic curve and SHA-384 are necessary for the protection of TOP SECRET information."
Effect of quantum computing attacks on key strength
The two best known quantum computing attacks are based on Shor's algorithmShor's algorithm
Shor's algorithm, named after mathematician Peter Shor, is a quantum algorithm for integer factorization formulated in 1994...
and Grover's algorithm
Grover's algorithm
Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....
. 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 RSA, Diffie-Hellman and elliptic curve cryptography
Elliptic curve cryptography
Elliptic curve cryptography is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz and Victor S...
. According to Professor Gilles Brassard, an expert in quantum computing: "The time needed to factor an RSA integer is the same order as the time needed to use that same integer as modulus for a single RSA encryption. In other words, it takes no more time to break RSA on a quantum computer (up to a multiplicative constant) than to use it legitimately on a classical computer." The general consensus is that these public key algorithms are insecure at any key size if sufficiently large quantum computers capable of running Shor's algorithm become available. The implication of this attack is that all data encrypted using current standards based security systems such as the ubiquitous SSL
Transport Layer Security
Transport Layer Security and its predecessor, Secure Sockets Layer , are cryptographic protocols that provide communication security over the Internet...
used to protect e-commerce and Internet banking and SSH
Secure Shell
Secure Shell is a network protocol for secure data communication, remote shell services or command execution and other secure network services between two networked computers that it connects via a secure channel over an insecure network: a server and a client...
used to protect access to sensitive computing systems is at risk. Encrypted data protected using public-key algorithms can be archived and may be broken at a later time.
Mainstream symmetric ciphers (such as AES
Advanced Encryption Standard
Advanced Encryption Standard is a specification for the encryption of electronic data. It has been adopted by the U.S. government and is now used worldwide. It supersedes DES...
or Twofish
Twofish
In cryptography, Twofish is a symmetric key block cipher with a block size of 128 bits and key sizes up to 256 bits. It was one of the five finalists of the Advanced Encryption Standard contest, but was not selected for standardisation...
) and collision resistant hash functions (such as SHA
Sha
For other uses, see Sha .Sha is a letter of the Cyrillic alphabet. It commonly represents the voiceless postalveolar fricative , like the pronunciation of ⟨sh⟩ in "sheep", or the somewhat similar voiceless retroflex fricative . It is used in every variation of the Cyrillic alphabet, for Slavic and...
) are widely conjectured to offer greater security against known quantum computing attacks. They are widely conjectured to be most vulnerable to Grover's algorithm
Grover's algorithm
Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O time and using O storage space . It was invented by Lov Grover in 1996....
. Bennett, Bernstein, Brassard, and Vazirani proved in 1996 that a brute-force key search on a quantum computer cannot be faster than roughly 2n/2 invocations of the underlying cryptographic algorithm, compared with roughly 2n in the classical case. Thus in the presence of large quantum computers an n-bit key can provide at least n/2 bits of security. Quantum brute force is easily defeated by doubling the key length, which has little extra computational cost in ordinary use. This implies that at least a 160-bit symmetric key is required to achieve 80-bit security rating against a quantum computer.
External links
- www.keylength.com: An online keylength calculator
- A discussion on the importance of key length (PDFPortable Document FormatPortable Document Format is an open standard for document exchange. This file format, created by Adobe Systems in 1993, is used for representing documents in a manner independent of application software, hardware, and operating systems....
file), available also in PostScriptPostScriptPostScript is a dynamically typed concatenative programming language created by John Warnock and Charles Geschke in 1982. It is best known for its use as a page description language in the electronic and desktop publishing areas. Adobe PostScript 3 is also the worldwide printing and imaging...
and other formatFile formatA file format is a particular way that information is encoded for storage in a computer file.Since a disk drive, or indeed any computer storage, can store only bits, the computer must have some way of converting information to 0s and 1s and vice-versa. There are different kinds of formats for...
s - A discussion on how much time we have available before we must take steps to protect against quantum computing attacks
- NIST crypto toolkit
- The FreeS/WANFreeS/WANFreeS/WAN, for Free Secure Wide-Area Networking, was a free software project, which implemented a reference version of the IPsec network security layer for Linux and other Unix-like operating systems. The project goal of ubiquitous opportunistic encryption of Internet traffic was not realized,...
project's discussion of key length - Burt KaliskiBurt KaliskiBurton S. "Burt" Kaliski, Jr. is a cryptographer, director of the EMC Innovation Network at EMC Corporation since its 2006 acquisition of RSA Security...
: TWIRL and RSA key sizes (May 2003)