Re: [Cfrg] Updated bounds in AES-GCM-SIV paper

"Paterson, Kenny" <> Wed, 26 July 2017 20:57 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 45F6E13146C for <>; Wed, 26 Jul 2017 13:57:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.921
X-Spam-Status: No, score=-1.921 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, RCVD_IN_DNSWL_NONE=-0.0001, RCVD_IN_MSPIKE_H3=-0.01, RCVD_IN_MSPIKE_WL=-0.01, SPF_HELO_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (1024-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id N1iR4iXlA6jo for <>; Wed, 26 Jul 2017 13:56:57 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 88521129A9F for <>; Wed, 26 Jul 2017 13:56:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=selector1-rhul-ac-uk; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version; bh=hd/iMxrQRUEhkcAW+2MvR2ph9uL7lBVnI3wksr5Jg8U=; b=0mwSdmYdpdG1C3JCWPzKmtDiVEFqg2uKPA1HYKdDST9pWAUanNUXLXvKRIwG12VJFGiz1bkK24/dm1UK2s/LAsn/AoGpCv9W8Im6ZDpW1Li4UXAn7HdRbhrbP9EER/2Kad+B7i5uIzpr1G6NpbwOIITK/taRO7DKFJzKJ3MBn/0=
Received: from ( by ( with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_CBC_SHA256_P256) id 15.1.1282.10; Wed, 26 Jul 2017 20:56:53 +0000
Received: from ([fe80::e475:7abc:5c25:5e28]) by ([fe80::e475:7abc:5c25:5e28%14]) with mapi id 15.01.1282.021; Wed, 26 Jul 2017 20:56:52 +0000
From: "Paterson, Kenny" <>
To: Yannick Seurin <>, Tetsu Iwata <>
CC: "" <>, Adam Langley <>, Yehuda Lindell <>, Shay Gueron <>, Alexey Melnikov <>
Thread-Topic: [Cfrg] Updated bounds in AES-GCM-SIV paper
Thread-Index: AQHS/qHBtQ7+7q8LEkGkBdeni4MsaKJmEV+AgAClr4A=
Date: Wed, 26 Jul 2017 20:56:52 +0000
Message-ID: <>
References: <> <>
In-Reply-To: <>
Accept-Language: en-GB, en-US
Content-Language: en-US
user-agent: Microsoft-MacOutlook/
authentication-results: spf=none (sender IP is );
x-originating-ip: []
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; AM4PR0301MB1907; 7:Aw0OIEDN4FCqgCJMCy6z3iBh6Gi80VI3XmXRHEax5dM88fPxKMwGa7oWf+vV1CQg4DTqA66xM7PvhzaqlOid8FUFG22IeVsAGJjplkw6/sb+XjxiZOvt6cllh9aMUve4FHyOVcTU3yJenn4iw76v+F7XdKrJbA6wbychRJQb9Qtt9bDkVtc7l6VXPc4xfK60P0yjOvNDsf5jwr7LnoT14We3oyAqPbZAKk8lw/5t535uy72onyHxiFYo0WCgcobdMJlT06+8vYNrGq3Y8YSp0MND0QDZZfYymPayQDkq89dYtw6ZWxGFBAbbKifhqsc5fCvK3P3T2Z/2l5xlfFIEysOQ6HHsIdN3E6nXBCWvOKLRXCxAH8ki6fgzl/PRKOcPClK6xUz3D6axuQ/RA7nhr6Qf/z/2BiXvKdRd/uPKniI/jTfX+LcX/kzNxIErbyFrLefmAr86pgu8BijG5ZN8cji2YjwL5ttVGXTiA8cpDJ9NgkmzJWNKOTXt5LKCA4dPWllLYFUV8BM21vZdLjCTL+qIy/DpLbLUaJ1OlEaPd/YnGOtqrPVx8gEyjEcSbVgEenJkqcJb89tpDwzykStFhfzpAj76ROiDJbbSYSfy+YbTyB7VYlIAytP0IaeMjPU5mM3mvzf9/89DAVe6qOdY9uFx86Zo65A8/+yUnbrk/6GPxYzdAF65t6aKjeKCmkdCbIbIaRY8DjoP042n13IJAByEDguTo0rHRdYNa2EeBUa7g5iD3vr8kSem6KqT/gwtzjcCiyM7qbkzVK7FvgQe99WaplATcnaOJTpfywYzkUM=
x-forefront-antispam-report: SFV:SKI; SCL:-1; SFV:NSPM; SFS:(10009020)(6009001)(39400400002)(39410400002)(39840400002)(39450400003)(39850400002)(189002)(377424004)(66654002)(199003)(24454002)(2950100002)(106356001)(36756003)(39060400002)(42882006)(54906002)(6512007)(6306002)(966005)(4001350100001)(72206003)(97736004)(2906002)(74482002)(38730400002)(68736007)(53936002)(99286003)(4326008)(105586002)(66066001)(6246003)(25786009)(83506001)(2900100001)(101416001)(3280700002)(7736002)(14454004)(189998001)(15650500001)(102836003)(6116002)(305945005)(3660700001)(5660300001)(561944003)(3846002)(50986999)(6436002)(8676002)(81166006)(81156014)(8936002)(230783001)(478600001)(5250100002)(6506006)(6486002)(76176999)(53546010)(54356999)(229853002)(86362001)(21314002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM4PR0301MB1907;; FPR:; SPF:None; PTR:InfoNoRecords; MX:1; A:1; LANG:en;
x-ms-office365-filtering-correlation-id: 4bc9ed72-c2db-4a68-1126-08d4d468d7de
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(300000500095)(300135000095)(300000501095)(300135300095)(22001)(300000502095)(300135100095)(2017030254075)(300000503095)(300135400095)(2017052603031)(201703131423075)(201703031133081)(300000504095)(300135200095)(300000505095)(300135600095)(300000506095)(300135500095); SRVR:AM4PR0301MB1907;
x-ms-traffictypediagnostic: AM4PR0301MB1907:
x-exchange-antispam-report-test: UriScan:(192374486261705);
x-microsoft-antispam-prvs: <>
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6040450)(601004)(2401047)(8121501046)(5005006)(100000703101)(100105400095)(93006095)(93001095)(10201501046)(3002001)(6041248)(201703131423075)(201702281529075)(201702281528075)(201703061421075)(201703061406153)(20161123564025)(20161123555025)(20161123562025)(20161123560025)(20161123558100)(6072148)(100000704101)(100105200095)(100000705101)(100105500095); SRVR:AM4PR0301MB1907; BCL:0; PCL:0; RULEID:(100000800101)(100110000095)(100000801101)(100110300095)(100000802101)(100110100095)(100000803101)(100110400095)(100000804101)(100110200095)(100000805101)(100110500095); SRVR:AM4PR0301MB1907;
x-forefront-prvs: 038002787A
received-spf: None ( does not designate permitted sender hosts)
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-ID: <>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-originalarrivaltime: 26 Jul 2017 20:56:52.8113 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 2efd699a-1922-4e69-b601-108008d28a2e
X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM4PR0301MB1907
Archived-At: <>
Subject: Re: [Cfrg] Updated bounds in AES-GCM-SIV paper
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Wed, 26 Jul 2017 20:57:00 -0000

Dear Tetsu and Yannick,

Many thanks for performing this thorough security analysis of AES-GCM-SIV.
Your contribution to the process is an important and timely one as the
document describing this scheme progresses towards its final form in CFRG.

I trust that the authors of draft-irtf-cfrg-gcmsiv will carefully update
their text in the light of this new analysis.

Adam, Shay, Yehuda: could you also please give due consideration to Tetsu
and Yannick's proposal for an alternative key-derivation function?

Many thanks,

Kenny (for the chairs)

On 26/07/2017 13:04, "Cfrg on behalf of Yannick Seurin"
< on behalf of> wrote:

>Dear CFRG,
>Our paper "Reconsidering the Security Bound of AES-GCM-SIV", which
>prompted Adam's email, is now available on ePrint:
>The main contribution of this paper is an independent security analysis
>for AES-GCM-SIV motivated by some problems that we discovered in the
>security proofs presented in [1] and [2]. We also propose a different
>key-derivation function with similar efficiency
> but better security than the one currently specified.
>As explained by Adam, we noticed that the security claims made in [2]
>were overly optimistic because the PRP-PRF indistinguishability term had
>been neglected, whereas it was actually the dominating term of the
>security bound. As a consequence, the security
> guarantees provided by AES-GCM-SIV must be lowered compared with what
>was originally announced in [2], especially for long messages.
>We stress that our paper is based on version 20160310:063701 of [1] and
>version 20170223:140759 of [2]. Both [1] and [2] were updated after we
>sent our paper to AES-GCM-SIV's designers on July 7.
>We believe that the CFRG specification (especially Section 9) should be
>updated as well to reflect the new security analysis. Recommended usage
>limitations for an AEAD scheme (such as the maximal number of messages
>that can be encrypted with the same key)
> should be based on the maximal message length allowed by its
>specification (currently, 2^{32} 128-bit blocks). More fine-grained
>recommendations (such as "if the maximal message length in an application
>is 2^m and the maximal number of nonce repetitions is
> R, then the maximal number of messages that can be encrypted with the
>same key can be pushed to XXX") are likely to create confusion and incur
>implementations errors. For AES-GCM-SIV with randomly generated nonces
>(which has been put forward by the designers
> as the preferred way of generating nonces when no state can be saved by
>encrypting devices), this means that no more than 2^{30} messages should
>be encrypted with the same key, which contrasts with the recommended
>limit of 2^{50} given (without context) in
> Section 9 of the CFRG specification and in the abstract of [2].
>Tetsu and Yannick.
>2017-07-17 4:09 GMT+02:00 Adam Langley <>rg>:
>Dear CFRG,
>We would like to thank Yannick Seurin and Tetsu Iwata for alerting us
>to the fact that we had erroneously assumed that one of the terms in
>the security bounds of AES-GCM-SIV was negligible when, for
>indistinguishability, it was not. Thus, while the security proof was
>correct, the example concrete bounds were over optimistic, most
>notably for very large messages. This was most evident in Fig 4.
>We have updated the paper[1] to correct this mistake and we draw the
>group's attention to the revised figure four (now called Table 1). For
>typical uses, thankfully, the difference is not material but for we
>wish to highlight that one cannot encrypt many messages of
>many-gigabytes using AES-GCM-SIV, in contrast to what the figures
>previously suggested. However, even in such a case of very long
>messages, the overall number of blocks encrypted safely is still
>significantly higher than previous schemes.
>Adam Langley agl@imperialviolet.org
>Cfrg mailing list