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

From: David McGrew <[email-masked]>
Date: Fri, 9 Apr 2010 14:37:46 -0700

Hi Dan,

what security level would that provide?   Or, for example, what choice  
of parameters and algorithms would you recommend in order to achieve a  
96-bit equivalent security level?    My understanding is that, if one  
uses the implementation strategy that you suggest, and then claims  
provable security, then they're likely to be unhappy either with the  
security level that they get or the parameter sizes they'll need to use.

David

On Mar 24, 2010, at 1:15 PM, Dan Harkins wrote:

>
>  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:
>> 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.
>>
>> _______________________________________________
>> Cfrg mailing list
>> [email-masked]
>> http://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg

---

From: "Dan Harkins" <[email-masked]>
Date: Fri, 9 Apr 2010 17:51:43 -0700 (PDT)

Hi David,

  Good question! My (probably naive) answer is that using a block cipher
with a block size of 128 bits and assuming the nonces are uniformly random
to provide a random permutation of the block cipher then the DH secret
input to the CBC-MAC function must be from a group with an order of at
least 2^256, which for ECP groups that would correspond to a prime of at
least 512 bits, and then the 128-bit output would be computationally
indistinguishable from random. So I think the 521-bit random ECP group
from RFC 5114 would do the trick.

  Please correct me where I'm wrong.

  Dan.