Re: [Cfrg] CMAC for extraction

[Robert Moskowitz <[e-mail]>]

Oh, and this is the sort of analysis that somehow has to be captured for 
future reference when some where along the line some other person asks 
this again.

On 07/13/2010 06:50 PM, Hugo Krawczyk wrote:
> Bob, I cannot give an assessment of protocols or standards that I am not
> familiar with, and IEEE 802.15.6 is one of them.  So let me give you a 
> generic
> answer to your question (quoted at the end of this message) that does not
> take into account the specifics of IEEE 802.15.6 but only the question 
> of how
> to use a block cipher in CMAC mode to process a DH key (the details of
> IEEE 802.15.6 may or may not interfere with this advise).
>
> There are two obvious problems with inputting the DH key directly as 
> CMAC key:
> (1) the DH key is likely to be of a different size than the CMAC key,
> (2) the DH key is not a uniformly distributed string (but rather a 
> uniformly
> distributed element in some algebraic group -- more precisely, 
> assuming the
> Decisional Diffie-Hellman assumption, the distribution of DH keys is
> computationally indistinguishable from the uniform distribution on the DH
> group).
>
> A trivial way to resolve the first issue (assuming the DH key is 
> longer than the
> CMAC one) is to truncate the DH key to the number of CMAC key bits. 
> There are
> theoretical reasons (though not necessarily an attack) NOT to do so 
> (e.g., since
> the DH key is not a uniform string of bits, a subset of it may not be 
> uniform
> either). A better way would be to apply an extractor to the DH key and 
> use the output
> as the CMAC key (much as in the HKDF design). Since you do not want to 
> use a
> hash function then you need to do the extraction using the block 
> cipher itself.
> I only know of one work that analyzes such a scheme and it is the
> Dodis-Gennaro-Hastad-Krawczyk-Rabin paper from Crypto'04. There we 
> show that if
> the block cipher acts as a family of random permutations then you can 
> use CMAC
> with that block cipher as an extractor. The security bounds guaranteed 
> by that
> analysis are not great (and the random permutation assumption is an 
> idealized
> one), yet it is the best analysis we have for such a beast.
>
> NOTE: Our revised analysis of the CBC case replaces the expression e(L,K)
> in the proceedings version of the paper with L^4/K^2 which is worse 
> than the
> original bound but of little consequence in the application below 
> where L is a
> very small number (i.e., L= the number of blocks in the representation 
> of DHK,
> where the length of a block is determined by the underlying block cipher).
> The available version of the paper (with the old bound) is
> http://cs.nyu.edu/~dodis/ps/hmac.ps 
> <http://cs.nyu.edu/%7Edodis/ps/hmac.ps>.
>
> If you want to buy that analysis as an indication of security then I 
> can suggest
> the following. Let DHK be the DH key that is output by your protocol 
> and let CK
> be the CMAC key that you want to generate.
>
> (a) Assuming that you are running an authenticated Diffie-Hellman protocol
> between the parties to generate the DH key DHK, add to the protocol the
> generation of a nonce that is exchanged and AUTHENTICATED by the parties.
> This nonce, call it N, is to be of the length of the CMAC key (and it 
> should be
> independent of the DH key DHK).
>
> (b) Apply CMAC with N as the key and DHK as the input (i.e., DHK acts 
> as the
> message, or plaintext, for the CMAC function and N acts as the key).
>
> (c) Use the value output by (b) as the key CK (this assumes that the 
> output
> length from CMAC is the same as the length of a CMAC key -- this is 
> the case
> for AES-128 but not for AES-256).
>
> IMPORTANT: If your protocol cannot exchange a nonce, or can exchange 
> it but
> cannot authenticate it (in which case the nonce can be chosen by an 
> attacker)
> then replace N with a fixed value that is defined and wired it into 
> the protocol
> as a constant. Choose N to be any "random" string of the length of a 
> CMAC key.
> (I prefer to use a random-looking N rather than something like 
> all-zero string
> in case that such a structured key may turn to be a "weak key" of the 
> underlying
> cipher).
>
> Hugo
>
> > Hugo,
> >
> > In the proposed IEEE 802.15.6 standard, an ECDH derived key is 
> expanded via CMAC
> > to produce the actual keying material.  No cryptographic hash is 
> used in this
> > protocol.
> >
> > This seems to go contrary to the recommendation in
> > http://www.ietf.org/id/draft-irtf-cfrg-kdf-uses-00.txt that DH 
> derived keys are
> > NOT uniformly distributed and MUST be passed through an extract 
> phase (eg as in
> > HKDF).
> >
> > Can you please point me to a reference to the nature of the attack 
> in this
> > usage.  This method will end up in medical devices like Insulin pumps,
> > Pacemakers, etc and I am looking for hard references to get the 
> authors to make
> > needed changes.
>
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> http://www.irtf.org/mailman/listinfo/cfrg
>