Re: [Cfrg] aPAKE Analysis

[Hugo Krawczyk <[e-mail]>]

Jonathan, I have not looked into making OPAQUE quantum annoying. I assume
that one can do it with some password-based blinding but then it would be a
different protocol.  But OPAQUE is better in other important ways, both
with respect to a quantum future and present reality.

A main point in OPAQUE design (in addition to being secure against
pre-computation attacks and efficient) is its modularity. Namely, the
generic composition of *any* OPRF with *any* KCI authenticated key exchange
(AKE) protocol. In particular, it means that you can implement it with a PQ
AKE (as in NIST competition) and a PQ OPRF.

The latter seems to be missing from our current PQ arsenal but one will be
built much before quantum becomes a reality (more precisely we do have PQ
OPRFs, based on 2-party computation, but I am talking about more efficient
ones).

Once we have the PQ OPRF, OPAQUE is quantum READY (not sure you can say
that for other proposals, at least without specialized components and
analysis).

As for the task of building a PQ OPRF note that we do not really need an
Oblivious PRF but rather an Oblivious Weak Unpredictable function. That is,
a function whose output is hard to guess when computed on random inputs.
This is a much weaker primitive than full fledged PRF (the reason this
suffices for our purposes is that both input and output are processed by a
random oracle).

Hugo

On Tue, Sep 17, 2019 at 8:15 AM Jonathan Hoyland <[e-mail]>
wrote:

> Hi Steve,
>
> It's interesting what you say about OPAQUE not being quantum annoying.
> I initially thought it would be easy to tweak OPAQUE to make it so, but
> even after a some thought it's unclear to me that you can make OPAQUE
> quantum-annoying / quantum secure without substantive changes.
>
> Because of the AEAD/key committing requirement of the Envelope you can
> always verify a guess if you can derive the salt.
>
> I'm also not aware of any quantum alternatives to current OPRF
> constructions, so it's not obvious that you could just compile a
> quantum-secure variant.
>
> An attacker is still limited to one DLP solve per user, but after that
> it's classically brute-forcible.
>
> I'd be very interested what other people think of ways to make OPAQUE
> quantum annoying.
>
> BSPAKE is very similar to OPAQUE in structure so it's probably do-able
> with some thought.
>
> The issue with AuCPace is that it's complicated to bind to TLS without
> adding two round trips, but I'm sure the issues aren't insurmountable.
>
> Regards,
>
> Jonathan
>
> On Tue, 17 Sep 2019 at 07:21, <[e-mail]> wrote:
>
>> TL;DR AuCPace (with blind salt) is the best submitted algorithm, but
>> B-SPEKE (with blind salt), which was not submitted, might be better. Also
>> OPAQUE and VTBPEKE should not be used due to having bad properties and/or
>> not having good properties.
>>
>>
>> Good properties in an aPAKE: low complexity, low cost, not fragile,
>> prevents precomputation, quantum annoying, and minimal trips.
>>
>> * Fragile is you give an attacker offline password guessing if there is a
>> minor error in the implementation of ECC (CVE-2017-8932, Dragonblood,
>> timing attacks, etc).
>> * Quantum annoying is an attacker with a quantum computer needs to solve
>> a DLP per password guess.
>>
>> Hmm I found another property "forward secrecy" from a VTBPEKE paper, but
>> I can't find their definition. It's obviously not actual forward secrecy
>> since I know SPAKE2, SPEKE, SRP6a, and SPAKE2+ don't leak the session key
>> if the password is later known. Never mind found their definition and their
>> comparison chart is just wrong. Oh I think they by "no" they mean it wasn't
>> proven to have forward secrecy as part of the security proof.
>>
>> Augmented PAKE summary
>> Name    | PQ-ish | Trips*  | Precomp** | Fragile
>> --------+--------+---------+-----------+---------
>> AuCPace | Good   | 4 (2/3) | Bad       | Good
>> BSPAKE  | Good   | 4 (2/3) | Good      | Good
>> OPAQUE  | Bad    | 3 (2/1) | Good      | Bad
>> VTBPEKE | Bad    | 4 (2/3) | Bad       | Good
>>
>> Augmented PAKE summary (continued)
>> Name    | Client Cost          | Server Cost
>> --------+----------------------|------------------
>> AuCPace | ff*iH**[ii]          | **[ii]H*if*i
>> BSPAKE  | H*iffI*i*H+H-**[iii] | f**+[ii]f-**[ii]
>> OPAQUE  | H**[ii]ffI*ix*+*i    | ff**x*+*[iii]
>> VTBPEKE | *if*+**[iii]x        | *if*idi
>>
>> * "number of total trips" ("number of trips to client can
>> encrypt"/"number of trips to server can encrypt")
>> ** Preventing precomputation is a minor change. All you need to do is add
>> blind salt. AuCPace and VTBPEKE can add blind salt without any extra trips.
>> Also I just read that AuCPace has this as an option in a paper.
>>
>> Cost:
>> d: Double scalar point multiple and add "a * B + c * D"
>> *: Scalar point multiple
>> H: Hash to point
>> i: Field invert
>> I: Scalar invert
>> f: From bytes (field square root or free for Montgomery curves)
>> -: Point subtraction
>> +: Point addition
>> x: Field multiplication
>> [ii...]: Field inverts that can be combined. Cost is 1 field invert and
>> 3*(n-1) field multiplications.
>>
>> Note that trips for client/server to be authenticated is one more than
>> when they can encrypt because at that point they can also authenticate but
>> haven't.
>>
>> OPAQUE is fragile and not quantum annoying and thus the worst of the
>> four. Only good part is it needs fewer trips for the server to authenticate
>> and/or send encrypted data.
>>
>> OPAQUE (as stated in https://eprint.iacr.org/2018/163 figures 9 and 10)
>> is fragile because all you need is the salt value from the server ("k_s" or
>> "k" depending on which part of the paper you are reading). You can send the
>> server any valid point and receive the salt applied to it which could be
>> recovered by CVE-2017-8932. Once you have the salt, you can make offline
>> password guesses by trying to decrypt the user encrypted data ("c").
>>
>> OPAQUE is not quantum annoying because you only need to solve 1 DLP to
>> get offline classical computer password guessing. Also it suffers from a
>> weaker form as an attacker does not need to observe a successful exchange
>> to start their attack. With AuCPace, BSPAKE, and VTBPEKE an attacker needs
>> to observe a successful exchange or masquerade as the server to start an
>> attack.
>>
>> VTBPEKE is not quantum annoying because you only need to solve 2 DLPs to
>> get offline classical computer password guessing.
>> Solve DLP to get u: U = u * V
>> Given X: X = x * G where G = U + pw * V
>> X = x * (U + pw * V)
>> X = x * (u * V + pw * V)
>> X = (x * (u + pw)) * V
>> Solve DLP to get z: X = z * V
>> Now guess a password to get assumed x (x' = z / (u + pw)) test if x' is
>> correct.
>>
>> -----------------------------------------------------------
>>
>> After looking at all the submissions. The best two are AuCPace and
>> BSPAKE. If you add blind salt to AuCPace then I would say that's the best
>> as it's less complex and lower cost than BSPAKE. Also AuCPace doesn't
>> require point addition so it can use Montgomery curves (like X25519). For
>> hash to point X25519 is faster than Ed25519 because with Elligator you
>> generate a X25519 point then convert to Ed25519. Which costs a field invert
>> and square root.
>>
>> What I'd really like to know is which is better AuCPace or B-SPEKE (or
>> B-SPEKE' "modified B-SPEKE"). B-SPEKE (or B-SPEKE') was not submitted but
>> has all the desired properties (like AuCPace) but is less complex/cost than
>> AuCPace. Also B-SPEKE can use Montgomery curves, like AuCPace, which means
>> "from bytes" is free. I want to say B-SPEKE' (with blind salt) is the best
>> due to low server costs because HSMs are expensive and slow. I understand
>> why CPace added the "s" and "t" random values to SPEKE, but I don't think
>> this adds value to AuCPace vs B-SPEKE (or B-SPEKE'). One last thing
>> B-SPEKE' is a modified version of B-SPEKE that I came up with. Thus it
>> might be broken and obviously invalidates any proofs. It's just SPEKE with
>> an extra term "b * v * P" (b: server ephemeral key, v: derived from
>> password, P: hash to point from password). This is basically the change
>> from SPAKE2 to SPAKE2+.
>>
>> Name     | Client Cost | Server Cost
>> ---------+-------------|---------------
>> AuCPace  | ff*iH**[ii] | **[ii]H*if*i
>> B-SPEKE  | ffH***[iii] | **[ii]f**[ii]
>> B-SPEKE' | fH***[iii]  | *if**[ii]
>>
>> Note to add blind salt to each of these it adds the same cost: client
>> (H*ifI*i) and server (f*[i]). The server field invert is combined to other
>> field invert(s) thus it costs 3 field multiples.
>>
>> -----------------------------------------------------------
>> -----------------------------------------------------------
>>
>> ****************
>> ** Algorithms **
>> ****************
>>
>> Note these might not be accurate. If something above is wrong it might
>> stem from an error below.
>>
>> AuCPace
>> Both have:
>>       G = generator
>> Client has:
>>       idC = client identity
>> Server has these for "idC":
>>       salt
>>       settings
>>       W = w * G
>>
>> C:    t = random()
>> C->S: idC, t
>>    S: s = random()
>>    S: ssid = H(s, t)
>>    S: x = random()
>>    S: X = x * G
>>    S: a = random()
>>    S: A = a * hashToPoint(H(ssid, x * W, idC))
>> C<-S: s, X, A, salt, settings
>> C:    w = pwKdf(pw, salt, settings)
>> C:    ssid = H(s, t)
>> C:    b = random()
>> C:    B = b * hashToPoint(H(ssid, w * X, idC))
>> C:    K = H(ssid, b * A)
>> C->S: B, verifier_C[, encryptedData_C]
>>    S: K = H(ssid, a * B)
>> C<-S: verifier_S[, encryptedData_S]
>>
>> -----------------------------------------------------------
>>
>> B-SPEKE
>> Both have:
>>       G = generator
>> Client has:
>>       idC = client identity
>> Server has these for "idC":
>>       salt
>>       settings
>>       P = hashToPoint(p)
>>       V = v * G
>>
>> C->S: idC
>>    S: b = random()
>>    S: B = b * P
>>    S: x = random()
>>    S: X = x * G
>> C<-S: B, X, salt, settings
>> C:    p, v = pwKdf(pw, salt, settings)
>> C:    P = hashToPoint(p)
>> C:    a = random()
>> C:    A = a * P
>> C:    K = H(idC, idS, A, B, a * B, v * X)
>> C->S: A, verifier_C[, encryptedData_C]
>>    S: K = H(idC, idS, A, B, b * A, x * V)
>> C<-S: verifier_S[, encryptedData_S]
>>
>> -----------------------------------------------------------
>>
>> B-SPEKE'
>> Client has:
>>       idC = client identity
>> Server has these for "idC":
>>       salt
>>       settings
>>       P = hashToPoint(p)
>>       V = v * P
>>
>> C->S: idC
>>    S: b = random()
>>    S: B = b * P
>> C<-S: B, salt, settings
>> C:    p, v = pwKdf(pw, salt, settings)
>> C:    P = hashToPoint(p)
>> C:    a = random()
>> C:    A = a * P
>> C:    K = H(idC, idS, A, B, a * B, v * B)
>> C->S: A, verifier_C[, encryptedData_C]
>>    S: K = H(idC, idS, A, B, b * A, b * V)
>> C<-S: verifier_S[, encryptedData_S]
>>
>> -----------------------------------------------------------
>>
>> BSPAKE
>> Both have:
>>       G = generator
>>       idS = server identity
>> Client has:
>>       idC = client identity
>> Server has these for "idC":
>>       salt
>>       settings
>>       BlindC = hashToPoint(clientBlind)
>>       BlindS = hashToPoint(serverBlind)
>>       k3
>>       V = v * G
>>
>> C:    r = random()
>> C:    R = r * hashToPoint(H(password, idC, idS))
>> C->S: idC, 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:    clientBlind || serverBlind || k3 || v
>>           = pwKdf(password, BlindSalt, idC, idS, settings)
>> C:    a = random()
>> C:    A = a * G + hashToPoint(clientBlind)
>> C:    B' = B - hashToPoint(serverBlind)
>> C:    K = H(idC, idS, A, B, a * B', k3, v * B')
>> C->S: A, verifier_C[, encryptedData_C]
>>    S: A' = A - BlindC
>>    S: K = H(idC, idS, A, B, b * A', k3, b * V)
>> C<-S: verifier_S[, encryptedData_S]
>>
>> -----------------------------------------------------------
>>
>> OPAQUE
>> Both have:
>>       G = generator
>> Client has:
>>       idC = client identity
>> Server has these for "idC":
>>       salt
>>       settings
>>       ct = AuthEnc(k, c, C, S)
>>       s = random()
>>       S = s * G
>>       C = c * G
>>
>> C:    r = random()
>> C:    R = r * hashToPoint(H(pw))
>> C:    a = random()
>> C:    A = a * G
>> C->S: idC, A, R
>>    S: R' = H(salt) * R
>>    S: b = random()
>>    S: B = b * G
>>    S: K = H((b + H(B, idC) * s) * (A + H(A, idS) * C))
>> C<-S: B, R', ct, settings, verifier_S[, encryptedData_S]
>> C:    BlindSalt = (1/r) * R'
>> C:    k = pwKdf(pw, BlindSalt, settings)
>> C:    c, C, S = AuthEnc(k, ct)
>> C:    K = H((a + H(A, idS) * c) * (B + H(B, idC) * S))
>> C->S: verifier_C[, encryptedData_C]
>>
>> -----------------------------------------------------------
>>
>> VTBPEKE
>> Both have:
>>       V = generator
>>       U = generator
>>       idS = server identity
>> Client has:
>>       idC = client identity
>> Server has these for "idC":
>>       salt
>>       settings
>>       G = U + p * V
>>
>> C:    a   = random()
>> C:    R   = a * V
>> C:    R'  = H(11, R)
>> C->S: idC, R'
>>    S: y   = random()
>>    S: Y   = y * G
>>    S: e   = random()
>> C<-S: Y, e, salt, settings
>> C:    p   = pwKdf(pw, salt, settings)
>> C:    V'  = p * V
>> C:    G   = U + V'
>> C:    x   = random()
>> C:    X   = x * G
>> C:    Z   = x * Y
>> C:    K_e = H(01, idC, idS, G, X, Y, Z, R', salt, e)
>> C:    p'  = a + e * p
>> C:    o   = enc(K_e, p')
>> C:    K   = H(00, idC, idS, G, X, Y, Z, R', salt, e, o)
>> C->S: X, o[, encryptedData_C]
>>    S: Z   = y * X
>>    S: K_e = H(01, idC, idS, G, X, Y, Z, R', salt, e)
>>    S: p'  = dec(K_e, o)
>>    S: R   = p' * V - e * V'
>>    S: R' == H(11, R)
>>    S: K   = H(00, idC, idS, G, X, Y, Z, R', salt, e, o)
>> C<-S: verifier_S[, encryptedData_S]
>>
>> _______________________________________________
>> Cfrg mailing list
>> [e-mail]
>> https://www.irtf.org/mailman/listinfo/cfrg
>>
> _______________________________________________
> Cfrg mailing list
> [e-mail]
> https://www.irtf.org/mailman/listinfo/cfrg
>