Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06

"Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk> Mon, 02 October 2017 16:42 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 32B2713234B for <cfrg@ietfa.amsl.com>; Mon, 2 Oct 2017 09:42:03 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.699
X-Spam-Level:
X-Spam-Status: No, score=-4.699 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_H2=-2.8, URIBL_BLOCKED=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 aYT4IUGfgbkX for <cfrg@ietfa.amsl.com>; Mon, 2 Oct 2017 09:41:58 -0700 (PDT)
Received: from EUR03-AM5-obe.outbound.protection.outlook.com (mail-eopbgr30079.outbound.protection.outlook.com [40.107.3.79]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DFAC0133052 for <cfrg@irtf.org>; Mon, 2 Oct 2017 09:41:57 -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=ycRLd1w26PMtXXkvG4YYqa81ahDknInHNNUAfRjQJ74=; b=ST0qiWX5xWJgtCS8iBkHU5Wk+eAjzz6eFa/Hns/+/fnSBq+pXOVSgfwETqwDFKbiIzE1f1P1dGWBQpvAscyAug8hp3IyyqJP5tgAsB4zNcWmC/qiDe2HJ/B8yiuJvfT9ZaIeD3ShM8B1I7ITovamyBbcljUdreZfr0QaTNd+DEQ=
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_256_CBC_SHA384_P256) id 15.20.77.7; Mon, 2 Oct 2017 16:41:54 +0000
Received: from AM4PR0301MB1906.eurprd03.prod.outlook.com ([fe80::a90a:8fa5:3111:efe]) by AM4PR0301MB1906.eurprd03.prod.outlook.com ([fe80::a90a:8fa5:3111:efe%13]) with mapi id 15.20.0077.016; Mon, 2 Oct 2017 16:41:53 +0000
From: "Paterson, Kenny" <Kenny.Paterson@rhul.ac.uk>
To: Stefano Tessaro <tessaro@cs.ucsb.edu>, "cfrg@irtf.org" <cfrg@irtf.org>
CC: Priyanka Bose <priyanka@cs.ucsb.edu>, Viet Tung Hoang <tvhoang@cs.fsu.edu>
Thread-Topic: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06
Thread-Index: AQHTLv48nHq8en1/7kuyRQJV92Vw1qLNiuCAgANjBoA=
Date: Mon, 02 Oct 2017 16:41:53 +0000
Message-ID: <D5F82A2E.9F935%kenny.paterson@rhul.ac.uk>
References: <EA4347BF-D26F-4303-9A8D-E7B28986DE56@isode.com> <CAEB_pddu5Z9xo7y3v9rbr-1inzyf9=0YsO2M1rNRF4MWamK=5Q@mail.gmail.com>
In-Reply-To: <CAEB_pddu5Z9xo7y3v9rbr-1inzyf9=0YsO2M1rNRF4MWamK=5Q@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: [134.219.227.30]
x-ms-publictraffictype: Email
x-microsoft-exchange-diagnostics: 1; AM4PR0301MB1907; 6:FZTJuK9H49WzijSUqrXExeZ+iRoAv8yfuKKi6kHZ6njLcxwrrO7mcrnqqCA30H+OIcfx8sUsgeekAOPkf9rr6yL/fxUz7dsql71vF3kLIuRcrkZFkPufRc/vvRkAaZqD51FDjJKSiehnMSHOdf8+0tWFiQNqSwi3NmUURrHKXI/gbq0LOd15UzxqXn4xhHsoratvJ5xmwSTDrsarBcQOkd5qTS/alQZ+VYdcGMfKgZR0cxBtqmavPbqcc3vacroiljB4DCRDD9UqOpPGhfgYfBjC1Dp/spDgzuVFs4J8qjRgnbW1RerI605Jpr8uEvp/HS/h/EoKzbrdPUyOZs+ViQ==; 5:bNWi7OJUE/sIymnsrOZ7CbrnEPj/jiKjF7UTOhPWXCu+ALJUKjXDjQZycsAduibMh+J/2ho6KsRNS3GFywgFKWr40gUMC+8Dj6OYu/00Vd6EUz/+KpDeNfFmaAzMPW55mePkdSNcNStavbwd75vGMA==; 24:ArgFnGIAf/oe0AI219FW2TWkOPVYcqbkCiwltIolkAppl8+d+7ZPNkL74qm1ECBBCxxzT5hd4tV1ct9OT+LGNCcSx03y2VmFZll8zlQ2WLI=; 7:i1AHilU3n9wmeoC7cP7QESR4jTI+6I6CM22zrRV5/VBddBYLJCPlzbUNIEHgN8FM8YPxvoDtdxqMzhwMvioU1MkcM9Gzb7RcTOXtGAbvw3uLiEh4riIK1K7KweniIrJu8qoCib0xiCdFi0dizoaAybS5oY9wpHww+ADNlegM98bq6xJqvhoiAAjSUoWa7M/XlyvRDRjoO0LC2H+CB2+qdS8EHZ/s2tz64gUBhf0S3r4=
x-ms-exchange-antispam-srfa-diagnostics: SSOS;SSOR;
x-forefront-antispam-report: SFV:SKI; SCL:-1; SFV:NSPM; SFS:(10009020)(6009001)(376002)(346002)(377454003)(24454002)(199003)(189002)(110136005)(6116002)(3846002)(229853002)(50986999)(2900100001)(966005)(83506001)(189998001)(102836003)(5660300001)(25786009)(81166006)(81156014)(105586002)(305945005)(478600001)(7736002)(8676002)(413944005)(72206003)(101416001)(561944003)(86362001)(8936002)(2501003)(5250100002)(6486002)(66066001)(6512007)(53546010)(786003)(54906003)(2906002)(97736004)(106356001)(54356999)(316002)(76176999)(58126008)(6506006)(6436002)(74482002)(68736007)(3280700002)(3660700001)(53936002)(36756003)(230783001)(4326008)(6306002)(14454004)(42882006)(8666007)(6246003)(2950100002)(2171002)(99286003); DIR:OUT; SFP:1101; SCL:1; SRVR:AM4PR0301MB1907; H:AM4PR0301MB1906.eurprd03.prod.outlook.com; FPR:; SPF:None; PTR:InfoNoRecords; A:1; MX:1; LANG:en;
x-ms-office365-filtering-correlation-id: 189af7cf-5904-4977-2a10-08d509b47cdf
x-microsoft-antispam: UriScan:; BCL:0; PCL:0; RULEID:(22001)(2017030254152)(2017052603199)(201703131423075)(201703031133081)(201702281549075); SRVR:AM4PR0301MB1907;
x-ms-traffictypediagnostic: AM4PR0301MB1907:
x-exchange-antispam-report-test: UriScan:(192374486261705)(148717330147763);
x-microsoft-antispam-prvs: <AM4PR0301MB1907344F5A9743FD39444B2EBC7D0@AM4PR0301MB1907.eurprd03.prod.outlook.com>
x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(100000700101)(100105000095)(100000701101)(100105300095)(100000702101)(100105100095)(6040450)(2401047)(8121501046)(5005006)(93006095)(93001095)(100000703101)(100105400095)(3002001)(10201501046)(6041248)(201703131423075)(201702281529075)(201702281528075)(201703061421075)(201703061406153)(20161123562025)(20161123558100)(20161123560025)(20161123564025)(20161123555025)(6072148)(201708071742011)(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: 0448A97BF2
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: <C42C6E3F7257A746A085B3AAC439FA8B@eurprd03.prod.outlook.com>
Content-Transfer-Encoding: base64
MIME-Version: 1.0
X-OriginatorOrg: rhul.ac.uk
X-MS-Exchange-CrossTenant-originalarrivaltime: 02 Oct 2017 16:41:53.5931 (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/UrOowjV9n6XedE5WiWTEr5eghVU>
Subject: Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06
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: Mon, 02 Oct 2017 16:42:03 -0000

Dear Stefano, Priyanka and Viet,

Thanks for bringing this new research to the list. We (the chairs) really
welcome your work, and look forward to hearing from the draft's authors on
how they would view the proposed change to the draft that is implicit in
your message. There is no problem for us to extend the duration of
on-going "last call" for the draft in order to discuss it in detail.

At the same time, we would encourage you to put the details of your
analysis in the public domain as soon as you have it ready, so that
everyone can start to look at the fine detail.

Best wishes,

Kenny (for the chairs)

On 30/09/2017 15:00, "Cfrg on behalf of Stefano Tessaro"
<cfrg-bounces@irtf.org on behalf of tessaro@cs.ucsb.edu> wrote:

>Dear CFRG:
>
>We wanted to bring to your attention a potential optimization of the
>key-derivation step in AES-GCM-SIV that has come out of some of our
>related research work. Sorry this comes somewhat late: We are in the
>process of finalizing a clean write up, but due to time sensitivity,
>we wanted to make the CFRG list aware of this related work.
>
>Currently, the key-derivation function DeriveKey of AES-GCM-SIV uses
>4-6 AES calls (4 to generate a 256-bit key, and 6 to generate a
>384-bit key). The overhead of key derivation over plain GCM-SIV can be
>up to 10% for messages under 1KB (according to the authors’
>benchmarks). Our findings suggest a simple optimization that halves
>the number of calls.
>
>Concretely: Suppose that we have a master key K and a 96-bit nonce N.
>If we want to produce a 256-bit key, DeriveKey(K,N) will output
>
>AES_K(pad(N, 0)) || AES_K(pad(N, 1)),
>
>whereas if we want to produce a 384-bit key, we will instead output
>
>AES_K(pad(N, 0)) || AES_K(pad(N, 1)) || AES_K(pad(N, 2)).
>
>Here, we demand that pad(N, 0), pad(N, 1), pad(N, 2) is different from
>pad(N’, 0), pad(N’, 1), pad(N’, 2), and that pad(N, 0) is not a
>possible input to AES within CTR encryption. Due to the way in which
>AES-GCM-SIV already adopts domain separation elsewhere, it is enough
>to implement pad(N, i) as the concatenation of the 96-bit nonce N and
>a 32-bit counter of value i, but here note that one has to swap the
>relative ordering of nonce and counter in the current proposal, namely
>the nonce comes first, and then the counter.
>
>To see why this would work, we note that the current DeriveKey
>function, and other proposals by Iwata and Seurin, are required to be
>a highly-secure pseudorandom function. Intuitively, this is because
>the current approach to prove security of AES-GCM-SIV reduces (as an
>intermediate step) to the security of GCM-SIV, and in turn of AES,
>under (multiple) independent random keys. This independence is not
>necessary in general, and security proofs go through even when key
>distributions are much more structured, such as the one produced by
>our simple DeriveKey proposal. (This can be validated in the so-called
>ideal cipher model, and we are not aware of any cryptanalytic insights
>that would invalidate this when using AES.) Similar ideas of more
>structured block-cipher based key-derivation have been used in
>different contexts, e.g., in https://eprint.iacr.org/2017/877.
>
>We can prove excellent security bounds for this variant of
>AES-GCM-SIV, in particular in the so-called “multi-user setting”,
>where attackers are accessing multiple instantiations of the scheme
>under independent keys (think of this as multiple TLS sessions using
>the scheme). In this case, we obtain a bound of the order LB / 2^{128}
>+ d(T + L) / 2^k, where: L is a bound on the number of blocks, B is a
>bound on the number of blocks encrypted/verified for a nonce-user
>pair, d is the maximum number of users that re-use a nonce in
>encryption queries, T is a bound on the time-complexity of the
>attacker, and k is the key length of AES, which is either 128 or 256
>bits. (For the single-user setting then obviously d = 1.) If nonces in
>encryption queries are picked at random then d is a small constant,
>and thus the multi-user security is roughly the same as the
>single-user security. (In particular, there is a folklore
>understanding that multi-user security fails when more than 2^{64}
>users are involved, for k = 128, as two of them will likely have the
>same key, but show that this is not an issue for AES-GCM-SIV.)
>
>If nonces are picked arbitrarily then d can be as big as the number of
>queries; in this case we need to pick key length k = 256 for high
>security in the multi-user setting.
>
>We note that previous analyses do not consider the multi-user setting.
>
>Best,
>
>Priyanka Bose (UC Santa Barbara)
>Viet Tung Hoang (Florida State University)
>Stefano Tessaro (UC Santa Barbara)
>
>
>On Sat, Sep 16, 2017 at 5:15 PM, Alexey Melnikov
><alexey.melnikov@isode.com> wrote:
>> Dear CFRG participants,
>>
>> This message starts 2 week RGLC on "AES-GCM-SIV: Nonce Misuse-Resistant
>> Authenticated Encryption" (draft-irtf-cfrg-gcmsiv-06), that will end on
>> October 1st. Please send you comments, as well as expression of support
>>to
>> publish as an RFC (or possible reasons for not doing so) in reply to
>>this
>> message or directly to CFRG chairs. Your feedback will help chairs to
>>decide
>> whether the document is ready for review by IRSG and subsequent
>>publication
>> as an RFC.
>>
>> Thank you,
>> Kenny and Alexey
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>
>
>
>-- 
>Stefano Tessaro
>Assistant Professor of Computer Science
>University of California, Santa Barbara
>http://cs.ucsb.edu/~tessaro/
>
>_______________________________________________
>Cfrg mailing list
>Cfrg@irtf.org
>https://www.irtf.org/mailman/listinfo/cfrg