AuCPace is an augmented PAKE

aucpace.txt

AuCPace

AuCPace with blind salt (OPRF) is the best augmented PAKE that I know of that
comes with a proof.

Costs per step
C: H*i            fffI*i*iH**[ii]
S:    f*iH***[iii]               f*i

*: 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
No pre-computation: Yes

Both have:
      idS = server identity
      hashToPoint() is Elligator or SWU
Client has:
      idC = client identity
Server has these for "idC":
      salt
      settings
      V = v * G

C:    s = random()
C:    r = random()
C:    R = r * hashToPoint(H(password, idC, idS))
C->S: idC, s, R
   S: t = random()
   S: sessionSalt = H(s, t)
   S: x = random()
   S: X = x * G
   S: b = random()
   S: B = b * hashToPoint(H(x * V, sessionSalt, idC, idS))
   S: R' = H(salt) * R
C<-S: t, B, X, R', settings
C:    sessionSalt = H(s, t)
C:    BlindSalt = (1/r) * R'
C:    v = pwKdf(password, BlindSalt, idC, idS, settings)
C:    a = random()
C:    A = a * hashToPoint(H(v * X, sessionSalt, idC, idS))
C:    K_c = H(sessionSalt, a * B)
C:    verifierC = H(K_c, verifyCModifier)
C->S: A, verifierC[, encryptedDataC]
   S: K_s = H(sessionSalt, b * A)
   S: Checks verifierC == H(K_s, verifyCModifier)
   S: verifierS = H(K_s, verifySModifier)
C<-S: verifierS[, encryptedDataS]
C:    Checks verifierS == H(K_c, verifySModifier)

On success K_c == K_s, 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 that a
clamped scalar doesn't have full coverage and there is a theoretical info
leakage. If you observer 2**100 successful exchanges, then with 2**255 memory
and 2**223 work you can eliminate less than 1 in 200 million password guesses
offline. Thus every 200 million online guesses you get one free (ie never will
happen, impossible, and you get a worthless attack). To "fix" this you could
generate a random number like this:
r' = random([0, (2**252 + 27742317777372353535851937790883648493 - 1) / 2 - 1])
r = 8 * (r' + 1).

Note "H(salt) * R" vs "salt * R", this is so you don't need to store a large 
salt. A salt of just 128 to 256 bits is fine once expanded to the required
length.