Subject: [Cfrg] CMAC for extraction

From: Hugo Krawczyk <[email-masked]>
Date: Tue, 13 Jul 2010 21:50:21 -0400

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.

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.

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 13 Jul 2010 19:59:23 -0700

Thank you Hugo!

Fantastic analysis, I my very limited, but appreciative opinion.

I can 'run' with this.

On 07/13/2010 06:50 PM, Hugo Krawczyk wrote:
> take into account the specifics of IEEE 802.15.6 but only the question 
> of how
> There are two obvious problems with inputting the DH key directly as 
> CMAC key:
> 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
> either). A better way would be to apply an extractor to the DH key and 
> use the output
> hash function then you need to do the extraction using the block 
> cipher itself.
> Dodis-Gennaro-Hastad-Krawczyk-Rabin paper from Crypto'04. 

I had this 'handed' to me this afternoon by one person here at the 802 
meeting that just happened to have this buried in his archive of 
interesting papers and remembered it.  Lots more reading for me.

> 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
> 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,
> 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
> This nonce, call it N, is to be of the length of the CMAC key (and it 
> should be
> 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 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.
> >
> > 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).
> >
> > Pacemakers, etc and I am looking for hard references to get the 
> authors to make
> > needed changes.
>
>
> _______________________________________________
> Cfrg mailing list
> [email-masked]
> http://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Robert Moskowitz <[email-masked]>
Date: Tue, 13 Jul 2010 20:05:06 -0700

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:
> Dodis-Gennaro-Hastad-Krawczyk-Rabin paper from Crypto'04. There we 
> show that if