Skip to content

Instantly share code, notes, and snippets.



Created Jan 21, 2020
What would you like to do?
CPace is a balanced PAKE
CPace is the best balanced PAKE that I know of.
Costs per step
A: - fH**[ii]
B: H*i f*i
-: Negligible work
*: 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
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.
Forward secrecy: Yes
Not fragile: Yes
Quantum annoying: Yes
Both have:
hashToPoint() is Elligator or SWU
User A has:
idA = User A's identity
User B has:
idB = User B's identity
A: x = random()
A->B: idA, x
B: y = random()
B: salt = H(x, y)
B: b = random()
B: B = b * hashToPoint(pwKdf(pw, salt, idA, idB))
A<-B: idB, y, B
A: salt = H(x, y)
A: a = random()
A: A = a * hashToPoint(pwKdf(pw, salt, idA, idB))
A: K_a = H(salt, a * B)
A: verifierA = H(K_a, verifyAModifier)
A->B: A, verifierA[, encryptedDataA]
B: K_b = H(salt, b * A)
B: Checks verifierA == H(K_b, verifyAModifier)
B: verifierB = H(K_b, verifyBModifier)
A<-B: verifierB[, encryptedDataB]
A: Checks verifierB == H(K_a, verifyBModifier)
On success K_a == K_b, 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 "pwKdf()" does not need to be a password KDF as nothing is stored or
encrypted with said key. Thus there are no offline password cracking attacks.
Unless you have a quantum computer. Since CPace is quantum annoying, one would
need to solve a DLP per password guess, and the cost of the password KDF will
likely be negligible in comparison. One benefit to using a password KDF is it
will make timing attacks harder, but why not add password KDFs to all crypto?
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment