Re: [Cfrg] AES GCM SIV analysis

Brian Smith <brian@briansmith.org> Wed, 18 January 2017 20:51 UTC

Return-Path: <brian@briansmith.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 92AA3129564 for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 12:51:47 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.601
X-Spam-Level:
X-Spam-Status: No, score=-2.601 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, 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=briansmith-org.20150623.gappssmtp.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 WgplPh8cfPeq for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 12:51:46 -0800 (PST)
Received: from mail-io0-x22a.google.com (mail-io0-x22a.google.com [IPv6:2607:f8b0:4001:c06::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 F423F1294DF for <cfrg@irtf.org>; Wed, 18 Jan 2017 12:51:45 -0800 (PST)
Received: by mail-io0-x22a.google.com with SMTP id v96so22044352ioi.0 for <cfrg@irtf.org>; Wed, 18 Jan 2017 12:51:45 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=briansmith-org.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=JNVPZ+RkkJIvfYTsI+JtLYOuvYjS2Ll+1ol/IKeS3U4=; b=NaFLU2Ei05CajUy3B4NXLvBuQea9Au7HtNig0Om4MQzZ/EMkE96s9DY39xDe5vN3yC t7ufpqxjptgNYiKCbypIiSTWVrm5gPXbXiK1RfiRwgIV9LEahfgplaq9/qLoW1hvEVm9 08QHZmQ9ggWCRT/P3izFBr42Zr9ws4zH2iv4mX2mx1xj+MRJljdzL0CKVi1i3bpBh+yJ uR8te97LThTkgcD92aVPmz9q0xalH3Gz1V+Syrzc7p8IsgSm8RyRagMwfTz262nsPg3q D5bTvUvfjo7jEUjNvmR/rX0JRvNxUDe2u+krMw4De6YXL8iTnTBI/7sughlAbtDey+zB ltAA==
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=JNVPZ+RkkJIvfYTsI+JtLYOuvYjS2Ll+1ol/IKeS3U4=; b=WHF56vFrKUTD8ySo0CALSJhzbnkw2sKEDKcjagKjt0/HUix2OABbLDvepC6yTvZ95w 02IvZ68UQPXoPg6JTXbI8ua7HqVZxy1iywHisnnYCM0viBDlnLuGmEOIEhuFiFxYQMzE Gaw2Zn/K4ogHaa+ABuHGRyHAfQbOSc1mOzNAYXAdcwbyeoRQV4QTJW7MMTN3GYvRPGiR Sgy6nPd8cmh/36MyeigdrkGb+9eEvQs6aO+tPyukRM4DXiGFl3oTdk7KfGuqOUgmbiC/ i2NwkuJAPNAr7eh7jlF0yQbkC86nOwdZ4RlShVK8E0SkIKsmWZp9cZ0OHNVTFa5mz45o s76Q==
X-Gm-Message-State: AIkVDXJDapJCBS2uy0lAeuqnMRJb2x49Gcy0NAxWDB9Ft9JOfPcMAoRWQRJ8W/QMncWdEUfGBQkHiVyaA9C0tw==
X-Received: by 10.107.173.95 with SMTP id w92mr6301234ioe.136.1484772705225; Wed, 18 Jan 2017 12:51:45 -0800 (PST)
MIME-Version: 1.0
Received: by 10.36.65.206 with HTTP; Wed, 18 Jan 2017 12:51:44 -0800 (PST)
In-Reply-To: <CAMfhd9V77LN41QTt4YvNs-bjUan_PtdrEiQeHvKXY+G+k2z1kw@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>
From: Brian Smith <brian@briansmith.org>
Date: Wed, 18 Jan 2017 10:51:44 -1000
Message-ID: <CAFewVt5VVpEKVGCt_c6UhG5sJ66xFfLUdOs4EZdnbgbTNPrFjA@mail.gmail.com>
To: Adam Langley <agl@imperialviolet.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/Np2SfVg6zDoTN_273jPwQSxjDCM>
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 20:51:47 -0000

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/