Skip to content

Instantly share code, notes, and snippets.

@Sc00bz
Last active January 31, 2023 16:16
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Sc00bz/1375a5dc7d1e8a1ffdfb789d3f4c6593 to your computer and use it in GitHub Desktop.
Save Sc00bz/1375a5dc7d1e8a1ffdfb789d3f4c6593 to your computer and use it in GitHub Desktop.
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

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