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

Yannick Seurin <yannick.seurin@gmail.com> Wed, 26 July 2017 12:04 UTC

Return-Path: <yannick.seurin@gmail.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 41D9A126E3A for <cfrg@ietfa.amsl.com>; Wed, 26 Jul 2017 05:04:58 -0700 (PDT)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id kg43EQi0JaY0 for <cfrg@ietfa.amsl.com>; Wed, 26 Jul 2017 05:04:55 -0700 (PDT)
Received: from mail-yw0-x22e.google.com (mail-yw0-x22e.google.com [IPv6:2607:f8b0:4002:c05::22e]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 66DEA131C7A for <cfrg@ietf.org>; Wed, 26 Jul 2017 05:04:55 -0700 (PDT)
Received: by mail-yw0-x22e.google.com with SMTP id u207so24569585ywc.3 for <cfrg@ietf.org>; Wed, 26 Jul 2017 05:04:55 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=zf7R6IRnXtKPJXQ2AFrSLpjOZuAIOCcdcoN3Qu8L1qk=; b=SRMqGmBiCfqNefbX4O/nNcIIUJEHqdQRQfEJ3t3DiVvjHdLgykUN6Drm4PMW/NfD3m cHJEzvosZo/tYhbMmkKg8jb7QT/NSmfLIZZIdz5dXNd6xqhyT3KwGeCR9V75/7m4D1bu I2XNhm0WNeG7MXTT9afnwm5J3bLJiYRIHSvjbH5y66Js9ge6Wngh9m3idZnLqkYSOLOF bnoLQ9g7wl3YtwZZuuYpjMRCYPSrQ1/cdeXntOQQ1WhLGcBci/ctoucIee/54IIPqv1e f7GBbqgTKn0MznfUUpOjnE8wVXNdZU8CjsQdXFmPuv4cIZYIMBmaI9mUBFsrkoq+ho16 1HqA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=zf7R6IRnXtKPJXQ2AFrSLpjOZuAIOCcdcoN3Qu8L1qk=; b=a7lPP0sF4OPT1q8Oe4jhi7w9pcAaubd4HEDzqvIChC9Us4MFfqj3F3Glde4za2QS4C zmLhV9wBsAygOIFL7k9MaGqAAcXsnWCdX0PWSVb8+WsUPd8aVQmc7/CuDlpTRVqoBQBj M5OUpx/4t+6U2DpQrcOdJTTMsPBMt19tkD4sTUV22/FEwWlkLWDYqgaJA35gzMxARQZ1 HuNoJticyqIwed0Ih3AIY3NtjTZVWAlX5ordDdsryxRpLuAVTsc5mFUwaeuTFbeb0ofi ph6RWUJO8YIg68OnD18DompkQb0iDdVSxdGNGTnQqKQGql+7/Vxuh7XtPjRstrx3Qc1T 7yxQ==
X-Gm-Message-State: AIVw111oVadedvDBe8qV7Er7TxE50xp65t3A1xb/NJPVP27AVj4t0zu1 KFTNiNNZXs1BGmy5JxHiFrowo9EmyTGhx+s=
X-Received: by 10.37.206.9 with SMTP id x9mr563933ybe.79.1501070694224; Wed, 26 Jul 2017 05:04:54 -0700 (PDT)
MIME-Version: 1.0
Received: by 10.37.91.7 with HTTP; Wed, 26 Jul 2017 05:04:23 -0700 (PDT)
In-Reply-To: <CAMfhd9UOFNfqoEp31r2moVaEfQZoeppP7h2Anrz0BBP518SeYA@mail.gmail.com>
References: <CAMfhd9UOFNfqoEp31r2moVaEfQZoeppP7h2Anrz0BBP518SeYA@mail.gmail.com>
From: Yannick Seurin <yannick.seurin@gmail.com>
Date: Wed, 26 Jul 2017 14:04:23 +0200
Message-ID: <CAOOV4XvpdCuEc8s5iXr3mzxuCTXj63AP6wATriu=D3Dxs3zz4Q@mail.gmail.com>
To: cfrg@ietf.org
Cc: Tetsu Iwata <iwata@cse.nagoya-u.ac.jp>
Content-Type: multipart/alternative; boundary="94eb2c190112831eac0555374180"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JHB3l9CpENIIsoFLZlXH9yOypsM>
Subject: Re: [Cfrg] Updated bounds in AES-GCM-SIV paper
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Wed, 26 Jul 2017 12:04:58 -0000

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>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, 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 agl@imperialviolet.org https://www.imperialviolet.org
>
> _______________________________________________
> Cfrg mailing list
> Cfrg@irtf.org
> https://www.irtf.org/mailman/listinfo/cfrg
>