Hi Zooko, On Dec 9, 2009, at 10:15 AM, Zooko Wilcox-O'Hearn 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.
I agree that it would be useful to come up with a definition of what we expect from a KDF. I don't think the HKDF paper has a concise definition. The really important aspect to capture is that of the computational extractor. If I recall correctly, that paper cites a definition of computational min-entropy, but the definition was not immediately applicable (or at least I couldn't see how to apply it).
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.
The important aspect here is that SKM is not uniformly random, but instead has a min-entropy that has a known lower bound.
A document that defined of a KDF and that explained (computational) min-entropy and (computational) extractors would be valuable. If we can find enough people to write and review this work, it would be valuable to have it as a CFRG draft. I think that a good approach here would be to write it up as something like a requirements document, saying what applications the KDF is targeting (this was already discussed on the list), what assumptions go into its use, and what security properties it should have. This approach would make the new work a nice complement to the HKDF draft. Any other thoughts?
David
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 _______________________________________________ Cfrg mailing list Cfrg at irtf.org http://www.irtf.org/mailman/listinfo/cfrg