BS-SPEKE is an augmented PAKE and defined on multiplicative groups

bs-speke-mg.txt

BS-SPEKE (defined on multiplicative groups)

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. BS-SPEKE
is the best augmented PAKE that I know of. Only problem is 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
defined on ECC can be found here:
https://gist.github.com/Sc00bz/e99e48a6008eef10a59d5ec7b4d87af3

Costs per step
C: *E  EE*^^^
S:   ^^      ^^

E: Full size exponential
^: Exponential
*: Multiplication

Properties
Forward secrecy:     Yes
Not fragile:         Yes
Quantum annoying:    Yes
No precomputation:   Yes
Secure registration: Yes

** Registration **
Both have:
      idS = server identity
      N is a safe prime
      G = standard generator
Client has:
      idC = client identity

C:    sqrtP = H(password, idC, idS)
C:    p = sqrtP ^ 2 (mod N)
C:    r = randomRange(1, (N-3)/2)  // 1 <= r <= (N-3)/2
C:    R = p ^ r (mod N)
C->S: idC, R, settings
   S: Approve settings
   S: salt = random()
   S: R' = R ^ H(salt) (mod N)
   S: b = random()
   S: B = g ^ b (mod N)
C<-S: R', B
C:    1/r = r ^ ((N-5)/2) (mod (N-1)/2)
C:    BlindSalt = R' ^ (1/r) (mod N)
C:    K_pw = pwKdf(password, BlindSalt, idC, idS, settings)

C:    sqrtG || v = pwKdf(password, BlindSalt, idC, idS, settings)
C:    g = sqrtG ^ 2 (mod N)
C:    a = random()
C:    A = g ^ a (mod N)
C:    K_c = H(idC, idS, A, B, B ^ a (mod N), B ^ v (mod N))
C:    verifierC = H(K_c, verifyCModifier)
C->S: A, verifierC[, encryptedDataC]



C:    p      = H(K_pw, pModifier)
C:    v      = H(K_pw, cModifier)
C:    macKey = H(K_pw, macKeyModifier)
C:    P = hashToPoint(p)
C:    V = v * P
C:    regMac = MAC(macKey, B)
C:    a = random()
C:    A = a * G
C:    K_c = H(a * B [|| a * ServerPublicKey])
C:    encServerData = aead_encrypt(K_c, P || V || regMac)
C->S: A, encServerData
   S: K_s = H(b * A [|| serverPrivateKey * A])
   S: P || V || regMac = aead_decrypt(K_s, encServerData)
   S: store for idC: salt, settings, P, V, b (as reg), regMac


   S: K_s = H(idC, idS, A, B, A ^ b (mod N), V ^ b (mod N))
   S: Checks verifierC == H(K_s, verifyCModifier)
   S: verifierS = H(K_s, verifySModifier)
C<-S: verifierS[, encryptedDataS]
C:    Checks verifierS == H(K_c, verifySModifier)






** Use **
Both have:
      idS = server identity
      N is a safe prime
      G = standard generator
Client has:
      idC = client identity
Server has these for "idC":
      salt
      settings
      g = sqrtG ^ 2 (mod N)
      V = g ^ v (mod N)

C:    sqrtP = H(password, idC, idS)
C:    p = sqrtP ^ 2 (mod N)
C:    r = randomRange(1, (N-3)/2)  // 1 <= r <= (N-3)/2
C:    R = p ^ r (mod N)
C->S: idC, R
   S: b = random()
   S: B = g ^ b (mod N)
   S: R' = R ^ H(salt) (mod N)
C<-S: B, R', settings
C:    1/r = r ^ ((N-5)/2) (mod (N-1)/2)
C:    BlindSalt = R' ^ (1/r) (mod N)
C:    sqrtG || v = pwKdf(password, BlindSalt, idC, idS, settings)
C:    g = sqrtG ^ 2 (mod N)
C:    a = random()
C:    A = g ^ a (mod N)
C:    K_c = H(idC, idS, A, B, B ^ a (mod N), B ^ v (mod N))
C:    verifierC = H(K_c, verifyCModifier)
C->S: A, verifierC[, encryptedDataC]
   S: K_s = H(idC, idS, A, B, A ^ b (mod N), V ^ b (mod N))
   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 public key (`A`, `B`, `R`, `R'`), you must check it is in the
range [2, N-2]. Theoretically `sqrtP` and `sqrtG` should be
`ceiling(log2(N)/8)+16` bytes of output from `H()`, modulo by `N-4`, and then
add 2. This is so it is in the range [2, N-2]. You can use a KDF or XOF to
generate the necessary bytes. Take care when using a password KDF to generate
the large `sqrtG || v` because some take O(cost*outputLen) time, such as with
PBKDF2.

For perfect informational security, you should use rejection sampling on `a` and
`b` so they are in the range [1, (N-3)/2], but this is not really necessary.
Looking at https://datatracker.ietf.org/doc/html/rfc3526#section-8 you should
probably go with the high-end (note this was before Logjam, also this being
"quantum annoying" makes Logjam less of a threat):

Prime Size | Exponent Size | Exponent Size
-----------+---------------+---------------
2048 bits  | 320 bits      | 40 bytes
3072 bits  | 420 bits      | 53 bytes
4096 bits  | 480 bits      | 60 bytes
6144 bits  | 540 bits      | 68 bytes
8192 bits  | 620 bits      | 78 bytes

Note "R ^ H(salt)" vs "R ^ salt", 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.