Re: [Cfrg] AES GCM SIV analysis

Adam Langley <agl@imperialviolet.org> Wed, 18 January 2017 21:35 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 ABB9B1294C4 for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 13:35:18 -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 19gfKOZgXDWS for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 13:35:17 -0800 (PST)
Received: from mail-io0-x234.google.com (mail-io0-x234.google.com [IPv6:2607:f8b0:4001:c06::234]) (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 EC1101294C9 for <cfrg@irtf.org>; Wed, 18 Jan 2017 13:35:16 -0800 (PST)
Received: by mail-io0-x234.google.com with SMTP id v96so22955836ioi.0 for <cfrg@irtf.org>; Wed, 18 Jan 2017 13:35:16 -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=ygcK+nuQxHzq44YE3SdMqoWB60+dAlFEuXancUnvADM=; b=g4ezcSa68zdEJLZ3GhZUbUNptpRqpO3tC4GPa39KlmIPaDMU0siYJpblNiV/D87XDd /z6gpIbAskrdfjOMMzvZpk3H/MeRk1FnNJKVaAtizWtRgZ6raO2wjqpkNMGGEsSqsot3 YXOsqpzSqYzGyCJoqzNbiTCVZX4e/fDduuBWg2TI6rUp13LkWv7j4TjBqdcTGwPCS8VB TNELy3kPHkOBTTo9gCYQJn5JNGayIMowMYXBN17LScuzNVJ3G+TWnDH+zDtMwU4f2IiM 9oJrqKOHfPIZqc38QvWy+FBEegfPvQX9IiFHahZcBM96CrQhF0vcNjeV3C4I8VsDKi2L auHQ==
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=ygcK+nuQxHzq44YE3SdMqoWB60+dAlFEuXancUnvADM=; b=sfxsgHtvP3mKBUQjZOXK1wJOISjCTKwPh3bZg4J4sh335iBi0INoKj6IEVHpYsSybh 0o0jTiFpMGS5URu7Rq+skvBBklBbuIoHAV95neOl/Ts7wsWs0EgVYFUdT0U618m0e0hD 6Jr2yenYEnxTtAsKRvKM7jxrOiz0mis5e7hwLZpZtmkgubMX4R2Pyhiq36xUQexc0iI5 F7XOcYiEYWoO3bkRTHO+xsajaEWAMC5MK1Nr5apbs9z54SxdAM80J3TW5lA5Hpngi8xI fMkPER0IqGzxTXHPfMKecRLb8KEiNM00Pj7hfIw0j7kfB7oH4LC5ywNsO3e/jiponvKq 8qgg==
X-Gm-Message-State: AIkVDXLorlIxcPRMVET/DmtKK4y6MYSr9rAcZLa9zCX8ctz6MiBAc6kCsZ30ChQk3J/q+HW9ZD6gZMBme0jBlA==
X-Received: by 10.107.134.36 with SMTP id i36mr5609100iod.168.1484775316244; Wed, 18 Jan 2017 13:35:16 -0800 (PST)
MIME-Version: 1.0
Sender: alangley@gmail.com
Received: by 10.36.144.4 with HTTP; Wed, 18 Jan 2017 13:35:15 -0800 (PST)
In-Reply-To: <CAFewVt5VVpEKVGCt_c6UhG5sJ66xFfLUdOs4EZdnbgbTNPrFjA@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>
From: Adam Langley <agl@imperialviolet.org>
Date: Wed, 18 Jan 2017 13:35:15 -0800
X-Google-Sender-Auth: qBu9maR1nAbU6Q89LixDWvm6cq8
Message-ID: <CAMfhd9VNXAO=c2zw0UoVLDSL=BQL0JYVf8qVFLguoVv0ADsoWg@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/4ElxOnLJ_iEfQwM6iKyXuwPbO-Q>
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: Wed, 18 Jan 2017 21:35:19 -0000

On Wed, Jan 18, 2017 at 12:51 PM, Brian Smith <brian@briansmith.org> wrote:
> On Wed, Jan 18, 2017 at 7:34 AM, Adam Langley <agl@imperialviolet.org> wrote:
>> 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.
>
> The actual text in the draft is "Thus with AES-GCM-SIV we recommend
> that, for a specific key, a nonce not be repeated more than 2^8
> times."
>
> Is this a meaningful recommendation? How would one go about following
> this recommendation in a practical implementation? In particular,
> AES-GCM-SIV is mostly interesting in implementations that cannot
> reliably and/or consistently save state, and it seems like any attempt
> to write code to enforce this relies on saving state in the manner. Is
> the idea here that one would, every 2^8 or so messages, force some
> kind of "sync state or force rekey" operation that would be too
> expensive to do on every message?

No, nothing like that. Perhaps this part of the document isn't clear.

Basically, before we noted that AES-GCM-SIV with a fixed nonce like
like AES-GCM with a random nonce (except that it also leaks when
plaintexts are equal). We noted that NIST recommends no more than 2^32
messages be encrypted with a given key in that context.

So someone could, not completely unreasonably, say that they're not
worried about leaking when plaintexts are equal and use AES-GCM-SIV
with a fixed nonce for 2^32 messages.

We're now clearly saying that's not a great idea. Instead, generate
nonces at random. With a random, 96-bit nonce you don't have to worry
about the probability of having repeated a single value > 2^8 times
until you have a staggering number of plaintexts: greater than 2^100
of them. Since that vastly exceeds our current recommendation for
number of plaintexts per key (2^50), it's basically not a concern.

If that makes sense, what could we have written to be clearer?

> Do we really need a 32-bit counter for this mode? Why not have a
> 16-bit counter? This would allow single messages up to 1MB. Then one
> could more safely use a 96-bit random + 16-bit fixed ID nonce or an
> 80-bit random + 32-bit fixed ID nonce. In general, super large
> messages don't work well with AEADs because it's hard to verify the
> integrity of a giant message before using the plaintext, so 32-bit
> counters seem excessive. I expect protocols would limit the maximum
> message length such that a ~16-bit counter would be sufficient.

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


Cheers

AGL

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