Re: [Cfrg] AES-GCM weakness

David McGrew <mcgrew@cisco.com> Mon, 18 July 2011 21:18 UTC

Return-Path: <mcgrew@cisco.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 1E77E21F86C7 for <cfrg@ietfa.amsl.com>; Mon, 18 Jul 2011 14:18:26 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -104.449
X-Spam-Level:
X-Spam-Status: No, score=-104.449 tagged_above=-999 required=5 tests=[AWL=-2.150, BAYES_00=-2.599, MIME_8BIT_HEADER=0.3, USER_IN_WHITELIST=-100]
Received: from mail.ietf.org ([64.170.98.30]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id eBEBb357mnaQ for <cfrg@ietfa.amsl.com>; Mon, 18 Jul 2011 14:18:22 -0700 (PDT)
Received: from rcdn-iport-3.cisco.com (rcdn-iport-3.cisco.com [173.37.86.74]) by ietfa.amsl.com (Postfix) with ESMTP id 4EA7021F86C4 for <cfrg@irtf.org>; Mon, 18 Jul 2011 14:18:22 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=mcgrew@cisco.com; l=3202; q=dns/txt; s=iport; t=1311023902; x=1312233502; h=cc:message-id:from:to:in-reply-to: content-transfer-encoding:mime-version:subject:date: references; bh=/RUO/279Papb7tiaZJYCStJKrXJRbHsS9IU+CBiF5Og=; b=LHuNjEr+zr+cNvddlI8r/frq7ypRdd+wWjX81YC/RxErK2h/2p6awOeY b/qxKQJWym9SM+6v8/DhhTCjONKx+vLEHo5tw50luztExL1AwIJ2Trr1i z0v+ALWNYxr8vBhU3bmkseM+qp8Y2IfZ3gEcv+a4Sas0unGEt3dcegYFr 8=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: Av8EAMChJE6rRDoG/2dsb2JhbABThANGozN3iHylLY0ckR2BK4QCMF8Eh1SLEpB2
X-IronPort-AV: E=Sophos;i="4.67,223,1309737600"; d="scan'208";a="4110287"
Received: from mtv-core-1.cisco.com ([171.68.58.6]) by rcdn-iport-3.cisco.com with ESMTP; 18 Jul 2011 21:18:21 +0000
Received: from stealth-10-32-254-213.cisco.com (stealth-10-32-254-213.cisco.com [10.32.254.213]) by mtv-core-1.cisco.com (8.14.3/8.14.3) with ESMTP id p6ILIKbm005494; Mon, 18 Jul 2011 21:18:20 GMT
Message-Id: <4461B7BB-E7E4-47BA-89CA-936F41177F53@cisco.com>
From: David McGrew <mcgrew@cisco.com>
To: =?ISO-8859-1?Q?J=E9r=E9mie_Crenne?= <jeremie.crenne@univ-ubs.fr>
In-Reply-To: <000001cc4583$5f371720$1da54560$@crenne@univ-ubs.fr>
Content-Type: text/plain; charset=UTF-8; format=flowed; delsp=yes
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Apple Message framework v936)
Date: Mon, 18 Jul 2011 14:18:19 -0700
References: <mailman.0.1311004169.25609.cfrg@irtf.org> <000001cc4583$5f371720$1da54560$@crenne@univ-ubs.fr>
X-Mailer: Apple Mail (2.936)
Cc: cfrg@irtf.org
Subject: Re: [Cfrg] AES-GCM weakness
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <http://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <http://www.irtf.org/mail-archive/web/cfrg>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <http://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Mon, 18 Jul 2011 21:18:26 -0000

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