Skip to content

Instantly share code, notes, and snippets.

@Sc00bz
Last active Oct 12, 2021
Embed
What would you like to do?
CPace is a balanced PAKE and defined on multiplicative groups
CPace (defined on multiplicative groups)
CPace is the best balanced PAKE that I know of. CPace defined on ECC can be
found here:
https://gist.github.com/Sc00bz/545eb39a369b67242634bd9c3302627c
Costs per step
A: - *^^
B: *^ ^
-: Negligible work
^: Exponential
*: Multiplication
Properties
Forward secrecy: Yes
Not fragile: Yes
Quantum annoying: Yes
Both have:
N is a safe prime
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: sqrtG = H(password, salt, idA, idB)
B: g = sqrtG ^ 2 (mod N)
B: b = random()
B: B = g ^ b (mod N)
A<-B: idB, y, B
A: salt = H(x, y)
A: sqrtG = H(password, salt, idA, idB)
A: g = sqrtG ^ 2 (mod N)
A: a = random()
A: A = g ^ a (mod N)
A: S_a = B ^ a (mod N)
A: K_a = H(salt, S_a)
A: verifierA = H(K_a, verifyAModifier)
A->B: A, verifierA[, encryptedDataA]
B: S_b = A ^ b (mod N)
B: K_b = H(salt, S_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 public key (`A`, `B`), you must check it is in the range
[2, N-2]. Theoretically `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.
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 you do not need to use 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.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment