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.   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.

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