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

Jonathan Trostle <> Thu, 27 July 2017 14:43 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BC0CF1200C5 for <>; Thu, 27 Jul 2017 07:43:44 -0700 (PDT)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: 0.809
X-Spam-Status: No, score=0.809 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FORGED_MUA_MOZILLA=2.309, FREEMAIL_ENVFROM_END_DIGIT=0.25, FREEMAIL_FROM=0.001, FREEMAIL_REPLYTO_END_DIGIT=0.25, RCVD_IN_DNSWL_NONE=-0.0001, RP_MATCHES_RCVD=-0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=no autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id BYeoluUchfar for <>; Thu, 27 Jul 2017 07:43:43 -0700 (PDT)
Received: from ( []) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id E997D1317CC for <>; Thu, 27 Jul 2017 07:43:42 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=s2048; t=1501166622; bh=xyxh6/CwsHUAW0NlKH8wbyw1htULd9dthy1TVB9A83I=; h=Date:From:Reply-To:To:Cc:Subject:References:From:Subject; b=BmKNnKaU+4VGmj0b1zEVfwTmS8AQumATqbhRqiiHnoa1w8nHy8ZvAhXGsRHTRJBkzF3Y8Xvqt94JqhY6Tjd3ZGMTDzv0AoTBH98PwXklZe+4qEvGJNe53qOplHPqKsolHcFHgf2A+zDvh2AdR4NXYwBa3LkXS350zCuIz1yzHQlmtsMmpwVfaSadzVzd8fc5So1GSnLuImQasIIvTHOyTq7j+rK2zAUQt6S14v4QyeNfOpLbx504RaJKR1bm0rm3zpwRzQayuiLr1BK7lklTj9xCzPQTPOHA6IeoVZPOFknXlFBn3PNSe29fC50qoRQu+SkN9WkPm++Vsc6UQc1tfw==
X-YMail-OSG: 7pFz9g4VM1n8xRMsit.X1268zRG5MlyjrRr9JwXnXwvcJWIrEgmYTvOYFHVUUic uGUyV.rm7RmBpccABI_LA1CfkxRA7QpTMAPVNglaWBG956n4rjhzakksotgS5Ml5RINZVErHNd5Q 6XxiKs2HFX9uTFhO.XKU7OYdEtbL3w6MHfaLgGWja499RcnpXoYST.cd5hD3ZmQx3pk3fMsgUWK2 iDWZLpWzpWXN_4opC1A7Z8UmbwW7bzSqBWJtu_3a6eicCq_IpCeCZ0bT1AIu9NGhRbwVOYp16Aar KE56_wnSRiVpvdhIwVz_Uv8IkF2iHMJ_0HdY8QprDVJAod67prMs6cF0XHitak27gEFr9enuHdCg fhjwBQ_U5spLMgEB9IWEHIQQTopD9Jp1oXNqyuwxvohCICTKrSXUBeyLm1Cb3RyRAg8T22gcMGLL ofSH03Y5LIs.z585.RDVHaI0P.1w1EROcF4.DiRq5bShYxB0w84Cy3S7kwy4OXMLjXkKGf70_MFV T4gO2rNO0iEavXQEt5qpGLCChi9M7GxM5kyUL6teytjIv4GHLmQ--
Received: from by with HTTP; Thu, 27 Jul 2017 14:43:42 +0000
Date: Thu, 27 Jul 2017 14:39:41 +0000 (UTC)
From: Jonathan Trostle <>
Reply-To: Jonathan Trostle <>
To: <>, Yannick Seurin <>
Cc: Tetsu Iwata <>, <>
Message-ID: <>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable
References: <>
X-Mailer: WebService/1.1.10181 YahooMailBasic Mozilla/5.0 (Windows NT 6.1; WOW64; rv:54.0) Gecko/20100101 Firefox/54.0
Archived-At: <>
Subject: Re: [Cfrg] Updated bounds in AES-GCM-SIV paper
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 27 Jul 2017 14:43:45 -0000

[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.


On Wed, 7/26/17, Yannick Seurin <> wrote:

 Subject: Re: [Cfrg] Updated bounds in AES-GCM-SIV paper
 Cc: "Tetsu Iwata" <>
 Date: Wednesday, July 26, 2017, 5:04 AM
 Our paper
 "Reconsidering the Security Bound of AES-GCM-SIV",
 which prompted Adam's email, is now available on
 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.
 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
 2017-07-17 4:09 GMT+02:00
 Adam Langley <>rg>:
 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,
 indistinguishability, it was not. Thus, while the security
 proof was
 correct, the example concrete bounds were over optimistic,
 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
 many-gigabytes using AES-GCM-SIV, in contrast to what the
 previously suggested. However, even in such a case of very
 messages, the overall number of blocks encrypted safely is
 significantly higher than previous schemes.
 Adam Langley
 ______________________________ _________________
 Cfrg mailing list
 Cfrg mailing list
 -----Inline Attachment Follows-----