[noise] Noise and PAKE handhakes

[Trevor Perrin]

On Mon, Dec 17, 2018 at 12:49 AM Keziah Biermann <keziah at kizzycode.de> wrote:
>
> Is there any progress regarding PAKE handshakes?

Great question, we haven't discussed PAKE much on-list [1].

I've been chatting about this with Brian Warner recently, though.

There seem to be (at least) 2 good approaches:


(1) Use the original "EKE" or "DH-EKE" concept from Bellovin and
Merritt [2], where one (or both) of the ephemeral DH public keys is
somehow encrypted or masked with the password.  In the elliptic-curve
setting, this would mean creating a password-derived point and adding
it to the ephemeral.  The password-derived point could be created
either by taking h^password (like SPAKE2), where h is some generator
independent from the "main" generator g; or with a map-to-point
function like Elligator (e.g. [3]).


(2) Use the OPRF / OPAQUE idea from Hugo Krawczyk and others.
Essentially, the server implements an "Oblivious PRF" (OPRF) as
follows:
 * client sends p^b, where b is some blinding factor and p is the OPRF input
 * server responds (p^b)^k = p^(b*k), where k is the server's secret key
 * client calculates p^k, which is the result of OPRF(key=k, input=p)

This is an "Oblivious" PRF because from the client's perspective, the
output is a random function (PRF) of p, but the server doesn't learn
either the PRF input or output.

To turn this into a PAKE the client maps their password to a point p
(eg Elligator), and executes the OPRF protocol.  In addition the
server sends the client's identity keypair encrypted under the OPRF
output.  The client decrypts their identity keypair and then uses it
to execute a standard handshake (e.g. any Noise client-authenticated
handshake).


Anyways, the EKE approach is probably a little more efficient, but the
OPAQUE approach is more modular and directly gives you an "augmented
PAKE" where the server doesn't store "password-equivalent" data:
i.e., if the server's OPAQUE password database leaks to an attacker,
the attacker would have to brute-force individual passwords to be able
to execute the OPAQUE-based protocol.


Implementing the EKE approach into Noise might look like this:

An "eke" pattern modifier converts the initial ephemeral token "e" to
a masked-ephemeral token "me".  It also requires an additional
public-key algorithm name to specify the masking operation, e.g.

XXeke_25519+SPAKE2_AESGCM_SHA256:
  -> me
  <- e, ee, s, es
  -> s, se

or

XXeke_25519+Elligator_AESGCM_SHA256:
  -> me
  <- e, ee, s, es
  -> s, se

(The idea behind a general "masked ephemeral" token is that there are
potentially other reasons to mask the ephemeral, e.g. creating a
protocol where all bits are indistinguishable from random via
Elligator or encryption with a symmetric key, so that might be a
different pattern modifier that results in a differently-masked
ephemeral).

I've thought less about OPAQUE, but it might be an even easier
integration, since the OPRF and the rest of the handshake are
conceptually separate.

So there's some promising things we could work on, though I have a bit
of a backlog right now.  If anyone feels like fleshing this out
further or starting a draft extension spec though, go right ahead.

Trevor

[1] https://moderncrypto.org/mail-archive/noise/2017/001081.html
[2] https://www.cs.columbia.edu/~smb/papers/neke.pdf
[3] https://moderncrypto.org/mail-archive/curves/2015/000424.html