Skip to content

Instantly share code, notes, and snippets.

@Sc00bz
Last active Dec 10, 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.
@BjoernMHaase
Copy link

BjoernMHaase commented Dec 10, 2021

Hello thomas,

Fyi, we have just released a new draft version regarding cpace and would appreciate your feedback!

Yours,

Björn.

@BjoernMHaase
Copy link

BjoernMHaase commented Dec 10, 2021

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment