DES parity bits

Question

The key is nominally stored or transmitted as 8 bytes, each with odd parity. According to ANSI X3.92-1981 (Now, known as 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.

As I understand this Wikipedia text, in each byte of DES there are essentially only 6 bits, as seventh one is determined because of parity. Does this mean that there are essentially only 2^48 possible keys for DES (8 parity bits, 8 determined because of parity and 48 random ones)?

Answer 1

Every 8th bit is the odd parity of the previous 7 bits. This means that there are 8 parity bits, and 56 random bits adding up to a total of 64. The keyspace is thus 2⁵⁶ and the effective key size is 56 bits.

Answer 2

No you are not correct. The bit in each byte used for "error detection" is the parity bit. Note that bits are generally counted strangely, using an offset of 1 rather than 0 for the first, leftmost bit - commonly the most significant bit.

So if you'd have a byte array then every least significant bit of every byte is the parity bit. This bit is set in such a way that every byte has an odd number of bits set after the operation. In other words, it is set if the count of the other bits is even and unset if not. Or it is flipped if the amount of all 0 bits or 1 bits is even - which amounts to same thing.

So say you'd have the following single DES key:

pos: 1234 5678 9 .. etc. .... .... .... .... .... .... .... .... .... .... .... ....
bin: 0000_0000 0000_0001 0000_0010 0000_0011 0000_0100 0000_0101 0000_0110 0000_0111
hex:    0    0    0    1    0    2    0    3    0    4    0    5    0    6    0    7
1's:         0         1         1         2         1         2         2         3

then the result is after parity adjustment is this:

pos: 1234 5678 9 .. etc. .... ...P .... ...P .... ...P .... ...P .... ...P .... ...P
bin: 0000_0001 0000_0001 0000_0010 0000_0010 0000_0100 0000_0100 0000_0111 0000_0111
hex:    0    1    0    1    0    2    0    2    0    4    0    4    0    7    0    7
1's:         1         1         1         1         1         1         3         3

So as there are 8 bytes, and one bit of every byte is used for parity, each byte has 7 bits used in the cipher itself. There are 64 / 8 = 8 bytes with 7 bits each, 8 * 7 = 56 bits effective key size.

Parity adjustment and validation depends on the library, but commonly you do need to at least present 8 full bytes / 64 bits.