Subject: [Cfrg] AES GCM SIV analysis

From: "Cooley, Dorothy E" <[email-masked]>
Date: Wed, 18 Jan 2017 16:49:11 +0000

P { MARGIN-BOTTOM: 0px; MARGIN-TOP: 0px }   

NSA's Information Assurance organization did some analysis of AES-GCM-SIV, as described in "AES-GCM-SIV:  Nonce Misuse-Resistant Authenticated Encryption", dated August 29, 2016 [1].  We shared this analysis privately with the three authors of AES-GCM-SIV, who requested that we post it to the CFRG forum. The attachment describes the results of the analysis. We believe the authors will be posting an update shortly.

Any comments on this work can be directed to me.  But I will note that I didn't do the actual analysis (I can't claim to be a 'real' cryptographer these days).

Deb Cooley

NSA Information Assurance Standards.

[email-masked]

[1]  https://tools.ietf.ort/html/draft-irtf-cfrg-gcmsiv-02

---

From: Adam Langley <[email-masked]>
Date: Wed, 18 Jan 2017 09:34:31 -0800

On Wed, Jan 18, 2017 at 8:49 AM, Cooley, Dorothy E <[email-masked]> wrote:
> NSA's Information Assurance organization did some analysis of AES-GCM-SIV,
> as described in "AES-GCM-SIV:  Nonce Misuse-Resistant Authenticated
> Encryption", dated August 29, 2016 [1].  We shared this analysis privately
> with the three authors of AES-GCM-SIV, who requested that we post it to the
> CFRG forum. The attachment describes the results of the analysis. We believe
> the authors will be posting an update shortly.
>
>
>
> Any comments on this work can be directed to me.  But I will note that I
> didn't do the actual analysis (I can't claim to be a 'real' cryptographer
> these days).
>
>
>
> Deb Cooley
>

Dear CFRG,

We thank Deb Cooley's team very much for doing this analysis! As she
mentioned, they shared their results with us prior to posting here so
we already had an update ready and we've just posted
https://tools.ietf.org/html/draft-irtf-cfrg-gcmsiv-03.

This update contains three noteworthy changes:

1) We now XOR the nonce into the result of POLYVAL before encrypting
to form the tag. This was in the original paper, it was even specified
for /decryption/ in -02, but it was omitted in the specification for
encryption. This was a mistake. Without it, an attacker can build a
lookup table of encryptions of zero under a variety of per-nonce keys
and then attack them in parallel (as pointed out in the comments from
the IAD), under a single-user-multi-key model.

Draft -03 fixes this omission and reintroduces the nonce.

2) A different KDF. As I mentioned at the previous CFRG meeting (in
Seoul, 2016) , we had this design in mind but didn't feel that it
warranted a new version of the design. However, since we needed a
respin because of (1), we have included it.

Previously, per-nonce key material was generated by repeated
encryption, E(nonce), E(E(nonce)), and so on. This cascade leads to
impractical but needling issues including those noted by IAD. We now
generate keys by using counter mode and discarding half of each
ciphertext block. This solves those issues and also gives improved
indistinguishability bounds.

In order to make room for the counter, the nonce size has been reduced
to 96 bits.

3) A much more minor change is that we now suggest a limit of 2^8 as
the maximum number of plaintexts encrypted with a single nonce. We
previously noted that AES-GCM-SIV with a fixed nonce is similar to
AES-GCM with a random nonce, and that NIST recommends a limit of 2^32
messages in that context.

Note that we do NOT recommend nonce reuse by choice even inside
AES-GCM-SIV. This is for two reasons. First, encrypting the same
message twice will be detected. Second, the security bounds when using
different nonces are better. For example, when encrypting 2^{32}
messages with the same nonce, the probability of a bad event is
2^{-32}. However, as we have shown, when encryption with different
nonces, it is possible to go up to about 2^{50} messages without any
problem.

If nonces repeat mistakenly, for which providing protection is the
main aim of this mode of operation, then very strong bounds are still
obtained for a large number of ciphertexts (much more than 2^32) as
long as a single nonce is not repeated more than say 2^8 times. In
practice, such an event is highly unlikely.

Cheers

AGL

---

From: Adam Langley <[email-masked]>
Date: Wed, 18 Jan 2017 10:25:38 -0800

Also, in the interests of keeping things on the working-group mailing
list, I am including the two follow-ups that Shay and Yehuda sent,
previously, in response to this.

(The discussion took place in two back-and-forth iterations. Hence
they sent two replies, which are attached here.)

-----Message one-----
We greatly thank you for your interest in the AES-GCM-SIV
authenticated encryption scheme, and for your work on analyzing it.

We begin with the first attack. It is well known that in the model of
multi-key security, if there are M different users with M different
keys, and the key-space is of size N, then it is possible to find one
of the keys in time M/N. We cast the attacks you describe in this
light. Specifically, since our CFRG essentially changes the keys in
every encryption, we obtain a multi-key setting even for a single
user. Considering, for example, attack number 1: this attack works
since it is possible to obtain encryptions of a single known block
under many keys. Thus, the original multi-key attack of [1] is
applicable.

Having said the above, we find that the tradeoff between the CFRG and
original GCM-SIV paper to be favorable toward the CFRG. This is
because as with all counter modes, the original GCM-SIV and GCM with a
random nonce (counter) has the property that after 2^32 different
encryptions, the probability of a collision on the nonce (counter) is
about 2^-32. Now, if less than 2^32 encryptions are carried out, then
neither the multi-key attacks nor the collision on the counter is a
concern. However, if more than 2^32 encryptions are computed, then the
amount of work required for the multi-key attacks is still extremely
large, whereas the probability of a collision on the nonce becomes a
very real concern.

We do not dismiss the threat of multi-key attacks, and it has been
recently noted that this may be a real problem in TLS sessions. This
has prompted recent work, one example being [2]. Indeed, [2] explain
that in TLS it is preferable to use a random nonce for GCM even though
a fresh key is used in every session (and thus one could always start
with a fixed nonce of 0). This is exactly to prevent/mitigate
multi-key attacks.

We stand behind our proposal to change keys in every message, and were
surprised that changing the nonce does not solve the problem (Ref. [1]
in your document). We then noticed that in the original GCM-SIV paper
appearing in ACM CCS, we XOR the nonce with the result of POLYHASH on
the AAD and message, and then encrypt it (using AES). While our
intention was to mount some nonce-based key derivation on top of
GCM-SIV, we forgot (in one of the versions of the proposal) this XOR
in the CFRG specification. By returning this XOR, we mitigate the risk
of multi-key attacks since different nonces would now not enable an
attacker to obtain many encryptions of the same (known) block under
different keys.

Regarding the other attacks:

Attack 3 requires 2^128 chosen plaintexts. We do not consider this to
be realistic. Furthermore, when the block size is 128 bits then
everything breaks well before that (with repeating inputs to AES).
Attack 2 is just a type of time-space tradeoff and these types of
bounds are always possible on block ciphers. Note also that in order
to reduce the work time by just two bits, the number of queries
required is already 2^96. As stated regarding attack 3, with a 128-bit
block size everything breaks well before this anyway. Once again, we
thank you for your interest in GCM-SIV, and we will make the change to
mitigate the first attack as described. Although we think that users
of GCM-SIV should not be concerned with the other attacks, as
described above, we appreciate the feedback and we will document them
for full transparency.

[1] E. Biham. How to Forge DES-Encrypted Messages in 228 Steps.
Information Processing Letters, 84(3):117-124, 2002.

[2] M. Bellare and B. Tackmann. The Multi-user Security of
Authenticated Encryption: AES-GCM in TLS 1.3. In CRYPTO 2016, Springer
(LNCS 9814), pages 247-276, 2016.

Shay Gueron and Yehuda Lindell

-----Message two-----

We thank you very much for your response, and greatly appreciate your
feedback and analysis.

We would like to point out what we recommend (and plan to post) a
maximal number of usages (q_max) of a single master key, with
AES-GCM-SIV. This would better put things in context. As we promised
to the CFRG community since we posted the specifications, we are
working on a paper that analyzes the scheme and derives this
recommendation. Hopefully, it will be ready in a few weeks. In order
to explain our bound, let us first denote the 2-key specification in
the CCS paper by GCM-SIV (K1, K2, N, AAD, M). The CFRG proposal can
then be viewed as a two step protocol:

1. Key derivation: Compute (Record_Encryption_Key, Record_Hash_Key) =
KDF (Master_Key, N)
2. Encryption: Compute (Tag, C) = GCM-SIV (Record_Encryption_Key,
Record_Hash_Key, N, AAD, M)

We now consider the recommended restriction regarding the number q_max
of times that the Master_Key can be used (which actually translates to
how many different nonces can be used, but since a different nonce
should be used for every message this is the same as the number of
different messages, but messages can be long). Our calculation is that
q_max ~ 2^47 is an appropriate recommendation in order to preserve the
2^-32 security margins recommended by NIST. This 2^47 limit is based
on a failure of indistinguishability of the generated nonce-based
keys, unlike the deeper failure that AES-GCM would suffer by a nonce
misuse. This number shows that the additional key derivation increases
the number of allowed usages of a (master) key for AES-GCM-SIV,
compared to the CCS version that was limited to ~2^32 usages(and the
security margins). We are working on a way to increase q_max even
further, and this will be announced in the upcoming paper.

>From a practical viewpoint, we comment that if a user sends, say, 1
million messages per second, then a key replacement after 2^47 usages
would be necessary after ~4 years.

Since AES-GCM-SIV is designed for cases where a user needs to encrypt
multiple messages, but nonce uniqueness may be a concern, we suggest
to compare q_max to the number of times that a key can be used with
AES-GCM with a randomly selected 96-bit IV (i.e., 2^32).

With this limit on q_max, we conclude that your mentioned attacks do
not apply. We understand that you agree with this analysis.

The last question that remains is regarding the current KDF that uses
a hierarchy of keys, and this cascade generates some relation between
the derived keys. We are not extremely concerned with 2^128 work to
extract additional keys /after/ one key is compromised (with no
cryptographic method know so far). However, we agree that for 256-bit
keys, this should not be possible. This brings us to the question
about the KDF. In fact, we have been contemplating amongst ourselves
about a better KDF that not only has better indistinguishability
bounds, but is also faster than the current one. Also, some CFRG
member have very recently asked about this. Therefore, we do intend to
replace the KDF, as follows. AES-GCM-SIV will receive a 96-bit nonce.
The KDF will compute AES (Master_Key, IV || IntToString32 (j)) for
j=0, …, 3 (128-bit key) or j=0, …, 5 (256-bit key). From each of these
4 (or 6) generated blocks, 64 bits will be discarded, and then pairs
will be combined into 2 (3) 128-bit values. These will be used as the
Record_Hash_Key and the Record_Encryption_Key. The
indistinguishability advantaged of this KDF (assuming AES is a close
approximation to a random permutation), is bounded by 6q/2^96 where q
is the number of times that the KDF was called with a single (master)
key (see [1]). Now, for q different random nonces, the probability of
an r-multi-collision (i.e., at least one value appears at least r
times), and hence also on the pernonce keys, can be bounded by
1/u^{r-1} * Binomial (q, r) (where u=2^96 here). Note that if for
different nonces, there is a collision on the derived keys, this will
not be a case of nonce misuse.

We can require a limited number of allowed nonce repetitions. Based on
the above calculation, the probability that selecting the nonce
(uniformly) at random will show r-multi-collisions (for a large r), is
negligible, when staying with the bounds of q_max. Assume now that for
the q_max (randomly) generated nonces, each value appears at most 4
times. Using some bound on the (intentional) number of messages
encrypted by one selected nonce (and the lengths of the messages and
AAD’s), we can apply the security bounds that we have on GCM-SIV.

We plan to post the updated specification next week.

Thank you again, Shay and Yehuda

[1] S. Gilboa, S. Gueron, “The Advantage of Truncated Permutations”,
https://arxiv.org/abs/1610.02518 (submitted on 8 Oct 2016).
[2] K. Suzuki, D. Tonien, K. Kurosawa, K. Toyota, “Birthday Paradox
for Multi-collisions”, Proceedings of the 9th International Conference
on Information Security and Cryptology, 29-40 (2006).
http://dl.acm.org/citation.cfm?id=2172962

---

From: Brian Smith <[email-masked]>
Date: Wed, 18 Jan 2017 10:51:44 -1000

> messages in that context.

The actual text in the draft is "Thus with AES-GCM-SIV we recommend
that, for a specific key, a nonce not be repeated more than 2^8
times."

Is this a meaningful recommendation? How would one go about following
this recommendation in a practical implementation? In particular,
AES-GCM-SIV is mostly interesting in implementations that cannot
reliably and/or consistently save state, and it seems like any attempt
to write code to enforce this relies on saving state in the manner. Is
the idea here that one would, every 2^8 or so messages, force some
kind of "sync state or force rekey" operation that would be too
expensive to do on every message?

Do we really need a 32-bit counter for this mode? Why not have a
16-bit counter? This would allow single messages up to 1MB. Then one
could more safely use a 96-bit random + 16-bit fixed ID nonce or an
80-bit random + 32-bit fixed ID nonce. In general, super large
messages don't work well with AEADs because it's hard to verify the
integrity of a giant message before using the plaintext, so 32-bit
counters seem excessive. I expect protocols would limit the maximum
message length such that a ~16-bit counter would be sufficient.

Cheers,
Brian
-- 
https://briansmith.org/

---

From: Shay Gueron <[email-masked]>
Date: Wed, 18 Jan 2017 13:33:35 -0800

>>> Is this a meaningful recommendation?
>>> How would one go about following this recommendation in a practical
implementation?

This is a very valid question, that is answered in the specification. But
perhaps it is worth clarifying on the mailing list. It is rather easy to
adhere to the recommendation. Simply choose the 96-bit nonce uniformly at
random. After, say, 2^{50} encryptions, what the probability that a nonce
repeated, even 5 times, can be bounded from above (see the "multibirthday"
reference in the spec) by 2^(-134).
(To this, you need to add occurrences where the keys also collide. All this
analysis will be posted soon, together with the matching bounds).

>>> Do we really need a 32-bit counter for this mode?
>>> Why not have a 16-bit counter?
Also a very valid question.
The answer is that you don't really need a 32-bit counter.
It is possible for a usage to specify a shorter restriction on the allowed
message length. This will improve the security bounds, which are also a
function of k, where 2^k is the largest number of blocks in a message. You
can choose any k <= 32.

Thanks, Shay

2017-01-18 12:51 GMT-08:00 Brian Smith <[email-masked]>:

> _______________________________________________
> Cfrg mailing list
> [email-masked]
> https://www.irtf.org/mailman/listinfo/cfrg
>

---

From: Adam Langley <[email-masked]>
Date: Wed, 18 Jan 2017 13:35:15 -0800

> expensive to do on every message?

No, nothing like that. Perhaps this part of the document isn't clear.

Basically, before we noted that AES-GCM-SIV with a fixed nonce like
like AES-GCM with a random nonce (except that it also leaks when
plaintexts are equal). We noted that NIST recommends no more than 2^32
messages be encrypted with a given key in that context.

So someone could, not completely unreasonably, say that they're not
worried about leaking when plaintexts are equal and use AES-GCM-SIV
with a fixed nonce for 2^32 messages.

We're now clearly saying that's not a great idea. Instead, generate
nonces at random. With a random, 96-bit nonce you don't have to worry
about the probability of having repeated a single value > 2^8 times
until you have a staggering number of plaintexts: greater than 2^100
of them. Since that vastly exceeds our current recommendation for
number of plaintexts per key (2^50), it's basically not a concern.

If that makes sense, what could we have written to be clearer?

> message length such that a ~16-bit counter would be sufficient.

I agree that large AEAD messages have several problems. But I don't
think that we have any need for a larger nonce (see above). (And the
nonce is used with a counter only in the KDF phase, so it's unrelated
to the maximum plaintext size.)

Cheers

AGL

-- 
Adam Langley [email-masked] https://www.imperialviolet.org

---

From: Brian Smith <[email-masked]>
Date: Wed, 18 Jan 2017 17:53:09 -1000

Adam Langley <[email-masked]> wrote:
> Brian Smith <[email-masked]> wrote:
>> to write code to enforce this relies on saving state [snip]

> [snip] With a random, 96-bit nonce you don't have to worry

Perhaps: "We recommend instead that an implementation try to avoid
repeating a nonce for a specific key, just like it would it would do
for an AEAD that isn't nonce-misuse-resistant." This shifts the
emphasis away from the 2^8 number to where it belongs, IMO. Note that
"256" and how it is derived and why it is safe is explained in the
next paragraph anyway.

> to the maximum plaintext size.)

Is there any way that a larger nonce (e.g. 120 bits) hurts, other than
being inconsistent with existing IETF AEADs?

Cheers,
Brian
-- 
https://briansmith.org/

---

From: John Mattsson <[email-masked]>
Date: Thu, 19 Jan 2017 08:29:59 +0000

I think that having the same nonce length as previous IETF AEADs should
not be a goal. My view is that the GCM-SIV nonce length should be based
purely on math.

John

---

From: Shay Gueron <[email-masked]>
Date: Wed, 18 Jan 2017 09:55:19 -0800

Dear CFRG,

In the interests of keeping things on the working-group mailing list, I am
including the two follow-ups that we sent, previously, in response to this

(note: the discussion with  "NSA Information Assurance Standards" team took
place in two  back-and-forth iterations. Hence we sent two replies, which
are attached here).

Due to the limit on the size of a posting, the two files will be
transmitted in two separate mails.

This attachment: Reply 1

Thank you, Shay Gueron

2017-01-18 9:46 GMT-08:00 Shay Gueron <[email-masked]>:

> Dear CFRG,
>
>
> In the interests of keeping things on the working-group mailing list, I am
> including the two follow-ups that we sent, previously, in response to this
>
>
> (note: the discussion with  "NSA Information Assurance Standards" team
> took place in two  back-and-forth iterations. Hence we sent two replies,
> which are attached here).
>
>
> Thank you, Shay Gueron
>
>
>
> 2017-01-18 9:34 GMT-08:00 Adam Langley <[email-masked]>:
>

---

From: Shay Gueron <[email-masked]>
Date: Wed, 18 Jan 2017 10:06:33 -0800

Dear CFRG,

In the interests of keeping things on the working-group mailing list, I am
including the two follow-ups that we sent, previously, in response to this.

A note: the discussion with  "NSA Information Assurance Standards" team
took place in two  back-and-forth iterations. Hence we sent two replies,
which are attached here.

Thank you, Shay Gueron

---

From: Adam Langley <[email-masked]>
Date: Thu, 19 Jan 2017 09:33:59 -0800

> "256" and how it is derived and why it is safe is explained in the

After some discussions on Twitter I've discovered that several people
(possibly including Brian) understand "nonce-misuse resistant" to mean
a stronger property than AES-GCM-SIV has. Namely they understood it to
mean that the value of the nonce is /irrelevant/ for security, except
that a fixed nonce discloses equality of plaintexts.

AES-GCM-SIV doesn't have this property. It is robust to random nonce
duplication but not designed for a fixed nonce. Specifically, after
2^n full-sized (i.e. 64MB) messages, there's ~2^(96-2n) chance that
two of the messages reused counter values and thus keystream. (The
bounds are better if messages are smaller.)

Consider a broken TLS implementation that always uses a zero nonce and
is sending 16KB records as fast as possible. By the time it has sent
2^40 records (44 TB) there's about a 2^-32 chance that two of those
records shared keystream bytes. (That's very rough and there might be
a few stray factors of two missing in there.)

That's a lot better than AES-GCM, but we're not saying that the nonces
are completely irrelevant to security.

Perhaps we need a different term to clarify this? Occasional nonce
duplication tolerant?

> being inconsistent with existing IETF AEADs?

With three bits for the counter, the largest the nonce could be is 125
bits. But I think a nonce that's not a whole number of bytes would be
too confusing.

The nonce could be 120 bits (15 bytes) but that has no practical
advantage over 96 bits. If you're picking nonces at random then the
change in bounds is trivial (see multibirthday reference in the spec).
If your nonce generation is broken and you're using a fixed value then
the size is irrelevant.

96 bits is a "rounder" number and might save some alignment problems
is all, really.

Cheers

AGL

---

From: Dan Harkins <[email-masked]>
Date: Thu, 26 Jan 2017 18:26:17 -0800

Hello,

> that a fixed nonce discloses equality of plaintexts.

   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.

> Perhaps we need a different term to clarify this? Occasional nonce

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

> 96 bits is a "rounder" number and might save some alignment problems

   The size of the nonce should not matter to a generic misuse-resistant
cipher mode.

   regards,

   Dan.

   [1] https://eprint.iacr.org/2006/221.pdf

---

From: Adam Langley <[email-masked]>
Date: Fri, 27 Jan 2017 12:21:42 -0800

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

> 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

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.

> 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

---

From: Alex Cope <[email-masked]>
Date: Mon, 30 Jan 2017 13:58:50 -0800

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/

---

From: Watson Ladd <[email-masked]>
Date: Mon, 30 Jan 2017 16:39:13 -0800

On Mon, Jan 30, 2017 at 1:58 PM, Alex Cope <[email-masked]> wrote:
> 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:

I think it is important to look at how endianness matters in
polynomial arithmetic. GHASH takes the least
significant bit of a byte to be x^7, then takes a sequence of bytes
(a_0, a_1, \ldots a_15) to represent
a_0+a_1*x^8+a_2*x^16+\ldots+a_15*x^120. This is "little-endian": the
least significant byte is lowest. However,
it is an independent choice from the representation and layout of
words in memory.

Intel's implementation of GHASH does not reflect bytes, nor is byte
reflection sufficient in a naive implementation. For
details see: https://software.intel.com/sites/default/files/m/4/1/2/2/c/1230-Carry-Less-Multiplication-and-The-GCM-Mode_WP_.pdf

It's true that the specified polynomial doesn't have a Barret friendly
form. But the division by 128 naturally falls out of a Montgomery
based approach: precompute H*x^-8, then perform a multiplication add a
multiple of p(x) to clear out from x^0 to x^120, then shift down by a
whole number of bytes. The
multiplication by p(x) can be written as (x^8+x^7+x^6+x^1)*x^120+1 to
show that we don't need that many invocations of multiply. (Also, the
operations are linear: there are many ways to reduce the number of
reductions).

> 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.
> long term this will lead to more code reuse than having POLYVAL as a one off
> finite field representation.
>

I don't know what "big-endian" is supposed to mean here. But yes,
reusing polynomial and field specific hardware is important on devices
which aren't Intel chips, many of which will want to use hardcoded
keys and may not be able to generate nonces effectively.

-- 
"Man is born free, but everywhere he is in chains".
--Rousseau.

---

From: Shay Gueron <[email-masked]>
Date: Tue, 31 Jan 2017 03:04:06 +0200

>>> 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 <[email-masked]>:

> 1) On X86, no performant implementation of POLYVAL will reduce to GHASH,
> as that would result in unnecessarily byte swapping twice then calling
> 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

---

From: Alex Cope <[email-masked]>
Date: Mon, 30 Jan 2017 17:45:49 -0800

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 <[email-masked]> wrote:

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

---

From: Andy Lutomirski <[email-masked]>
Date: Mon, 30 Jan 2017 19:55:34 -0800

> perhaps it's well trodden ground for those who are more familiar with

AEZ looks promising to me:

http://web.cs.ucdavis.edu/~rogaway/aez/

--Andy