Re: [Cfrg] Proposed PAKE Selection Process

[Hugo Krawczyk <[e-mail]>]

Hi Steve, thanks for pointing to this generic transformation from a regular
aPAKE to a Strong aPAKE (Strong aPAKE refers to aPAKE protocols secure
against pre-computation attacks). This transformation is indeed presented
and proved in the OPAQUE  paper
https://eprint.iacr.org/2018/163.pdf (section 4).
It consists of a first OPRF execution in which the user "exchanges" his
password pw for a random value rw and then uses this value rw as the
password in the given aPAKE protocol. Here is the intuitive explanation
from the paper:

First, the user transforms its password pw into a randomized value rw by
interacting with the server in an OPRF protocol where the user inputs pw
and the server inputs the OPRF key. Nothing is learned at the server about
pw (i.e., rw is indistinguishable from random as long as the input pw is
not queried as input to the OPRF). Next, the user sets rw as its password
in the given aPAKE protocol. Note that since the password rw is taken from
a pseudorandom set, then even if the size of this set is the same as the
original dictionary D from which pw was taken, the pseudorandom set is
unknown to the attacker (the attacker can only learn this set via OPRF
queries which require an online dictionary attack).  Thus, any previous
ability to run a pre-computation attack against the aPAKE protocol based on
dictionary D is now lost.

You suggest to apply this technique to SPAKE2+ which is fine but note that
no security proof has been claimed or published for SPAKE2+  as an aPAKE
protocol. Thus, even if the general transformation has been proven, it only
applies to aPAKE protocols that also have a proof of security.

In defining OPAQUE we used the second OPRF compiler in our paper, namely,
the one that composes the OPRF with any (KCI-secure) key exchange. This is
a better starting point as it does not require an aPAKE at all, and it can
use any of the many proven key exchange protocols. Moreover, one can use
existing deployed protocols such as TLS or IKE as the base KE which makes
integration of aPAKE with real-world protocols simpler. It also results in
more efficient protocols (e.g., if we take something like HMQV as your base
KE protocol).

Hugo

On Sun, Jun 30, 2019 at 7:45 PM <[e-mail]> wrote:

> Just making sure someone submitted "SPAKE2+EE with blind salt" or at least
> someone stated that you can add blind salt to almost any
> augmented/asymmetric PAKE. Blind salt is the interesting part of OPAQUE.
>
> I call "SPAKE2+EE with blind salt" BSPAKE because the name is getting long
> and has a misnomer with EE. Name is from (B)lind (S)alt PAKE or (B)lind
> salt (S)imple PAKE because it’s based off SPAKE2+, but it's not so simple
> any more. You can pronounce "BSPAKE" either "be es pake" or like bespoke
> but with an a "bespake".
>
> Brief history of BSPAKE:
>
> 1) SPAKE2+ adds "b*v*G" to SPAKE2 to make it an aPAKE.
>
> 2) SPAKE2+EE is the Elligator edition of SPAKE2+. For NIST P curves use
> SWU instead of Elligator. SPAKE2+EE changes the blinding factors x*N and
> y*M in SPAKE2+ to hashToPoint(x) and hashToPoint(y). This give it the
> property I call "quantum annoying". This property means that quantum
> computers need to solve a DLP for each password guess. For most other PAKEs
> one would only need to solve 1 or 2 DLPs and then get classical computer
> offline password cracking.
>
> 3) SPAKE2+EE with blind salt adds blind salt to SPAKE2+EE. Blind salt is
> the interesting property in OPAQUE. Where an attacker cannot precalculate
> password guesses. Once they gain access to the verifier, they could of
> quickly check all of those precalculated passwords, but is not the case
> with blind salt.
>
> ** Blind salt **
> C:    r = random()
> C:    R = H(password, C_id, S_id) ** r
> C->S: R
>    S: R' = R ** H(salt)
> C<-S: R'
> C:    BlindSalt = R' ** (1/r)
> BlindSalt == H(password, C_id, S_id) ** H(salt)
>
> Note H(salt) vs salt, this is so salt can be 128 to 256 bits and expanded
> to the necessary size.
>
> 4) I shorten the name "SPAKE2+EE with blind salt" to BSPAKE.
>
> ----
>
> ** BSPAKE (Note `hashToPoint()` is either Elligator or SWU depending on
> curve) **
>
> Both have:
>       G = generator
>       C_id = client identity
>       S_id = server identity
> Server has:
>       salt
>       settings
>       BlindC = hashToPoint(H(pwKey, clientModifier))
>       BlindS = hashToPoint(H(pwKey, serverModifier))
>       k3 = H(pwKey, key3Modifier)
>       V = H(pwKey, verifyModifier) * G
>
> C:    r = random()
> C:    R = r * hashToPoint(password, C_id, S_id)
> C->S: R
>    S: b = random()
>    S: B = b * G + BlindS
>    S: R' = H(salt) * R
> C<-S: B, R', settings
> C:    BlindSalt = (1/r) * R'
> C:    pwKey = pwKdf(password, BlindSalt, C_id, S_id, settings)
> C:    a = random()
> C:    A = a * G + hashToPoint(H(pwKey, clientModifier))
> C:    B' = B - hashToPoint(H(pwKey, serverModifier))
> C:    k3 = H(pwKey, key3Modifier)
> C:    vbG = H(pwKey, verifyModifier) * B'
> C:    K_c = H(C_id, S_id, A, B, a * B', k3, vbG)
> C->S: A, verifierC[, encryptedDataC]
>    S: A' = A - BlindC
>    S: K_s = H(C_id, S_id, A, B, b * A', k3, b * V)
> C<-S: verifierS[, encryptedDataS]
>
> The implementation of the password KDF to BlindC, BlindS, v*G, and k3
> doesn’t really matter besides v can't depend on BlindC, BlindS, or k3. To
> save bandwidth on set up (saves 2 ECC points), client operations on set up
> (saves 2 hash to point operations), and storage (saves storing 2 ECC
> points), one method is k | v = pwKdf(…) and send k, v*G. Then the server
> can do BlindC = hashToPoint(H(k, clientModifier)), BlindS =
> hashToPoint(H(k, serverModifier)), and k3 = H(k, key3Modifier) or k3 = k.
> The server can do that on the fly or store BlindC, BlindS, and k3.
>
> Note on name "k3", it is from a SPAKE2 paper: `k1 | k2 | k3 = pwKdf(...)`
> k1 and k2 were the blinding factors: k1*N and k2*M. k3 was in the final
> KDF: H(C_id, S_id, A, B, a*b*G, k3). Or at least that's what I remembered.
>
>
> > Dear CFRG,
> >
> > We’re planning to start the main phase of PAKE selection process. This
> > proposal was developed by Stanislav Smyshlyaev with the support of the
> CFRG
> > chairs.
> >
> > In addition to helping drive this PAKE selection process, Stanislav has
> > been selected to the role of Secretary of the CFRG, a position that was
> > previously vacant.
> >
> > To be 100% sure that the process will be as transparent and effective as
> > possible, we would like to announce the proposed plan of handling the
> > process. If you have any concerns about the plan, please send them to the
> > chairs before 27.05.2019.
> >
> >
> >
> >
> > Step 1, 01.06.2019-30.06.2019:
> >
> > ·        Call for candidate protocols. Note: the chairs especially
> > encourage to nominate PAKEs that have been discussed in CFRG recently
> (the
> > list can be found in the slides from IETF 104 CFRG session
> > <
> https://www.ietf.org/proceedings/104/slides/slides-104-cfrg-pake-selection-01.pdf
> >;,
> > slide 9). Third Party nominations are encouraged.
> >
> > ·        Discussing the list of questions to be asked in addition to the
> > ones that are present in RFC 8125. Starting point for such list of
> > questions can be the questions gathered before IETF 104 (can be found in
> the
> > slides from IETF 104 CFRG session
> > <
> https://www.ietf.org/proceedings/104/slides/slides-104-cfrg-pake-selection-01.pdf
> >;,
> > slides 7-8).
> >
> > Step 2, 01.07.2019-19.07.2019:
> >
> > ·        The designers of the protocols (or persons who volunteered to
> push
> > them forward) prepare papers with:
> >
> > a.      expanded answers for all positions of RFC 8125;
> >
> > b.      their own opinions on additional questions selected at Step 1
> (they
> > could be incomplete in some sense – for example, a designer of a PAKE
> might
> > not be an expert in TLS and might not be able to reply how his PAKE can
> be
> > incorporated in TLS 1.3).
> >
> > IETF 105 meeting:
> >
> > ·        The chairs give a review of the progress with the process and
> make
> > corrections of plans.
> >
> > ·        The chairs enumerate questions (from the list that has been
> > prepared during Step 1) which should be considered by independent
> reviewers
> > before asking the Crypto Review Panel for reviews and analysis. For
> > instance, it will be important that experts from other WGs consider how
> > certain PAKEs fits into TLS 1.3, or into IoT devices.
> >
> > Further steps (subject to corrections after IETF 105 meeting).
> >
> > Step 3, 01.08.2019-15.08.2019:
> >
> > ·        Call for reviewers for the enumerated questions, which require
> > additional consideration.
> >
> > ·        Crypto Review Panel members start the process of verification of
> > security proofs of the candidates (Requirement 2 in RFC 8125).
> >
> > Step 4, 16.08.2019-15.09.2019:
> >
> > ·        The reviewers who volunteered at step 3 prepare their analysis
> > regarding the assigned questions.
> >
> > ·        Crypto Review Panel members are in the process of verification
> of
> > security proofs of the candidates (Requirement 2 in RFC 8125).
> >
> > Step 5, 16.09.2019-30.10.2019:
> >
> > ·        Crypto Review Panel members review all gathered materials on
> each
> > of the protocols to prepare the final list of verified answers to the
> > positions of RFC 8125 and all additional questions from the list that has
> > been prepared during Step 1.
> >
> > ·        If additional explanations are needed, Crypto Review Panel
> members
> > ask for them from the designers.
> >
> > ·        Crypto Review Panel members write overall reviews for all
> > candidate PAKEs, based on the materials that have been gathered and
> > verified.
> >
> > Step 6, 01.11.2019-16.11.2019:
> >
> > ·        CFRG chairs discuss the obtained reviews and make their
> > recommendations to CFRG (or convey to CFRG that they can’t make a
> > recommendation yet).
> >
> >  IETF 106 meeting:
> >
> > ·        The chairs give a review of the progress with the process and
> make
> > corrections of plans.
> >
> > ·        If everything is clear:
> >
> > o   one (or more) PAKEs are selected;
> >
> > o   the process with CFRG document “Recommendations for password-based
> > authenticated key establishment in IETF protocols” is initiated: all
> > practically important recommendations (parameter selection, protecting
> > implementations against side-channel attacks, handling of counters etc.)
> > must be given there;
> >
> > o   at this point documents on usage of selected PAKEs in TLS/IPsec/etc.
> > can be developed.
> >
> >
> > Best regards,
> > Nick on behalf of Stanislav, Kenny, and Alexey
>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>