Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06

Shay Gueron <> Tue, 19 September 2017 07:47 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 38E6E1342CB for <>; Tue, 19 Sep 2017 00:47:31 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Status: No, score=-1.998 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, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id n49SB7UGBExN for <>; Tue, 19 Sep 2017 00:47:29 -0700 (PDT)
Received: from ( [IPv6:2a00:1450:4010:c07::231]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 1A1D713306A for <>; Tue, 19 Sep 2017 00:47:27 -0700 (PDT)
Received: by with SMTP id k23so2799669lfi.11 for <>; Tue, 19 Sep 2017 00:47:27 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=NN2JQa9C9kUsKboxdXg6w/HHWozZTRx30iZPoQti1+Y=; b=TRiCigRu3dvK4jQOAfEt2MvZZ6u2vktkRg6rbHqdvc/h7aiB0P9WosPBRJYMDbtgyz 5U6R0EoPkZncbyCKTtXJ/wWB3NTp5yW9S7AQou2g4VcXBe3EeMbzqF//whlin5qq4dui hl8R1stplPjz76s0t/bPhapo73A03yujNckGA5Ky1m4IZ1lqXy0m2gTdBy+2Pkd8i+Em 09JUS7V7+DLMr6qpj/cyc6ZNibvjxPPASVZfkDqojdDgE/EcgFROgz1yjAtRMDeT+KSM g+1SNpnJyXH5DPfqm61mM1qC3E4iiI08Cg2iO3MNTUTunOfshU3zomGZSw/lXMUckMoy gxAw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=NN2JQa9C9kUsKboxdXg6w/HHWozZTRx30iZPoQti1+Y=; b=eQOvYU25LNJXLWxXSCr3PtdiPaEUGiT6hhaU+qkcO7xk5ryzU9c/ScDk89dHOCsiRq HnZRp5d5lep4YImI9+cxrGA//iO0y4Th/dtsO4PoW5rgyUgp4II4/briG78YtejzowjO 9eyj9RRecpsmyW03A56AIqtsBVkOZGg1QZNmAAMooyUi+f8XbWt+QAY0bnhESdagNiNQ aUjjtK9ywkIeslc3vhIRZcTEBaQF9z1hKTrB0Zk6f4yaJ1orVuc78c/GdwFTL2uUsiRz SGpnS4tsGLX1ReLLz7J0IrDh5QUO/nWATxtCyAg9qzOYMZifK/p9+12sqlHWtA6Jxore neeQ==
X-Gm-Message-State: AHPjjUi0x520KQLcVP9d536D6xnQbzq/Ccvi0YC9WFzM7zVXO4WXM8A8 U4wEE2ovJ7yxwdtJywL/nnFK8f2wCzTLmnMyeEs=
X-Google-Smtp-Source: AOwi7QBkvJ+O1n60I0RRPk6HgX4mHHikxR0RdexCclnKWy+0QJrV2E9fWDBQ9RvZX+Cn+cmIZemdgy/DI/mZk+LIbEs=
X-Received: by with SMTP id u25mr232230lfk.111.1505807246146; Tue, 19 Sep 2017 00:47:26 -0700 (PDT)
MIME-Version: 1.0
Received: by with HTTP; Tue, 19 Sep 2017 00:47:25 -0700 (PDT)
In-Reply-To: <>
References: <> <> <> <>
From: Shay Gueron <>
Date: Tue, 19 Sep 2017 10:47:25 +0300
Message-ID: <>
To: Andy Polyakov <>
Cc: Watson Ladd <>, "" <>, Shay Gueron <>
Content-Type: multipart/alternative; boundary="94eb2c1c064601c22f05598612a1"
Archived-At: <>
Subject: Re: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Tue, 19 Sep 2017 07:47:31 -0000

Dear Andy (and everyone),

I would like to re-emphase a few points (although they have been already
nicely stated).

The purpose of using POLYVAL is not performance. It is "consistency". The
performance gains are a marginal bonus (and if they are ephemeral it does
not matter).

My purpose in defining the hash function as POLYVAL and not GHASH are
"consistency", as follows. A polynomial of degree 127 is sum (j=0..127) a_j
x^j. The relation between a polynomial and a string of bits is an arbitrary
choice (i.e., the direction from which the string is read). However, when
GHASH is combined with AES, to define AES-GCM, there is some inconsistency.
AES is defined over a state of 16 bytes. And bytes have a specific order of
bits inside them. This is independent of endianness (which is related to
the order of the bytes). For AES-GCM - the order of the bits for GHASH, is
inconsistent with the order of the bits in the bytes of the AES state (and
in general).

If you look at the AES-GCM spec, you will see that GHASH is defined via a
bit-wise algorithm. The interpretation that it is a polynomial in
GF(2^128), with the specific reduction polynomial, is somehow misleading.
Because the actual field representation would then need to involve a bit

I proposed a way to solve this ( , by
describing GHASH over a GF(2^128) with a different reduction polynomial, Q
= x^128 + x^127+x^126+x^121+1.  And then, the operation is not the field
multiplication, but rather  it is A * B * x^(-127) mod Q. With this,
AES-GCM gets an algebraic formulation.

Computing A * B * x^(-127) is not conveninet, nor efficient. So, for
implementation  AES-GCM uses the identity
(A * x)  B * x^(-128) mod Q, taking advantage that A is fixed (the hash

For POLYVAL, we started from A * B * x^(-128) mod Q, and from a definition
of the polynomials is consistent with the way that bytes are used. This
makes a cleaner definition.

The AES-GCM-SIV spec provides a formula that one can use, to implement it
via calls to GHASH, if one wishes to do that. BoringSSL does it.
Also, if someone is interested in an implementation that interleaves
decryption and hashing, there is such code published (and BoringSSL does


2017-09-19 10:19 GMT+03:00 Andy Polyakov <>:

> > I don't get a clear impression from your email what implementations
> > you used or what strategies and representation.
> I apologize for not being clear enough. I suppose I assumed that it's
> obvious that I referred to OpenSSL implementation[s]. At least that's
> what accompanying paper refers to as baseline. The absolute cycles per
> byte results are quoted from <openssl>/crypto/modes/asm/,
> where you can also find details about implementation techniques. Do note
> that it uses reduction algorithm proposed by Shay, which he already
> mentioned here in another thread.
> > I'm thus extremely doubtful that your numbers below are correct: they
> > may be. But I'm skeptical. Benchmarking is really hard, and I know
> > I've screwed up plenty of these measurements myself.
> Don't take my word for it, collect your own and tell us about it. [Do
> note though that Skylake results are in perfect agreement with referred
> paper. And non-Skylake results were collected using same method.]
> _______________________________________________
> Cfrg mailing list