Skip to content

Instantly share code, notes, and snippets.

@jedisct1
Forked from Sc00bz/bs-speke.txt
Created January 13, 2020 01:39
Show Gist options
  • Save jedisct1/5fdddc49483d0da2255bf37e801c0bb4 to your computer and use it in GitHub Desktop.
Save jedisct1/5fdddc49483d0da2255bf37e801c0bb4 to your computer and use it in GitHub Desktop.
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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment