Subject: RE: [Cfrg] AES GMAC

From: [email-masked]
Date: Thu, 15 Sep 2005 12:50:21 +0300

Dear Russ Housley,

As response to your request we express our concerns about the
cryptographic quality of the MAC construction given in the GMAC
specification by David MacGrew and John Viega. 

The basic cryptographic requirement for a MAC with tag of length n is
that the forgery probability of a tag should be close to 2^{-n}. Our
concern is that the GMAC construction proposed by MacGrew and Viega does
not meet this requirement. Indeed, for a message of length 2^m blocks
the forgery probability is about 2^{m-n}. In the current proposal,
upperbound of 2^{-64} to the forgery probability is achieved by using
128-bit tags and setting an upperbound of 2^64 to the message length.
Moreover, truncation of tags is forbidden.

This means that the current proposal mandates the use of 128-bit tags to
achieve 64-bit security level for the MAC algorithm. If not a security
risk, it is a cryptogaphic flaw, and a serious drawback. Even more so,
since one could do better. In our note to NIST in June we drew attention
to a previously known construction using which n-bit security level can
be achieved with n-bit tags for messages of practically any length.
Using this construction, for example, 64-bit security level can be
achieved with 64-bit tags for messages of up to 2^{64} blocks, and it
does not take more key, or more calls to the AES, or essentially more
computations than with the construction by MacGrew and Viega.

Our note to NIST can be found at:

http://csrc.nist.gov/CryptoToolkit/modes/comments/General_Comments/paper
s/Nyberg_Gilbert_and_Robshaw.pdf 

With best regards,

Kaisa Nyberg
Henri Gilbert
Matt Robshaw

>-----Original Message-----
>From: [email-masked] [mailto:[email-masked]] On Behalf Of

>ext Russ Housley
>Sent: 30 August, 2005 19:31
>To: [email-masked]
>Subject: [Cfrg] AES GMAC
>
>David McGrew and John Viega have requested publication of an IPsec ESP 
>cipher specification that uses AES GMAC.  The specification can be 
>found at:
>
>    
>http://www.ietf.org/internet-drafts/draft-mcgrew-aes-gmac-esp-00.txt
>
>Please let me know if any cryptographic concerns with this 
>specification in the next two weeks.
>
>Russ
>
>
>_______________________________________________
>Cfrg mailing list
>[email-masked]
>https://www1.ietf.org/mailman/listinfo/cfrg
>

_______________________________________________
Cfrg mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/cfrg

---

From: "D. J. Bernstein" <[email-masked]>
Date: 15 Sep 2005 11:46:40 -0000

It is _not_ true that truncation---specifically, twisted truncation of a
128-bit GMAC authenticator to 64 bits---preserves security level. Here's
the chart:

   * Maximum forgery probability for _very long_ messages: Not affected
     by twisted truncation (unlike naive truncation).

   * Maximum forgery probability without regard to message length: Not
     affected by twisted truncation (unlike naive truncation).

   * Maximum forgery probability for _short_ messages: Made much worse
     by twisted truncation (like naive truncation).

   * Maximum forgery probability _per byte sent by the attacker_: Made
     much worse by twisted truncation (like naive truncation).

For the record: I do not endorse, and I have never endorsed, 64-bit
authenticators. Attackers can try an amazing number of short forgeries
and end up with an unacceptably high chance of success.

As for the ``secure truncation'' misquote: What my securitywcs paper
discusses is the idea of _reducing_ forgery probabilities by using a
 ``larger field'' with a ``larger output size'' that (if you care about
every last byte of bandwidth) can then be ``safely truncated after an
appropriate twist.'' The original field size is 128 bits; the larger
field size is, typically, 160 bits; the truncation is back to the
original 128 bits.

> that the forgery probability of a tag should be close to 2^{-n}.

No. There's a cryptographic requirement that forgery probability be
extremely small, but there's no cryptographic requirement that every
last byte of bandwidth be saved.

Should cryptographers pay attention to bandwidth? Of course. But this
doesn't mean that we should take the crazy step of excluding all the
non-minimal-bandwidth solutions. Minimizing bandwidth often imposes
other costs that are much more important to the users---as illustrated
by short elliptic-curve signatures whose verification time is, for many
applications, unacceptably slow.

Similar comments apply to key sizes, collision-free-hash output lengths,
etc. A 128-bit security level requires _at least_ a 128-bit key and a
256-bit hash output, but there's no cryptographic justification for
demanding _exactly_ a 128-bit key and _exactly_ a 256-bit hash output.
Perhaps the most efficient way to achieve 128-bit security is with a
192-bit key and a 384-bit hash output.

---D. J. Bernstein, Professor, Mathematics, Statistics,
and Computer Science, University of Illinois at Chicago

---

From: David McGrew <[email-masked]>
Date: Thu, 15 Sep 2005 07:35:21 -0700

Hi Kaisa,

thanks for your comments.  Your comments to NIST are interesting and  
make some good points for a general-purpose message authentication  
code.  However, they are less pertinent in the particular case of  
authentication of packetized data, especially at high data rates, which  
is the particular domain of draft-mcgrew-aes-gmac-esp-00.txt.  I don't  
claim that ESP GMAC is the perfect general-purpose MAC, but it is well  
suited for its domain.  More inline:

> that the forgery probability of a tag should be close to 2^{-n}.

I disagree that this is a requirement.  If it was, then MACs would be  
essentially equivalent to PRFs, though the literature is full of MACs  
that aren't PRFs.

>  Our

But in the internet draft under discussion, messages are not going to  
be anywhere near that length.  The largest that an IPv4 packet can get  
is 64 kilobytes (2^{12} blocks), which puts the single packet forgery  
probability at 2^{-116}.  This value compares favorably to that of the  
recommended ESP authentication methods, which use 96-bit tags.  In  
practice, packets on the Internet are significantly smaller, and only  
very rarely exceed 2kb (256 blocks) (see  
http://www.caida.org/outreach/papers/1998/Inet98/Inet98.pdf or similar  
studies), and MTUs around this size are common.

> Moreover, truncation of tags is forbidden.

This is a feature, not a bug!   First, having a single tag length  
promotes interoperability and makes implementation easier.  Second, ESP  
encapsulation overhead is significant, and truncating an ESP tag in  
order to save bandwidth is a questionable tradeoff.  Each ESP packet  
has a minimum of ten bytes of data besides the payload, and GMAC uses  
an eight-byte IV that is explicitly carried in each packet, so each  
packet has 18 bytes of overhead in addition to the tag.  There is  
little advantage in using a 96-bit tag, with total overhead of at least  
30 bytes, over using a full tag with a total overhead of at least 34  
bytes.

> computations than with the construction by MacGrew and Viega.

I don't understand the claim in the last sentence.  Is the "second  
64-bit quantity" \lambda in Section 3 of your note to NIST not  
additional key material?

When protecting packetized data at high data rates, there is a  
significant cost incurred for making keys larger, since they must be  
stored and must be fetched before packet processing.  Each clock cycle  
that a fully-pipelined AES engine is idle is a missed opportunity to  
process 16 bytes.  In many IPsec VPN implementations, there are large  
numbers of security associations, and the cost of storing and fetching  
them is non-trivial.  This was the motivation behind minimizing the  
size of the GCM/GMAC context.   This is not to say that your suggestion  
to NIST is no viable, it is just to explain our thinking.

Your suggestions to NIST are interesting, and worth considering for the  
design of future MACs.  However, draft-mcgrew-aes-gmac-esp-00.txt  
provides an adequate level of security and is compatible with RFC4106.   
Let's continue the discussion about MACs in a broader context.

Best regards,

David

p.s. - your note to NIST mentions that there is an ETSI SAGE effort  
that is considering MAC designs.  It would be great if CFRG and the  
IETF could liaison with that group and hear a report on the status of  
this work.  Could you please let me know who in ETSI I could bug about  
this?