[Cfrg] OPAQUE responses (PAKE Selection Process: Round 2, Stage 2)
Hugo Krawczyk <hugokraw@gmail.com> Mon, 10 February 2020 16:22 UTC
Return-Path: <hugokraw@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 0F4FC120839 for <cfrg@ietfa.amsl.com>; Mon, 10 Feb 2020 08:22:37 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.997
X-Spam-Level:
X-Spam-Status: No, score=-1.997 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_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=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 GFol60ERs0O8 for <cfrg@ietfa.amsl.com>; Mon, 10 Feb 2020 08:22:33 -0800 (PST)
Received: from mail-il1-x132.google.com (mail-il1-x132.google.com [IPv6:2607:f8b0:4864:20::132]) (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 A50F412084E for <cfrg@irtf.org>; Mon, 10 Feb 2020 08:22:33 -0800 (PST)
Received: by mail-il1-x132.google.com with SMTP id f5so715868ilq.5 for <cfrg@irtf.org>; Mon, 10 Feb 2020 08:22:33 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to; bh=x7LDFSIBR+0YNm7pEKauM9oqTGQoPpam5o9XEWyU+g8=; b=tRJwNvXpDJ+MNNyOhymf6BARxy9RzgFdlU8x9qdCpi0qMzFgSbtoGi/5ZziyMYoiVS d14JJuBGhtaBVDApD2XwudHBN+xGKOeEIr/Ci3dbUrfWlak5CcKb37PBOmub/GvP/Wkk fxD0ifCc4Y07xr6kuRRG/t0m2VnTCeqBu/XMjBeDDjKH8p0shOi5m8oIypQii2x2l9cd jIaWxxZ8ZqR+Kgp/wG71Tzd8y7auuv9vWbb8wj7qjtbKkOGbJf/1X8+QFb+VD32pvHqZ wAhXo657HlEd8++gc8r/B73/5XKvIkLqNtUbTs1rO0PLi3OXuEzh7TegBgxqzpA9nG8E QW7A==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=x7LDFSIBR+0YNm7pEKauM9oqTGQoPpam5o9XEWyU+g8=; b=OA1He2Fyo2PXqKGJd3+AB8ij5ZrPcgFavvhUc9rW9i4KMG52TOD/xnJcsZ3oa+zy4o 89yGOsgnwWGca4BafaZm+6o20GQiZrCjb2QqyIA++qLaKS7oSVi21kg7X/qqjLX4fHxU LJXB0cZF8iFdPSODp/BJt0DhfRpcwPi+kGPOeYYy2rs73YubeDyqEpY5eQ1yhrkw5UCu pJU3NxUpJK2EwAgwQvC8ZCPZr2B/Q8rKorVTllULYnZdc7TC7RQEsOcwJ/wlHJSubZXJ vCkJ1SuZZHMgpu1fEk2Yk81/mK6Ykn5ol1Oat4vjGCE7sZE5CrmnNYoe+Ll1ognLPFX/ Jlpg==
X-Gm-Message-State: APjAAAUOgf6oxPY8lVgGe7mh4ERRz6Aq8NLoXAsTwtlYkXA5/rSG0luJ 1C+XxWpOc2EbE0Q9XPLE8r4bnSGUMlWF0jVm8ehsJw==
X-Google-Smtp-Source: APXvYqwyXaN1VdEpeBwY0WdIb+BUXlMOl7oMPyNNcTzTd30DrTgNM+64Rv+g5T4sYnl87SK2sgrYa/WqZem8SA62qbU=
X-Received: by 2002:a05:6e02:1014:: with SMTP id n20mr2148272ilj.172.1581351752571; Mon, 10 Feb 2020 08:22:32 -0800 (PST)
MIME-Version: 1.0
From: Hugo Krawczyk <hugokraw@gmail.com>
Date: Mon, 10 Feb 2020 11:22:07 -0500
Message-ID: <CADi0yUPrbWwoyHhz8z_-fVNP=3OzsM0OMRR4e30KSamDa0yUTg@mail.gmail.com>
To: CFRG <cfrg@irtf.org>, cfrg-chairs@ietf.org
Content-Type: multipart/alternative; boundary="0000000000007a28c0059e3b2599"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/EJnaKEh_RamzghcjAik5v9_Fwf8>
Subject: [Cfrg] OPAQUE responses (PAKE Selection Process: Round 2, Stage 2)
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: Mon, 10 Feb 2020 16:22:43 -0000
Dear Stanislav and the CFRG selection committee, Below are answers to the questions you posed for OPAQUE. Let me know if you need more information at this time. As a reminder, our analysis paper is in https://eprint.iacr.org/2018/163.pdf At the end of the introduction you can find several notes explaining the revisions we did since the time we initially submitted OPAQUE to this selection process. Some of the important revisions were motivated by the excellent feedback from this committee (especially Bjorn and Julia). We are truly grateful for that. The protocol itself has not changed except for noting that the (full) PFS requirement for the key exchange component (AKE) eliminates the option of a 2-message protocol (see my email to cfrg from 11/18/2019). This does not change the analysis of OPAQUE performed by the TLS and IKE teams. The current internet draft (revision 03) is in https://datatracker.ietf.org/doc/draft-krawczyk-cfrg-opaque/ It is intended as a high level description of the protocol built in a modular way based on three components: OPRF, Authenticated Encryption, and AKE. The draft is purposely light in implementation details. These details will emerge through CFRG input as well as via our work on implementation planned to start very soon in collaboration with a group of IETF and TLS 1.3 experts. We expect to build on existing tools and specifications, particularly the OPRF work in https://tools.ietf.org/html/draft-irtf-cfrg-voprf-02 and AKE specifications borrowed from TLS 1.3. See also response to question (3) below. The only module currently lacking a standardized specification is the key-committing authenticated encryption required for building the OPAQUE envelope. Several simple options are listed in the OPAQUE draft, one of which will be chosen for specification and implementation. There is also the option of minimizing the size of envelope for communication-constrained scenarios. ================================ Question 3 (to all 4 remaining PAKEs): Can the nominators/developers of the protocols please re-evaluate possible IPR conflicts between their candidates protocols and own and foreign patents? OPAQUE can use any AKE (with KCI and PFS security) and therefore is not limited to any particular AKE protocol. The current OPAQUE internet draft illustrates the protocol using HMQV and SIGMA as the AKE component. HMQV is presented as the most efficient instantiation and SIGMA as the basis for integration with TLS 1.3 and IKEv2. Since HMQV is encumbered by an IBM-owned patent, the instantiation with HMQV cannot be standardized, at least for the moment (it can change if IBM agrees to donate the patent for royalty-free use within OPAQUE). The 3DH protocol (the basis of Signal) can serve as a drop-in replacement for HMQV as the only difference between the protocols is in the formula for the computation of the session key (which involves one extra exponentiation in 3DH). However, moving forward, OPAQUE specification and implementation will center around SIGMA as this is the way the protocol would be integrated with TLS 1.3 and IKEv2 (both of which build on SIGMA already). It is important to note that any asymmetric PAKE requires a mechanism that will protect user account information and a data channel protocol for transmitting data protected under the shared session key. It makes no sense to re-invent any of these mechanisms rather than using established and standardized protocols like TLS or IKE/IPsec. Furthermore, when run inside TLS 1.3 (similarly for IKEv2), the cost of OPAQUE-SIGMA-ECDSA is virtually the same as with HMQV (just one extra fixed-base exponentiation for server and client). In comparison to Strong AuCPace, OPAQUE-SIGMA-ECDSA is more efficient in terms of exponentiations and number of messages. The latter is particularly advantageous for integration with TLS 1.3. An additional performance advantage of OPAQUE is that the DH exchange in TLS and IKE is re-used in OPAQUE while for AuCPace it represents an additional cost (one fixed and one variable exponentiation for client and server). The favorable performance cost of OPAQUE when integrated with TLS, in terms of number of messages and exponentiations, holds also with respect to non-strong AuCPace. The size of the OPAQUE envelope can be minimized in settings where server storage and/or communication are scarce resources. ============================================== Question 5 (to all 4 remaining PAKEs): What can be said about "post-quantum preparedness" of the PAKE? I have already expressed my opinion that post-quantum-preparedness is a much more important property than "quantum annoyance" in this posting from 10/27/2019: https://mailarchive.ietf.org/arch/browse/cfrg/?q=Quantum%20annoyance%20vs%20post-quantum%20preparedness Thus, I will first refer to the really important question: Post-Quantum (PQ) preparedness. OPAQUE seems to be the only candidate among all CFRG proposals that could be implemented today with a full PQ design, albeit not a very efficient one. Indeed, one can take any PQ PKE submission to NIST's competition and generate a PQ AKE with the properties of forward secrecy and KCI required by OPAQUE [1]. As for the OPRF, we already have candidate PQ instantiations of this primitive [2,3] though not efficient enough for current deployment. However, note that even if the OPRF is not PQ but the AKE is (e.g., when TLS, or other settings where OPAQUE is used, adopts a PQ AKE), data will remain secure even if the OPRF is fully broken in the future. This is similar to the situation with digital signatures used in TLS 1.3. Breaking them in the future has no bearing on data protected under keys authenticated with these signatures. One difference is that breaking the DH-OPRF in the future would enable a dictionary attack on the user's password as used in the past (say, 10-20 years earlier). However, once TLS moves to PQ AKE (before that all data will be vulnerable, with and without OPAQUE), this attack will be limited to active attackers. Namely, only attackers that actively impersonated a user in an OPAQUE session with the old OPRF may be able to attack the password in the future. In other words, to learn today's password in 10-20 years, an attacker needs to impersonate the user now, hope that in 10-20 years it will have a machine that solves discrete log, and if all of that happens, it will have the chance to find the 20-year old password through an exhaustive dictionary attack. (We already have honest-but-curious attackers in cryptography; this one will qualify as wasteful-and-very-curious.) I believe it is a very reasonable expectation (see below) that long before we build a quantum computer capable of breaking today's elliptic curves, PQ OPRF schemes will reach the performance we need for the fully-PQ operation of OPAQUE. Given the increasing applications for OPRFs we can expect to see such schemes in just a few years. I am not sure one can say anything like this for the other PAKE candidates where completely new PQ PAKE schemes may need to be invented. References: [1] Kathrin Hövelmanns, Eike Kiltz, Sven Schäge, Dominique Unruh Generic Authenticated Key Exchange in the Quantum Random Oracle Model https://eprint.iacr.org/2018/928 (They show how to build PQ AKE from PQ PKE in the ROM). [2] Martin R. Albrecht, Alex Davidson, Amit Deo, Nigel P. Smart Round-optimal Verifiable Oblivious Pseudorandom Functions From Ideal Lattices https://eprint.iacr.org/2019/1271 The above paper builds a PQ OPRF from lattices. It is not efficient enough for the OPAQUE purposes, particularly as it is optimized for cases where one applies the OPRF with the same OPRF key on multiple inputs which is not the OPAQUE case. But it is very good progress. Also, it tackles the harder problem of *verifiable* OPRF while OPAQUE does not need the verifiability property. [3] Jonathan Katz, Samuel Ranellucci, Mike Rosulek, Xiao Wang Optimizing Authenticated Garbling for Faster Secure Two-Party Computation https://eprint.iacr.org/2018/578.pdf The above paper, as many others in this area, shows how to do secure two-party computation and reports on performance when the computed function is AES. More specifically, in this setting one party (call it a server) holds a AES key K while a client has an input x. The client learns AES(K,x) and nothing else. The server learns nothing. This is exactly the OPRF setting. Is the scheme in the paper PQ secure? It is if one uses AES for Yao's garbling and uses lattice-based oblivious transfer. Are we done then? Not really, because, as above, this results in a not-very-efficient scheme (particularly in terms of communication). But again, it is significant progress towards finding a practical PQ OPRF. Note: In addition to performance issues, one will probably need to adapt the above constructions to the UC setting in which OPAQUE is analyzed (e.g., the user will need to apply a hash function on top of the AES(K,x) result). These are important details but the point is to demonstrate that we have some good reasons to believe that an efficient enough PQ OPRF is expected to be built in the not-too-far future (probably much much sooner than the quantum computer that will break DH-OPRF), and that is ALL we need to have a fully-PQ OPAQUE. No other change to OPAQUE will be needed. ============================================== Question 4 (to all 4 remaining PAKEs): What can be said about the property of "quantum annoyance" (an attacker with a quantum computer needs to solve [one or more] DLP per password guess) of the PAKE? I wrote an extensive message to CFRG on 10/27/2019 under the subject "Quantum annoyance vs post-quantum preparedness" (see link above) where I discuss the significance of Quantum Annoyance (QA) vs that of "Post-quantum preparedness". It is true that OPAQUE does not fare well in the QA setting. An attacker that breaks dlog can mount an exhaustive dictionary attack on user's password. A single dlog solution per user suffices. But as explained above while a dlog attack may compromise a 10-20 year old password, data remains secure assuming a PQ AKE is adopted (before that, all TLS communications, with and without PAKE, would be broken with a machine solving dlog instances). Also as said above, this attack will only be possible against users actively impersonated by the attacker at the time the target password was still in use. Bottom line: QA may be one way to compare between protocols that do not offer a good transition to PQ security which is not the case for OPAQUE. PQ preparedness as discussed above should be the real consideration.
- [Cfrg] OPAQUE responses (PAKE Selection Process: … Hugo Krawczyk
- Re: [Cfrg] OPAQUE responses (PAKE Selection Proce… Stanislav V. Smyshlyaev