CPace is a balanced PAKE and defined on multiplicative groups

cpace-mg.txt

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.

Hello thomas,

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

Yours,

Björn.

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