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

[2] incorrectly states that the only fully nonce misuse-resistant AE schemes submitted to Caesar were Julius, AEZ, and HS1-SIV. CMCC is also fully nonce misuse-resistant.

Jonathan

--------------------------------------------
On Wed, 7/26/17, Yannick Seurin <yannick.seurin@gmail.com> wrote:

 Subject: Re: [Cfrg] Updated bounds in AES-GCM-SIV paper
 To: cfrg@ietf.org
 Cc: "Tetsu Iwata" <iwata@cse.nagoya-u.ac.jp>
 Date: Wednesday, July 26, 2017, 5:04 AM

 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/1
 68

 Cheers

 AGL

 --

 Adam Langley agl@imperialviolet.org
 https://www.imperialviolet.org

 ______________________________ _________________

 Cfrg mailing list

 Cfrg@irtf.org

 https://www.irtf.org/mailman/l
 istinfo/cfrg

 _______________________________________________
 Cfrg mailing list
 Cfrg@irtf.org
 https://www.irtf.org/mailman/listinfo/cfrg

 -----Inline Attachment Follows-----