The HKDF paper does have a (very detailed) definition: See appendix B.
(I have a somewhat more complete/formal version which I can send to you off-line but I do not think it makes a significant difference for the understanding)
You can think of the KDF definition, essentially, as a computational extractor: It gets as input a sample from a Source of Keying Material SKM, is keyed with a salt value XTS (for eXTractor Salt), a length parameter L and outputs L bits that are computationally indistinguishable from the uniform distribution for any SKM that has sufficiently high entropy. Actually what differentiates a KDF from a computational extractor as above is that it gets another "context parameter" CTXT that represents some context information to be bound to the key (such as a session id, a protocol identifier, etc). This CTXT parameter can be chosen by the adversary and you want that the output of the KDF with same SKM but different CTXT values to be computationally independent (i.e., seeing the output with CTXT gives no efficiently computable information about the output with any other value CTXT' ).
The core technique for building such KDFs is to first extract a short but cryptographically strong key K from the SKM and then use K as a key to a PRF (with variable length output) and using CTXT as part of the input to the PRF.
If you want to use an "unpredictable function" as the single KDF you need to argue why that is secure in the above sense. Or why the definition sketched above is not the right one.
One last remark: If you want to use the SKM as a key to any function (as you seem to indicate), you need to argue that this "any function" has whatever properties you are assuming when keyed with a high-entropy but NOT UNIFORM (or not pseudorandom) key. ALso, note that as you say correctly, MAC functions are unpredictable but this is guaranteed only when they are keyed with a UNIFORM (or pseudo-random) key -- nothing can be said for high-entropy non-uniform keys -- and even then the output of the MAC must not be pseudorandom. If you use a PRF instead the MAC, then the output is pseudo-random but ONLY when keyed with a UNIFORM (or pseudorandom) key which you do NOT have in KDF context (if you had such a PRF key to start with you could use any PRF to expand it -- no need for extraction.
HugoOn Wed, Dec 9, 2009 at 1:15 PM, Zooko Wilcox-O'Hearn
<zooko at zooko.com> wrote:
There are a lot of questions that I don't yet understand the answers to. The first one is: what is the definition of a secure KDF?
I didn't see such a definition in the HKDF paper [1]. If we have a definition, then we can productively argue about whether this or that algorithm will meet the goal.
Clearly we haven't achieved this first step yet, since Hugo Krawczyk writes: "a MAC function does NOT exist without a secret key and a HKDF does NOT have a secret key.". This surprises me because I think of a KDF as having a secret key, and in particular HKDF has a secret key, named "SKM" on page 1 of hkdf.pdf.
Naor and Reingold [2] suggest that the formal definition of a MAC is an Unpredictable Function. I think they are right. They also show a black-box reduction from UF to PRF.
An Unpredictable Function is one where if I give you black-box access to it, i.e. you can invoke it but you can't examine its implementation, then you won't be able to predict what f(x) will return for some x that you didn't actually invoke it with.
Now an Unpredictable Function is an unkeyed thing, but a KDF (in my view) has a secret key which is unknown to the adversary. So let's model that by saying that we use the key to select one Unpredictable Function, f_s(), out of a family of Unpredictable Functions.
Does anyone agree that this notion of a function chosen from a family of Unpredictable Functions is a good enough definition of what we want out of our KDFs?
Regards,
Zooko Wilcox-O'Hearn
[1] Hugo Krawczyk: "On Extract-then-Expand Key Derivation Functions and an HMAC-based KDF" http://webee.technion.ac.il/~hugo/kdf/kdf.pdf
[2] Moni Naor, Omer Reingold: "From unpredictability to indistinguishability: A simple construction of pseudo-random functions from MACs" http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.121.6517
---
Your cloud storage provider does not need access to your data.
Tahoe-LAFS -- http://allmydata.org