Purpose of DES parity bits

Question

DES has a 64-bit key size, but only 56 of those are used during encryption. The other 8 are "parity bits".

What was the intended purpose of the party bits, and why are they no longer used in modern ciphers?

Answer 1

They are there to check if the key was indeed correctly retrieved. It could for instance be that the key is a result of key decryption or key agreement. In that case, or simply during transmission, wrong keys are used. According to NIST FIPS 46-3:

The 8 error detecting bits..."

Or even better, Wikipedia states ANSI INCITS 92-1981), section 3.5:

One bit in each 8-bit byte of the KEY may be utilized for error detection in key generation, distribution, and storage. Bits 8, 16,..., 64 are for use in ensuring that each byte is of odd parity.

So you see, they're there to protect against errors reinstating/recreating the key.

---

Nowadays transmission errors are usually taken care of at the transport layer. As e.g. TCP/IP (and most other network protocols) already deliver a reliable transport mechanism the need for the parity bits has been strongly reduced. Things like parity checking are not seen as part of a cipher definition. Nowadays it is seen as an unnecessary nuisance, complexity where it isn't required.

In the unlikely event that you'd ever need to perform parity or CRC checking it is of course easy to add the necessary bits; as long as you strip them away again before using the key.

Answer 2

Parity of DES key bytes was introduced on request of US authorities during the design of DES in the late 1970s:

• it mitigates the risk of accidental key alteration; in particular, any all-zeros or all-ones byte of the key is rejected by the mandatory odd parity check, and any one-bit alteration is caught, which are advantages from a functionality perspective;
• it makes brute force key search for single DES 256 times easier than if these bits where true key bits, which is an advantage from an attacker's perspective; the NSA wanted something that it could brute-force if necessary, and the additional 256 factor would have made that overly costly for the times (see Matt Nordhoff's comment).

A very strong argument about the reality of the second motivation is on page marked 232 of a partially declassified book edited by the NSA: American Cryptology during the Cold War, 1945-1989 (linked here):

Could a public encryption standard be made secure enough to protect against everything but a massive brute force attack, but weak enough to still permit an attack of some nature using very sophisticated (and expensive) techniques? NSA worked closely with IBM to strengthen the [DES] algorithm against all except brute force attacks and to strengthen substitution tables, called S-boxes. Conversely, NSA tried to convince IBM to reduce the length of the key from 64 to 48 bits. Ultimately, they compromised on a 56-bit key.

Here is the bottom of that page (now fully declassified; see what we got earlier)