Re: [Cfrg] AES GCM SIV analysis

Shay Gueron <shay.gueron@gmail.com> Wed, 18 January 2017 17:55 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 CF8CF12954A for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 09:55:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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_NONE=-0.0001, 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 njJLX92hnLzu for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 09:55:22 -0800 (PST)
Received: from mail-yb0-x22f.google.com (mail-yb0-x22f.google.com [IPv6:2607:f8b0:4002:c09::22f]) (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 84F601294C8 for <cfrg@irtf.org>; Wed, 18 Jan 2017 09:55:21 -0800 (PST)
Received: by mail-yb0-x22f.google.com with SMTP id w194so6485071ybe.0 for <cfrg@irtf.org>; Wed, 18 Jan 2017 09:55:21 -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=godffJjkjLq26O+dv8lgsJThrYrvx+rH9EgU7Oz/31I=; b=JP5ULxxEUrwjmH/cJoi5c0OYhkqg5ug4UAMC7kJRZXbLfsyOS1F5fhOPAP3d1Xrde7 uAIM3wkAZEVUmzbJ8XSPrDQfiXbwDgUzESTik9WUgXFXZzlGonYYyAmihzv/vYxzK2f8 ot1jCVnwPK4wH87mGY0hUieRjw2WZIZM3UJ8XXB92FZMdaun31f1qVzZ3t/zmSVmXclU ZxI2yCDYvIKrLcbZu8E7VKCFnHNML3uAEJSl/L5Ani1BdCUoc7/yxXFc8rv9T6qDUqKT LlWROe+FJrjICeEJYBMfB44uRhEA0qt/PDZT+L8Lnv6ax2i9Ht+QGyRTnBxt38wbx0Cd 4SZQ==
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=godffJjkjLq26O+dv8lgsJThrYrvx+rH9EgU7Oz/31I=; b=M+jKhPLqinsZKowRNrtiZTaEARSOb027nZa3s9N8ESrQy7xifGt9TbSndxQvL6RbG4 T5LEB0MbiuUhxUHDAlB3n0mGZtx4+bCtf80GfCAbt5U+sBMwnc5880rjPAjld6bKzsxK 4hkkewvCX1G5HSy00bkBw48c7EV244NVoUCEL7zjLPW8COTNlDvzh793jvPEzkurv6j7 ktyzmOF8dbS3yaLsqGe9uS5FRx9wAps1lberT6VjFKpbx1mk+SQ2RyYS+SmKIb+neOFp dnb1onLTeQmDDz0g2DZ2jCPxb3csSMx6ZG02JIb7xnV//XQVxGp+tf4C4bmsjyguwUK1 Wt2A==
X-Gm-Message-State: AIkVDXIrY1TLCqZZlcBMDKJkhGNGbkDHiTibyTEoApqlzT95AnD01zPKHImnxL4K1AERm6BAY1qsfwy7jEvjwg==
X-Received: by 10.37.215.8 with SMTP id o8mr3408395ybg.158.1484762120649; Wed, 18 Jan 2017 09:55:20 -0800 (PST)
MIME-Version: 1.0
Received: by 10.129.160.141 with HTTP; Wed, 18 Jan 2017 09:55:19 -0800 (PST)
In-Reply-To: <CAHP81y_RhweePefHwdb=WxBFBro-SwhT6hS2Rs0o9H5_7DirjQ@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> <CAHP81y_RhweePefHwdb=WxBFBro-SwhT6hS2Rs0o9H5_7DirjQ@mail.gmail.com>
From: Shay Gueron <shay.gueron@gmail.com>
Date: Wed, 18 Jan 2017 09:55:19 -0800
Message-ID: <CAHP81y_EWwK57cHkN7_rLreHWJ5fvjKL9FhqnRsCpKFp3H=SOg@mail.gmail.com>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: multipart/mixed; boundary=94eb2c0799b6c747370546621ee7
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/7Vr4uVNZYPe_v7CLMCnH5hRQ_bA>
X-Mailman-Approved-At: Thu, 19 Jan 2017 08:09:58 -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 17:55:25 -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

(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).

Due to the limit on the size of a posting, the two files will be
transmitted in two separate mails.

This attachment: Reply 1

Thank you, Shay Gueron


2017-01-18 9:46 GMT-08:00 Shay Gueron <shay.gueron@gmail.com>om>:

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