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

["Paterson, Kenny" <[e-mail]>]

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"
<[e-mail] on behalf of [e-mail]> wrote:

>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 <[e-mail]>:
>
>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 [e-mail]://www.imperialviolet.org
>
>_______________________________________________
>Cfrg mailing list
>[e-mail]
>https://www.irtf.org/mailman/listinfo/cfrg
>
>
>
>
>
>