Re: [Cfrg] A standard for committing authenticated encryption

Paul Grubbs <pag225@cornell.edu> Tue, 12 November 2019 16:36 UTC

Return-Path: <pag225@cornell.edu>
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 780C312006E for <cfrg@ietfa.amsl.com>; Tue, 12 Nov 2019 08:36:28 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=cornell.edu
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 rUQ0HM992ZsK for <cfrg@ietfa.amsl.com>; Tue, 12 Nov 2019 08:36:25 -0800 (PST)
Received: from mail-il1-x12a.google.com (mail-il1-x12a.google.com [IPv6:2607:f8b0:4864:20::12a]) (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 2D960120108 for <cfrg@irtf.org>; Tue, 12 Nov 2019 08:36:25 -0800 (PST)
Received: by mail-il1-x12a.google.com with SMTP id m5so16138805ilq.0 for <cfrg@irtf.org>; Tue, 12 Nov 2019 08:36:25 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=cornell.edu; s=g.20171207; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=CFO1j1kBaml8SqdB/1VoNJfiMAvrPr+IccYWnqxXEAE=; b=AJOv/AmaWFL9gHEMZzHCEtwfNcUKEkeknt+RB/FEBXV3fbOHMMcLw17xz8Zv8y0TBg xtHSi3+14BkJ0i5beqk5IGIEd6205zLHLZ2yDVby53xxxOacUan6GrhXxZseVZIBHoya LplavV7KFQE4wWX29bTtUutciz1REQVQmDj2fzr8bxjhVjq4q1G7VSU4TN1Nnf1jbzC3 TZsR5LlgkOorC88Ngc42dSaxtDqyI6ywW2OretF+yhe4nC8BWmEwqmkQ9UbETXqAoI/V 8Tyn/ej0mhuj68HY84RVdxdSDiGRHBKIWu7FjkN2OJ7k9uuMrHxyk37QYeyEr5xuwsK2 tJUQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=CFO1j1kBaml8SqdB/1VoNJfiMAvrPr+IccYWnqxXEAE=; b=lRT9VCAc/SPbNRbtvpCzJZGdgXYQ2f9Ls8gCOg2M7/8v5/xObJK/35HPdqxsOxCC58 J0NUUe/LP9SCVnNTnT/LSFYGcUZoC1qoD9zkAbjC52JuPvPLAdc3HVxPbIarvKsCJxDW XR0DGk+unpFdA+REaI8Eh3tDBUQ6bzSMVM5lo2l+V+7XFdiPp0YjRHgspNErauMyy4AT KbdvpEBiZrUSkV4Ncv6Kul8NG93muZhDVNj4NYnLTOKWLa92JajrVaPXQ2/GvTofn3dY Vsi96t/GLOdZZ2oEa/m7jkzRfV4ife9mG//sQ69nN8f2IWnjop5Y1p2hc2l+mtv2unrw EXyw==
X-Gm-Message-State: APjAAAWGrlUE+XyMDJZaxkRyhB5pm2D5EWAfITQFfzvz6ZGU8xWj6QPo zBBxrhkVaaMIAdGphFvcEL0G0qavneJRZTgf2IXfjw==
X-Google-Smtp-Source: APXvYqw+l1Q4c22Jl+QAGFK+5KJ5uMtvcLqbtXaLmS+FtkByXlFDFndqzH5hdmWj/GnKzVmj503ApWCQ6q3gIaneM6k=
X-Received: by 2002:a92:3b0c:: with SMTP id i12mr35309503ila.190.1573576584221; Tue, 12 Nov 2019 08:36:24 -0800 (PST)
MIME-Version: 1.0
References: <CAKDPBw_Vew+hc4mb49BeMaxG8a-Tu1GcHq5XtWKyE0rsu=uZ5Q@mail.gmail.com> <CAMvzKsgDo+mpAuWEKyk_gadr7kzUw1-HWQbv1JmXqPHY4aMSSA@mail.gmail.com>
In-Reply-To: <CAMvzKsgDo+mpAuWEKyk_gadr7kzUw1-HWQbv1JmXqPHY4aMSSA@mail.gmail.com>
From: Paul Grubbs <pag225@cornell.edu>
Date: Tue, 12 Nov 2019 11:36:12 -0500
Message-ID: <CAKDPBw-=gGi3MCLqyOSgGYU-gKcPPxPLCBYMRj4MVPbLRmXZ0w@mail.gmail.com>
To: Yevgeniy Dodis <dodis@cs.nyu.edu>
Cc: cfrg@irtf.org
Content-Type: multipart/alternative; boundary="0000000000005473d9059728d903"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/VrmR0rNGqg8RS787WFYFAETaZ2c>
Subject: Re: [Cfrg] A standard for committing authenticated encryption
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
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: Tue, 12 Nov 2019 16:36:28 -0000

Thanks Yevgeniy! Yes, our "Invisible Salamanders" paper shows
collision-resistant hashing is required if one wants commitments to be
small. This doesn't necessarily imply a huge efficiency penalty over what
is currently used, though - for example, Signal's AEAD (CBC-then-HMAC)
already uses collision-resistant hashing. Also, SHA256 instructions are
increasingly available in new CPUs, which will make collision resistance
cheaper still. Without the need for small commitments, cAE can be nearly as
efficient as GCM, but with a different set of tradeoffs.

(Incidentally, these kinds of subtleties are exactly why I think an RFC is
sorely needed!)


On Mon, Nov 11, 2019 at 7:11 PM Yevgeniy Dodis <dodis@cs.nyu.edu>; wrote:

> I am highly biased, but I think the idea is fantastic. I will be happy to
> participate in this if you guys decide to go ahead...
>
> Of course, to be upfront, one needs to understand that cAE requires some
> use of collision-resistant hashing. So, in
> terms of current implementations, could be close to an order of magnitude
> slower than encrypt-then-MAC or OCB
> schemes based on only a block cipher (e.g., AES).
>
> So this might not be for everybody if speed in concerned. But a clear
> standard, with appropriate warnings (more secure,
> wider applicability, but potentially slower), seems like a great idea.
>
> Yevgeniy
>
> On Mon, Nov 11, 2019 at 6:57 PM Paul Grubbs <pag225@cornell.edu>; wrote:
>
>> Hello all,
>>
>> A 'committing' authenticated encryption (cAE) scheme is one for which it
>> is hard to find a ciphertext having multiple correct decryption keys.*
>> More formally, a cAE scheme's ciphertexts are binding commitments. AE
>> security of a scheme does not imply its ciphertexts are binding
>> commitments, and widely-used AE schemes like Galois/Counter Mode and
>> two-key encrypt-then-MAC are not cAE [1]. This has already led to attacks
>> on already-deployed protocols like message franking [2]; cAE is also needed
>> in protocols like OPAQUE [3, 4] that may soon be standardized and deployed,
>> and is useful elsewhere (e.g., group messaging/MLS).
>>
>> Though cAE is needed in practice, there is no standards document
>> explaining cAE and defining secure schemes. I think such a document would
>> be really helpful to researchers and practitioners alike, so I'd like to
>> initiate some discussion in the mailing list ahead of the CFRG meeting at
>> IETF 106 next week, where hopefully Nick will present a few slides to get
>> people thinking about cAE.
>>
>> Right now, I'd really like to know whether people think this is needed or
>> useful, and what they'd like to see out of an eventual RFC. Also, if you've
>> ever needed committing AE or have encountered a setting where encryption
>> keys and/or ciphertexts can be adversarially chosen, I'd love to hear about
>> it.
>>
>> Thanks everybody!
>>
>>
>> *Some prior work [5] calls this and other similar properties
>> 'robustness'. Since 'robust' is already an overloaded term in cryptography,
>> I prefer 'committing'.
>>
>> [1] Message Franking via Committing Authenticated Encryption (
>> https://eprint.iacr.org/2017/664)
>> [2] Fast Message Franking: From Invisible Salamanders to Encryptment (
>> https://eprint.iacr.org/2019/016.pdf)
>> [3] OPAQUE draft (
>> https://tools.ietf.org/html/draft-krawczyk-cfrg-opaque-03)
>> [4] OPAQUE in TLS draft (
>> https://tools.ietf.org/html/draft-sullivan-tls-opaque-00)
>> [5] Security of Symmetric Primitives under Incorrect Usage of Keys (
>> https://eprint.iacr.org/2017/288)
>> _______________________________________________
>> Cfrg mailing list
>> Cfrg@irtf.org
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
>