Re: [Cfrg] Answers to HKDF questions

[David McGrew <[e-mail]>]

Hi Zooko,

On Oct 21, 2009, at 8:01 PM, Zooko Wilcox-O'Hearn wrote:

> Dear Hugo Krawcyck:
>
> Thank you for the detailed answers.  I still have a question about  
> HMAC as compared to other MACs.  Feel free to point me to existing  
> documents if they answer my question.  Suppose I were to instantiate  
> HKDF with the keyed PRF being a cipher based MAC such as Poly1305  
> instead of HMAC.  Which of the arguments for HKDF's security would  
> still apply?
>

HKDF has two stages, extract and expand.  Replacing HMAC in the  
extract stage with Poly1305 is not going to work as well as you would  
like.   It will have provable security bounds given realistic  
assumptions (because universal hash functions like that in Poly1305  
can be used as statistical extractors), but to get the security bound  
to be as high as you would like will force you to do things very  
inefficiently.  To use this instantiation to extract keys from Diffie- 
Hellman, for example, would require you to double the size of the DH  
keys in order to claim the benefit of the security bound.   Hugo's  
paper points this out: "Statistical extractors require a significant  
gap between the min-entropy m of the source and the required number m 
′ of extracted bits (no statistical extractor can achieve a  
statistical distance, on arbitrary sources, better than 2^(−(m−m 
′)/2) [59])".

The use of CBC-MAC as a computational extractor has been studied, and  
its security bounds also do not match that we can achieve with hash- 
based extractors.

David