Subject: Re: [Cfrg] existing KDFs and their uses

From: "Blumenthal, Uri" <[email-masked]>
Date: Wed, 21 Oct 2009 11:33:22 -0400

So having this many different KDF's - why do we need one more, and how is it more secure (and more "random") than those already standardized??? 

----- Original Message -----
From: [email-masked] <[email-masked]>
To: Peter Gutmann <[email-masked]>; Dan Brown <[email-masked]>; David Jacobson <[email-masked]>
Cc: [email-masked] Eronen <[email-masked]>; [email-masked] <[email-masked]>; Hugo Krawczyk <[email-masked]>
Sent: Wed Oct 21 11:29:06 2009
Subject: [Cfrg] existing KDFs and their uses

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: Simon Josefsson <[email-masked]>
Date: Wed, 21 Oct 2009 18:48:25 +0200

> So having this many different KDF's - why do we need one more, and how is it more secure (and more "random") than those already standardized??? 

That is a reasonable question.  So far I haven't seen any answer to why
there is any need to make HKDF applicable to the medium-entropy password
scenario.  If I missed any argument in the recent flurry of e-mails,
please remind me.

/Simon

---

From: Zooko Wilcox-O'Hearn <[email-masked]>
Date: Wed, 21 Oct 2009 13:05:25 -0600

I'm speaking as a consumer of such standards rather than as a  
producer.  I have already invented my own KDF [1] because, as far as  
I know, the existing specs don't spell out how to generate a random  
key which isn't just a certain number of bytes or bits, but instead a  
random element from a group.  (Fortunately I haven't yet deployed  
this KDF that I invented so I am still free to change it.)

At this time I would probably prefer to use HKDF over the other KDF  
algorithms that I know of because the accompanying full paper [2]  
comes with much more thorough arguments about its theoretical  
security properties.  It isn't perfect for me!  As I mentioned in my  
initial questions, HKDF has the same omission that the others do in  
specifying how to generate keys which aren't just byte sequences, and  
it isn't entirely clear to me whether the security arguments for HKDF  
are predicated on the underlying primitive being HMAC, being a MAC,  
being a PRF, or what.  (I am more comfortable relying on AES or  
Salsa20 to be like an ideal cipher than relying on SHA-256 or SHA-512  
to be like an ideal hash function.)

Also I don't know which of those same security arguments apply to the  
other KDFs.

Also it isn't clear whether I should skip the extract step when my  
original key is already densely packed with nutritious entropy.

However, as things stand I would much rather use HKDF since it is  
apparent that someone (Hugo Krawczyck) has spent the effort to  
analyze and write down a bunch of relevant security arguments.   
HKDF's rigorous reductions (as far as I understand them) and its  
heuristic design both look good to me.

Regards,

Zooko

[1] http://allmydata.org/trac/pycryptopp/browser/pycryptopp/publickey/ 
ecdsamodule.cpp?rev=672#L269
[2] http://webee.technion.ac.il/~hugo/kdf/kdf.pdf

---

From: <[email-masked]>
Date: Wed, 21 Oct 2009 22:03:09 +0200

Uri and Peter,

This is not a new KDF; it's the IKEv2 PRF+ (also used in PANA and EAP-AKA').
So we're *not* proposing creating one more.
 
This is merely moving the KDF specification to a stand-alone document,
so it would be easier to reference it from new protocol specifications 
(that would like to avoid both (1) normative reference to RFC 4306, and 
(2) copy-pasting the specification from RFC 4306). 

(BTW, I'm speaking from personal experience here -- in RFC 5448, we 
ended up copy-pasting the specification...)

Best regards,
Pasi

> -----Original Message-----
> From: [email-masked] [mailto:[email-masked]] On Behalf Of
> ext Blumenthal, Uri
> Sent: 21 October, 2009 18:33
> To: [email-masked]'; [email-masked]';
> [email-masked]'; [email-masked]'
> Cc: [email-masked]'
> Subject: Re: [Cfrg] existing KDFs and their uses
> 
> So having this many different KDF's - why do we need one more, and how
> is it more secure (and more "random") than those already
> standardized???
> 
> 
> To: Peter Gutmann <[email-masked]>; Dan Brown
> <[email-masked]>; David Jacobson <[email-masked]>
> Cc: [email-masked] Eronen <[email-masked]>; [email-masked]
> <[email-masked]>; Hugo Krawczyk <[email-masked]>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 21 Oct 2009 14:17:16 -0700 (PDT)

Hi Pasi,

  You're generalizing IKEv2's KDF. Specifically, you're loosening
the requirements on the "salt" to the extract function. In IKEv2
each side contributes a nonce, which cannot be reused (!!), and the
concatenation of them becomes the key to a pseudo-random function,
which is the "extract" phase of HKDF. But in HKDF the "salt" can be
reused or it can not even exist.

  What properties does HMAC-SHA256(0^32, X) have that SHA-256(X | X)
doesn't?

  Dan.

---

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

Hi Zooko,

On Oct 21, 2009, at 12:05 PM, Zooko Wilcox-O'Hearn wrote:

> key which isn't just a certain number of bytes or bits, but instead  
> a random element from a group.

check out example 9.10 of http://www.shoup.net/ntb/ntb-v2.pdf	

David

> (Fortunately I haven't yet deployed this KDF that I invented so I am  
> still free to change it.)
>
> specifying how to generate keys which aren't just byte sequences,  
> and it isn't entirely clear to me whether the security arguments for  
> HKDF are predicated on the underlying primitive being HMAC, being a  
> MAC, being a PRF, or what.  (I am more comfortable relying on AES or  
> Salsa20 to be like an ideal cipher than relying on SHA-256 or  
> SHA-512 to be like an ideal hash function.)
>
> Also I don't know which of those same security arguments apply to  
> the other KDFs.
>
> [1] http://allmydata.org/trac/pycryptopp/browser/pycryptopp/publickey/ecdsamodule.cpp?rev=672#L269