Re: [Cfrg] I-D Action: draft-irtf-cfrg-gcmsiv-03.txt

Adam Langley <agl@imperialviolet.org> Thu, 19 January 2017 00:24 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 C8EAE12946F for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 16:24:10 -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, RCVD_IN_DNSWL_NONE=-0.0001, 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 y_thEAZdbQ4g for <cfrg@ietfa.amsl.com>; Wed, 18 Jan 2017 16:24:08 -0800 (PST)
Received: from mail-it0-x242.google.com (mail-it0-x242.google.com [IPv6:2607:f8b0:4001:c0b::242]) (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 955FA129445 for <cfrg@ietf.org>; Wed, 18 Jan 2017 16:24:08 -0800 (PST)
Received: by mail-it0-x242.google.com with SMTP id e137so3411485itc.0 for <cfrg@ietf.org>; Wed, 18 Jan 2017 16:24:08 -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=eeatx9+EFacJALjIllKCvXmna7B83k1mrkoJAg29FMA=; b=O2Tg8XlnU7RirtCf0yedz6oer0boPBk5yf8FRwsA2GsO+H72jjGzy+ZE1HgqZ3NFkG sZaxR1V0lB9IiIAqRb1WM+KL2/ys2IeM9hQlOkQXedBkQXJlIAaFC4L2iDDHpv7WlAqa xN5GcgqhfWAPgl89fzAHqW2kMq1ciutgWgV2brqMUwHM02ziHLS9DeFP/NlQaXDJheog 3jVRoMnQtx9FSZALUI4LyJ5owQrwiuaTWOWHIZ8QbajinsmsXHOanL6x9zCePBeKGv2J ka7sz4h+sV4tqltApBfgl4v8eoPAqWkahh+eB7mhtEHqzHWhpFDocZUldyJNpoymVarI +pHA==
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=eeatx9+EFacJALjIllKCvXmna7B83k1mrkoJAg29FMA=; b=l8C1ZbBWeaDqonraEFi6sQF+7D87QRs9k09V7ZKixBaIaUQy0Ct0UfX3G7z7m7pyTC /kX7vUOeAKVSc0UYSMSMpfRD1RniVfmhG4TnIja95iJPKVw9CEydDFUzhC7XdycgylSj fiBiG+jmozBuaaEom5tfViW2VOtz3dPRXBhqsMYy63gjCKVnIlv3A8TSyF/Ggcg4DKfV zcoccPdiw/56vsDV0zvqAGMAmqmJYOLSyQQ2ATf/dLo8Y6lrt/JX8qrFP22R+n3ofP+e vAT8FwFQh2z7bZhmxwtPeLOuAd/RLSTKGrXd46uO+WamdouHfhVMqmpG7RNrBUSZLQKi 4ciQ==
X-Gm-Message-State: AIkVDXJG6L/h0J06GHlv4cAuS+6BcIUbgyb+L4vowNH0HARDKrCWvALa4Yc1tzNylYIoKNOlULu2rvWaAaLagQ==
X-Received: by 10.36.178.74 with SMTP id h10mr5890521iti.82.1484785447878; Wed, 18 Jan 2017 16:24:07 -0800 (PST)
MIME-Version: 1.0
Sender: alangley@gmail.com
Received: by 10.36.144.4 with HTTP; Wed, 18 Jan 2017 16:24:07 -0800 (PST)
In-Reply-To: <CAFewVt4DTQZoRO6qaQxuOeSNk=vJyWifTX4r4EqPDmXEvYxpzg@mail.gmail.com>
References: <148476063144.1938.2025448065922517313.idtracker@ietfa.amsl.com> <CAFewVt4DTQZoRO6qaQxuOeSNk=vJyWifTX4r4EqPDmXEvYxpzg@mail.gmail.com>
From: Adam Langley <agl@imperialviolet.org>
Date: Wed, 18 Jan 2017 16:24:07 -0800
X-Google-Sender-Auth: TBR_8kGQw8civ29whcXPQMW284Y
Message-ID: <CAMfhd9XHRJp437MwfGRN1k2pwzakb8b-EV=QCFoN3j3oDXyMLg@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/wqO7IJc7UtTH3UgD8s2-BlRUGOU>
Cc: cfrg@ietf.org
Subject: Re: [Cfrg] I-D Action: draft-irtf-cfrg-gcmsiv-03.txt
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 00:24:11 -0000

On Wed, Jan 18, 2017 at 3:46 PM, Brian Smith <brian@briansmith.org> wrote:
> The intro defines nonce-misuse-resistant AEADS as ones that are
> safe(r) to use when "two distinct messages are encrypted with the same
> nonce". However, in reality we usually don't care only about the case
> where *two* (==2) distinct messages are encrypted with the same (key,
> nonce), but rather we care about the case where *multiple* (>=2)
> messages are encrypted with the same (key, nonce). In particular the
> new draft makes a distinction between encrypting <2^8 vs >=2^8
> messages with the same (key, nonce), not a distinction between 1 vs 2
> messages with the same (key, nonce).

You're correct that the problem is multiple messages (potentially)
encrypted with the same (key, nonce) pair. But the number is very
small since the number of random nonces that need to be sampled from a
96-bit space in order to expect at least one to appear > x times,
rises *very* fast with x. As noted in the draft, for x=256, it's about
2^102.

The main thrust of that section in the spec is to say "pick nonces at
random". The 2^8 number was picked out of the aim to emphasize this
over fixing a specific nonce and not encrypting too many messages.

> The practical motivation for POLYVAL is unclear. In an email message
> in an earlier mailing list thread, Shay said "We chose to use POLYVAL
> so that 128-bit blocks can be viewed as field elements and as AES
> ciphertexts in a consistent way (with respect to the order of the bits
> inside each byte))," and I think that this should be included in the
> spec, along with a more plain explanation that this is done (IIUC)
> simply to avoid byte byteswapping on little-endian systems that GHASH
> requires.

I'll let Shay add something about this if he wishes, but I think the
bit ordering in GHASH is weird and it''s not just a big/little endian
thing. I know, having spoken to other people who have dealt with
GHASH, but I'm not unique in this either.

POLYVAL straightens this out :)

> It isn't clear how the nonce length of 96 bits was chosen. I can see
> some advantages, e.g. it is more of a drop-in replacement for AES-GCM,
> which is almost exclusively used with 96-bit nonces in IETF protocols,
> but is there any other reason?

It used to be 128 bits, but we wanted to change the KDF to use counter
mode. Thus we needed three bits for the counter. However, a 125-bit
nonce would be too weird so we rounded down to 96 bits.

An analysis of the probabilities of repeats shows that, even with 96
bits, there is a vast security margin so we're happy with that length.

> The email also said "We now generate keys by using counter mode and
> discarding half of each ciphertext block." The motivation for
> discarding half of each ciphertext block should be added to the draft
> (maybe in security considerations), along with a reference of how
> discarding half of each ciphertext block achieves that goal.

Agreed and I'm hoping that a more concrete comparison of how the new
KDF affects the bounds will come from Shay and Yehuda soon :)

> The draft makes an argument about safety when "nonces are selected
> uniformly at random." However, isn't a key motivation for AES-GCM-SIV
> our lack of confidence in our ability to select nonces uniformly at
> random?

No. The motivation is that selecting nonces at random with AES-GCM
isn't very comforting. NIST recommends a limit of 2^32 plaintexts for
a given key in this case, and that still has a 2^-33 chance of serious
failure.

> I personally would like to see discussion of the case where we
> can't assume nonces are selected uniformly at random. (While I can't
> come up with one off the top of my head right now, it seems likely
> that there would be simpler and less invasive ways of defining a
> nonce-misuse-resistant AEAD based on AES-GCM if we can also assume we
> have a good random number generator and we're willing to accept the
> birthday bound analysis in the draft. Thus, based on intuition it
> seems like AES-GCM-SIV must be useful in contexts where nonces aren't
> chosen uniformly at random in order to justify its complexity.)

Off the top of my head, I think we would need a cipher with a 256-bit
block in order for a scheme that doesn't depend on nonces being
(mostly) distinct to have comfortable security margins. AES-GCM-SIV is
not such a scheme.


Cheers

AGL

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