Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06
Stefano Tessaro <tessaro@cs.ucsb.edu> Sat, 30 September 2017 14:00 UTC
Return-Path: <stefano.tessaro@gmail.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 EDF0113292F for <cfrg@ietfa.amsl.com>; Sat, 30 Sep 2017 07:00:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.499
X-Spam-Level:
X-Spam-Status: No, score=-0.499 tagged_above=-999 required=5 tests=[DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.199, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.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 twGn9iXFEMYa for <cfrg@ietfa.amsl.com>; Sat, 30 Sep 2017 07:00:15 -0700 (PDT)
Received: from mail-lf0-x22c.google.com (mail-lf0-x22c.google.com [IPv6:2a00:1450:4010:c07::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 41238132D54 for <cfrg@irtf.org>; Sat, 30 Sep 2017 07:00:15 -0700 (PDT)
Received: by mail-lf0-x22c.google.com with SMTP id k23so2015106lfi.11 for <cfrg@irtf.org>; Sat, 30 Sep 2017 07:00:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-transfer-encoding; bh=FxTP6m7g/aOOG5BSbX28baU+z3gRusJ27Z4QblLc4mw=; b=SK5ydaTkH1WT6D6NcM7m75C7FcjeGlF6ngHvHO7xmxEPP5P5vZ3axVpCp9iqNAO/YI 0spe4xoJ7ir5LEESQ+5CVv+QVyDQjMKei4OhHNgN+yz1svfHR79lB9+YdyLO1JhsyRJU 8csH0DZBVOGykbiwEEixSZK0kNPHFxwq5MPKj+WEl/5FctDTyxAsxiDYfuEnxz9MA1Dx mCoe6NyWVpOPEMPDljB2defxL9IAlHjQLDsxuBIsMeUFJtVAq7KfOqqCpY1CWPUHfjlE M5giLRZv1DWu2ybqZIg+Y4luHuz6ew3nzJPWxZlr/Vk8Ar/oCqRPUc9lkdaaHSrJqEIn 7xYg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc:content-transfer-encoding; bh=FxTP6m7g/aOOG5BSbX28baU+z3gRusJ27Z4QblLc4mw=; b=pTZyrCnJE6InOtIVXnG4ITiBtbdkyZwRJSfFor3zLtwiqR5dCAwy9pm49EyzuoKfzw wwtW9kby1CIErb1MOXeWzM2CC3vWk+aBmS7cQY4inkAmvIxE7K6qCGCjTzmmGgaYYxJE y7TyCrK4NEJBIo4ygLTKBkZ8MCAJQzMyhJ2mHyHnP5r/3UZuVEktxUDDpfTTKDz0zqs1 0omlOACV3b8Tgm/uUAjPGbqep5KDeQ9EfHAPsDUnut3Z1P3CdceAmh3srWDHriG3Oh6d zgH8hKbWWnn7VDAXOStgYhikgv8jtVvEFV2RjqkmyCoBynJ6e7hXPmp1bPWWIif++vhU ranw==
X-Gm-Message-State: AMCzsaX2qhLh5/CZ3V2GC7w2/HFVUiuXn6MAvIXQowMPv+Um9yZDBeqG S2Ui1BLbmWc5qZN/Eei4ucDwTJUYhmfGFq/ESywQcMS+
X-Google-Smtp-Source: AOwi7QCu50cYmen+2HXU38rwIJuC+T6DecuE+SN2rLuibLWyD3zMphgheaS9rvHt/ko2IOgv4TJMBkSEYQ1vx+9Jx84=
X-Received: by 10.46.92.136 with SMTP id q130mr1519378ljb.41.1506780013017; Sat, 30 Sep 2017 07:00:13 -0700 (PDT)
MIME-Version: 1.0
Sender: stefano.tessaro@gmail.com
Received: by 10.25.76.215 with HTTP; Sat, 30 Sep 2017 07:00:11 -0700 (PDT)
In-Reply-To: <EA4347BF-D26F-4303-9A8D-E7B28986DE56@isode.com>
References: <EA4347BF-D26F-4303-9A8D-E7B28986DE56@isode.com>
From: Stefano Tessaro <tessaro@cs.ucsb.edu>
Date: Sat, 30 Sep 2017 16:00:11 +0200
X-Google-Sender-Auth: 5UlmJcf8mbjBexFCObX6qwprrLM
Message-ID: <CAEB_pddu5Z9xo7y3v9rbr-1inzyf9=0YsO2M1rNRF4MWamK=5Q@mail.gmail.com>
To: "cfrg@irtf.org" <cfrg@irtf.org>
Cc: Alexey Melnikov <alexey.melnikov@isode.com>, Viet Tung Hoang <tvhoang@cs.fsu.edu>, Priyanka Bose <priyanka@cs.ucsb.edu>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/stuWAXaqRUj4t2Q8ECzhalldkQg>
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: Sat, 30 Sep 2017 14:00:18 -0000
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/
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Paterson, Kenny
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Yehuda Lindell
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Stefano Tessaro
- [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06 Alexey Melnikov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Andy Polyakov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Blumenthal, Uri - 0553 - MITLL
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Ted Krovetz
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Watson Ladd
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Adam Langley
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Andy Polyakov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Andy Polyakov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Andy Polyakov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Andy Polyakov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Shay Gueron
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Andy Polyakov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Shay Gueron
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Andy Polyakov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Andy Polyakov
- Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv… Stefano Tessaro