Re: [Cfrg] AES GCM SIV analysis

Adam Langley <agl@imperialviolet.org> Wed, 18 January 2017 17:34 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 E39141294A9 for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 09:34:34 -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 htmP9ZGyh_Zv for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 09:34:33 -0800 (PST)
Received: from mail-it0-x241.google.com (mail-it0-x241.google.com [IPv6:2607:f8b0:4001:c0b::241]) (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 DF2151294EF for <cfrg@irtf.org>; Wed, 18 Jan 2017 09:34:32 -0800 (PST)
Received: by mail-it0-x241.google.com with SMTP id e137so2369224itc.0 for <cfrg@irtf.org>; Wed, 18 Jan 2017 09:34:32 -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:cc; bh=vcW8TXW5uP7WppYnxFg3suDHrEu9mtuRqgixxvHNcgk=; b=lwEPpR6ZANvUmlie72yA7e7FVstjrFoRcNcAnqaIXYNisbYefS/ktxWDTP7wWUppSp m340SX96fUhdhu0dHUvab1qJF2li4Hfzo0DTt2Z/PldO6meSek+Ckgsf8LLwyl/vWjzo TCNLYcrKaJxh07RqYwSjTKGcLIS97X5Kngpx5vEmp1BOngs+3Ser/n7j1BchkyoDS6ZF My+/Y038gdDtaVp08eIH/vH2Ht0qNaJMbvmTD4rIeZ/drgXU4NR5/kKsPwyDfVn0Au/B nwCAYMN9aX3HTFQ5iqnUJBOawzJzodv2I7yQ3JQfECr/TCTbTLz6BLahVdawjbSfCa6s WXog==
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; bh=vcW8TXW5uP7WppYnxFg3suDHrEu9mtuRqgixxvHNcgk=; b=npP0htExakBMoA7GXloW88Z81heTuTMBH89yDDTTm8wToxQkX+UjwPwBch4tseHFpa qz3tnCMGc9qPd/NDIbXrVJflKyhbM7heOCrelghbH+rjgpy9JlhsDxljKyGgDVuSJx21 UM/uDre6D983m57pob4giPdcTLkAZJYgR0+exaOTbrjUf24ryE/UlSFWdgfoQpXDrfeE 3E4yc4PQuubx7a04XiSey/Id41s7gswG/BooCHljHYWJpHOyKwSk2l5xtJhIMEEO4vtv hZbZMriPWvLWIeMjgNpdgwH5k2OeE/wco4tiKyNqJqrXvrRtEa4a/YFVlfXyV+oB4ZZB Ztbw==
X-Gm-Message-State: AIkVDXLQPoTpg14Lstz/b7x9DWV8D8RqsDTXr+W0zl43Wgy40jAh+DBX8Phzcs4/ONGp2wS054iB3RcxM1eiSw==
X-Received: by 10.36.52.203 with SMTP id z194mr27625723itz.121.1484760872147; Wed, 18 Jan 2017 09:34:32 -0800 (PST)
MIME-Version: 1.0
Sender: alangley@gmail.com
Received: by 10.36.144.4 with HTTP; Wed, 18 Jan 2017 09:34:31 -0800 (PST)
In-Reply-To: <D120A224329B7F4CA6F000FB5C0D964C01EBE26FEA@MSMR-GH1-UEA07.corp.nsa.gov>
References: <D120A224329B7F4CA6F000FB5C0D964C01EBE26F73@MSMR-GH1-UEA07.corp.nsa.gov> <D120A224329B7F4CA6F000FB5C0D964C01EBE26F86@MSMR-GH1-UEA07.corp.nsa.gov> <D120A224329B7F4CA6F000FB5C0D964C01EBE26FEA@MSMR-GH1-UEA07.corp.nsa.gov>
From: Adam Langley <agl@imperialviolet.org>
Date: Wed, 18 Jan 2017 09:34:31 -0800
X-Google-Sender-Auth: XO6O6vZFmrt-XK8g1qt9M2YLtYs
Message-ID: <CAMfhd9V77LN41QTt4YvNs-bjUan_PtdrEiQeHvKXY+G+k2z1kw@mail.gmail.com>
To: "Cooley, Dorothy E" <decoole@nsa.gov>
Content-Type: text/plain; charset=UTF-8
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/rnyd9zoCZgVM8ruK3Zh_aLb-WIg>
Cc: "cfrg@irtf.org" <cfrg@irtf.org>
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 17:34:35 -0000

On Wed, Jan 18, 2017 at 8:49 AM, Cooley, Dorothy E <decoole@nsa.gov> wrote:
> NSA's Information Assurance organization did some analysis of AES-GCM-SIV,
> as described in "AES-GCM-SIV:  Nonce Misuse-Resistant Authenticated
> Encryption", dated August 29, 2016 [1].  We shared this analysis privately
> with the three authors of AES-GCM-SIV, who requested that we post it to the
> CFRG forum. The attachment describes the results of the analysis. We believe
> the authors will be posting an update shortly.
>
>
>
> Any comments on this work can be directed to me.  But I will note that I
> didn't do the actual analysis (I can't claim to be a 'real' cryptographer
> these days).
>
>
>
> Deb Cooley
>
> NSA Information Assurance Standards.
>
> decoole@nsa.gov

Dear CFRG,

We thank Deb Cooley's team very much for doing this analysis! As she
mentioned, they shared their results with us prior to posting here so
we already had an update ready and we've just posted
https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-03.

This update contains three noteworthy changes:

1) We now XOR the nonce into the result of POLYVAL before encrypting
to form the tag. This was in the original paper, it was even specified
for /decryption/ in -02, but it was omitted in the specification for
encryption. This was a mistake. Without it, an attacker can build a
lookup table of encryptions of zero under a variety of per-nonce keys
and then attack them in parallel (as pointed out in the comments from
the IAD), under a single-user-multi-key model.

Draft -03 fixes this omission and reintroduces the nonce.

2) A different KDF. As I mentioned at the previous CFRG meeting (in
Seoul, 2016) , we had this design in mind but didn't feel that it
warranted a new version of the design. However, since we needed a
respin because of (1), we have included it.

Previously, per-nonce key material was generated by repeated
encryption, E(nonce), E(E(nonce)), and so on. This cascade leads to
impractical but needling issues including those noted by IAD. We now
generate keys by using counter mode and discarding half of each
ciphertext block. This solves those issues and also gives improved
indistinguishability bounds.

In order to make room for the counter, the nonce size has been reduced
to 96 bits.

3) A much more minor change is that we now suggest a limit of 2^8 as
the maximum number of plaintexts encrypted with a single nonce. We
previously noted that AES-GCM-SIV with a fixed nonce is similar to
AES-GCM with a random nonce, and that NIST recommends a limit of 2^32
messages in that context.

Note that we do NOT recommend nonce reuse by choice even inside
AES-GCM-SIV. This is for two reasons. First, encrypting the same
message twice will be detected. Second, the security bounds when using
different nonces are better. For example, when encrypting 2^{32}
messages with the same nonce, the probability of a bad event is
2^{-32}. However, as we have shown, when encryption with different
nonces, it is possible to go up to about 2^{50} messages without any
problem.

If nonces repeat mistakenly, for which providing protection is the
main aim of this mode of operation, then very strong bounds are still
obtained for a large number of ciphertexts (much more than 2^32) as
long as a single nonce is not repeated more than say 2^8 times. In
practice, such an event is highly unlikely.



Cheers

AGL