Re: [Cfrg] AES-GCM weakness

"Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com> Mon, 18 July 2011 22:14 UTC

Return-Path: <sfluhrer@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 E967821F8880 for <cfrg@ietfa.amsl.com>; Mon, 18 Jul 2011 15:14:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.299
X-Spam-Level:
X-Spam-Status: No, score=-2.299 tagged_above=-999 required=5 tests=[BAYES_00=-2.599, MIME_8BIT_HEADER=0.3]
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 pjdmAUQNjliH for <cfrg@ietfa.amsl.com>; Mon, 18 Jul 2011 15:14:31 -0700 (PDT)
Received: from rcdn-iport-8.cisco.com (rcdn-iport-8.cisco.com [173.37.86.79]) by ietfa.amsl.com (Postfix) with ESMTP id E825221F880C for <cfrg@irtf.org>; Mon, 18 Jul 2011 15:14:30 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=cisco.com; i=sfluhrer@cisco.com; l=5560; q=dns/txt; s=iport; t=1311027271; x=1312236871; h=mime-version:content-transfer-encoding:subject:date: message-id:in-reply-to:references:from:to:cc; bh=uSqeUbIPzWtVC5nYGJifZd9Pk/0uVWn7oNq/qR32XgU=; b=XFS9vW8zwPUB6BlVAwXwOx4YY6Rhk6cdAAWxWIPHFmeeL0/QO4mAaqD5 u7ryV/BmKaqZ5YRNXzOxOxOG84xNZyFCfcH/vHS6qIQY7z+/fjm1+Qxlt c6cgrcrvdUMaFYLGk6MGDU2XZa+m+uHNe8JUZhI8F1XV68pl9t6HGgg1u Q=;
X-IronPort-Anti-Spam-Filtered: true
X-IronPort-Anti-Spam-Result: AuAAAFCvJE6rRDoH/2dsb2JhbABThANGkz2OTXd3iHylJo0ckRuBK4QCMF8Eh1SQHIts
X-IronPort-AV: E=Sophos;i="4.67,224,1309737600"; d="scan'208";a="4128529"
Received: from mtv-core-2.cisco.com ([171.68.58.7]) by rcdn-iport-8.cisco.com with ESMTP; 18 Jul 2011 22:14:29 +0000
Received: from xbh-sjc-231.amer.cisco.com (xbh-sjc-231.cisco.com [128.107.191.100]) by mtv-core-2.cisco.com (8.14.3/8.14.3) with ESMTP id p6IMEMWq010701; Mon, 18 Jul 2011 22:14:22 GMT
Received: from xmb-sjc-23e.amer.cisco.com ([128.107.191.15]) by xbh-sjc-231.amer.cisco.com with Microsoft SMTPSVC(6.0.3790.4675); Mon, 18 Jul 2011 15:14:21 -0700
X-MimeOLE: Produced By Microsoft Exchange V6.5
Content-class: urn:content-classes:message
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: base64
Date: Mon, 18 Jul 2011 15:14:17 -0700
Message-ID: <EE0C2F9E065E634B84FC3BE36CF8A4B20754562A@xmb-sjc-23e.amer.cisco.com>
In-Reply-To: <4461B7BB-E7E4-47BA-89CA-936F41177F53@cisco.com>
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
Thread-Topic: [Cfrg] AES-GCM weakness
Thread-Index: AcxFkEl/NJKBIdpYRj+jE1yXsqkI/QABgDvQ
References: <mailman.0.1311004169.25609.cfrg@irtf.org><000001cc4583$5f371720$1da54560$@crenne@univ-ubs.fr> <4461B7BB-E7E4-47BA-89CA-936F41177F53@cisco.com>
From: "Scott Fluhrer (sfluhrer)" <sfluhrer@cisco.com>
To: "David McGrew (mcgrew)" <mcgrew@cisco.com>, =?UTF-8?B?SsOpcsOpbWllIENyZW5uZQ==?= <jeremie.crenne@univ-ubs.fr>
X-OriginalArrivalTime: 18 Jul 2011 22:14:21.0727 (UTC) FILETIME=[0B814AF0:01CC4598]
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 22:14:32 -0000


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