Subject: [Cfrg] existing KDFs and their uses

From: David McGrew <[email-masked]>
Date: Wed, 21 Oct 2009 08:29:06 -0700

Hi Peter, Dan, and David,

> "Dan Brown" <[email-masked]> writes:
>
>> 2.  The menagerie of key derivation functions (i.e. DH-like shared  
>> secret
>> value to symmetric key, which unlike key generation are needed for
>> interoperability) such as IEEE KDF1 and KDF2, ANSI X9.63 X9.42,  
>> NIST SP
>> 800-56A, TLS-PRF, and IKE, and now HKDF,
>

Peter Gutmann wrote:
> You missed out the SSH one, and what S/MIME uses for its DH keying,  
> and there
> are probably several others as well used in lesser-known protocols.   
> In fact
> every protocol that I know of has invented its own KDF, incompatible  
> with
> every other KDF out there, thus my question about why we need yet  
> another one.

David Jacobson wrote:
> NIST SP 800-90, which is actually about random number generation,  
> specifies two extractors, which it calls Derivation Functions, in  
> Section 10.4.1 and 10.4.2. These are hash based and block cipher  
> based, respectively.  Both can deal with generating internal key  
> material wider than a single block.  (I write "internal key  
> material" because the data so generated is used to as input to the  
> expansion function.)

good points, and it looks like underestimated the number of KDFs used  
to extract keys from DH in my note yesterday.   It would be valuable  
to list and categorize all of these functions and their uses, to  
better understand the situation.  Collecting text from all of our  
emails, here is a start:
Uses:
  1. Generate one key from another. In this case, no extraction stage  
is needed.
  2. Generate a key from a DH shared secret.  In this case,  
computational extraction seems to be needed, because statistical  
extraction would be inefficient.

  3. Generate key material from a non-uniform random source.  In this  
case, either statistical or computational extraction could be used.

   4. Generate a key from a passphrase.

KDFs:
P_SHA256 from Section 5 of RFC 5246, The Transport Layer Security  
(TLS) Protocol, Version 1.2.  (HMAC in an OFB mode variant)   Uses #1  
and #2.
P_MD5 XOR P_SHA1 from Section 5 of RFC 4346, The Transport Layer  
Security (TLS) Protocol Version 1.1.  (HMAC in an OFB mode variant,  
XORed with MD5 in the same mode.)  Uses #1 and #2.
AES-CMAC-PRF-128 from RFC 4615, The Advanced Encryption Standard- 
Cipher-based Message Authentication Code-Pseudo-Random Function-128  
(AES-CMAC-PRF-128) Algorithm for the Internet Key Exchange Protocol  
(IKE).   Uses #1 and #2.

PRF+ from Section 2.13 of RFC 4306, IKEv2.   (HMAC in counter mode.)   
Uses #1 and #2.

SSH-KDF, Section 7.2 of RFC4253, The Secure Shell (SSH) Transport  
Layer Protocol.  (Hash function in counter mode.)  Uses #1 and #2.

AES-CM-PRF, Section 4.3.3 of RFC3711, The Secure Real-time Transport  
Protocol.

S/MIME DH KDF.  Section 2.1.2 of RFC 2631.  (Hash function.)  (Is this  
really the most up-to-date reference for SMIME DH?)   Uses #1 and #2.
Krb5-KDF from RFC 4402 A Pseudo-Random Function (PRF) for the Kerberos  
V Generic Security Service Application Program Interface (GSS-API)  
Mechanism.  (Hash function in counter mode.)  Use #1.

PBKDF1 (Hash function in OFB mode.) PBKDF2 (HMAC iterated, with all of  
the iterates XORed together.) from RFC2898, PKCS #5: Password-Based  
Cryptography Specification Version 2.0.   Use #4.

IEEE KDF1 (Hash function.)   Uses #1 and #2.

IEEE KDF2 (Hash function in counter mode.)   Uses #1 and #2.

ANSI X9.42 (Hash function.)   Uses #1 and #2.

ANSI X9.63 (Hash function in counter mode.)   Uses #1 and #2.

NIST SP 800-56A Concatenation-KDF and ASN.1-KDF (Hash function in  
counter mode.)   Uses #1 and #2.

NIST SP 800-90, Section 10.4 defines two extractors (hash function in  
counter mode, and a block cipher mode) and Sections 10.1, 10.2, and  
10.3 define some "expanders".   Use #3.

Additions and corrections are welcome.  Also, pointers to security  
analyses would be good to have, wherever they exist.
For each of these functions, it would be good to know a) under what  
conditions is it secure (e.g. what has to be assumed of the hash  
function) b) where and how is it used, c) does the protocol using it  
admit the replacement of its KDF, and if so, d) what is its interface  
(does it take a "salt" input, for example).
David

---

From: David McGrew <[email-masked]>
Date: Thu, 22 Oct 2009 13:54:55 -0700

Hi Peter,

On Oct 21, 2009, at 10:51 PM, Peter Gutmann wrote:

> David McGrew <[email-masked]> writes:
>
>> Uses:
>
> There's also a fifth use which I don't think is covered by any of  
> the other
> four, generate multiple sets of cryptovariables (keys, IVs, nonces  
> whatever)
> from a single block of something-or-other (key + nonce + other odds  
> and ends),
> which is what SSL/TLS and SSH do.

I was counting that as "generating one key from another"; this is the  
easy case cryptographically speaking, where we start with a  
(uniformly) random key.

>
>> S/MIME DH KDF.  Section 2.1.2 of RFC 2631.  (Hash function.)  (Is  
>> this really
>> the most up-to-date reference for SMIME DH?)
>
> Yes.  X9.42 was chosen for political reasons over RSA, so the spec  
> stipulated
> MUST X9.42, MAY RSA.  Implementors everywhere interpreted it as MUST  
> RSA,
> SHOULD NOT X9.42, and after awhile the spec stopped trying to  
> pretend it was a
> MUST as well, and then was allowed to fade into obscurity.
>
>> PBKDF2 (HMAC iterated, with all of the iterates XORed together.) from
>> RFC2898, PKCS #5: Password-Based Cryptography Specification Version  
>> 2.0.
>> Use #4.
>
> It's really all of them, since an iterated KDF is also a standard  
> KDF when
> iterations = 1.

I guess that I should be careful to distinguish between what a  
function is designed for and what it is used for.  Is PBKDF2 used with  
anything other than passwords as its "secret" input?

>
>> Additions and corrections are welcome.
>
> There's also the PKCS #12 PRF and the OpenPGP PRF.

Ah, I'd forgotten those.

>
> How obscure can the protocols get?  There's others I know of in  
> little-used or
> application-specific standards that probably don't carry much  
> weight, does
> anyone really care what (say) the CMP PRF looks like?

If it is specified for use on the Internet, and is actually used, it's  
worth cataloging.

thanks,

David

>
>> Also, pointers to security analyses would be good to have, wherever  
>> they
>> exist.
>
> Security analyses?  Do we do those?
>
> (The only ones I know of are for PBKDF2 and HKDF, although I haven't  
> looked at
> every available document on the PRFs.  For most that I've seen it's  
> just
> security by executive fiat).
>
> Peter.

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 22 Oct 2009 19:02:58 -0400

Peter,

> >RFC2898, PKCS #5: Password-Based Cryptography Specification Version 2.0.
> >Use #4.
>
> It's really all of them, since an iterated KDF is also a standard KDF when
> iterations = 1.
>

Correct. You can replace password with any initial keying material but then
you end keying the HMAC of PBKDF2 with this non-uniform keying material (say
a 160-bit entropy 2040 DH value or a very non-uniform string of 2Kbyes). Is
that good?
The mathematically correct way is to first apply the extractor to that key
material and then use it as a key.

I people think it would be useful we could add to the draft a section on
passwords, that will add a "slowing down" module to the KDF either between
the extract and expansion or as a replacement of the extract, but only for
the password case.

[....]

> Security analyses?  Do we do those?

Yes, we (sometimes) do!
(that is why we are having this discussion)

> (The only ones I know of are for PBKDF2 and HKDF, although I haven't looked
> at
> every available document on the PRFs.  For most that I've seen it's just

executive fiat is dead, long live formal analysis ;-)

Hugo

---

From: Hugo Krawczyk <[email-masked]>
Date: Thu, 22 Oct 2009 19:06:37 -0400

David, this work that you are doing in compiling usage scenarios and
existing KDFs is VERY useful. Hopefully, you can put it as a separate
document. I am very interested to know if there is anything, except
passwords, for which plain HKDF is insufficient.

I am interested in applications that require the KDF to generate regular
random keys rather than some structured elements (such as group elements
that require dedicated group-specific  techniques).

Thanks!

Hugo