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

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

I proposed a way to solve this (
https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf) , 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
key).

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
it).

Shay

2017-09-19 10:19 GMT+03:00 Andy Polyakov <appro@openssl.org>:

> > 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/ghash-x86_64.pl,
> 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
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>