Re: [Cfrg] AES GCM SIV analysis

Shay Gueron <shay.gueron@gmail.com> Wed, 18 January 2017 21:33 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 EF062129569 for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 13:33:41 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 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_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 9h3ekJSrgeEY for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 13:33:40 -0800 (PST)
Received: from mail-yw0-x230.google.com (mail-yw0-x230.google.com [IPv6:2607:f8b0:4002:c05::230]) (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 40DBD129494 for <cfrg@irtf.org>; Wed, 18 Jan 2017 13:33:37 -0800 (PST)
Received: by mail-yw0-x230.google.com with SMTP id l75so18441392ywb.0 for <cfrg@irtf.org>; Wed, 18 Jan 2017 13:33:37 -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=e+19vhOa25zw5o1r+I6LjMv5Omr5myXFjxFX+gnJ2C8=; b=VlBSLaSYBtbLVUNWwnZkZsM7sYoU2xyWR08Jhl/x2FxpO1SKgb6hBZfry/8XBoC8j0 66Ht4farw8J/Z+HD3AYw8JZVK36yQaUA50G7xAmLXGQ8wlQ8ilVsXwC3rOevzXzcp8q4 pEZAbhgPNK0vCNTLWB4uQfvCHBYod6vAMc9eGhkRPKP4tKPb4yLiN7ZSf2iruJitw5MF SC1WRlCUiuZ9CElSPFU7vy5Ishc+vcNveMck0oIF1Mb+G6hxW2bJFaYHuBuvUnr8bDyN afIErRKdP/Ow1yL0Md9kCcNTnh4Xf3t0irxyLeqMGanqI6cs9QsuYYAlQejoxT8pe1bw M5zA==
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=e+19vhOa25zw5o1r+I6LjMv5Omr5myXFjxFX+gnJ2C8=; b=jMq3nMvgPXgWQRU02U9pVIaYtOpcB+NPqv+Sh/S8XWD+j3pDpQhJuLALk3Ha4JIji2 6OumQbO4gKsDvCShvcDzF6fUySDt30yqK0Po7egptFu2aY0Z/pcM9XR0OcJBLkPwCpE6 Kx1g14iKQwHnp0+KBgEKyBvY7BDE+rljGDaCNegMxezWn7x40EdDwzlB7pkHWGZ0RMQt oJKe1nxgNrpINeyCH8+dQhvZLnpSpkqNu+RxTfPaXTuFiAs+m+J9bvcWlI8xoxRk4pJp aEEMk9vpw9Av33S/2+7t0cL9nRJjbLuduNnwyaomXIhjYDlM5PY53OWKGgvy21AgCVf1 1fQQ==
X-Gm-Message-State: AIkVDXI5Hra0TzemgPQJ3mNBOZe+Pnm2fujHF8TpGNBSWOazJxAUORqDA3WxBbh8YFVEVQ58kC2+NwvDc3mIfw==
X-Received: by 10.129.81.12 with SMTP id f12mr4246011ywb.80.1484775216465; Wed, 18 Jan 2017 13:33:36 -0800 (PST)
MIME-Version: 1.0
Received: by 10.129.160.141 with HTTP; Wed, 18 Jan 2017 13:33:35 -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: Shay Gueron <shay.gueron@gmail.com>
Date: Wed, 18 Jan 2017 13:33:35 -0800
Message-ID: <CAHP81y9W-A7DTPTL1_D6bLfGd9DTN78P=fo9qZq+9Cu-+o3S=A@mail.gmail.com>
To: Brian Smith <brian@briansmith.org>
Content-Type: multipart/alternative; boundary=001a114630185979c20546652b94
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/oatsJguyqDpIZ2BECYKUPLNGXGQ>
Cc: Adam Langley <agl@imperialviolet.org>, "Cooley, Dorothy E" <decoole@nsa.gov>, "cfrg@irtf.org" <cfrg@irtf.org>, Yehuda Lindell <Yehuda.Lindell@biu.ac.il>
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:33:42 -0000

>>> Is this a meaningful recommendation?
>>> How would one go about following this recommendation in a practical
implementation?

This is a very valid question, that is answered in the specification. But
perhaps it is worth clarifying on the mailing list. It is rather easy to
adhere to the recommendation. Simply choose the 96-bit nonce uniformly at
random. After, say, 2^{50} encryptions, what the probability that a nonce
repeated, even 5 times, can be bounded from above (see the "multibirthday"
reference in the spec) by 2^(-134).
(To this, you need to add occurrences where the keys also collide. All this
analysis will be posted soon, together with the matching bounds).


>>> Do we really need a 32-bit counter for this mode?
>>> Why not have a 16-bit counter?
Also a very valid question.
The answer is that you don't really need a 32-bit counter.
It is possible for a usage to specify a shorter restriction on the allowed
message length. This will improve the security bounds, which are also a
function of k, where 2^k is the largest number of blocks in a message. You
can choose any k <= 32.

Thanks, Shay



2017-01-18 12:51 GMT-08:00 Brian Smith <brian@briansmith.org>rg>:

> 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?
>
> 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.
>
> Cheers,
> Brian
> --
> https://briansmith.org/
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>