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