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?

  • $\begingroup$ The intended purpose was already easily found in the DES Wikipedia article; fortunately the later question is somewhat more interesting. $\endgroup$ – Maarten Bodewes Apr 3 '16 at 1:50
  • 9
    $\begingroup$ Conspiracy theory: The parity bits are a contrived excuse to shorten the key by 8 bits, decreasing security to the desired level. $\endgroup$ – Matt Nordhoff Apr 3 '16 at 3:59
  • $\begingroup$ @MattNordhoff Although I'm sure that was quite convenient to them, quite a few other ciphers used parity bits and other control bits as well (it's only "relatively" recently that ciphers have striven for a completely flat keyspace). I imagine, because they agreed on using only 56 bits, IBM simply decided to re-purpose those other 8 bits for something that was not uncommon at the time. $\endgroup$ – forest May 14 '18 at 3:34

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.

  • 2
    $\begingroup$ You'd also find in a hardware implementation the parity could be checked once every 16 rounds during operation. Because the C and D registers would shift a distance of 1 or 2 every round and the key wouldn't get loaded except when changed it'd be nice to know it's still intact over some long use interval. $\endgroup$ – user1430 Apr 3 '16 at 4:51
  • $\begingroup$ @user1155120 At first I thought, wow, that's interesting. But the longer I think about it (with regards to usage scenarios) the more glad I am that they removed the parity bits from the AES requirements. Very interesting observation though. $\endgroup$ – Maarten Bodewes Apr 3 '16 at 12:28
  • 1
    $\begingroup$ DES takes around 4700 NAND gates, it's a HW design from a time when a 1 MIPS machine was big iron. Using MSI TTL it could be implemented in an 8 x 10 inch printed circuit board. Adding 48 16 to 1 multiplexers to use static key storage would have tripled the size and power, easier to duplicate the entire thing and compare outputs or just test parity once a block. In today's SW crypto world the underlying HW reliability is better due to higher levels of integration and you can precalculate round keys and periodically test without interfering with traffic, having MIPS and memory to spare. $\endgroup$ – user1430 Apr 3 '16 at 20:18
  • $\begingroup$ @user1155120 Unless you are programming smart cards, in which case you mainly have a memory issue (8-10KB SRAM for high end contactless cards). $\endgroup$ – Maarten Bodewes Apr 4 '16 at 15:48
  • 2
    $\begingroup$ Some of us lived through that history. That we can find documentation provides perspective. $\endgroup$ – user1430 Apr 4 '16 at 19:33

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)

American Cryptology during the Cold War, 1945-1989, page 232

  • 2
    $\begingroup$ Very nice referenced materials. Now I have something interesting to read :) $\endgroup$ – gusto2 Apr 4 '16 at 7:06
  • 2
    $\begingroup$ DES's exact key size is important. As early as 1977, Diffie and Hellman sketched out a DES cracking machine in "Exhaustive Cryptanalysis of the NBS Data Encryption Standard" for \$20 million (\$80 million today). 8 bits were the difference between no one, a handful of top spy agencies like NSA, or any large group breaking DES. $\endgroup$ – Matt Nordhoff Apr 4 '16 at 10:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy