Skip to content

Instantly share code, notes, and snippets.

Last active Oct 12, 2021
What would you like to do?
BS-SPEKE is an augmented PAKE and defined on multiplicative groups
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:
Costs per step
C: *E EE*^^^
S: ^^ ^^
E: Full size exponential
^: Exponential
*: Multiplication
Forward secrecy: Yes
Not fragile: Yes
Quantum annoying: Yes
No precomputation: Yes
Both have:
idS = server identity
N is a safe prime
Client has:
idC = client identity
Server has these for "idC":
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
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 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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment