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

Stefano Tessaro <> Sat, 30 September 2017 14:00 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id EDF0113292F for <>; Sat, 30 Sep 2017 07:00:17 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -0.499
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id twGn9iXFEMYa for <>; Sat, 30 Sep 2017 07:00:15 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4010:c07::22c]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 41238132D54 for <>; Sat, 30 Sep 2017 07:00:15 -0700 (PDT)
Received: by with SMTP id k23so2015106lfi.11 for <>; Sat, 30 Sep 2017 07:00:15 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; 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;; 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 with SMTP id q130mr1519378ljb.41.1506780013017; Sat, 30 Sep 2017 07:00:13 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Sat, 30 Sep 2017 07:00:11 -0700 (PDT)
In-Reply-To: <>
References: <>
From: Stefano Tessaro <>
Date: Sat, 30 Sep 2017 16:00:11 +0200
X-Google-Sender-Auth: 5UlmJcf8mbjBexFCObX6qwprrLM
Message-ID: <>
To: "" <>
Cc: Alexey Melnikov <>, Viet Tung Hoang <>, Priyanka Bose <>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Archived-At: <>
Subject: Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06
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: 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

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.


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

Stefano Tessaro
Assistant Professor of Computer Science
University of California, Santa Barbara