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

From: Hugo Krawczyk <[email-masked]>
Date: Mon, 10 Feb 2020 11:22:07 -0500

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.

---

From: "Stanislav V. Smyshlyaev" <[email-masked]>
Date: Mon, 10 Feb 2020 19:24:02 +0300

Many thanks, Hugo!

пн, 10 февр. 2020 г. в 19:22, Hugo Krawczyk <[email-masked]>:

> that will break DH-OPRF), and that is ALL we need to have a fully-PQ OPAQUE