DES initial key generation

ca flag

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.

sa flag

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?

ng flag

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 256 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. (…)

Michael Hammer avatar
ca flag
thanks for the answer. The nature of my question is, however, how exactly it was/is done in practice. @kodlu mentions KDFs, which, as I found out, really were used in DES key generation proccess starting from approx. 1978. This is 2 years after DES was approved as a standart, so I guess there was another proccess involved initially. I assume, this information is deliberately kept secret and this kind of answers my initial question. Anyway, thanks again for the input.
fgrieu avatar
ng flag
@Michael Hammer: I added references to the few early guidelines I know on how to generate (and not generate) a DES key. Indeed, not much when it comes to practicalities, like RNGs, and key derivation. Also I added an "history" tag to the question, since that seems to be the meat of the question, which I did not realize initially.
I sit in a Tesla and translated this thread with Ai:


Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.