Re: [Cfrg] AES GCM SIV analysis

Dan Harkins <> Fri, 27 January 2017 02:26 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 6A58D129894 for <>; Thu, 26 Jan 2017 18:26:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -4.202
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 ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id mzEtgOGQEq6r for <>; Thu, 26 Jan 2017 18:26:23 -0800 (PST)
Received: from ( []) by (Postfix) with ESMTP id EC8771293FE for <>; Thu, 26 Jan 2017 18:26:22 -0800 (PST)
Received: from thinny.local ( []) (using TLSv1 with cipher DHE-RSA-AES128-SHA (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPSA id E1A0810224086; Thu, 26 Jan 2017 18:26:21 -0800 (PST)
To: Adam Langley <>, Brian Smith <>
References: <> <> <> <> <> <> <> <>
From: Dan Harkins <>
Message-ID: <>
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: <>
Content-Type: text/plain; charset="windows-1252"; format="flowed"
Content-Transfer-Encoding: 7bit
Archived-At: <>
Cc: "Cooley, Dorothy E" <>, "" <>
Subject: Re: [Cfrg] AES GCM SIV analysis
X-Mailman-Version: 2.1.17
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Fri, 27 Jan 2017 02:26:24 -0000


On 1/19/17 9:33 AM, Adam Langley wrote:
> On Wed, Jan 18, 2017 at 7:53 PM, Brian Smith <> 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.




> Cheers