Re: [Cfrg] AES GCM SIV analysis

Shay Gueron <shay.gueron@gmail.com> Wed, 18 January 2017 18:06 UTC

Return-Path: <shay.gueron@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 45EB91294AC for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 10:06:38 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.689
X-Spam-Level:
X-Spam-Status: No, score=-2.689 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, T_FREEMAIL_DOC_PDF=0.01] 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 UpgRJ7OKGi70 for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 10:06:35 -0800 (PST)
Received: from mail-yw0-x22b.google.com (mail-yw0-x22b.google.com [IPv6:2607:f8b0:4002:c05::22b]) (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 87889129401 for <cfrg@irtf.org>; Wed, 18 Jan 2017 10:06:35 -0800 (PST)
Received: by mail-yw0-x22b.google.com with SMTP id l75so13962485ywb.0 for <cfrg@irtf.org>; Wed, 18 Jan 2017 10:06:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=F+HqM395ZtJXa8ERswnWx4sQMNGTnuDeLo0795wqm0o=; b=COTZyBe/8T8FKFPnZ09o7LyHZpB8SCrReCyoCB7pljZAMREr1/q1iD/Ef6g2CprR7D LA+d2rbXblvKOvV4kSmDUxuQpSK85E5jjBNn4iRptJItCB2+y+Y2psfc9ODcPTdlWDc2 wdrL98sAPQQvZpfAc+5r5zqGqN9xO41p5zijCAQfLcC3zZDBaUmU2ZPfI2Hk6he3iWg/ W0zf45UE6CIpmHflWYIRgATpp/dj7VtXF36rPrKJqRMgXK13+twodQLSGQGmwMfxR2KH t9RtTkBFiQkXwmHpLb+JGT72+hXvTsQCzW1XSs9ydsp6gIIC9CSUlqhVQzfwsr7k+C3A izug==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=F+HqM395ZtJXa8ERswnWx4sQMNGTnuDeLo0795wqm0o=; b=ECHKYSoYbDOG62SDdZSLFKIMkwwrgwpv7ZAs1ze/ooHyxnlwiunKg32QwHEO2DNat3 GZVNXLT7RYBulAcUhvV+sOIjyq9dSE/cdtYiMjOu/zNFx7v3XWQWWPdXCh/s9XbqYtRV z1ujzahvf3RPhTRvVKkhfph2T2nCwWHZwRkyXA2FKbYiRUuhpuvm2Z+B5d/c4kgz6jDv DnXAsI4Zc8qOD6+ZsJiQVvYTgQq/nPnu2XQyy6v5Jr5kMFK8Z4sKamQubMWODUsrbJry aReKpMddHDk+RpPHut4e3TnXVMTe/CfhowwhW384b896uLggYQ4znxdwwbQiOLwVTCci kecQ==
X-Gm-Message-State: AIkVDXIF75cQvW7t2FLV6yDeH5XgK3q1jsB+6NyVsZZJ1NpGZCtGlUfMddxzLw7qBKze4i8YkSAF0fbLbULG3g==
X-Received: by 10.129.158.144 with SMTP id v138mr3477493ywg.65.1484762794517; Wed, 18 Jan 2017 10:06:34 -0800 (PST)
MIME-Version: 1.0
Received: by 10.129.160.141 with HTTP; Wed, 18 Jan 2017 10:06:33 -0800 (PST)
In-Reply-To: <CAMfhd9V77LN41QTt4YvNs-bjUan_PtdrEiQeHvKXY+G+k2z1kw@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>
From: Shay Gueron <shay.gueron@gmail.com>
Date: Wed, 18 Jan 2017 10:06:33 -0800
Message-ID: <CAHP81y8+rABGeFpjGi0gcG4QsyoOnmxYsYpqyzXiB1ZzwP9jrQ@mail.gmail.com>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: multipart/mixed; boundary=94eb2c0b8d1ef19e7505466246c4
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/12QqTcByEZb4TfIuwu3n4mWKVBM>
X-Mailman-Approved-At: Thu, 19 Jan 2017 08:09:59 -0800
Cc: "Cooley, Dorothy E" <decoole@nsa.gov>, Yehuda Lindell <Yehuda.Lindell@biu.ac.il>, "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 18:06:38 -0000

Dear CFRG,

In the interests of keeping things on the working-group mailing list, I am
including the two follow-ups that we sent, previously, in response to this.


A note: the discussion with  "NSA Information Assurance Standards" team
took place in two  back-and-forth iterations. Hence we sent two replies,
which are attached here.

Thank you, Shay Gueron


2017-01-18 9:34 GMT-08:00 Adam Langley <agl@imperialviolet.org>rg>:

> 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
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>