[591] in Kerberos
Re: string_to_key: a better suggestion
daemon@TELECOM.MIT.EDU (Ted Anderson)
Wed Jan 11 09:46:48 1989
From: Ted Anderson <ota+@andrew.cmu.edu>
To: Bill Sommerfeld <wesommer@ATHENA.MIT.EDU>
Cc: kerberos@ATHENA.MIT.EDU
In-Reply-To: <8901102136.AA02634@ANUBIS.MIT.EDU>
I realized last night that my previously suggested StringToKey algorithm is
inadequate because it is fairly easy to invert. If the key corresponding to a
user's password is compromised in one realm and that user has the same password
in a different realm, that realm's key could be guessed with a probability of
about 1 on 2000 on each attempt. We can do much better than that at little
additional cost.
- As before, append the realm name to the password entered by the user.
- Pad this string to a multiple of 8 bytes with zeros. If the result is less
than 16 bytes (unlikely), duplicated the first 8 bytes to make the minimum
length 16 bytes.
- Use the first 8 byte block to initialize the encryption key.
- Encrypt each block, including the first, converting the result into a key to
use for the next block.
- The key produced from the last block is returned.
Since DES was designed to make discovering the key, given the encryption output,
or input or both, as difficult as possible, this algorithm is extremely
difficult to invert. It should do nearly as good a job at producing keys from
long strings as the cbc_cksum approach.
I didn't know that the kerberos string_to_key used the fan-folding only to
producing a key to use in calling cbc_cksum. That makes it much better than
using a constant key as my previous proposal did, but the fan-folding seems
needlessly complicated and error prone. The above approach is almost fool
proof, and only maybe 50% slower than the cbc_cksum alone. I don't know how
long the fan-folding takes. It is also more difficult to invert though the
difference between 2^-56 and 2^-(n*56) may not be a big deal. It may not be
quite as good at preserving the entropy of the password string because you
repeatedly discard 8 bits of every block (after encryption) to make the key for
the next block. I doubt that this is a big effect though.
Ted Anderson
