Subject: Re: [Cfrg] draft-irtf-cfrg-kdf-uses-00

From: Zooko Wilcox-O'Hearn <[email-masked]>
Date: Tue, 2 Mar 2010 15:06:47 -0800

Folks:

Just for your information, in the Tahoe-LAFS project we've decided  
not to use HKDF after all for our key-derivation needs.

We do not need extraction, only expansion—all of the seeds (or  
"master keys") that we input to a KDF are unguessable, evenly  
distributed values of exactly the appropriate size.

Therefore, we now intend to use a KDF which we think is simple,  
widely understood, efficient, and with a nice security reduction  
argument. Our proposed KDF is: let the resulting key be the first few  
bytes of the XSalsa20 keystream keyed by the master key.

If this KDF is distinguishable from random then this immediately  
implies a significant weakness in XSalsa20 as a cipher. XSalsa20  
exhibiting such a weakness would be very surprising.

We can use test vectors from other people's XSalsa20 implementations  
to check the correctness of our KDF in our unit tests.

Currently we are working on the next problem—which is out-of-scope of  
HKDF standardization—of how to securely, efficiently, and testably  
generate an integer of the appropriate range to use as the private  
exponent in elliptic curve DSA. You can see our notes about how to do  
that here:

http://allmydata.org/trac/pycryptopp/ticket/2#comment:13

Thank you very much to everyone, especially Dave McGrew and Hugo  
Krawcyck for patiently answering my questions about HKDF.

Regards,

Zooko Wilcox-O'Hearn
---
Your cloud storage provider does not need access to your data.
Tahoe-LAFS -- http://allmydata.org

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 24 Mar 2010 11:42:11 -0700

David suggested I bring this discussion to the list.

As I have mentioned previously on this list, I want a CMAC based KDF 
where the key was derived from a DH exchange.  As you will see below, 
per this ID, CMAC can only be used as a KDF (and this is the case in its 
use in NIST 800-108) if the key is uniformly distributed (use case #3).

So scan down to the important stuff....

On 03/24/2010 07:30 AM, David McGrew wrote:
> Hi Robert,
>
> On Mar 23, 2010, at 6:55 PM, Robert Moskowitz wrote:
>
>> Further questions...
>>
>> Does ECDH keys also fit in use case #2?
>
> yes, this use case was meant to cover any public key algorithm whose 
> output is a value that is secret, but which is not a binary string 
> that is uniformly randomly distributed.
>
>>
>> Can you define a KDF for #2 that uses CMAC? It seems from your 
>> document that current there is not one.
>>
>
> Not if you want provable security.
>
> From http://people.csail.mit.edu/dodis/ps/hmac.ps:
>
> The Extraction Properties of CBC-MAC Mode. We show, in Section 3, that 
> if f is a random permutation over
> {0, 1}^k and X is an input distribution with min-entropy of at least 
> 2k, then the statistical distance between F (X) (where F represents 
> the function f computed in CBC-MAC mode over L blocks) and the uniform 
> distribution on {0, 1}^k is L · 2^{−k/2}.
>
> In practice, using this proof of security would mean that public keys 
> providing 4*n bits of security would be needed in order to be provably 
> secure at the n-bit level.  For ECC, this would mean we'd need to use 
> 1024-bit keys (four times 256 bits) in order to claim 128 bits of 
> security based on something "provable".  So in short it seems that if 
> one demands "provable security", this is not a good way to go.

I ASSuME you mean used in an ECDH key agreement to get the non-uniformly 
distributed key?

>
> There might be more recent results, but I'm not aware of any.   It 
> would be useful to take this discussion to the list, if you don't 
> mind.  "I want an AES-based KDF for use case #2" is a good topic for 
> discussion.

OK, I am trying to Grok this...

Does CMAC have the same extraction properties as CBC-MAC?

Someone mentioned that you should first run the DH output through a 
function that uniformly distributes the randomness, then feed it into 
CMAC.  But what would that be if not a hash function?  And it has to be 
tight enough code that it is a reasonable alternative.

Is my only alternative for a 'light weight keying' to pitch DH and just 
deliver a random key encrypted with a public ECC key?   Then I fit in 
case #3 and can use CMAC?  Though an arguement can be made that you want 
to pitch DH as well when you strive for a real small code size and low 
CPU hit.

---

From: "Dan Harkins" <[email-masked]>
Date: Wed, 24 Mar 2010 13:15:42 -0700 (PDT)

Hi Bob,

  I don't know what the protocol is but if you added a nonce exchange
to the DH exchange (and had appropriate assumptions on the randomness
of the nonces) then you could use the nonces as the key to the CMAC-based
KDF and the DH shared secret as (part of) the data that's MAC'd.

  regards,

  Dan.

On Wed, March 24, 2010 11:42 am, Robert Moskowitz wrote:
>> distribution on {0, 1}^k is L Â· 2^{âˆ’k/2}.
>>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Robert Moskowitz <[email-masked]>
Date: Wed, 24 Mar 2010 14:32:04 -0700

> KDF and the DH shared secret as (part of) the data that's MAC'd.

Good points. I need to think this through....