Subject: Re: DES key derivation

From: "Ron Hoffman" <[email-masked]>
Date: Wed, 3 Apr 2002 09:23:08 -0500

It is taken directly from the MIT Kerberos V5 1.2.2 code.  Look at
k5_des_make_key() in src/lib/crypto/enc_provider/des.c.  This is the
situation where the key is derived from 56 bits of key material.  The
algorithm is different when the key is derived from a password string
(mit_des_string_to_key()).  I'll take a look at the DES FIPS since I
think that would be the correct way to generate the key for DES-MAC and
DES-CBC.

Ron

----- Original Message -----
From: "Ted Anderson" <[email-masked]>
To: "nfsv4-wg" <[email-masked]>; "Ron Hoffman"
<[email-masked]>
Sent: Wednesday, April 03, 2002 7:38 AM
Subject: Re: DES key derivation

> This description doesn't match my recollection of how Kerberos 4
works.
> In the AFS implementation of the Kerberos server, which interoperates
> with the MIT version, the keys are derived by hashing the password
then
> forcing odd parity.  This latter function[1] computes the parity of
each
> byte and stores it in the least significant bit.  I recall that this
> mapping from 56 to 64 bits is specified in the original DES FIPS[2].
> While it is possible that this changed in K5, I doubt it.
>
> On Tue, 26 Mar 2002 16:42:29 -0500 "Ron Hoffman"
<[email-masked]> wrote:
> > However, Kerberos takes a different approach and treats the 56-bits
of
> > key material as 7 blocks of 8 bits each.  The high-order 7 bits of
> > each key material byte remain unchanged and are used for the first 7
> > bytes of the DES key.  The final key byte is formed from the
low-order
> > bits of each key material byte.  The parity bits are then set,
> > overwriting the low-order bit in each byte.
>
> Where did you find this algorithm described?
>
> Ted Anderson
>
> [1]
http://www.openafs.org/cgi-bin/cvsweb.cgi/openafs/src/des/key_parity.c
> [2] http://www.itl.nist.gov/fipspubs/fip46-2.htm
>

---

From: "Ron Hoffman" <[email-masked]>
Date: Wed, 3 Apr 2002 09:56:55 -0500

I don't see anything pertinent in the DES FIPS.  It describes the format
of the 8-byte key (7 key bits and 1 parity bit per byte).  But unless I
missed it, it doesn't say how those key bits are set from a raw 56-bit
value (and it really doesn't matter as far as DES itself is concerned).
So the question really relates to RFC 2025.  The RFC tells how to
generate 56 bits of key material but doesn't specify how those bits are
mapped into the 8-byte DES key.  The RFC also doesn't say what happens
if the generated key is a weak DES key.

The OpenSSL code has a DES key generation routine.  However, this
routine generates 64 bits of key material and then sets the correct
parity on each byte (essentially throwing away 8 of the key material
bits)

So, I've come up with 3 choices so far:

1) Generate 56 bits using the RFC 2025 generation algorithm and then map
these bits in order to the key bits in the 8-byte DES key (skipping the
parity bit in each byte).  There are two sub-variations here where the
mapping is done from MSBit to LSBit or from LSBit to MSBit in each tye.
I think this is the correct interpretation with the mapping done from
MSBit to LSBit.

2) Generate 56 bits using the RFC 2025 generation algorithm and use the
7-byte value as the first 7 bytes of the DES key.  Generate the eighth
byte from the LSBit of each of the key material bytes.  There are again
two sub-variations (Kerberos generates the last byte from LSBit to
MSBit).

3) Generate 64 bits using the RFC 2025 generation algorithm and then
just set the proper parity in each byte.

In any case, weak DES keys need to be handled because some crypto
implementations check for weak keys (Kerberos does this check, for
example, and will reject a weak key).  Since my SPKM and LIPKEY support
will be part of our Kerberos product, I'll be using the Kerberos crypto
support.  So for now, I'm using option 2 (the Kerberos k5_des_make_key()
routine) simply because it is already available.  It wouldn't be a big
deal to switch to another option as long as we can agree on one.  I
could also write a new DES routine without the weak key checking if that
is needed (I'm currently using the Kerberos DES support which will
reject a weak DES key).

Ron ([email-masked])

----- Original Message -----
From: "Ron Hoffman" <[email-masked]>
To: "nfsv4-wg" <[email-masked]>; "Ted Anderson"
<[email-masked]>
Sent: Wednesday, April 03, 2002 9:23 AM
Subject: Re: DES key derivation

---

From: RJ Atkinson <[email-masked]>
Date: Wed, 3 Apr 2002 10:03:09 -0500

> I think this is the correct interpretation with the mapping done from

	This sounds right to me, where "skipping the parity bit
in each byte" means don't waste any of the 56 bits of entropy
on a parity bit position -- instead set the parity bit correctly
based on the 7-bits of entropy in that byte (where the 7
bits are part of the 56 bits previously generated).

Ran

---

From: RJ Atkinson <[email-masked]>
Date: Wed, 3 Apr 2002 10:08:27 -0500

> So, I've come up with 3 choices so far:

	Whenever the documents get edited, the selected choice
ought to be made crystal clear in the next document version.
That we have more than 1 choice means the current documents
are not adequately clear.

IMHO,

Ran

---

From: "Ron Hoffman" <[email-masked]>
Date: Wed, 3 Apr 2002 11:20:56 -0500

Sounds good to me.  I'll map the bits using option 1 then (going from
MSBit to LSBit in each byte).  I'll still check for a weak key after
constructing the 8-byte key and exclusive-or the last byte with x'f0' so
that Kerberos will be happy with the key (we shouldn't use a weak key
anyways to encrypt application data)

Ron

----- Original Message -----
From: "RJ Atkinson" <[email-masked]>
To: "Ron Hoffman" <[email-masked]>
Cc: "nfsv4-wg" <[email-masked]>; "Ted Anderson"
<[email-masked]>
Sent: Wednesday, April 03, 2002 10:03 AM
Subject: Re: DES key derivation