Subject: [Cfrg] background for SAAG presentation for on variant of GCM

From: Tim Polk <[email-masked]>
Date: Mon, 23 Jul 2007 09:43:52 -0500

Folks,

Here is some background on the GCM variant under consideration by  
NIST which will be discussed at SAAG this week.  (I have CC'ed the  
cfrg in case their participants find this interesting as well...)

NIST Special Publication 800-38D specifies the Galois/Counter Mode  
(GCM) of the AES algorithm, restricted to large tag sizes. GCM  
combines the counter mode for confidentiality with authentication  
that is based on a universal hash function. GCM is intended for high- 
throughput applications that can take advantage of its  
parallelizability while tolerating its tag size restrictions.  GCM  
was proposed to NIST for considerations by David McGrew and John Viega.

Anton Joux submitted public comments on the first draft of the  
document.  The complete comment submission is available at
   http://csrc.nist.gov/CryptoToolkit/modes/comments/800-38_Series- 
Drafts/GCM/Joux_comments.pdf
To quote the conclusions section:

> In this paper, we have shown an important attack of the NIST version
> GCM mode. This stems from the fact that GCM excessively relies on
> the hypothesis that IVs are never repeating. Moreover, the  
> modification
> introduced by NIST turns this fact into a effective attack when  
> variable
> length IVs are used.
>
>

Joux made some concrete suggestions for changing GCM at the end of   
Section 5:

1.  replace the counter encryption for MACs by the classical   
encryption with the block cipher usually used with Wegman-Carter MACs.
2.  use a strong key derivation at the beginning of the algorithm  
and  computing a different key for each different purpose (one for   
encryption, one for intiializing J, one for the keyed hash and one   
for the MAC encryption).

The current draft of SP 800-38D did not accept Joux's modifications  
to the algorithm, but responded to the Joux comments in several  
concrete ways:
(a) the provision for variable-length IVs is omitted from the new  
draft, and
(b) the draft elaborates on the requirement that initialization  
vectors (IVs) must be unique across all implementations with a given  
key:
        (i) The critical importance of this requirement is indicated.
        (ii) For validation of a module to the requirements of FIPS  
140-2, an IV "generation unit" is required to be within the  
cryptographic boundary of the module.
        (iii) Two IV constructions are outlined: one that relies on  
deterministic elements to meet the uniqueness requirement, and one  
that relies on an output string from a random bit generator.
        (iv) Some design and implementation considerations with  
respect to IVs are discussed.

The current draft of SP 800-38D is available at
     http://csrc.nist.gov/CryptoToolkit/modes/ 
800-38_Series_Publications/ 
NIST_SP_800-38D_June_2007_for_public_comment.pdf

One important note:  I expect to see one additional change in this  
publication when it is officially published.  NIST will be adding a  
section 8.3 that permits use of a KDF to generate both the key and  
the IV to support RFC 4106 and some other AES-based protocols.  These  
protocols ensure that IVs are (statistically) unique across all  
implementations with a given key by generating a new key-IV pair for  
every protocol run.  (It was my assertion that these protocols  
already met the requirements in Section 8 of SP 800-38D, but it was  
decided that an explicit statement was preferable.)

While NIST determined that the GCM mode should be added to the "NIST  
Crypto Standards Toolkit", there have been extensive discussions with  
respect to the utility of the Joux submission.  There is a  
possibility that NIST might recognize the Joux variant as well.  I  
suggested that the needs of protocol developers be considered as a  
primary driver for this decision.  As a result, Morrie Dworkin (the  
author of 800-38D) will be presenting at SAAG to get a feel for the  
level of interest in such a mode.

Thanks,

Tim Polk

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