Re: [Cfrg] AES-GCM weakness

> -----Original Message-----
> From: cfrg-bounces@irtf.org [mailto:cfrg-bounces@irtf.org] On Behalf Of
> David McGrew (mcgrew)
> Sent: Monday, July 18, 2011 5:18 PM
> To: Jérémie Crenne
> Cc: cfrg@irtf.org
> Subject: Re: [Cfrg] AES-GCM weakness
> 
> Hi Jérémie,
> 
> http://eprint.iacr.org/2011/202 provides some interesting insights
> into how polynomial hash based authentication works, but it does *not*
> describe any way of attacking GCM that improves on what was known
> before GCM was adopted.
> 
> "GCM, GHASH and Weak Keys" describes a particular way of forging a
> message, given a valid message, which works with probability of about
> n/2^128 for messages that are n*128 bits long.  Observation 1 reads:
> "Let n be a number satisfying gcd(2^128 − 1, n) = n. Blindly swapping
> Xi and Xj , where i ≡ j (mod n) will result in a successful forgery
> with probability of at least n/2^128."
> 
> This corresponds to the original security analysis, from "The Security
> and Performance of the Galois/Counter Mode (GCM) of
> Operation" (Indocrypt 2004).  Lemma 2 from that reference(GHASH is
> almost xor universal) reads: "The function GHASH is (n + 1)/2^128
> almost xor universal when its second and third inputs are restricted
> so that their lengths sum to n*128 or fewer bits ..."   Here I have
> set w=128 and l=n*128 so that the notations are similar.
> 
> The newer work does describe an optimal attack, which is interesting,
> though see also the attacks described by Ferguson in his comments to
> NIST [1], and [2].  But it does not describe a way to attack GCM that
> works with higher chance of success than was previously known.
> 
> SGCM, described in http://eprint.iacr.org/2011/326, I don't think is a
> good idea, because it shares GCM's least desirable property (a broken
> implementation that repeats IVs will give away its authentication key)
> and it is not backwards compatible with GCM.

In addition, SGCM doesn't address the problem that's under discussion: that by modifying a valid n-word message, you can create a forgery with probability circa n/2^128.  The specific attack described in the paper doesn't work, however there are other ways of modifying the message that will achieve this probability with SGCM.

> If that algorithm is
> extended, it would be much more worthwhile to have a different method
> of encrypting the hash, as suggested by Joux (Section 5 of [3]) and as
> done by the CWC authors [4].  It might be useful to have an additional
> ECB encryption of the tag, which could be described as a post-
> processing step for GCM as it is currently specified.

That would help against accidental reuse of the nonce.  However, it doesn’t address deliberate forgery attempts (because the forger can choose not to modify the tag).

> 
> regards,
> 
> David
> 
> [1] http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/comments/CWC-
> GCM/Ferguson2.pdf
> 
> [2] http://eprint.iacr.org/2005/161.pdf
> 
> [3]
> http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/Joux_comments.pdf
> 
> [4]
> http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/cwc/
> cwc-spec.pdf
> 
> On Jul 18, 2011, at 12:46 PM, Jérémie Crenne wrote:
> 
> > Hi everybody,
> >
> > What is the feeling of the community about the recent potential AES-
> > GCM
> > weakness due to weak keys ? I'm still considering the usage of AES-
> > GCM to be
> > an attractive mode for hardware implementations. I'm a little bit
> > concerned
> > about this since the "new" proposition described here would require
> > significant addition of logic.
> >
> > http://eprint.iacr.org/2011/202
> > http://eprint.iacr.org/2011/326
> >
> > Thanks,
> >
> > Jérémie
> >
> > _______________________________________________
> > Cfrg mailing list
> > Cfrg@irtf.org
> > http://www.irtf.org/mailman/listinfo/cfrg
> 
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> http://www.irtf.org/mailman/listinfo/cfrg