Last active
August 10, 2022 16:20
-
-
Save Sc00bz/e99e48a6008eef10a59d5ec7b4d87af3 to your computer and use it in GitHub Desktop.
BS-SPEKE is an augmented PAKE
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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. 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 multiplicative groups can be found here: | |
https://gist.github.com/Sc00bz/ec1f5fcfd18533bf0d6bf31d1211d4b4 | |
** Costs per step ** | |
BS-SPEKE | |
C: H*i ffI*iH***[iii] xi | |
S: f**[ii] f**[ii] | |
OPAQUE-3DH | |
C: Hx*[ii] ffI*i***[iii] | |
S: ffx***[iiii] | |
** Costs OPRF AKE ** | |
BS-SPEKE | |
C: fHI**ii fx***iiH | |
S: f*i f***i | |
OPAQUE-3DH | |
Costs OPRF AKE | |
C: fHI**ii fx***i | |
S: f*i fx*** | |
*: 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. | |
Properties | |
Forward secrecy: Yes | |
Not fragile: Yes | |
Quantum annoying: Yes | |
No precomputation: Yes | |
Secure registration: Yes | |
** Registration ** | |
Both have: | |
idS = server identity | |
hashToPoint() is Elligator or SWU | |
G = standard generator | |
Client has: | |
idC = client identity | |
C: r = random() | |
C: R = r * hashToPoint(H(password, idC, idS)) | |
C->S: idC, R, settings | |
S: Approve settings | |
S: salt = random() | |
S: R' = H(salt) * R | |
S: b = random() | |
S: B = b * G | |
C<-S: R', B | |
C: BlindSalt = (1/r) * R' | |
C: K_pw = pwKdf(password, BlindSalt, idC, idS, settings) | |
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 | |
** Use ** | |
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: R' = H(salt) * R | |
S: b = random() | |
S: B = b * P | |
C<-S: R', B, settings | |
C: BlindSalt = (1/r) * R' | |
C: K_pw = pwKdf(password, BlindSalt, idC, idS, settings) | |
C: p = H(K_pw, pModifier) | |
C: v = H(K_pw, vModifier) | |
C: macKey = H(K_pw, macKeyModifier) | |
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) | |
S: sessionKey = H(K_s, sessionKeyModifier) | |
S: encReg = aead_encrypt(sessionKey, reg || regMac) | |
C<-S: verifierS, encReg[, encryptedDataS] | |
C: Checks verifierS == H(K_c, verifySModifier) | |
C: sessionKey = H(K_c, sessionKeyModifier) | |
C: reg || regMac = aead_encrypt(sessionKey, encReg) | |
C: Checks regMac == MAC(macKey, reg * G) | |
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 observe 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: | |
order = 2^252 + 27742317777372353535851937790883648493 | |
r = 8 * random([1, (order - 1) / 2]) | |
or | |
r = random([8, 8 * ((order - 1) / 2) + 7]) & ~7 | |
For X25519, you'll want to have r be a multiple of 8 and swap r and 1/r. This is | |
so you multiply the point out of your control by a multiple of 8. So you can | |
check for zero. If the only functions available always clamp before scalar | |
multiplication then generate r and 1/r ("rInv") like this: | |
order = 2^252 + 27742317777372353535851937790883648493 | |
r = clamp(random()) | |
rInvPos = (r ^ (order - 2)) % (8 * order) | |
rInvNeg = 8 * order - rInvPos | |
rInv = ((rInvPos >> 254) & 1) ? rInvPos : rInvNeg // do bit select | |
if ((rInv >> 254) & 1) == 0 // "rInv != clamp(rInv)" | |
// This happens <1 in 2^100 | |
// When both rInvPos and rInvNeg's 254th bit are 0 | |
restart | |
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