Re: [Cfrg] AES GCM SIV analysis

[Adam Langley <[e-mail]>]

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