Re: [Cfrg] Updated bounds in AES-GCM-SIV paper

Dear CFRG,

Our paper "Reconsidering the Security Bound of AES-GCM-SIV", which prompted
Adam's email, is now available on ePrint:
https://eprint.iacr.org/2017/708

The main contribution of this paper is an independent security analysis for
AES-GCM-SIV motivated by some problems that we discovered in the security
proofs presented in [1] and [2]. We also propose a different key-derivation
function with similar efficiency but better security than the one currently
specified.

As explained by Adam, we noticed that the security claims made in [2] were
overly optimistic because the PRP-PRF indistinguishability term had been
neglected, whereas it was actually the dominating term of the security
bound. As a consequence, the security guarantees provided by AES-GCM-SIV
must be lowered compared with what was originally announced in [2],
especially for long messages.

We stress that our paper is based on version 20160310:063701 of [1] and
version 20170223:140759 of [2]. Both [1] and [2] were updated after we sent
our paper to AES-GCM-SIV's designers on July 7.

We believe that the CFRG specification (especially Section 9) should be
updated as well to reflect the new security analysis. Recommended usage
limitations for an AEAD scheme (such as the maximal number of messages that
can be encrypted with the same key) should be based on the maximal message
length allowed by its specification (currently, 2^{32} 128-bit blocks).
More fine-grained recommendations (such as "if the maximal message length
in an application is 2^m and the maximal number of nonce repetitions is R,
then the maximal number of messages that can be encrypted with the same key
can be pushed to XXX") are likely to create confusion and incur
implementations errors. For AES-GCM-SIV with randomly generated nonces
(which has been put forward by the designers as the preferred way of
generating nonces when no state can be saved by encrypting devices), this
means that no more than 2^{30} messages should be encrypted with the same
key, which contrasts with the recommended limit of 2^{50} given (without
context) in Section 9 of the CFRG specification and in the abstract of [2].

Cheers,
Tetsu and Yannick.

[1] https://eprint.iacr.org/2015/102
[2] https://eprint.iacr.org/2017/168

2017-07-17 4:09 GMT+02:00 Adam Langley <agl@imperialviolet.org>:

> Dear CFRG,
>
> We would like to thank Yannick Seurin and Tetsu Iwata for alerting us
> to the fact that we had erroneously assumed that one of the terms in
> the security bounds of AES-GCM-SIV was negligible when, for
> indistinguishability, it was not. Thus, while the security proof was
> correct, the example concrete bounds were over optimistic, most
> notably for very large messages. This was most evident in Fig 4.
>
> We have updated the paper[1] to correct this mistake and we draw the
> group's attention to the revised figure four (now called Table 1). For
> typical uses, thankfully, the difference is not material but for we
> wish to highlight that one cannot encrypt many messages of
> many-gigabytes using AES-GCM-SIV, in contrast to what the figures
> previously suggested. However, even in such a case of very long
> messages, the overall number of blocks encrypted safely is still
> significantly higher than previous schemes.
>
> [1] https://eprint.iacr.org/2017/168
>
>
> Cheers
>
> AGL
>
> --
> Adam Langley agl@imperialviolet.org https://www.imperialviolet.org
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>