[Cfrg] KDF algorithm and properties

["Allen Pulsifer" <pulsifer3 at comcast.net>]

About a year ago I had a need for a KDF, and was unable to find a algorithm
that met my requirements.

Enclosed is a description of what I came up with.  I offer it in case there
might be something useful in this work.  The algorithm is my original work,
although it is of course based on the work of others.  To the extent it is
original, it is donated to the public domain.

Allen Pulsifer

-----------------------------------------------------

Key Derivation Algorithm (KDF)

The following describes a Key Derivation Algorithm, or KDF.  The KDF is
intended to be used in two ways: (1) to derive a long-term Master Secret
from a short-lived shared secret, and (2) to derive secure channel session
keys from a shared secret and a seed.

The inputs to the KDF are some random secret data plus a seed, and the
output is some new random-looking data.  The desired properties for the KDF
are:

1. The KDF accepts an arbitrary-sized secret and seed as inputs.

2. The KDF can be used to generate an arbitrary amount of output data.

3. The KDF is deterministic, which means if two parties run the function on
the same input data, they will get the same output data.

4. The KDF is a Pseudo Random Function (PRF), which means the output "looks"
random.  It is essentially impossible to predict the output without knowing
the inputs.  In addition, to the extent possible, the output bits are
independent.  As a result, if the KDF is used to output a session key, an
attacker who wanted to use brute force computation to discover the value of
that key would have to assume all possible values are equally likely.
Finally, if the KDF is used to derive more than one key, an attacker who
finds the value of one key can't use it to help find the value of the other
keys.

5. When KDF is used to derive a single N-bit key, the key actually has N
bits of entropy.  This is not true when there is a "skinny pipe" somewhere
in the KDF.  For example, some applications such as SSL use HMAC-SHA1 for a
KDF, with the secret is used as the HMAC key.  In the HMAC function, the
first operation is to pad and hash the secret.  An attacker who wants to try
all possible outputs of this KDF only needs to try all 2^160 possible values
for SHA1(secret).  Therefore, HMAC-SHA1(secret, seed) has only 160 bits of
entropy, no matter how many bits of entropy are in the secret.  In the
desired KDF, if a 512-bit secret is used to derive a 256-bit key, the key
can actually take on each of the 2^256 values with equal probability, which
means that is has 256 bits of entropy.

6. If we use the KDF to derive many keys, the joint entropy of all of the
keys equals the entropy of the secret.  To state this another way, if we put
a 512-bit secret into the KDF, we want to get 512 bits of entropy out.

7. The KDF "protects" the input data.  This is important when using a
long-term Master Secret to derive session keys.  Even if an attacker is able
to deduce the session keys, it should be impossible to reverse the key
derivation to determine the Master Secret.  This property also applies to
any subset of the Master Secret, so an attacker who knew one or more session
keys could not use that information to deduce any part of the Master Secret.
This is also known as a "piece-wise" attack, and would be a problem, for
example, if the KDF only used part of the input secret to derive each key,
instead of using the entire input secret for every key.

8. Changing the value of the seed results in a completely different output.
Furthermore, the output with one seed provides as little help as possible to
an attacker trying to predict the output with a different seed.

9. The KDF uses at its core a proven or widely accepted cryptographic
algorithm with well-known properties.


The KDF is as follows:

	KDF(secret, seed, trunc) = T(1) + T(2) + T(3) + ...
		
		where T(i) = HMAC-SHA1-trunc(i + seed + secret, seed)

		and "+" represents the concatenation of binary data

This KDF satisfies has all of the desired properties.  SHA1 is widely
considered to be a good PRF, and the secret is protected by using it as the
HMAC key.  To further protect the secret, the seed is included within the
HMAC key so that this key changes each time the secret is used.  A long term
secret can also be protected by truncating the HMAC output to "trunc" bits
when deriving session keys.  For example, when trunc = 64, only 64 bits of
each HMAC output are used in the KDF output.  This decreases the amount of
information available to an attacker regarding each iteration of the HMAC.
The KDF output can be as long a required by concatenating T's.

As discussed earlier, the output of SHA1 is 160 bits and the entropy of the
HMAC key is effectively reduced to 160 bits.  However, by prefixing the HMAC
key with i, the different bits of the secret contribute to the various
outputs T(i) in unpredictable ways, even if secret is larger than 160 bits.
The net affect is that the concatenated T's have as much entropy as the
secret.  To the extent that changing the prefix of the HMAC key results in
independent outputs, the T's are also independent.

This KDF is an improvement on the PRF used in SSL/TLS, IPsec and SSH because
the entropy of its output is not limited to 160 bits.  It is an improvement
on the PRF used in SSH because the secret is protected by HMAC, which is
more secure than an unpadded hash.


_______________________________________________
Cfrg mailing list
Cfrg at ietf.org
https://www1.ietf.org/mailman/listinfo/cfrg