Instantly share code, notes, and snippets.

# Sc00bz/cpace-mg.txt

Last active January 31, 2023 16:16
CPace is a balanced PAKE and defined on multiplicative groups
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
 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.

### BjoernMHaase commented Dec 10, 2021 • edited

As a second comment,

When using cpace on a multiplicative group, it is fully covered with the proofs if the password is hashed to the full number of bits and then squared, as you suggested.

For a short generator there might be attacks of the number field sieve style.

So I'd recommend to use shake128 and expand the pw hash to the prime size.
Then square.Then reduce to get g.

Yours,

Björn