DES initial key generation

Question

I am working through a textbook on crypto, currently on DES section. What bothers me is that there was no explanation about where do we get initial 64-bit key from. This question is also very hard to google, because you get straight away redirected to all sorts of articles about key schedule, where the existance of the initial 64-bit key seems to be always preassumed, as in the book. I'd really appriciate any input about initial key. Thanks in advance.

Answer 1

In any cipher system the key is required to be generated by a uniformly random process, and be equidistributed, each bit equally likely to be $0$ vs $1$ as well as independent of other bits.

Specifically for DES, note that it is actually a 56 bit uniform key that is randomly generated, the rest of the key bits are parity bits.

In practice, one option is to use a key derivation function, seeded by a password and other inputs as appropriate, see here.

A related question: How are the keys used in cryptography generated?

Answer 2

In symmetric cryptography, including DES, the standard assumption is that the key is randomly and secretly selected among the set of valid keys.

In DES, there are three variations of the set of valid keys, depending on presentation of DES:

• The set of 56-bit bitstrings; in this presentation, all bits potentially have an effect on the output.
• The set of 64-bit bitstrings; in this presentation, only 56 bit can have an effect on the output.
• The subset of 64-bit bitstrings such that when split into 8 segments of 8 bytes, the XOR of the 8 bits in each segment is 1. This is the official method in FIPS PUB 46:

  The key is generated in such a way that each of the 56 bits used directly by the algorithm are random and the 8 error detecting bits are set to make the parity of each 8-bit byte of the key odd, i.e., there is an odd number of "l"s in each 8-bit byte.

The main historical reason for this mess is reducing the keyspace of DES to 56 bits so that US authorities would not have excessive trouble breaking it; see this.

Section 6 of FIPS PUB 74 details:

(…) Certain fundamental guidelines should be followed in generating keys. Every bit of the active key should be generated or selected at random. Every possible combination of bits in the active key should have equal probability of being selected, and each key should be generated independently of every other key. The security provided by each of the possible 2⁵⁶ keys is the same although, in certain situations, the dual keys noted earlier may be undesirable because of the characteristic of the algorithm which makes the encrypt and decrypt functions identical for these keys. Repeating a short key to make a 56-bit key severely decreases security. (…)