[Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document ---- Some clarifications

"Gueron, Shay" <shay.gueron@gmail.com> Tue, 05 April 2016 13:14 UTC

Return-Path: <shay.gueron@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id 814C612D80E for <cfrg@ietfa.amsl.com>; Tue, 5 Apr 2016 06:14:36 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-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 ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id x2IgQMQJOOUx for <cfrg@ietfa.amsl.com>; Tue, 5 Apr 2016 06:14:30 -0700 (PDT)
Received: from mail-wm0-x236.google.com (mail-wm0-x236.google.com [IPv6:2a00:1450:400c:c09::236]) (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 299C312D69C for <cfrg@irtf.org>; Tue, 5 Apr 2016 06:14:16 -0700 (PDT)
Received: by mail-wm0-x236.google.com with SMTP id n3so21168420wmn.0 for <cfrg@irtf.org>; Tue, 05 Apr 2016 06:14:16 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=from:to:subject:cc:date:message-id:in-reply-to:reply-to:user-agent :mime-version; bh=9MVDqq6p6EJhOGStyVvj28vVd64gZz9svr4sE0M1haE=; b=yiOVa0u37chg/Ef53LbngaeYiO9T+cdeaGJbn57kbwY9jpscnLsLDXz0bakuOAmN6s SfhfMbHxPh6avXZR2U+UaNIUpwweH5ORbEdNCmCEeQgjWGpfBPPTS1vnb9iIOet5gY9v 9o1MQINotoWGK02mZY1A8uACsq8byrFSr4JpM9HpDRUmJ3Y/VJlPdFQ2f2unAIJyGx1H 3jbhMPU4UcYHN2tUcYg4CtTES5b8+dW974JvP27sL0IcvOk9T5ecxZDWAnl1OeYSeS6m TjECiNaIfC5y0Da/tRGo0VJQf17EXAWV4JQLEL63KKi24dZ2k4Rh19tCyK4n7N1Nhs32 oc1A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:subject:cc:date:message-id:in-reply-to :reply-to:user-agent:mime-version; bh=9MVDqq6p6EJhOGStyVvj28vVd64gZz9svr4sE0M1haE=; b=KT45KTIhlpKEzRShJ2qxvqJz31Q2gQMFHbE4PzlE2xUhFlyBiC2DmODvT+qRBrOQa7 ppxuiB5ukDxMwLFfFnvhJgMjmC1TcYm+zSl3WvffuNShgRyXptlsnISZBy8BUNcB1PM7 8RjkePSMkkC1DV3O/0TOuXhw4DUlQqAIfUhRKH0PNYMPUSyCAkDKLpegUTXQ5NsJl+IH byUnky0AZxW51IscCnmdNZysLmwjK30tVkzIHCbMLFOfga7H9W90B/APOJLqE1E/KPhB tjWSmb2QrUu8S3k0cHtvyIhauEaLexydCskxIC2EGN1VgsKMZdzc/z5Pz/jIfqBHUTti m7zA==
X-Gm-Message-State: AD7BkJJJYpTGSWWBTu9jWdy+HNbhks54v3PGwIFYIpWqUxTd62SRLz19O3Y+qJG8oShLlA==
X-Received: by with SMTP id c128mr18039990wma.10.1459862054680; Tue, 05 Apr 2016 06:14:14 -0700 (PDT)
Received: from [] (bzq-79-177-151-59.red.bezeqint.net. []) by smtp.gmail.com with ESMTPSA id x2sm23156951wjr.33.2016. (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Tue, 05 Apr 2016 06:14:13 -0700 (PDT)
From: "Gueron, Shay" <shay.gueron@gmail.com>
To: cfrg@irtf.org
Date: Tue, 05 Apr 2016 13:14:05 +0000
Message-Id: <em615f096a-5286-4b23-b267-26099193d002@sgueron-mobl3>
In-Reply-To: <CALCETrVP_Op+-jpoP0JBFWZZQkvo0JYuLNtAS=itSPTb4Ptkuw@mail.gmail.com>
User-Agent: eM_Client/6.0.24316.0
Mime-Version: 1.0
Content-Type: multipart/alternative; boundary="------=_MB501F1D44-E07B-4423-949A-91E7DB8EAFC9"
Archived-At: <http://mailarchive.ietf.org/arch/msg/cfrg/o4b2mH1DGaEmz1jw9uB5A4ipmKA>
Cc: Adam Langley <agl@imperialviolet.org>, Yehuda Lindell <yehuda.lindell@biu.ac.il>, Adam Langley <agl@google.com>
Subject: [Cfrg] Adopting "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" as a CFRG document ---- Some clarifications
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.17
Precedence: list
Reply-To: "Gueron, Shay" <shay.gueron@gmail.com>
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: Tue, 05 Apr 2016 13:14:36 -0000

Hello –

After we posted the AES-GCM-SIV draft, we saw several questions. We are 
trying to address the points that were raised, hence the lengthy mail.

Firstly, we’re sensitive to the concern that we’re pre-empting CAESAR 
here but we think that this is significantly smaller in scope than what 
CAESAR is attempting. AES-GCM-SIV just reformulates AES-GCM in a 
different order so that we can address some situations where the nonce 
requirements of AES-GCM are troubling.

AES-GCM-SIV has roughly the same cost as AES-GCM, which is already 
widely used on various platforms, both with and without AES hardware 
support. But, from an engineering point of view, there are a lot of 
machine with AES-GCM hardware support, which is driving the use of 
AES-GCM because of its performance on those machines. And it’s driving 
use of AES-GCM even in cases where the nonce can’t be a simple counter. 
Thus the motivation for a tweak to AES-GCM that avoids this problem.

We gladly offer it for free, for anyone to enjoy and use.

The code (reference, performance code, and performance numbers) is 
available in the github repository at 
https://github.com/Shay-Gueron/AES-GCM-SIV. BoringSSL will integrate it 
as well, so it could be used directly from that library.

The (ACM CCS) paper described a GCM-SIV implementation with 128-bit 
keys. The CFRG submission is different in two respects:
1. A 256-bit version that is added.
2. There is key derivation added (based on the nonce) to refresh the 
encryption key for each record.

The purpose of #2 is to allow AES-GCM-SIV to use a single key multiple 
times. In the original paper version, an IV is derived from the 
universal hash function (and the nonce) over the message, and occupies 
95 bits of the counter block during the encryption. Collisions are 
imminent after 2^48 uses, and to maintain safety margins, we would need 
to restrict the usage of one key to 2^32 messages. This could seem like 
a real constraint for a real AE scheme. With a differently derived key 
(derived from the nonce), the lifetime of one key can be extended.

The cost of extending the lifetime of the key is that of computing a key 
schedule, but this overhead is small on the target platforms that have 
AES hardware support.

To clarify a possible confusion about the 256-bit variant: no 256-bit 
key is ever derived from a 128-bit key. A 256-bit encryption key is 
derived from the 256-bit master key and a (128-bit) nonce but two 
encryptions. The authentication key has 128 bits, and so does the 
authentication tag.

Regarding the 256-bit key variant, and the key derivation in general, we 
are currently working on a full proof of security to show the exact 
bounds. However, for now, we would like to point you to this sketch of a 
proof, showing that obtaining a key by applying AES-256 to the nonce 
(twice) as we do, does not harm security (the full proof later will show 
that it significantly increases the security).


Let \Pi=(Gen,Enc,Dec) be an encryption scheme (including mode of 
operation) that uses AES256 directly and is (t,q,e)-indistinguishable 
(time t, with q queries to encryption oracle, advantage e). Now, modify 
to \Pi’=(Gen’,Enc’,Dec’) where the only difference is that Enc’ begins 
by deriving a 256 bit key by applying AES256 to the nonce with 0 and 
then to the nonce with 1.

Then, the distinguishing probability for \Pi’ is at most (t,q,e) PLUS 
what can be gained by distinguishing AES256 from a PRP with the number 
of queries equalling twice the number of different nonces queried PLUS 
2^{-128}. This follows since a distinguisher D for AES256 can derive the 
keys using its oracle. We have the following observations:

1) If the function being accessed by D is random, then the key is truly 
random EXCEPT that it cannot be of the form k'||k’. Thus, with 
probability 2^{-128} the key will be of this form and it won’t be the 
same as the original encryption scheme. Otherwise, it’s identical to the 
original encryption scheme.

2) If the function being accessed by D is AES256, then this is exactly 
the modified encryption scheme.

Note that the number of queries made by D to its oracle is twice the 
number of different nonces. Thus, this is the only difference.

We stress that the above just shows that nothing is lost by doing this 
derivation. However, we do it in order to gain inside \Pi. The bounds 
will be published soon.

Thank you,
Shay, Adam, Yehuda