Yet Another useful paper

[Steven M. Bellovin]

In article <12750 at bellcore.bellcore.com>, karn at ka9q.bellcore.com (Phil Karn) writes:
> 
> I'd also like to see a standard "key crunching"
> algorithm for transforming a password (or phrase) longer than 8 characters
> into a 56-bit DES key.

My original reaction, when someone raised this issue, was that it
wasn't necessary.  I'm no longer quite as certain.  The average user
seems to be using just 26 letters for a password, thereby using about
20% of the total key space.  Put another way, each character is only
using 26/128 of the total bit combinations available at that position.
To bring that to 56 bits, we need ~11.3 characters, which suggests a
minimum length for passwords.  The question, then, is what Phil asks:
how to crunch the 12 characters.  A better way to phrase the question
is this:  what algorithm will spread out the effect of each of the 12
characters?  Put that way, the answer is fairly obvious:  run each
character through DES.

DES has excellent distribution properties; on the average, changing a
single bit position in the input will change approximately half the bit
positions in the output.  I believe the same is true of key changes.
If so, what we can do is use each letter, with a lot of leading zeros,
to encrypt some constant string, then feed that output back in for the
next character.  If you want, you can take the final version and cycle
through another 25 times, as in the current code, but it isn't clear to
me that it's necessary.  It is necessary, I'd say, to always do the
same number of encryptions, in order to reduce the ability of an
intruder to get feedback from timing login attempts.  Other wrinkles
include using alternating encryption/decryption cycles; this tends to
produce better mixing.  (Of course, that would totally screw up
passwords with letter pairs, which suggests that each successive input
character be shift by a different number of bits.)