DES DECERTIFICATION Q&A

[NOTE: DES IS NOT OFFICIALLY DECERTIFIED YET -- THERE IS A DISCUSSION PERIOD CURRENTLY GOING ON.]

NIST is planning to decertify the use of the single DES block cipher in FIPS-approved products. The NIST decertification will provide additional urgency to ongoing efforts to replace single DES in commercial products. Because the single DES algorithm is widely used, particularly in the financial sector, upgrades may require significant upgrades to legacy hardware, software, and protocols.

Cryptography Research has compiled some of the questions we have received about the security weaknesses in DES and the effort to transition to stronger algorithms.

Q: Was there a new attack that motivated the decertification by NIST?
A: The DES algorithm itself has proven adequate for its 56-bit key length. The inadequacy of the DES key length is the only known reason for the decertification.

Q: How vulnerable are 56-bit keys?
A: 56-bit keys are practical to break using current technology. In 1998, Cryptography Research designed the $220,000 DES keysearch machine Deep Crack. This machine could test about 90 billion DES keys per second, taking an average of 111 hours to find a given DES key.

Moore's Law predicts that a similar machine built in 2004 would run 16 times faster (7 hours per key). In practice, key search machines improve faster than Moore's Law because their performance is the product of the clock rate and the circuit area. Assuming a doubling in performance every 12 months, a modern machine would run 64 times faster than Deep Crack and would average 1.7 hours per key.

Attacks using networks of ordinary PCs have also been common for several years and are becoming increasingly practical. As a result, DES keys could be broken by virtually any government or organization, or by people who have organized large numbers of PCs via the Internet.

Q: Is triple DES also vulnerable to brute force attacks?
A: No. Triple DES is 2^56 (or 72,057,594,037,927,936) times more resistant to brute force key searching attacks than single DES.

Q: When upgrading, is it better to switch to triple DES or to AES?
A: NIST is generally encouraging vendors to switch to AES, although either choice can provide good security. In legacy systems, triple DES may be simpler to implement, since it has the same block size as DES and can reuse hardware DES implementations. AES has a 128-bit block size which can provide some security benefits, particularly if extremely large amounts of data (e.g., several gigabytes or more) are being processed. Both triple DES and AES both have key lengths that are sufficiently long that the risk of brute force attacks is believed to be negligible compared to the risks of compromise due to implementation bugs or other flaws.

Q: Should products be upgraded to support both triple DES and AES?
A: In most cases, one algorithm is enough. Supporting multiple algorithms adds complexity, increasing the risk of security failures. Also, if attackers can choose which algorithm or mode to attack, there is no security benefit to supporting multiple algorithms.

Q: What about algorithms other than triple DES and AES?
A: In most cases, triple DES or AES will be the best choice because these algorithms are well-reviewed, widely believed to be mathematically strong, efficient, free, standardized, and officially-endorsed for government use. Alternatives are generally inferior in one or more of these attributes.

Q: What is the relationship between key length and security?
A: For most symmetric ciphers (block ciphers and stream ciphers, but not public key algorithms), each additional key bit doubles the effort required for a brute force attack. For example, a 56-bit key is 65536 times harder to find than a 40-bit key. (For public key schemes, the relationship between key lengths and security is algorithm-specific.) If brute force is the easiest attack against a system, then longer keys yield better security. Longer keys do not help against most other vulnerabilities, such as software bugs, power analysis attacks, and cryptanalysis. If brute force is not the easiest attack (as is often the case), longer keys generally provide no security benefit.

Q: What is the history of DES?
A: DES was originally proposed by the U.S. National Institution of Science and Technology as Federal Information Processing Standards Publication 46 (FIPS PUB 46) in 1977. DES was based on an IBM cipher called Lucifer, but included modifications by the U.S. National Security Agency. The DES standard was initially controversial due to the short key length and concerns that the cipher might have been intentionally weakened by the National Security Agency. While the latter concerns appear to have been unfounded, the key length ultimately proved to be the Achilles heel of DES.

Q: Should NIST have decertified DES years ago?
A: In an ideal world, DES would have been decertified earlier, but the algorithm is used in many hardware devices and protocols that cannot be upgraded easily.

Q: Can the problem be fixed by adding rounds or changing the DES algorithm?
A: No.