Subject: KDF definition and goal [was: [Cfrg] Fwd: Hash-Based Key Derivation]

From: David Wagner <[email-masked]>
Date: Tue, 25 Oct 2005 17:25:39 -0700 (PDT)

David Wagner writes:
>>Sure, the random oracle model and KDFs based on it are well  
>>accepted.  It would be nice to get something based on a reduction- 
>>based proof, though.
>
>I don't see how to get there without the random oracle if we want
>to be general purpose.

Sorry to respond to my own email, but--

It just occurred to me that I had a mental block here, and I wrote
too quickly.  I think what I said is not correct in full generality.
I believe that techniques from the extractors literature (e.g., the
Leftover Hashing Lemma) can be used to build provably secure KDFs in the
standard (reduction-based) model, as long as you are willing to put up
with randomized KDFs.  It is only deterministic KDF schemes where the
random oracle assumption seems to be necessary.

The simplest randomized construction is to let UH(.,.) be a 2-universal
hash, pick R randomly, publish R, and use UH(R,S) as your key, where
S is the secret input.  This is a KDF with no auxiliary inputs.  If we
wanted auxiliary inputs, presumably we can use F(UH(R,S),X), where F is
a PRF and X is an auxiliary input.  There are 2-universal hashes that are
provably secure in the standard model, without even needing any unproven
cryptographic assumptions.  This works so long as you have sufficient
min-entropy in S, though you need to set the parameters correctly.
Also, it does end up being wasteful of entropy: if I recall correctly,
you need 2x or 3x times as much entropy as you might naively think,
so in this sense it is much worse than the random oracle scheme.

One practical problem with randomized KDFs is that it can be a little
tricky to figure out how to pick R.  If two parties want to agree on a
session key, derived using the KDF, they both need the same value of R.
The obvious thing is to have R be chosen by one party and then sent in
the clear to the other.  That works if R was chosen honestly.  However,
if R is chosen maliciously by one of the parties, I think everything
could blow up and all security could be lost.  In some settings there is
only one party, so this might not be an issue.  In two-party settings,
there are still things you can do, but it might take some careful thought
to figure out how to deal with this issue.

I'm afraid I'm not a deep expert on the subject of extractors.  I know
that there are other subscribers to CFRG who can say more.  I hope
they'll chime in.

But the above practical issues make me think that there are important
advantages to deterministic KDFs, and these advantages are probably
significant enough that it is reasonable to put up with the random oracle
model in exchange.

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "D. J. Bernstein" <[email-masked]>
Date: 26 Oct 2005 09:09:44 -0000

David Wagner writes:
> S is the secret input.  This is a KDF with no auxiliary inputs.

For example, if you have a 1024-bit Diffie-Hellman result with 512 bits
of apparent entropy, and you want to convert it into a 256-bit key, you
can view it as a polynomial mod 2, multiply by x^256, and reduce the
result modulo a standard irreducible degree-256 polynomial.

On the other hand, if you have a 256-bit elliptic-curve-Diffie-Hellman
result x with 250 bits of apparent entropy, and you want to convert it
into a 512-bit key, then you'll have to take the time for some serious
cryptographic hashing, such as SHA-256(0,x),SHA-256(1,x).

Fortunately, serious cryptographic hashing isn't a bottleneck here. It
takes only a few thousand cycles, while Diffie-Hellman takes half a
million cycles.

Some people don't trust their cryptosystems to handle many packets under
a single key, so they produce a new key after (say) a megabyte of data.
But this rehashing is much faster than the packet processing, so again
it isn't a bottleneck.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

---

From: David McGrew <[email-masked]>
Date: Wed, 26 Oct 2005 06:20:02 -0700

Hi David,

> random oracle assumption seems to be necessary.

I was hoping this would be the case, though I didn't know enough  
about extractors.  And of course I was hoping to find something  
deterministic, and AFAICT the extractor-based approach can't provide it.

> so in this sense it is much worse than the random oracle scheme.

That's interesting; it could potentially harm the utility an  
extractor-based KDF.  Can you point to something in the literature  
which explains the inefficiency?

> tricky to figure out how to pick R.

Agreed, and a KDF wouldn't be very useful if it were difficult to use  
in protocols.

> If two parties want to agree on a

I agree that caution is needed, but I'm not sure that this is such a  
problem.  If we assume that Alice doesn't reveal a secret key, then  
it seems safe to assume that she will honestly choose the KDF- 
randomizer used to derive that key.

Has anyone studied this?  Seems like a result in either direction  
(showing a practical use of a randomized KDF, or showing security  
problems with their use in conventional protocols) would be interesting.

> significant enough that it is reasonable to put up with the random  

Yes, well put.

David

---

From: csjutla <[email-masked]>
Date: Wed, 26 Oct 2005 16:10:44 -0400 (EDT)

You can have deterministic extractors if you make some 
assumptions on the source. One of the most intriguing new results
is that if you have two independent sources each with certain
min-entropy, then you have a detereministic extractor. 

See Barak's homepage, or www.math.ias.edu/~boaz/Papers/BKSSW.html

Needless to say, these constructions are not very efficient.
Personally, I think SHA-1 makes a very good random oracle (despite
the recent attacks). As I point out in my recent paper
"Is SHA-1 conceptually sound?", it gets to be as good as one would
hope, and probably better than Discrete-log based "random oracles".

Charanjit