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

"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Wed, 26 July 2017 20:57 UTC

Return-Path: <Kenny.Paterson@rhul.ac.uk>
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 45F6E13146C for <cfrg@ietfa.amsl.com>; Wed, 26 Jul 2017 13:57:00 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.921
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=rhul.onmicrosoft.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id N1iR4iXlA6jo for <cfrg@ietfa.amsl.com>; Wed, 26 Jul 2017 13:56:57 -0700 (PDT)
Received: from EUR02-HE1-obe.outbound.protection.outlook.com (mail-eopbgr10078.outbound.protection.outlook.com [40.107.1.78]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 88521129A9F for <cfrg@ietf.org>; Wed, 26 Jul 2017 13:56:56 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=rhul.onmicrosoft.com; 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 AM4PR0301MB1906.eurprd03.prod.outlook.com (10.168.2.156) by AM4PR0301MB1907.eurprd03.prod.outlook.com (10.168.3.7) 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 AM4PR0301MB1906.eurprd03.prod.outlook.com ([fe80::e475:7abc:5c25:5e28]) by AM4PR0301MB1906.eurprd03.prod.outlook.com ([fe80::e475:7abc:5c25:5e28%14]) with mapi id 15.01.1282.021; Wed, 26 Jul 2017 20:56:52 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: Yannick Seurin <yannick.seurin@gmail.com>, Tetsu Iwata <iwata@cse.nagoya-u.ac.jp>
CC: "cfrg@ietf.org" <cfrg@ietf.org>, Adam Langley <agl@imperialviolet.org>, Yehuda Lindell <Yehuda.Lindell@biu.ac.il>, Shay Gueron <shay.gueron@gmail.com>, Alexey Melnikov <alexey.melnikov@isode.com>
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: <D59EBEFD.99A8F%kenny.paterson@rhul.ac.uk>
References: <CAMfhd9UOFNfqoEp31r2moVaEfQZoeppP7h2Anrz0BBP518SeYA@mail.gmail.com> <CAOOV4XvpdCuEc8s5iXr3mzxuCTXj63AP6wATriu=D3Dxs3zz4Q@mail.gmail.com>
In-Reply-To: <CAOOV4XvpdCuEc8s5iXr3mzxuCTXj63AP6wATriu=D3Dxs3zz4Q@mail.gmail.com>
Accept-Language: en-GB, en-US
Content-Language: en-US
X-MS-Has-Attach:
X-MS-TNEF-Correlator:
user-agent: Microsoft-MacOutlook/14.7.1.161129
authentication-results: spf=none (sender IP is ) smtp.mailfrom=Kenny.Paterson@rhul.ac.uk;
x-originating-ip: [78.25.226.140]
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; H:AM4PR0301MB1906.eurprd03.prod.outlook.com; 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: <AM4PR0301MB1907A09C3415390F852B0579BCB90@AM4PR0301MB1907.eurprd03.prod.outlook.com>
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 (protection.outlook.com: rhul.ac.uk does not designate permitted sender hosts)
spamdiagnosticoutput: 1:99
spamdiagnosticmetadata: NSPM
Content-Type: text/plain; charset="utf-8"
Content-ID: <6178C87165B28043A59220DE50B1DED3@eurprd03.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
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: <https://mailarchive.ietf.org/arch/msg/cfrg/7UmXqC2y9x4iTkb-0Ggd0SJ2FJk>
Subject: Re: [Cfrg] Updated bounds in AES-GCM-SIV paper
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=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"
<cfrg-bounces@irtf.org on behalf of yannick.seurin@gmail.com> wrote:

>Dear CFRG,
>
>
>Our paper "Reconsidering the Security Bound of AES-GCM-SIV", which
>prompted Adam's email, is now available on ePrint:
>https://eprint.iacr.org/2017/708
>
>
>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].
>
>
>Cheers,
>Tetsu and Yannick.
>
>
>[1] https://eprint.iacr.org/2015/102
>[2] https://eprint.iacr.org/2017/168
>
>2017-07-17 4:09 GMT+02:00 Adam Langley <agl@imperialviolet.org>:
>
>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.
>
>[1] https://eprint.iacr.org/2017/168
>
>
>Cheers
>
>AGL
>
>--
>Adam Langley agl@imperialviolet.orghttps://www.imperialviolet.org
>
>_______________________________________________
>Cfrg mailing list
>Cfrg@irtf.org
>https://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>
>
>