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

["Stanislav V. Smyshlyaev" <[e-mail]>]

Many thanks, Hugo!

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

> 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