Re: [Cfrg] AES GCM SIV analysis

Dan Harkins <dharkins@lounge.org> Fri, 27 January 2017 02:26 UTC

Return-Path: <dharkins@lounge.org>
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 6A58D129894 for <cfrg@ietfa.amsl.com>; Thu, 26 Jan 2017 18:26:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -4.202
X-Spam-Level:
X-Spam-Status: No, score=-4.202 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
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 mzEtgOGQEq6r for <cfrg@ietfa.amsl.com>; Thu, 26 Jan 2017 18:26:23 -0800 (PST)
Received: from colo.trepanning.net (colo.trepanning.net [69.55.226.174]) by ietfa.amsl.com (Postfix) with ESMTP id EC8771293FE for <cfrg@irtf.org>; Thu, 26 Jan 2017 18:26:22 -0800 (PST)
Received: from thinny.local (69-12-173-8.static.dsltransport.net [69.12.173.8]) (using TLSv1 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by colo.trepanning.net (Postfix) with ESMTPSA id E1A0810224086; Thu, 26 Jan 2017 18:26:21 -0800 (PST)
To: Adam Langley <agl@imperialviolet.org>, Brian Smith <brian@briansmith.org>
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> <CAFewVt5VVpEKVGCt_c6UhG5sJ66xFfLUdOs4EZdnbgbTNPrFjA@mail.gmail.com> <CAMfhd9VNXAO=c2zw0UoVLDSL=BQL0JYVf8qVFLguoVv0ADsoWg@mail.gmail.com> <CAFewVt7kXyUcDATZ4yjvC0OOBE3-NLh9rGkHvLm1z4K9YQEBhg@mail.gmail.com> <CAMfhd9V05m3UtPae_PV5wUS63HHFRgRxF5m-UKfuTmzjYVDd+A@mail.gmail.com>
From: Dan Harkins <dharkins@lounge.org>
Message-ID: <f6d2e9a7-4dde-efa7-ad9f-0e8dcd35b99a@lounge.org>
Date: Thu, 26 Jan 2017 18:26:17 -0800
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.10; rv:45.0) Gecko/20100101 Thunderbird/45.5.1
MIME-Version: 1.0
In-Reply-To: <CAMfhd9V05m3UtPae_PV5wUS63HHFRgRxF5m-UKfuTmzjYVDd+A@mail.gmail.com>
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/51QJZHlcN230Rg4eC092ATqv3os>
Cc: "Cooley, Dorothy E" <decoole@nsa.gov>, "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: Fri, 27 Jan 2017 02:26:24 -0000

   Hello,

On 1/19/17 9:33 AM, Adam Langley wrote:
> On Wed, Jan 18, 2017 at 7:53 PM, Brian Smith <brian@briansmith.org> wrote:
>> Perhaps: "We recommend instead that an implementation try to avoid
>> repeating a nonce for a specific key, just like it would it would do
>> for an AEAD that isn't nonce-misuse-resistant." This shifts the
>> emphasis away from the 2^8 number to where it belongs, IMO. Note that
>> "256" and how it is derived and why it is safe is explained in the
>> next paragraph anyway.
> After some discussions on Twitter I've discovered that several people
> (possibly including Brian) understand "nonce-misuse resistant" to mean
> a stronger property than AES-GCM-SIV has. Namely they understood it to
> mean that the value of the nonce is /irrelevant/ for security, except
> that a fixed nonce discloses equality of plaintexts.

   But that is the definition used in the seminal work on the matter, [1].
If you want to have a different notion concerning a lesser restriction on
nonce reuse then you should use a different term.

> AES-GCM-SIV doesn't have this property. It is robust to random nonce
> duplication but not designed for a fixed nonce. Specifically, after
> 2^n full-sized (i.e. 64MB) messages, there's ~2^(96-2n) chance that
> two of the messages reused counter values and thus keystream. (The
> bounds are better if messages are smaller.)
>
> Consider a broken TLS implementation that always uses a zero nonce and
> is sending 16KB records as fast as possible. By the time it has sent
> 2^40 records (44 TB) there's about a 2^-32 chance that two of those
> records shared keystream bytes. (That's very rough and there might be
> a few stray factors of two missing in there.)
>
> That's a lot better than AES-GCM, but we're not saying that the nonces
> are completely irrelevant to security.
>
> Perhaps we need a different term to clarify this? Occasional nonce
> duplication tolerant?

   Which brings up a question I've resisted asking: Why are you doing this?

   If you want to have an AEAD scheme that is nonce-misuse resistant that
can use a fast(er) authentication scheme then why not just do RFC 5297
with GHASH instead of AES-CMAC? You're defining a new irreducible
polynomial that, to my knowledge, is not in existing hardware the way
that PCLMULQDQ using x^128 + x^7 + x^2 + x + 1, is in Intel chips.
You're defining a(nother) KDF /inside/ the cipher mode itself instead of
just letting a KDF, which all users of AES-GCM-SIV will use, generate a
double-wide key. And I don't see the reason for either.

>>> I agree that large AEAD messages have several problems. But I don't
>>> think that we have any need for a larger nonce (see above). (And the
>>> nonce is used with a counter only in the KDF phase, so it's unrelated
>>> to the maximum plaintext size.)
>> Is there any way that a larger nonce (e.g. 120 bits) hurts, other than
>> being inconsistent with existing IETF AEADs?
> With three bits for the counter, the largest the nonce could be is 125
> bits. But I think a nonce that's not a whole number of bytes would be
> too confusing.
>
> The nonce could be 120 bits (15 bytes) but that has no practical
> advantage over 96 bits. If you're picking nonces at random then the
> change in bounds is trivial (see multibirthday reference in the spec).
> If your nonce generation is broken and you're using a fixed value then
> the size is irrelevant.
>
> 96 bits is a "rounder" number and might save some alignment problems
> is all, really.

   The size of the nonce should not matter to a generic misuse-resistant
cipher mode.

   regards,

   Dan.

   [1] https://eprint.iacr.org/2006/221.pdf

>
>
> Cheers
>
> AGL
>