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

From: Alexey Melnikov <[email-masked]>
Date: Sat, 16 Sep 2017 16:15:24 +0100

Dear CFRG participants,
This message starts 2 week RGLC on "AES-GCM-SIV: Nonce Misuse-Resistant Authenticated Encryption" (draft-irtf-cfrg-gcmsiv-06), that will end on October 1st. Please send you comments, as well as expression of support to publish as an RFC (or possible reasons for not doing so) in reply to this message or directly to CFRG chairs. Your feedback will help chairs to decide whether the document is ready for review by IRSG and subsequent publication as an RFC.

Thank you,
Kenny and Alexey

---

From: Andy Polyakov <[email-masked]>
Date: Mon, 18 Sep 2017 19:51:36 +0200

Hi,

I apologize for chiming in so late, but I wasn't aware of this endeavour
till very recently. The question I find myself struggling with is that I
can't find introduction of new primitives justified, at least not in
this context. I did my best sieving through
https://mailarchive.ietf.org/arch/search/?q=gcmsiv) to locate relevant
prior comments, so even with those in mind. One of arguments was that
POLYVAL gets bit order right in comparison to GHASH. Well, comparing the
two is actually boils down to one question: what is it you choose to
bit-flip, input or polynomial? [Do note "bit-flip", not "byte-flip".]
What I'm trying to say is that we have to recognize that POLYVAL is
simply formulated in terms of GHASH polynomial in reverse bit order. On
the other hand on more practical level, i.e. from software
implementation viewpoint, answer to the question is self-obvious, it's
more efficient to bit-flip single polynomial than each fragment of the
input. This last thing effectively means that sensible GHASH
implementation would actually use reverse-bit polynomial (and at least
OpenSSL implementations all do). This in turn means that the only
essential difference between GHASH and POLYVAL is byte order. Now, it
was argued that little-endian byte order gives performance edge [on
platform of popular choice]. But relevant question in the context is if
the edge actually justifies introduction of new algorithm. It was
asserted that it provides 20% improvement and it was attributed to the
fact that PCLMULQDQ-based GHASH implementations use vector byte swap
instructions, *one* per block. But we have to recognize that said
improvement coefficient is actually specific to Skylake. For example on
Haswell we'll observe ... 0% improvement, on Broadwell - 6%, on Ryzen -
3%. Let's even have a look at absolute cycles per processed byte values
for GHASH:

Haswell   0.41
Broadwell 0.29
Skylake   0.36

Do note that effectively we observe regression on Skylake, also note
that it's ~20%. I mean if Skylake inherited Broadwell qualities, GHASH
would have performed ~20% better. With all the numbers in mind it's only
natural to conclude that vector byte swap "costs" unproportionally much
specifically on Skylake [and in GHASH], and it's rather anomaly than
rule. And it's not unlikely to be addressed in next processor
generation. At least other alike cases were, just look at improvement
from Haswell to Broadwell above. And if not, maybe it would still be
more appropriate to demand that Intel fixes this in next-next
generation, instead of introducing new algorithm. Because latter
approach is not really sustainable. I mean how many algorithms would we
have to implement and support if they were introduced on per
specific-processor-pipeline-anomaly basis? Besides, even 20% improvement
has to be considered in overall context, not by itself. I mean if the
only difference between two otherwise equivalent proposals was POLYVAL
vs. GHASH, then improvement for *whole* operation would be ~6% [on
Skylake, and none to negligible on others]. Or in other words this
proposal *could* just as well be formulated with GHASH instead of
POLYVAL, there is no *compelling* reason to introduce another algorithm.

And same can be said about suggested CTR tweak. I.e. suggested mode
*could* just as well be formulated with standard CTR. Even more so, as
there is no apparent difference in performance [on platform of popular
choice].

Well, it's not like I actually reject the sentiment to favour
little-endian platform[s], question rather is if *mode* specification is
right place for it. Protocols are about *communication* and there are
more factors in play, most notably using already available primitives
would facilitate adoption. And if little-endian-centric primitives are
deemed desirable, wouldn't it be more appropriate to define them
separately to promote modularity and re-usability?

Cheers.

---

From: "Blumenthal, Uri - 0553 - MITLL" <[email-masked]>
Date: Mon, 18 Sep 2017 18:01:36 +0000

I support publishing this draft as an RFC.

Thanks!

--

Regards,

Uri Blumenthal

From: Cfrg <[email-masked]> on behalf of Alexey Melnikov <[email-masked]>
Date: Saturday, September 16, 2017 at 11:13
To: CFRG <[email-masked]>
Subject: [Cfrg] RG Last Call on draft-irtf-cfrg-gcmsiv-06

Dear CFRG participants,

Thank you,

Kenny and Alexey

---

From: Ted Krovetz <[email-masked]>
Date: Mon, 18 Sep 2017 12:14:51 -0700

For those unfamiliar with Andy's work, he is the primary contributor of assembly-language implementations to OpenSSL. For example, most of these were written by him and are first-rate.

https://github.com/openssl/openssl/tree/master/crypto/aes/asm
https://github.com/openssl/openssl/tree/master/crypto/modes/asm

If Andy says that there is likely no long-term performance benefit to using POLYVAL rather than GHASH, then I think this is probably right.

Before going further with the RFC, could the gcmsiv authors please address the long-term cost vs benefit of using POLYVAL and the modified CTR rather than GHASH and standard CTR?

Thanks,
Ted

---

From: Watson Ladd <[email-masked]>
Date: Mon, 18 Sep 2017 12:35:19 -0700

> 3%. Let's even have a look at absolute cycles per processed byte values

It's important to not conflate the following 3 distinct things:
- The maximum performance attainable by the best implementation on
each microarchitecture
- The maximum performance attainable by a single implementation on
each microarchitecture
- The maximum performance attainable by the best implementation for a
single implementation strategy on each microarchitecture

It's also important not to conflate the following 4 things:
- The arrangement of limbs in a bignum
- The internal arrangement of bits in a limb
- The arrangement of bits in a byte
- Reduction strategy

I don't get a clear impression from your email what implementations
you used or what strategies and representation.

POLYVAL takes the least significant bit of a byte to be the constant
coefficient. No matter what architecture (big or little endian) you
have, this is clearly the right choice as it is exactly the choice
made when considering a byte to be an integer in the range 0 to 255.
GHASH does something weird I don't recall exactly.

dot(a,b) is the result of a Montgomery reduction of the product ab
with Montgomery modulus x^128. This is true no matter what
representation of the polynomials is chosen. Most fast GHASH
implementations use Montgomery form internally, due to the advantages
of Montgomery form. POLYVAL thus removes conversions into and out of
Montgomery form. These conversions might be extremely cheap, but they
are not free. If combined with the GHASH weirdness they may be very
cheap indeed, but POLYVAL conversions are not more expensive even if
you have to swap byte order in a word on read.

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.

Sincerely,
Watson Ladd

---

From: Adam Langley <[email-masked]>
Date: Mon, 18 Sep 2017 12:41:52 -0700

> separately to promote modularity and re-usability?

Anyone who has implemented GHASH has had to wrestle with the
specification's handling of bit ordering, it's confusing beyond
questions of little- vs big-endian.

But it's also the case that little-endian machines now dominate. It's
nice that some big cores can largely hide the cost of doing the byte
swap, but hiding work is not the same as avoiding it (as your Skylake
numbers show) and smaller cores may not be able to do the
out-of-order, superscalar magic needed. POLYVAL is GHASH done right
for the world as we find it.

As for diversity: that's a cost. Although it's smaller here than in
many cases. Where the diversity costs really bubble up is when they
spread up the stack and we have, say, RSA-with-SHAKE128 to test and
validate everywhere. I think the diversity cost of AES-GCM-SIV is
concentrated in its very existence (i.e. that it's not AES-GCM). For
cases where AES-GCM-SIV isn't being written as a stitched asm blob
(where the full implementation cost of either POLYVAL or GHASH is be
paid anyway), BoringSSL uses the mapping to GHASH to avoid another
implementation, as specified in the draft.

Cheers

AGL

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

---

From: Andy Polyakov <[email-masked]>
Date: Mon, 18 Sep 2017 23:13:49 +0200

> If Andy says that there is likely no long-term performance benefit to using POLYVAL rather than GHASH, then I think this is probably right.

I don't feel that it's what I tried to say, not exactly. I said that
reported 20% improvement is rather anomaly than rule in the POLYVAL vs.
GHASH case, and it wouldn't be sustainable practice if decisions are
based on anomalies. Because anomalies tend to be resolved. In other
words long-run term of mental equation is rather how decisions are made,
than POLYVAL performance per se. As for POLYVAL per se. I'm not saying
that it doesn't offer *any* performance benefit, only that it doesn't on
some platforms, and that in non-anomalous cases it would be far from
"overwhelming". As additional couple of data points I've just collected
results for Cortex-A53, 6%, and Cortex-A57, 0%. It's common big.LITTLE
pair with A53 being "little". [Yes, equivalent of PCLMULQDQ was used. If
it wasn't, difference would be hardly measurable.]

> Before going further with the RFC, could the gcmsiv authors please address the long-term cost vs benefit of using POLYVAL and the modified CTR rather than GHASH and standard CTR?

In the context what I'm also trying to say/imply/suggest is that *mode*
specification is not necessarily right place to introduce primitives.

---

From: Andy Polyakov <[email-masked]>
Date: Tue, 19 Sep 2017 00:33:34 +0200

> questions of little- vs big-endian.

As mentioned in 1st message, it's all about what you bit-flip,
polynomial or input. Or rather how you view polynomial. If GCM
specification is considered confusing (I'm not saying that it isn't),
then why not address *that*? By re-specifying it with bit-flipped
polynomial?

> out-of-order, superscalar magic needed.

The assertion that 20% improvement is rather anomaly than rule has
lesser to do with cores being "little" or "big". And I feel that logic
is getting twisted here. "Big" cores are considered to be more likely to
amortize additional cost of byte swap, right? Skylake is "big" core and
it does have computational resources to do so. And fails miserably.

> POLYVAL is GHASH done right

Then let's say exactly that. Let's specify it as re-usable primitive.
Does it actually have to be interwoven into *this* or *any* specific
mode specification?

> validate everywhere.

I don't quite follow. This is rather argument against introducing new
primitives. Because as far as testing and validation goes, there is no
difference between these cases. I mean you get more to test in both
cases. But it would be less to test and validate if suggested mode used
existing primitives.

> I think the diversity cost of AES-GCM-SIV is
> paid anyway). BoringSSL uses the mapping to GHASH to avoid another> implementation, as specified in the draft.

I sense contradiction here. It's argued that alternative primitives
provide better performance. But attaining acclaimed performance *will*
take dedicated modules, i.e. significantly increase diversity. Even
without stitched implementation. If expectation is that majority will
take easy way out (perform byte swapping of GHASH input and output, and
build modified CTR with signle-block cipher subroutine), then question
about alternative primitives being well justified becomes even more acute...

[On side note, as for stitched implementation, core function in
aesni-gcm-x86_64.pl should be reusable if GHASH and standard CTR were used.]

Cheers.

---

From: Andy Polyakov <[email-masked]>
Date: Tue, 19 Sep 2017 09:19:18 +0200

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

---

From: Andy Polyakov <[email-masked]>
Date: Tue, 19 Sep 2017 09:46:14 +0200

> it does have computational resources to do so. And fails miserably.

I think I've misinterpreted the original remark in my head, as reply
appears orthogonal now, in the morning. Yes, some processors will fail
to amortize costs of byte swap, but point is that even if they won't,
*customarily* unamortized cost won't be anywhere near 20%. Yes, avoiding
byte swap will lift the question altogether, but question still is if
gain (and we are be talking about non-anomalous cases) justifies
introduction of new primitives. Yes, they might appear more elegant to
little-endian eye, but these two, performance and elegance, are not the
only parts of equation. Not to mention that every term has weight
coefficient. Performance's weight is improvement coefficient (6% on
Skylake, none to effectively negligible on others, negative for those
who choose easy way out(*)), and elegance's weight is...

(*) As mentioned earlier, "easy way out" refers to performing byte
swapping of GHASH input and output, and building modified CTR with
signle-block cipher subroutine. As opposite to investing into
high-performance code that would have to be dedicated. Even unstitched.

---

From: Shay Gueron <[email-masked]>
Date: Tue, 19 Sep 2017 10:47:25 +0300

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

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

---

From: Andy Polyakov <[email-masked]>
Date: Tue, 19 Sep 2017 11:53:03 +0200

Hi,

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

So we agree that performance *gains* are marginal. Should we consider
performance *losses* elsewhere? For example for those who choose "easy
way out". Or have to do so, for example because they have dedicated
GHASH hardware. But even if we take performance out of equation, do we
all agree that "consistency" is sufficient by its own? To justify
additional implementation/diversity costs that is. Do note that we are
not exactly still struggling with GCM. Effectively thanks to

> I proposed a way to solve this
> (https://crypto.stanford.edu/RealWorldCrypto/slides/gueron.pdf) ,

And once again, if we agree that "consistency" is sufficient by its own,
does it have to be interwoven with specific mode specification? Isn't it
like starting building house from *roof*? If we consider that we would
be better off if primitives were little-endian-centric, then let's say
that and start building *foundation*...

---

From: Shay Gueron <[email-masked]>
Date: Tue, 19 Sep 2017 13:19:35 +0300

Dear Andy,

>>> do we all agree that "consistency" is sufficient by its own?

To me, a clean and consistent specification has value. The ability to
express a mode which depends on algebraic properties, via natural algebraic
formulation, has value.
Here, by natural, I mean a*b*x^-128 in GF(2^128). Compare this to AES-GCM's
a*b*x^-127 and then pushing one "*x" into H (and pre-computing "H*x") to
actually shift it to something that can be computed efficiently.
But this is an opinion.

>>> those who choose "easy way out".
>>> because they have dedicated GHASH hardware.
As Adam had mentioned, adding AES-GCM-SIV (to gain misuse resistance) has
its cost anyway, so adding the bytes swap to that cost is not a big deal. I
think it is very good that we have the easy way out.

>>> does it have to be interwoven with specific mode specification?
In fact, one might say that it is GHASH that was interwoven with the
specific mode...

Regards, Shay

---

From: Andy Polyakov <[email-masked]>
Date: Tue, 19 Sep 2017 13:32:17 +0200

> To me, a clean and consistent specification has value.

I don't deny its value, question was it is sufficient [to justify
additional implementation/diversity costs].

> As Adam had mentioned, adding AES-GCM-SIV (to gain misuse resistance)
> has its cost anyway,

Yes, and assertion is that it could have been *lower* if it was
formulated with GHASH and standard CTR.

> so adding the bytes swap to that cost is not a big
> deal. I think it is very good that we have the easy way out.

As already mentioned, there is another actor in the drama, tweaked CTR.
If byte swap for GHASH can be considered acceptable (what's your
estimate by the way?), question about alternative CTR remains. Thing is
that if it's built upon single-block function, its performance would be
*significantly* lower in comparison to dedicated optimized CTR
subroutine. Well, one can mitigate it by deploying ECB, but not all
[OpenSSL] modules have dedicated ECB subroutine...

> In fact, one might say that it is GHASH that was interwoven with the

Fair point. But was it optimal choice? I mean does it actually mean that
it has to be that way even now and for all eternity? :-)

Cheers.

---

From: Andy Polyakov <[email-masked]>
Date: Wed, 27 Sep 2017 23:50:25 +0200

> additional implementation/diversity costs].

It's obvious that more natural bit order in POLYVAL was not the goal by
itself. Performance on par with GCM also was. And not just any GCM
performance, but one assisted by AES-NI and PCLMULQDQ instructions or
their equivalents. Next thing to understand is that referred GCM
performance is achieved by optimizing for specific cases, CTR and GHASH,
and in x86_64 case even stitched CTR-GHASH. And keyword is "specific
cases". Draft in question asserts that suggested mode decrypt
performance is virtually equivalent to GCM, but fails to emphasize that
this holds true only provided that one has devoted equivalent effort
into optimizing code for specific cases of modified CTR and POLYVAL.
Because if one doesn't do that and takes "easy way out" by exploiting
byte order equivalence with GHASH and modified CTR relying on
single-block encrypt, performance impact would be devastating, up to
several *times*. On the other hand if mode was specified using GHASH and
standard CTR, as already discussed, difference would be none to
negligible [in non-anomalous cases].

> formulated with GHASH and standard CTR.

Because it would be limited to ordering calls to existing GHASH and CTR.

Cheers.

---

From: Stefano Tessaro <[email-masked]>
Date: Sat, 30 Sep 2017 16:00:11 +0200

Dear CFRG:

We wanted to bring to your attention a potential optimization of the
key-derivation step in AES-GCM-SIV that has come out of some of our
related research work. Sorry this comes somewhat late: We are in the
process of finalizing a clean write up, but due to time sensitivity,
we wanted to make the CFRG list aware of this related work.

Currently, the key-derivation function DeriveKey of AES-GCM-SIV uses
4-6 AES calls (4 to generate a 256-bit key, and 6 to generate a
384-bit key). The overhead of key derivation over plain GCM-SIV can be
up to 10% for messages under 1KB (according to the authors’
benchmarks). Our findings suggest a simple optimization that halves
the number of calls.

Concretely: Suppose that we have a master key K and a 96-bit nonce N.
If we want to produce a 256-bit key, DeriveKey(K,N) will output

AES_K(pad(N, 0)) || AES_K(pad(N, 1)),

whereas if we want to produce a 384-bit key, we will instead output

AES_K(pad(N, 0)) || AES_K(pad(N, 1)) || AES_K(pad(N, 2)).

Here, we demand that pad(N, 0), pad(N, 1), pad(N, 2) is different from
pad(N’, 0), pad(N’, 1), pad(N’, 2), and that pad(N, 0) is not a
possible input to AES within CTR encryption. Due to the way in which
AES-GCM-SIV already adopts domain separation elsewhere, it is enough
to implement pad(N, i) as the concatenation of the 96-bit nonce N and
a 32-bit counter of value i, but here note that one has to swap the
relative ordering of nonce and counter in the current proposal, namely
the nonce comes first, and then the counter.

To see why this would work, we note that the current DeriveKey
function, and other proposals by Iwata and Seurin, are required to be
a highly-secure pseudorandom function. Intuitively, this is because
the current approach to prove security of AES-GCM-SIV reduces (as an
intermediate step) to the security of GCM-SIV, and in turn of AES,
under (multiple) independent random keys. This independence is not
necessary in general, and security proofs go through even when key
distributions are much more structured, such as the one produced by
our simple DeriveKey proposal. (This can be validated in the so-called
ideal cipher model, and we are not aware of any cryptanalytic insights
that would invalidate this when using AES.) Similar ideas of more
structured block-cipher based key-derivation have been used in
different contexts, e.g., in https://eprint.iacr.org/2017/877.

We can prove excellent security bounds for this variant of
AES-GCM-SIV, in particular in the so-called “multi-user setting”,
where attackers are accessing multiple instantiations of the scheme
under independent keys (think of this as multiple TLS sessions using
the scheme). In this case, we obtain a bound of the order LB / 2^{128}
+ d(T + L) / 2^k, where: L is a bound on the number of blocks, B is a
bound on the number of blocks encrypted/verified for a nonce-user
pair, d is the maximum number of users that re-use a nonce in
encryption queries, T is a bound on the time-complexity of the
attacker, and k is the key length of AES, which is either 128 or 256
bits. (For the single-user setting then obviously d = 1.) If nonces in
encryption queries are picked at random then d is a small constant,
and thus the multi-user security is roughly the same as the
single-user security. (In particular, there is a folklore
understanding that multi-user security fails when more than 2^{64}
users are involved, for k = 128, as two of them will likely have the
same key, but show that this is not an issue for AES-GCM-SIV.)

If nonces are picked arbitrarily then d can be as big as the number of
queries; in this case we need to pick key length k = 256 for high
security in the multi-user setting.

We note that previous analyses do not consider the multi-user setting.

Best,

Priyanka Bose (UC Santa Barbara)
Viet Tung Hoang (Florida State University)
Stefano Tessaro (UC Santa Barbara)

On Sat, Sep 16, 2017 at 5:15 PM, Alexey Melnikov
<[email-masked]> wrote:
> Dear CFRG participants,
>
> This message starts 2 week RGLC on "AES-GCM-SIV: Nonce Misuse-Resistant
> Authenticated Encryption" (draft-irtf-cfrg-gcmsiv-06), that will end on
> October 1st. Please send you comments, as well as expression of support to
> publish as an RFC (or possible reasons for not doing so) in reply to this
> message or directly to CFRG chairs. Your feedback will help chairs to decide
> whether the document is ready for review by IRSG and subsequent publication
> as an RFC.
>
> Thank you,
> Kenny and Alexey
>

-- 
Stefano Tessaro
Assistant Professor of Computer Science
University of California, Santa Barbara
http://cs.ucsb.edu/~tessaro/