Kerberos 3DES string-to-key

[Ken Raeburn]

On Apr 28, 2009, at 13:55, Ethan Heilman wrote:
> I'm doing a security project on n-folding within kerberos, and I've  
> I'm
> trying to understand the designer's intentions.

Great!  It could use more analysis.

> I was wondering if any of the developers of kerberos could answer a  
> design
> question for me.

The 3DES and n-fold stuff was put together many years ago -- I think  
in the early to mid '90s.  I don't know if any of the people behind  
the design of these specific bits are active on the mailing lists  
these days, so we may not be able to address the original intent or  
thought processes.

> Kerberos uses an interesting string-to-key method for 3DES.

"Interesting" is a good word. :-)

> This key-string-method uses a key expansion algorithm called n- 
> folding to
> reduce an arbitrary length string to a fixed length key. This  
> operation
> sounds very similar to a cryptographic hash function. In fact in the
> documentation provided below, the string-to-key function is claimed  
> to be a
> one way function.

> Why is n-folding, a key expansion algorithm, used instead of a  
> cryptographic
> hash function?

First, you should look at RFC 3961, not the text file you found.  That  
text file doesn't describe what we're actually using in Kerberos these  
days.

The pseudocode for DES3string-to-key in RFC 3961 includes:

      s = passwordString + salt
      tmpKey = random-to-key(168-fold(s))
      key = DK (tmpKey, KerberosConstant)

So n-fold scrambles the salt and password together.  The DK function  
basically iteratively encrypts the KerberosConstant (64-fold of the  
string "kerberos") and uses the output blocks concatenated to generate  
the final key.

There are certainly ways in which n-fold could work poorly here.   
Consider a long pass phrase, which when combined with the salt string  
produces a string that's 2*21 or 3*21 bytes (2*168 or 3*168 bits)  
long.  Then 168-fold just chops it into two or three chunks and adds  
them together bitwise.  Given ASCII input, the value range in each  
byte will likely be limited to 32-122 (and usually would exclude some  
of the punctuation characters in that range), so with 2*21 input bytes  
-- two blocks being added together -- each output byte will probably  
be limited to 64-244, about 70% of the possible values or 7.5 bits per  
byte; this from over 8000 possible pairs of ASCII input characters.

If pass+salt isn't a multiple of 21 bytes, then 168-fold gets a little  
more interesting, with multiple rotated copies of the input bit  
string, and individual input bits being added against different sets  
of other input bits.  But how good is this *really* at preserving  
entropy?

The n-fold algorithm came from a paper by Uri Blumenthal and Steve  
Bellovin.  You might also take a look at their paper.

> Is there a performance reason I am missing? Are the security  
> requirements
> different?

The more one works on Kerberos, the more one wishes that modern  
cryptographic algorithms and know-how were available in the mid-80s  
when Kerberos was first being developed. :-)  Performance concerns  
were probably behind a number of decisions (simple key generation  
functions, certain fields not getting encrypted or hashed) that we  
might do differently today if starting from scratch.  These days, when  
designing a new Kerberos cryptosystem, one should probably use "off- 
the-shelf" functions and modes as much as possible, for both security  
and performance reasons.

Ken

-- 
Ken Raeburn / raeburn at mit.edu / no longer at MIT Kerberos Consortium