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

From: Adam Langley <[email-masked]>
Date: Sun, 16 Jul 2017 19:09:20 -0700

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 [email-masked] https://www.imperialviolet.org

---

From: Yannick Seurin <[email-masked]>
Date: Wed, 26 Jul 2017 14:04:23 +0200

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

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

---

From: "Paterson, Kenny" <[email-masked]>
Date: Wed, 26 Jul 2017 20:56:52 +0000

Dear Tetsu and Yannick,

Many thanks for performing this thorough security analysis of AES-GCM-SIV.
Your contribution to the process is an important and timely one as the
document describing this scheme progresses towards its final form in CFRG.

I trust that the authors of draft-irtf-cfrg-gcmsiv will carefully update
their text in the light of this new analysis.

Adam, Shay, Yehuda: could you also please give due consideration to Tetsu
and Yannick's proposal for an alternative key-derivation function?

Many thanks,

Kenny (for the chairs)

On 26/07/2017 13:04, "Cfrg on behalf of Yannick Seurin"
<[email-masked] on behalf of [email-masked]> wrote:

>Dear CFRG,
>
>
>Our paper "Reconsidering the Security Bound of AES-GCM-SIV", which
>prompted Adam's email, is now available on ePrint:
>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.
>
>
>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.
>
>
>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
>(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.
>
>
>Adam Langley [email-masked]://www.imperialviolet.org
>

---

From: Adam Langley <[email-masked]>
Date: Wed, 26 Jul 2017 15:26:08 -0700

On Wed, Jul 26, 2017 at 5:04 AM, Yannick Seurin
<[email-masked]> wrote:
> 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].

While the maximal message length of AES-GCM-SIV is very large, we do
not think it useful to limit the total number of messages based on
it. Using such large messages is very rare (at best) and unwise with
any AEAD: large messages pressure consumers to process plaintext
before the whole message has been received and authenticated, because
buffering would be so costly.

We have just published -06, which contains updates in response to
several reviewer's feedback and also contains updated guidance
on the maximum number of messages for the case where the
maximum number of nonce repeats is 256 (which covers choosing nonces
randomly):

2^29 messages, where each plaintext is at most 1GiB
2^35 messages, where each plaintext is at most 128MiB
2^49 messages, where each plaintext is at most 1MiB
2^61 messages, where each plaintext is at most 16KiB

Cheers

AGL