# Kerberos 3DES string-to-key

Ken Raeburn raeburn at MIT.EDU
Tue Apr 28 15:28:04 EDT 2009

```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:

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

```