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

From: Jonathan Trostle <[email-masked]>
Date: Thu, 27 Jul 2017 14:39:41 +0000 (UTC)

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

 Subject: Re: [Cfrg] Updated bounds in AES-GCM-SIV paper
 To: [email-masked]
 Cc: "Tetsu Iwata" <[email-masked]>
 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 <[email-masked]>:
 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 [email-masked]
 https://www.imperialviolet.org

 ______________________________ _________________
 
 Cfrg mailing list
 
 [email-masked]
 
 https://www.irtf.org/mailman/l
 istinfo/cfrg

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