Re: [Cfrg] aPAKE Analysis

[Jonathan Hoyland <[e-mail]>]

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
>