Re: [Cfrg] AES GCM SIV analysis

Shay Gueron <shay.gueron@gmail.com> Tue, 31 January 2017 01:04 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 3F364129784 for <cfrg@ietfa.amsl.com>; Mon, 30 Jan 2017 17:04:11 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
X-Spam-Status: No, score=-1.999 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_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 fQgZWCOhs5Tl for <cfrg@ietfa.amsl.com>; Mon, 30 Jan 2017 17:04:08 -0800 (PST)
Received: from mail-yb0-x232.google.com (mail-yb0-x232.google.com [IPv6:2607:f8b0:4002:c09::232]) (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 410B21294AD for <cfrg@irtf.org>; Mon, 30 Jan 2017 17:04:08 -0800 (PST)
Received: by mail-yb0-x232.google.com with SMTP id o65so20668546ybo.2 for <cfrg@irtf.org>; Mon, 30 Jan 2017 17:04:08 -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=w/cAzYirsmp1f/owo5GJZgcnbqDJwNCl+8CIEnHf2uQ=; b=Kbt9z6JECm0xG/XAwgn7nTp/VPs94AlOmBspM3nQDp7CXFidSdxGABCyNir5YwQdxZ oYQPF/AE5UnHpgrM/cvVYw1h9PIydkXQThRNWbC4XZPssiXvq2EWuyzZRiIoPnTkDO4I 8DN5jyPK1Vk/c7PJjx/G1VilZlYZ3ENYYUe61Rn+i7ff2vx27GIwoj8hpiZhvljykKj0 u/K+t5wQtMOtWEm9Gab+Odt2MyfGcC0dn6MfYQWTNUnYn0VEP4Em7MQRUWvogmzOce4t uj1mMoarFpNS6W0MLjmy4FOCgZzvR4CHZpOA4mNAVt4yAJrvVOZFKtB1vyF9XVmrDX9y wnow==
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=w/cAzYirsmp1f/owo5GJZgcnbqDJwNCl+8CIEnHf2uQ=; b=ej+8eF/NkZj9+S2bOqzGrSeSd3o25sRr36ZxiU09MvCFBtZAFpNQzl2CPgoAodn9Xe tp3w3ZYeMsf7pqZ922SOZy70xvwCOo/sVAFEE9i97CUgf8HhiGSWWt5heflutxTeSfpT OyWc99j4XEma/nEe7B55UESzhwEQq4F9TdMiY/1F9uG0u93PXDuVwElHoByjcbTz/VA+ h+/OehCSRLNc8z6VxndJm9fkgsJj5FbuSaxqibwyTT8V2YltfhDGZZOGXxpj4RbSNe/p 4n9Tfot0Slnj9MOXoKsZalXfgpZzhbS3ExvJqeqQEkTS6KP2cByCCeijXznM4KCcpYnS mmiQ==
X-Gm-Message-State: AIkVDXKoz2nEX78RJesS2gTalFjhkwfLQ5JyhLHOam9heV0yv5ulIuoPftCym4rcLPFndRmyWs60APuSNPe/nQ==
X-Received: by 10.37.173.1 with SMTP id y1mr13159189ybi.140.1485824647458; Mon, 30 Jan 2017 17:04:07 -0800 (PST)
MIME-Version: 1.0
Received: by 10.129.160.141 with HTTP; Mon, 30 Jan 2017 17:04:06 -0800 (PST)
In-Reply-To: <CA+cSK136NFr7gxzT1-fjDq9ZO5QGQR_67bZr1sCpL4KOTcoeDQ@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>
From: Shay Gueron <shay.gueron@gmail.com>
Date: Tue, 31 Jan 2017 03:04:06 +0200
Message-ID: <CAHP81y9twsgdWK6BXXL6rjR2uCPxf_qDr2fxqVTpX_UkEsVS1A@mail.gmail.com>
To: Alex Cope <alexcope@google.com>
Content-Type: multipart/alternative; boundary=f403045dc5d24f7b3805475982a5
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/0JiLQxMy9iR6EcqxecdlyN0xPwI>
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:04:11 -0000

>>> 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
>
>