Re: [Cfrg] AES GCM SIV analysis

Adam Langley <agl@imperialviolet.org> Thu, 19 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 414ED129461 for <cfrg@ietfa.amsl.com>; Thu, 19 Jan 2017 09:34:03 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.898
X-Spam-Level:
X-Spam-Status: No, score=-1.898 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, 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 zX_NkPN8Or3o for <cfrg@ietfa.amsl.com>; Thu, 19 Jan 2017 09:34:00 -0800 (PST)
Received: from mail-it0-x22a.google.com (mail-it0-x22a.google.com [IPv6:2607:f8b0:4001:c0b::22a]) (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 BA6281293F9 for <cfrg@irtf.org>; Thu, 19 Jan 2017 09:34:00 -0800 (PST)
Received: by mail-it0-x22a.google.com with SMTP id 203so1929198ith.0 for <cfrg@irtf.org>; Thu, 19 Jan 2017 09:34:00 -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=p7NYdac9uq/jzdIxNQNhpx/+7nJ/mawz3sZANG/wctE=; b=MRKiJ63oMg6//IY58LbsDObJZxgT/+6n6IrO0NJ1ExuEJajGQUSgUQiEDcd0ga390g cmyyVxscmKxBf4tXk6oab+FA6KJEuj6irGbH83zIINAzxHO3SNN2ygY88k3CFWr7FE7q oq9S+D0DPMTvwA+H2hXUGnSsloQSd9/D8WoBEDN3MP79fQYR8R+Tf5N/M+VFv8VGu9up uXTs0E8Vqn0iBjIsmRoSr7AVbvGy3Ewjd6piPxPyzgY2S1y4dGvdTaXpfM/Q5ZpQUwhy JJx4KgiTOedAAjrF+TAcFDsngFyylXYZrXJainssERRZqHZlxoOf+FmvjMbwfx2lkaJW JnEg==
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=p7NYdac9uq/jzdIxNQNhpx/+7nJ/mawz3sZANG/wctE=; b=g8kEUWpmovE33oUl4z1SrAlXQ5+1RIYMdFkaCjVBgGChFc5HkgGo+W9l4sESeom0Qd tU8xKTyhw97SdPGn0MMo3rPRw+ThKmBfG9x0vTDbn7Wrkw06IuDeSIOyuKpt5CLjoOqS lucY6A8EMkqQZdJknQMWhF+KZBAAT7llt12McQqoRyIO97mUt05qa0q56yKgUMprdazs cmmo0/k5z+Y59RSv9zEJuGUSsWAZHx7SDySU6ITN08I7zSMumtdBeZnnXsr0nFrjy8vT 1Mhrl5DY7mmSJLv5oowrx6An7RZQ7VGr5FVdz+td0LuGRGNOShfT1yxVsEKEEvZxZ0lL OZcw==
X-Gm-Message-State: AIkVDXKhRs3rUM4K4f1zy5dS3ZnVPflTDnZkq9/K6WVzfFDYuCsqd2elPbfOeO3HH3939yqH0CfoUYHtwmqgxw==
X-Received: by 10.36.230.5 with SMTP id e5mr9098280ith.92.1484847240019; Thu, 19 Jan 2017 09:34:00 -0800 (PST)
MIME-Version: 1.0
Sender: alangley@gmail.com
Received: by 10.36.144.4 with HTTP; Thu, 19 Jan 2017 09:33:59 -0800 (PST)
In-Reply-To: <CAFewVt7kXyUcDATZ4yjvC0OOBE3-NLh9rGkHvLm1z4K9YQEBhg@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> <CAFewVt5VVpEKVGCt_c6UhG5sJ66xFfLUdOs4EZdnbgbTNPrFjA@mail.gmail.com> <CAMfhd9VNXAO=c2zw0UoVLDSL=BQL0JYVf8qVFLguoVv0ADsoWg@mail.gmail.com> <CAFewVt7kXyUcDATZ4yjvC0OOBE3-NLh9rGkHvLm1z4K9YQEBhg@mail.gmail.com>
From: Adam Langley <agl@imperialviolet.org>
Date: Thu, 19 Jan 2017 09:33:59 -0800
X-Google-Sender-Auth: vbHteufCVVHClLVLDD0p_y7hAH4
Message-ID: <CAMfhd9V05m3UtPae_PV5wUS63HHFRgRxF5m-UKfuTmzjYVDd+A@mail.gmail.com>
To: Brian Smith <brian@briansmith.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/CVfp8_sy2sNIj_LXCwQ1vbdhpqQ>
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: Thu, 19 Jan 2017 17:34:03 -0000

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.

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?

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


Cheers

AGL

-- 
Adam Langley agl@imperialviolet.org https://www.imperialviolet.org