CPace is a balanced PAKE

cpace.txt

CPace

CPace is the best balanced PAKE that I know of. CPace defined on multiplicative
groups can be found here:
https://gist.github.com/Sc00bz/1375a5dc7d1e8a1ffdfb789d3f4c6593

Costs per step
A: -   fH**[ii]
B:  H*i        f*i

-: Negligible work
*: Scalar point multiply
H: Hash to point which is Elligator or SWU (depending on implementation this may
   require a field invert if scalar point multiply needs affine points)
i: Field invert
f: From bytes (field square root or free for Montgomery curves)
[ii...]: Field inverts that can be combined. Cost is 1 field invert and 3*(n-1)
         field multiplications.

Properties
Forward secrecy:  Yes
Not fragile:      Yes
Quantum annoying: Yes

Both have:
      hashToPoint() is Elligator or SWU
User A has:
      idA = User A's identity
User B has:
      idB = User B's identity

A:    x = random()
A->B: idA, x
   B: y = random()
   B: salt = H(x, y)
   B: b = random()
   B: B = b * hashToPoint(H(pw, salt, idA, idB))
A<-B: idB, y, B
A:    salt = H(x, y)
A:    a = random()
A:    A = a * hashToPoint(H(pw, salt, idA, idB))
A:    K_a = H(salt, a * B)
A:    verifierA = H(K_a, verifyAModifier)
A->B: A, verifierA[, encryptedDataA]
   B: K_b = H(salt, b * A)
   B: Checks verifierA == H(K_b, verifyAModifier)
   B: verifierB = H(K_b, verifyBModifier)
A<-B: verifierB[, encryptedDataB]
A:    Checks verifierB == H(K_a, verifyBModifier)

On success K_a == K_b, thus derived verifiers and encryption keys are the same.

When receiving a point, you must check it is valid and not a low order point.
When using random() to generate a scalar, you should generate a larger value and
modulo by one less than the order then add 1 or generate a value [1, order) with
rejection sampling. This makes sure it is uniformly distributed and not zero.
Similar should be done for H() when generating fields to avoid bad values. For
generating a scalar for X25519 you could just use X25519's clamping.

Note you do not need to use a password KDF as nothing is stored or encrypted
with said key. Thus there are no offline password cracking attacks. Unless you
have a quantum computer. Since CPace is quantum annoying, one would need to
solve a DLP per password guess, and the cost of the password KDF will likely be
negligible in comparison.