Re: [Cfrg] AES GCM SIV analysis

Alex Cope <alexcope@google.com> Tue, 31 January 2017 01:45 UTC

Return-Path: <alexcope@google.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 94DAD129849 for <cfrg@ietfa.amsl.com>; Mon, 30 Jan 2017 17:45:54 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -5.199
X-Spam-Level:
X-Spam-Status: No, score=-5.199 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-3.199, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=google.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 q3F7e_u27FjJ for <cfrg@ietfa.amsl.com>; Mon, 30 Jan 2017 17:45:52 -0800 (PST)
Received: from mail-wj0-x22f.google.com (mail-wj0-x22f.google.com [IPv6:2a00:1450:400c:c01::22f]) (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 9416012984C for <cfrg@irtf.org>; Mon, 30 Jan 2017 17:45:51 -0800 (PST)
Received: by mail-wj0-x22f.google.com with SMTP id b20so10657145wjs.2 for <cfrg@irtf.org>; Mon, 30 Jan 2017 17:45:51 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=I7OZ5ApKoU/Euw+JfNIa6D8Jo+OxhEj57cvzvOTu3QU=; b=q9dhsFSjQvJf0Ew/j0dsGjKRwtCRJTbGf+XJg5oXqJvJJ/4KfU3zaEJJWPifkB24u3 iA4amKP8UcWoYNbb76aQyztU3rixn4XADoKQZy4FIDhv05nCFaftozRr+CbO65j5Y1tm KOo1k3kMcf+muvze0/vNHfIYQ7mDtTIrpJZiUFoLsjSsuh50cd3b5Aag6FvzUNJ2hEue CLDOyw4fI9DBelyYNQRJP5lFAmF9W0tteLIYR66NyO5s+BYIeqiLVjDrwMOMJKhyKyJQ /G3n3N64YZ04kJa1otUTVFtBSis8NH1yp9R0S1lACy9uGHvw8ytPVe435TCMOTERo+ky WcJw==
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=I7OZ5ApKoU/Euw+JfNIa6D8Jo+OxhEj57cvzvOTu3QU=; b=F2SXmeWe7vEjXrAntbnMhEhAfOnTpCeVum8pCN9KM6NaaAxXdPb5YAarWv8hFBYPbu zKqejg3OslVajnYuwseZGrA19QzDIICG0eA8QqfU7vyHKz4i9eTTxgoAIkv1q/eLKhRK WIZrmk02D+Xe8x5Fe9VWLeE/aeGEnLHq47nVLbhufXHJzZCs60q7uKA4LHPZyu6H0rFu H5LGYya8+x91/qr6iBp9lkokW3ho6QF4rngH9FLKyAj6RhqBEyH0UdW3rh6B3EMZyaEy A9+OCQClKWCX6N89fFOtNE0K6K7t6l7Er1pTU0GRmMxJc5XqBgLj2cQNDyhMLqtMl2fO c0KA==
X-Gm-Message-State: AIkVDXL08lj774vX0J2/gzLeTTsfc1EJy2UoPhKMMjj1yLqo0kG6SXuAMX/ZKyIQffNMf1er4LbH13UI9VEGBlst
X-Received: by 10.223.166.137 with SMTP id t9mr21148867wrc.15.1485827149896; Mon, 30 Jan 2017 17:45:49 -0800 (PST)
MIME-Version: 1.0
Received: by 10.28.149.73 with HTTP; Mon, 30 Jan 2017 17:45:49 -0800 (PST)
In-Reply-To: <CAHP81y9twsgdWK6BXXL6rjR2uCPxf_qDr2fxqVTpX_UkEsVS1A@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> <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> <CAMfhd9WoNeEbhWMbOHFMy9_Aq2XtU=Q3P7Bd6S8r3FsXT0N1mA@mail.gmail.com> <CA+cSK136NFr7gxzT1-fjDq9ZO5QGQR_67bZr1sCpL4KOTcoeDQ@mail.gmail.com> <CAHP81y9twsgdWK6BXXL6rjR2uCPxf_qDr2fxqVTpX_UkEsVS1A@mail.gmail.com>
From: Alex Cope <alexcope@google.com>
Date: Mon, 30 Jan 2017 17:45:49 -0800
Message-ID: <CA+cSK11snbQDJPbOG9-HDmWnqsPEYWzK7VcQF-BM3OLq9bF7Rw@mail.gmail.com>
To: Shay Gueron <shay.gueron@gmail.com>
Content-Type: multipart/alternative; boundary=001a113c06d477de1e05475a1778
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/gXyVmR35JLaxOad2eXpCXRfMtrg>
Cc: Adam Langley <agl@imperialviolet.org>, "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: Tue, 31 Jan 2017 01:45:54 -0000

Thanks for the quick responses to my comments. I should have more carefully
proofread my first message, as I confused bit and byte reflection at
several points, my bad.

I'm in agreement that the bit ordering in POLYVAL is far more better, and
after looking into Montgomery multiplication a bit more, working
modulo x^128 + x^127 + x^126 + x^121 + 1 makes more sense. Consider me
convinced.

-Alex


On Mon, Jan 30, 2017 at 5:04 PM, Shay Gueron <shay.gueron@gmail.com> wrote:

> >>> 1) On X86, no performant implementation of POLYVAL will reduce to
> >>> GHASH, as that would result in unnecessarily byte swapping twice
> >>> then calling PCLMULQDQ.
>
> I suggest to count the number of byte swaps done with AES-GCM-SIV
> optimized implementation on X86 (see the code in my guthub, for example),
> and the number of bye swaps done with AES-GCM (take the OpenSSL example).
> The answers are: 0 for AES-GCM-SIV and 1 per each block (of the message
> and the AAD +1) in OpenSSL.
>
> The identity provided in the spec, relating GHASH and POLYVAL is provided
> for convenience, in case someone chooses to re-use software (or hardware).
> It is not suggesting that the fastest way to compute POLYVAL is through
> GHASH.
>
> The reason is (again) the order of bits inside the bytes. The definition
> of AES-GCM which has this order reversed with respect to the order of bits
> in the bytes of AES input/output.
>
> In fact, although many would think that AES-GCM operates natively in
> GF(2^128) with the reduction polynomial is x^128 + x^7 + x^2 + x + 1, this
> is not the case (unless you are reversing the bits in the bytes of each
> block). AES-GCM is operating in the field represented by the reduction
> polynomial x^128 + x^127 + x^126 + x^121 + 1.
>
> There will be explained in detail in a paper that I will post soon. But
> perhaps the slides in my RWC talk could explain this for now (
> https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf)
>
> Regards, Shay
>
>
> 2017-01-30 23:58 GMT+02:00 Alex Cope <alexcope@google.com>om>:
>
>> I'm also unconvinced that defining POLYVAL as modulo x^128 + x^127 +
>> x^126 + x^121 + 1 is better than defining it modulo x^128 + x^7 + x^2 + x +
>> 1.
>>
>> My reasons for thinking that  x^128 + x^7 + x^2 + x + 1 is a better
>> reducing polynomial are:
>> 1) On X86, no performant implementation of POLYVAL will reduce to GHASH,
>> as that would result in unnecessarily byte swapping twice then calling
>> PCLMULQDQ. The same seems true for any implementation in a little-endian
>> machine.
>> 2) If the concern is making a less performance sensitive implantation of
>> GCM-SIV easier to write given a GCM implantation, the relationship between
>> POLYVAL as currently defined and GHASH does help slightly. However,
>> implementing finite field multiplication with POLYVAL'S byte ordering
>> modulo x^128 + x^7 + x^2 + x + 1 given a reference GHASH implementation is
>> quite easy*, and most accidental errors in such implementation will be
>> detected by test vectors.  Thus I don't think the current design choice
>> makes GCM-SIV substantially easier to implement correctly.
>> 3) x^128 + x^7 + x^2 + x + 1 is more 'natural' as as the lexicography
>> first irreducible polynomial.  It seems likely that future work that relies
>> on finite field multiplication will opt to use the byte ordering of POLYVAL
>> because it makes the most sense on little endian machines, and will also
>> reduce modulo  x^128 + x^7 + x^2 + x + 1.  I doubt anyone else will want to
>> use GHASH as currently defined, but if it were defined modulo x^128 + x^7 +
>> x^2 + x + 1, the implementation could be nicely reused. I think that in the
>> long term this will lead to more code reuse than having POLYVAL as a one
>> off finite field representation.
>>
>> If you are strongly concerned reusing dedicated hardware or big-endian
>> implementations of GHASH then the current design makes some sense as a
>> compromise, but I'm unaware of such requirements.
>>
>> Regards
>> -Alex
>>
>> *I did it recently for a table-based implementation. You can look at the
>> patch here: https://patchwork.kernel.org/patch/9428397/
>>
>> On Fri, Jan 27, 2017 at 12:21 PM, Adam Langley <agl@imperialviolet.org>
>> wrote:
>>
>>> 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
>>>
>>> _______________________________________________
>>> Cfrg mailing list
>>> Cfrg@irtf.org
>>> https://www.irtf.org/mailman/listinfo/cfrg
>>>
>>
>>
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>>
>