Re: [Cfrg] AES GCM SIV analysis

Adam Langley <agl@imperialviolet.org> Fri, 27 January 2017 20:21 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 0AB6A1297F7 for <cfrg@ietfa.amsl.com>; Fri, 27 Jan 2017 12:21:45 -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 ohhHWbZtR0Y4 for <cfrg@ietfa.amsl.com>; Fri, 27 Jan 2017 12:21:43 -0800 (PST)
Received: from mail-io0-x230.google.com (mail-io0-x230.google.com [IPv6:2607:f8b0:4001:c06::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 37AAB12986B for <cfrg@irtf.org>; Fri, 27 Jan 2017 12:21:43 -0800 (PST)
Received: by mail-io0-x230.google.com with SMTP id l66so69348943ioi.1 for <cfrg@irtf.org>; Fri, 27 Jan 2017 12:21:43 -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=jr4IvJWgTJjAIl6vi64djFcUgHVmEqqJnM7HVMBekQk=; b=pxR7R6kUTnWsjegusu1ATqzdF56U3nT3tciQZySIFi/7TaCteZlba3aoDU1WnCO0aX EvZ6qsYe74j5a127g6QvsVuU0jq7GvdEuP8m8/pAmuSpoqaxsHOybHxhO7iyRqN2KjKk ioTjKYsOU6zKjP634Jj62Sdm3/QzMfLzJP6HKidNFiZAelDywcY2/E74Jn/ZBptlMjLm bHzCyLKcs8DvDUfHyVtI5vEJgXLD4gDrwJUxL2FgXUWab9hDb9lXsOY03CGrHOxGZX41 4DvDeZG+y0SXeiNcg9YwAqR0GMjdQ68v0oqiFKBT8QEJpLoqvWFbUuoNk/MuMs8U867h LXdg==
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=jr4IvJWgTJjAIl6vi64djFcUgHVmEqqJnM7HVMBekQk=; b=lWk8r08jtBQ1OF+UrBlGZpKBOpaVEAsMN65f0/3y7ae0xX9JIfgFU9QvD3S5fmX3HF g+abVcmnGTwtqTyAfEtI1fi0hb7rbj3x8sZlKuv1DAIvhpqs7XDTZqSiFHYHDWT0Ep+d I54ydO3tyFR/lu3/qtDatjia5exed4zy4xyRQl1oMIf15CO1aAj4ECBybwKXP43/sP/p jN/F+c51x1UI8y/CHPHu+2Ul0WA2QJlS1O3EuBXxXZ9pbIDY5EYMWcGV3dCfczyH/nWC HrBgFtghIsd1Z2AHrlSIU8Iu1Usl65luQP8y5TEd3o3vtsf12arwI8ydxN+gJTYfSnwG IkAw==
X-Gm-Message-State: AIkVDXLaxv+YHGccCvd1fGlceuZU6aAxwKN4c2sMSdTBnc2f+s3re9/gZtguB+3LOKmIxxlsJ5sFFFYqU2l+Mg==
X-Received: by 10.107.134.36 with SMTP id i36mr8927665iod.168.1485548502505; Fri, 27 Jan 2017 12:21:42 -0800 (PST)
MIME-Version: 1.0
Sender: alangley@gmail.com
Received: by 10.36.144.4 with HTTP; Fri, 27 Jan 2017 12:21:42 -0800 (PST)
In-Reply-To: <f6d2e9a7-4dde-efa7-ad9f-0e8dcd35b99a@lounge.org>
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> <CAMfhd9V05m3UtPae_PV5wUS63HHFRgRxF5m-UKfuTmzjYVDd+A@mail.gmail.com> <f6d2e9a7-4dde-efa7-ad9f-0e8dcd35b99a@lounge.org>
From: Adam Langley <agl@imperialviolet.org>
Date: Fri, 27 Jan 2017 12:21:42 -0800
X-Google-Sender-Auth: gGsyrAbjvSJNTSARVI50aJ3r2dg
Message-ID: <CAMfhd9WoNeEbhWMbOHFMy9_Aq2XtU=Q3P7Bd6S8r3FsXT0N1mA@mail.gmail.com>
To: Dan Harkins <dharkins@lounge.org>
Content-Type: text/plain; charset=UTF-8
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/9NXSRem3gD-x0IHesm3_SCIB_zY>
Cc: "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: Fri, 27 Jan 2017 20:21:45 -0000

On Thu, Jan 26, 2017 at 6:26 PM, Dan Harkins <dharkins@lounge.org> wrote:
>   But that is the definition used in the seminal work on the matter, [1].
> If you want to have a different notion concerning a lesser restriction on
> nonce reuse then you should use a different term.

That paper formalises an advantage that an attacker might have over an
ideal scheme. In the same way that block ciphers aren't ideal PRFs,
nonce-misuse-resistant schemes aren't hitting that ideal either. RFC
5297 doesn't hit it, at minimum because it'll run out of counter-space
after enough messages. AES-GCM-SIV isn't hitting it either.

But that doesn't mean that they aren't practically useful.

I'm not sure what an ideal NMR AEAD would look like, but it's probably
quite different to both RFC 5297 and AES-GCM-SIV and probably looks
like a wide-block construction. If someone can point at something they
think does hit it, that would be interesting to me at least. (Although
perhaps it's well trodden ground for those who are more familiar with
the literature than I.)

>   Which brings up a question I've resisted asking: Why are you doing this?
>
>   If you want to have an AEAD scheme that is nonce-misuse resistant that
> can use a fast(er) authentication scheme then why not just do RFC 5297
> with GHASH instead of AES-CMAC?

AES-GCM has lead to a state of the world where our large machines,
which need to encrypt and decrypt lots of data, end up having hardware
support for AES and GF(128) operations. We would like to take
advantage of that because it's hard to beat the speed and power
efficiency of dedicated hardware, but sometimes we want not to have to
worry about nonces.

> You're defining a new irreducible
> polynomial that, to my knowledge, is not in existing hardware the way
> that PCLMULQDQ using x^128 + x^7 + x^2 + x + 1, is in Intel chips.

PCLMULQDQ (and other hardware implementations, to my knowledge) is not
specific to that polynomial. Also, the polynomial in AES-GCM-SIV is
that polynomial, just with some ordering oddities addressed. See
https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-03#appendix-A.

> You're defining a(nother) KDF /inside/ the cipher mode itself instead of
> just letting a KDF, which all users of AES-GCM-SIV will use, generate a
> double-wide key. And I don't see the reason for either.

Our KDF is per-nonce; it's not the same as having a double-width key
and partitioning it internally. We do this in order to get better
bounds when encrypting very large numbers of messages.


Cheers

AGL