Quantum Resistance in PAKEs

pake.txt

TL;DR The best PAKE in this list is SPAKE2+EE with blind salt and client verifies first. Also don't
use standard clamping with Ed25519. For the 32 byte scalars, clear the highest bit and lowest 3 bits
then check for zero.


         Number of DLPs to solve to do offline guessing of N passwords

                              | SRP6a | "SRP6b" | OPAQUE | SPAKE2+ | SPAKE2+EE
------------------------------+-------+---------+--------+---------+-----------
Client, client verifies first |   -   |    -    |   1    |    -    |     -
Server, client verifies first |   1   |   -, 2  |  -, 1  |    1*   |     N
------------------------------+-------+---------+--------+---------+-----------
Observe                       |   1   |    2    |   1    |   1+1*  |     N
------------------------------+-------+---------+--------+---------+-----------
Client, server verifies first |   0   |    1    |   1    |    1*   |     N
Server, server verifies first |   -   |    -    |  -, 1  |    -    |     -

Note the "-, 2" and "-, 1". The first is if you only do that attack and don't do anything else. The
second is if you act as the client to the server to gain extra info.


PAKE      | Attack
----------+-----------------------------------------------------------------------------------------
SRP6a     | Solve DLP A = g ** a. Guess password with known salt, B, k, u, a, and Verifier.
"SRP6b"   | Solve DLP A = g ** a and salt. Guess password with known salt, B, k, u, a, and Verifier.
OPAQUE    | Solve DLP for salt. Guess password with known salt and ciphertext.
SPAKE2+   | Solve DLP of either blinding point N or M. For observe, also solve DLP of either initial
          |   message. * Those 1s are solve a DLP once per implementation instead of once per user.
SPAKE2+EE | Solve DLP of either unblinded point for each password guess.


"SRP6b" is SRP6a with blind salt. If you add blind salt to SPAKE2+ and SPAKE2+EE you need to solve
an extra DLP per user on attacks that work.

A good PAKE shouldn't have any attacks that don't require solving a DLP or solving just one DLP per
implementation. When an attacker is acting as a client and the client verifies first, there should
not be any attacks even if you can solve DLPs. To be a great PAKE you also need to be quantum
annoying, requires solving a DLP per password guess. This means there is only two good PAKE and one
great PAKE in this list. These are "SRP6b", SPAKE2+ with blind salt, and SPAKE2+EE respectively.
Adding blind salt to SPAKE2+EE makes it even better.

There is an attack on SPAKE2+ and SPAKE2+EE when acting as a client and the client verifies first,
but it is implementation specific. If you use Ed25519 and standard clamping, then you can test if
the scalar is in a valid range. Give a few hundred messages, you will be able to eliminate most
false positives. For Ed25519 clearing the highest bit and lowest 3 bits is enough to make this
infeasible, but ideally scalars are in the range of [1, ℓ). With Ed25519 you also want scalars to be
a multiple of 8. So all numbers that are divisible by 8 in the range [8, 8*ℓ).

DLP here is Discreet Logarithm Problem, right? (sorry, not a cryptographer or security researcher, just a developer trying to pick the best solution for her application.

Yes. The best balanced PAKE is CPace. The best augmented PAKE is BS-SPEKE, but if you want one with a proof then AuCPace. If you need both balanced and augmented, it might make sense to do CPace and AuCPace since they are more related. All of these are based off SPEKE so there's not too much different between them.