[noise] Pre-shared Secret - preventing DoS, and ensuring post-quantum PFS

[Jason A. Donenfeld]

On Wed, Nov 11, 2015 at 10:16 PM, Trevor Perrin <trevp at trevp.net> wrote:
>  * A Noise handshake specifies a fixed sequence of MixKey / MixHash
> steps, so we can't add an optional MixKey to a handshake.  This would
> require either specifying "preshared_key" versions of the handshakes,
> or always performing an extra MixKey().

Why would optional be bad? The idea would be - if both parties a) know
to use a pre-shared key and b) use the same pre-shared key, their
handshakes will be successful. Otherwise, they're not legitimate.


>  * h is intended to bind *all* previous data, but also to be
> non-secret, so we'd need to MixHash() some value derived from the
> pre-shared key.

I had feared this. So in that case what about: "If a pre-shared key is
provided, in Initialize, call MixKey(psk) followed by MixHash(psk)."
Off-hand, I can't imagine any reason why this would leak anything
important.


> So instead of a pre-shared symmetric key, the parties could use
> pre-shared ephemeral public keys, and you could augment any handshake
> to a "pse" version like this:
>
> Noise_IK_pse(s, rs):
>   -> e
>   <- s, e
>   ------
>   -> dhee, e, dhes, s, dhss
>   <- e, dhee, dhes

In this version, is the pre-shared ephemeral "e" a different "e" (say,
e prime) than what's later exchanged? In other words, do you mean
this:

  -> e'
  <- s, e'
  ------
  -> dhee, e, dhes, s, dhss
  <- e, dhee, dhes

But this has a major problem. From the spec:

    "Calls MixHash() once for each public key listed in the pre-messages
    from new_handshake_pattern, passing in that public key as input"

Since only MixHash() is called on each pre-shared ephemeral, the
pre-shared ephemerals do NOT become part of the symmetric encryption
key. The symmetric encryption key, then, is still derived from only
diffie-hellman results, the public keys for which are shared through
the wire. This means PFS is broken if the DH function is broken
(post-quantum, better rho, other DH weaknesses...), which is the
precise threat model I wanted to protect against. If all our traffic
is logged, I don't want it to be decryptable in the future.

In order for this to work, pre-shared non-DH results need to be mixed
into the symmetric key used.


> Trevor

There's also my second concern:

> > 2. If a pre-shared secret is provided, the first unencrypted public key written receives a MAC (using hmac or keyed-blake2) using the pre-shared secret.
> > This provides DoS defense, so that an attacker can not force a server to compute any DH operations, unless he has the pre-shared secret. Without this mitigation, Noise is very very DoS-able.

DH is expensive; the denial-of-service situation is real. It would be
nice to have a cryptographic solution for this (i.e. not token
buckets).

A weaker form than what I've proposed here with the pre-shared key is
to simply use the recipients public key as a key for a MAC over the
whole message. That way, at the very least, it's not DoS-able by
random third parties, but rather people who already know who they're
talking to.

What do you think of this?


[Or, sticking with the pre-shared key concept, if you're against MACs,
here's a flawed idea: authenticate-encrypt (or just authenticate) the
first ephemeral key using the current 'k'. And make that 'k' depend on
the pre-shared key, as discussed above. That way, there's a Poly1305
authentication that has to occur before a DH occurs. Big big big flaw:
this would result in key-reuse in catastrophic ways. I guess we could
introduce a random salt to mix in. Or adopt XChaCha20 with a massive
nonce, or... Well, things get more complicated I guess. I don't have a
solution to simplify it from there, except going back to my original
idea of a simple MAC (hmac or keyed blake).]