Re: [Cfrg] OPAQUE responses (PAKE Selection Process: Round 2, Stage 2)

"Stanislav V. Smyshlyaev" <> Mon, 10 February 2020 16:24 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id BAEA9120855; Mon, 10 Feb 2020 08:24:19 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.997
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: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id h3YcRDz43kYQ; Mon, 10 Feb 2020 08:24:16 -0800 (PST)
Received: from ( [IPv6:2a00:1450:4864:20::133]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 8EFFE120853; Mon, 10 Feb 2020 08:24:15 -0800 (PST)
Received: by with SMTP id l18so4634458lfc.1; Mon, 10 Feb 2020 08:24:15 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=IBLCsEfByyD/GQx9itQQyWsi/waAUzsgyZmzT9qsUNE=; b=F4qLJLIJkxO8lmlqwKd3zob5yh4KLceJ3L1/yg2T2cTppMa1OGuykHs5TC6k1+HYmH 1ezsv2iDxzwf5QRsp5XJhX7D5d33Wq2D/udKrkK2KqO8frjEF5Uu/kMIjuhh0Ug9e7fS IQko66CYpbSDq3j0SeLf4REH4WrvOY00iTThAkadO2KxKEHtNHikEdWSQheDSfjr1Zab HbN67Dxej2wM+MASZzvz/nBY6NzdHIsoOuDneFtw+kCeHdSoToqfI7ejitYYUpTlZL2l Df7odU8SnOQNUEGcyqhNStH/+pftYX8OoKxFWaAzvU2/UHqdD0A6vDdlgKl1hp0QkWeQ juVw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=IBLCsEfByyD/GQx9itQQyWsi/waAUzsgyZmzT9qsUNE=; b=RfTVCqIBcmu8M9ogd3AWdIw5W+sS1UCboDt8JEXM9mOjH7CIKzAlAKORVFQX2tDCVR BINrANiTPP5GLwi7geEwGQ7PiCOtkFHTUNfx0videLRLYwjEAruqhABhBjTFflF35krh 4hGASOdSgaF+q0NzyXw/vbWENB8OeOWMJ3/r1MGzT7MO5ro0CVLi5cqXtEIr80mwA1g1 7iRAgWVxR+redYeqdvCoLi9BwhJ+3lgkIxJaavY+iB422edQi/DX8IK6/rfJbSgpGRvC nED0C4fjloJgte5FCbHUddj08ogavp4Da8GBfD7LVNNEEuRVppEXRhlz0DgXMeDjj+um OxSA==
X-Gm-Message-State: APjAAAUAY5B5j++btQdoXicl90Yd5gOcE2epN/nwV/NrNLOgNTvg9QKm eKenTezsZMyz7jPWby03mGEtT/cHZYxKqxFeJgk=
X-Google-Smtp-Source: APXvYqxjK1LKMKnqR434E8EZ7GiQaNSBok9Kym2YsGlH7mTDfZmpHwcZ4fB3l09rRtv25N7d89jjVbS17H0y1E/+8BU=
X-Received: by 2002:a19:6449:: with SMTP id b9mr1151960lfj.5.1581351853276; Mon, 10 Feb 2020 08:24:13 -0800 (PST)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: "Stanislav V. Smyshlyaev" <>
Date: Mon, 10 Feb 2020 19:24:02 +0300
Message-ID: <>
To: Hugo Krawczyk <>
Cc: CFRG <>,, "" <>
Content-Type: multipart/alternative; boundary="0000000000007ac25f059e3b2b98"
Archived-At: <>
Subject: Re: [Cfrg] OPAQUE responses (PAKE Selection Process: Round 2, Stage 2)
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 10 Feb 2020 16:24:27 -0000

Many thanks, Hugo!

пн, 10 февр. 2020 г. в 19:22, Hugo Krawczyk <>:

> 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
> 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
> 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
> work in 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
> 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
> 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:
> 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
> schemes will reach the performance we need for the fully-PQ operation of
> 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
> (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
> 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
> 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