[Cfrg] aPAKE Analysis

[[e-mail]]

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]