bs-speke.txt

BS-SPEKE

BS-SPEKE is a modified B-SPEKE with blind salt (OPRF). Modified B-SPEKE is a
similar change from SPEKE as from SPAKE2 to SPAKE2+ to make it augmented. Doing
this saves a scalar point multiply vs original B-SPEKE with blind salt. There
are no proofs, but it's not hard to take the SPEKE proof, add the OPAQUE proof
for OPRF, and it's obvious that the augmented change makes it augmented. So if
anyone knows how to formally state that in a proof, that would be awesome to
have.

BS-SPEKE Costs per step
C: H*i       ffI*iH***[iii]
S:    f**[ii]              f**[ii]

*: 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
I: Scalar 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.

BS-SPEKE Properties
Forward secrecy:    Yes because it's a PAKE
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
      P = hashToPoint(p)
      V = v * P

C:    r = random()
C:    R = r * hashToPoint(H(password, idC, idS))
C->S: idC, R
   S: b = random()
   S: B = b * P
   S: R' = H(salt) * R
C<-S: B, R', settings
C:    BlindSalt = (1/r) * R'
C:    p || v = pwKdf(password, BlindSalt, idC, idS, settings)
C:    P = hashToPoint(p)
C:    a = random()
C:    A = a * P
C:    K_c = H(idC, idS, A, B, a * B, v * B)
C:    verifierC = H(K_c, verifyCModifier)
C->S: A, verifierC[, encryptedDataC]
   S: K_s = H(idC, idS, A, B, b * A, b * V)
   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.
After blinding and unblinding, check the point is not the point at infinity.
When using H() or random() to generate a scalar, you should generate a larger
value and modulo by one less than the order then add 1. This makes sure it is
uniformly distributed and not zero. Similar should be done for H() when
generating fields to avoid bad values.

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.