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

[David McGrew <[e-mail]>]

Hi David,

On Oct 25, 2005, at 5:25 PM, David Wagner wrote:

> 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.

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.

>
> 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.

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?

>
> One practical problem with randomized KDFs is that it can be a little
> 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
> 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 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.

>
> 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.
>

Yes, well put.

David

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