### Re: [Cfrg] AES GCM SIV analysis

Adam Langley <agl@imperialviolet.org> Wed, 18 January 2017 18:25 UTC

Return-Path: <alangley@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 EF3C2129551
for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 10:25:41 -0800 (PST)

X-Virus-Scanned: amavisd-new at amsl.com

X-Spam-Flag: NO

X-Spam-Score: -2.598

X-Spam-Level:

X-Spam-Status: No, score=-2.598 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
FREEMAIL_FORGED_FROMDOMAIN=0.001, FREEMAIL_FROM=0.001,
HEADER_FROM_DIFFERENT_DOMAINS=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 ([4.31.198.44])
by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id Yf4vSCrTOEsd for <cfrg@ietfa.amsl.com>;
Wed, 18 Jan 2017 10:25:39 -0800 (PST)

Received: from mail-io0-x231.google.com (mail-io0-x231.google.com
[IPv6:2607:f8b0:4001:c06::231])
(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 B9C441294DB
for <cfrg@irtf.org>; Wed, 18 Jan 2017 10:25:39 -0800 (PST)

Received: by mail-io0-x231.google.com with SMTP id j13so18684920iod.3
for <cfrg@irtf.org>; Wed, 18 Jan 2017 10:25:39 -0800 (PST)

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:content-transfer-encoding;
bh=gY57brPH7WuA3k+tKUFRCOFdci7lqOKp4EEjBVkE3ZM=;
b=Q2fafGxPzsP0ACfQ0cPuHpMyUjcvTLQ7KmG00UOHTBla5RG4jcNhdrqRA81G12O9HO
tkRvMsl35HGVs9hnHt5CjA39yKiCfMnWx6IAcAvMI1z4nhzHDQhUepQVykCnO3YlgunW
u3J46jV5Rxxpvs5NWZWLtWbd7Ba41/0gufj89K48HG135T5PFLqyXysBL8o+idYVETeM
UBqZCjoBSjAikmBkNlYjuRbk0/pPgWa9eLI3aI1hgB62nVjveTjfeAsaQdfmjIvLYkvG
8riQdnZm+orHX5JtNRpG/8TBvRKjyb88YBRWqE5n9dQOHW46ZtafEa69mRcDZOnR7cma
cLpA==

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:content-transfer-encoding;
bh=gY57brPH7WuA3k+tKUFRCOFdci7lqOKp4EEjBVkE3ZM=;
b=loXnjmVRWJyw16/6NCxa33ZiaD2ZwnHVKzc9oyca3o8mrrL40RwokEUlqlO7e70ENy
4j+vnnFPdRMHgWQrZtLol9Vt7+GtdnOtPuRFJE+dYSSrJbdUNUKq/UdAKOmjZ8Y8ZdHO
7mJpcadP/jXzd4tRlhspKwgm8e0vbeZ92yrsFRWwzB/t8Eey1dkuY8rF/Y1aGIywMa/K
IMEWwoxpwpNj4oQYbx109U0K9JkZ1vhgLVNBaHnXrYfMMJOyjILrZOFN0hSN1uK+ZFlY
LrTA69Kx8iLQkM7UbjcwiC+VMHHjVtbaQaduzSoOw05YR9tq/qI6boGgLk0+YKMuzSeB
Ftog==

X-Gm-Message-State: AIkVDXLVq5UODPbc2+hw6v0SqZEYwvw5/d2KSzmWEqfobRpDdxt2ePrj3Z3ck4WX/Qfj91nsYYqExj/jDuzOBg==

X-Received: by 10.107.9.141 with SMTP id 13mr5689176ioj.24.1484763938635; Wed,
18 Jan 2017 10:25:38 -0800 (PST)

MIME-Version: 1.0

Sender: alangley@gmail.com

Received: by 10.36.144.4 with HTTP; Wed, 18 Jan 2017 10:25:38 -0800 (PST)

In-Reply-To: <CAMfhd9U=E8bBaaRfs38E94TYJ4ryh2pRAXy370xOdYYXHUtLsw@mail.gmail.com>

References: <D120A224329B7F4CA6F000FB5C0D964C01EBE26F73@MSMR-GH1-UEA07.corp.nsa.gov>
<D120A224329B7F4CA6F000FB5C0D964C01EBE26F86@MSMR-GH1-UEA07.corp.nsa.gov>
<D120A224329B7F4CA6F000FB5C0D964C01EBE26FEA@MSMR-GH1-UEA07.corp.nsa.gov>
<CAMfhd9V77LN41QTt4YvNs-bjUan_PtdrEiQeHvKXY+G+k2z1kw@mail.gmail.com>
<CAMfhd9U=E8bBaaRfs38E94TYJ4ryh2pRAXy370xOdYYXHUtLsw@mail.gmail.com>

From: Adam Langley <agl@imperialviolet.org>

Date: Wed, 18 Jan 2017 10:25:38 -0800

X-Google-Sender-Auth: 3GJkyLVSn9lTbilDgOYtZxgfxPI

Message-ID: <CAMfhd9XnNsNPXAGx7jOoSTus8JyNTK0hCc-jmXo4siiDs+STYQ@mail.gmail.com>

To: "cfrg@irtf.org" <cfrg@irtf.org>

Content-Type: text/plain; charset=UTF-8

Content-Transfer-Encoding: quoted-printable

Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/pxUu3traVSUKZSPyX2dcQtwZyRQ>

Subject: Re: [Cfrg] AES GCM SIV analysis

X-BeenThere: cfrg@irtf.org

X-Mailman-Version: 2.1.17

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, 18 Jan 2017 18:25:42 -0000

Also, in the interests of keeping things on the working-group mailing list, I am including the two follow-ups that Shay and Yehuda sent, previously, in response to this. (The discussion took place in two back-and-forth iterations. Hence they sent two replies, which are attached here.) -----Message one----- We greatly thank you for your interest in the AES-GCM-SIV authenticated encryption scheme, and for your work on analyzing it. We begin with the first attack. It is well known that in the model of multi-key security, if there are M different users with M different keys, and the key-space is of size N, then it is possible to find one of the keys in time M/N. We cast the attacks you describe in this light. Specifically, since our CFRG essentially changes the keys in every encryption, we obtain a multi-key setting even for a single user. Considering, for example, attack number 1: this attack works since it is possible to obtain encryptions of a single known block under many keys. Thus, the original multi-key attack of [1] is applicable. Having said the above, we find that the tradeoff between the CFRG and original GCM-SIV paper to be favorable toward the CFRG. This is because as with all counter modes, the original GCM-SIV and GCM with a random nonce (counter) has the property that after 2^32 different encryptions, the probability of a collision on the nonce (counter) is about 2^-32. Now, if less than 2^32 encryptions are carried out, then neither the multi-key attacks nor the collision on the counter is a concern. However, if more than 2^32 encryptions are computed, then the amount of work required for the multi-key attacks is still extremely large, whereas the probability of a collision on the nonce becomes a very real concern. We do not dismiss the threat of multi-key attacks, and it has been recently noted that this may be a real problem in TLS sessions. This has prompted recent work, one example being [2]. Indeed, [2] explain that in TLS it is preferable to use a random nonce for GCM even though a fresh key is used in every session (and thus one could always start with a fixed nonce of 0). This is exactly to prevent/mitigate multi-key attacks. We stand behind our proposal to change keys in every message, and were surprised that changing the nonce does not solve the problem (Ref. [1] in your document). We then noticed that in the original GCM-SIV paper appearing in ACM CCS, we XOR the nonce with the result of POLYHASH on the AAD and message, and then encrypt it (using AES). While our intention was to mount some nonce-based key derivation on top of GCM-SIV, we forgot (in one of the versions of the proposal) this XOR in the CFRG specification. By returning this XOR, we mitigate the risk of multi-key attacks since different nonces would now not enable an attacker to obtain many encryptions of the same (known) block under different keys. Regarding the other attacks: Attack 3 requires 2^128 chosen plaintexts. We do not consider this to be realistic. Furthermore, when the block size is 128 bits then everything breaks well before that (with repeating inputs to AES). Attack 2 is just a type of time-space tradeoff and these types of bounds are always possible on block ciphers. Note also that in order to reduce the work time by just two bits, the number of queries required is already 2^96. As stated regarding attack 3, with a 128-bit block size everything breaks well before this anyway. Once again, we thank you for your interest in GCM-SIV, and we will make the change to mitigate the first attack as described. Although we think that users of GCM-SIV should not be concerned with the other attacks, as described above, we appreciate the feedback and we will document them for full transparency. [1] E. Biham. How to Forge DES-Encrypted Messages in 228 Steps. Information Processing Letters, 84(3):117-124, 2002. [2] M. Bellare and B. Tackmann. The Multi-user Security of Authenticated Encryption: AES-GCM in TLS 1.3. In CRYPTO 2016, Springer (LNCS 9814), pages 247-276, 2016. Shay Gueron and Yehuda Lindell -----Message two----- We thank you very much for your response, and greatly appreciate your feedback and analysis. We would like to point out what we recommend (and plan to post) a maximal number of usages (q_max) of a single master key, with AES-GCM-SIV. This would better put things in context. As we promised to the CFRG community since we posted the specifications, we are working on a paper that analyzes the scheme and derives this recommendation. Hopefully, it will be ready in a few weeks. In order to explain our bound, let us first denote the 2-key specification in the CCS paper by GCM-SIV (K1, K2, N, AAD, M). The CFRG proposal can then be viewed as a two step protocol: 1. Key derivation: Compute (Record_Encryption_Key, Record_Hash_Key) = KDF (Master_Key, N) 2. Encryption: Compute (Tag, C) = GCM-SIV (Record_Encryption_Key, Record_Hash_Key, N, AAD, M) We now consider the recommended restriction regarding the number q_max of times that the Master_Key can be used (which actually translates to how many different nonces can be used, but since a different nonce should be used for every message this is the same as the number of different messages, but messages can be long). Our calculation is that q_max ~ 2^47 is an appropriate recommendation in order to preserve the 2^-32 security margins recommended by NIST. This 2^47 limit is based on a failure of indistinguishability of the generated nonce-based keys, unlike the deeper failure that AES-GCM would suffer by a nonce misuse. This number shows that the additional key derivation increases the number of allowed usages of a (master) key for AES-GCM-SIV, compared to the CCS version that was limited to ~2^32 usages(and the security margins). We are working on a way to increase q_max even further, and this will be announced in the upcoming paper. >From a practical viewpoint, we comment that if a user sends, say, 1 million messages per second, then a key replacement after 2^47 usages would be necessary after ~4 years. Since AES-GCM-SIV is designed for cases where a user needs to encrypt multiple messages, but nonce uniqueness may be a concern, we suggest to compare q_max to the number of times that a key can be used with AES-GCM with a randomly selected 96-bit IV (i.e., 2^32). With this limit on q_max, we conclude that your mentioned attacks do not apply. We understand that you agree with this analysis. The last question that remains is regarding the current KDF that uses a hierarchy of keys, and this cascade generates some relation between the derived keys. We are not extremely concerned with 2^128 work to extract additional keys /after/ one key is compromised (with no cryptographic method know so far). However, we agree that for 256-bit keys, this should not be possible. This brings us to the question about the KDF. In fact, we have been contemplating amongst ourselves about a better KDF that not only has better indistinguishability bounds, but is also faster than the current one. Also, some CFRG member have very recently asked about this. Therefore, we do intend to replace the KDF, as follows. AES-GCM-SIV will receive a 96-bit nonce. The KDF will compute AES (Master_Key, IV || IntToString32 (j)) for j=0, …, 3 (128-bit key) or j=0, …, 5 (256-bit key). From each of these 4 (or 6) generated blocks, 64 bits will be discarded, and then pairs will be combined into 2 (3) 128-bit values. These will be used as the Record_Hash_Key and the Record_Encryption_Key. The indistinguishability advantaged of this KDF (assuming AES is a close approximation to a random permutation), is bounded by 6q/2^96 where q is the number of times that the KDF was called with a single (master) key (see [1]). Now, for q different random nonces, the probability of an r-multi-collision (i.e., at least one value appears at least r times), and hence also on the pernonce keys, can be bounded by 1/u^{r-1} * Binomial (q, r) (where u=2^96 here). Note that if for different nonces, there is a collision on the derived keys, this will not be a case of nonce misuse. We can require a limited number of allowed nonce repetitions. Based on the above calculation, the probability that selecting the nonce (uniformly) at random will show r-multi-collisions (for a large r), is negligible, when staying with the bounds of q_max. Assume now that for the q_max (randomly) generated nonces, each value appears at most 4 times. Using some bound on the (intentional) number of messages encrypted by one selected nonce (and the lengths of the messages and AAD’s), we can apply the security bounds that we have on GCM-SIV. We plan to post the updated specification next week. Thank you again, Shay and Yehuda [1] S. Gilboa, S. Gueron, “The Advantage of Truncated Permutations”, https://arxiv.org/abs/1610.02518 (submitted on 8 Oct 2016). [2] K. Suzuki, D. Tonien, K. Kurosawa, K. Toyota, “Birthday Paradox for Multi-collisions”, Proceedings of the 9th International Conference on Information Security and Cryptology, 29-40 (2006). http://dl.acm.org/citation.cfm?id=2172962

- [Cfrg] AES GCM SIV analysis Cooley, Dorothy E
- Re: [Cfrg] AES GCM SIV analysis Adam Langley
- Re: [Cfrg] AES GCM SIV analysis Adam Langley
- Re: [Cfrg] AES GCM SIV analysis Brian Smith
- Re: [Cfrg] AES GCM SIV analysis Shay Gueron
- Re: [Cfrg] AES GCM SIV analysis Adam Langley
- Re: [Cfrg] AES GCM SIV analysis Brian Smith
- Re: [Cfrg] AES GCM SIV analysis John Mattsson
- Re: [Cfrg] AES GCM SIV analysis Shay Gueron
- Re: [Cfrg] AES GCM SIV analysis Shay Gueron
- Re: [Cfrg] AES GCM SIV analysis Adam Langley
- Re: [Cfrg] AES GCM SIV analysis Dan Harkins
- Re: [Cfrg] AES GCM SIV analysis Adam Langley
- Re: [Cfrg] AES GCM SIV analysis Alex Cope
- Re: [Cfrg] AES GCM SIV analysis Watson Ladd
- Re: [Cfrg] AES GCM SIV analysis Shay Gueron
- Re: [Cfrg] AES GCM SIV analysis Alex Cope
- Re: [Cfrg] AES GCM SIV analysis Andy Lutomirski