[noise] Reworking PSK usage

[Trevor Perrin]

Hi all,

Jason's put a lot of thought into PSKs in Noise and WireGuard and
pointed out the current Noise design could use improvement:

Noise currently assumes the "preshared symmetric key" is known to both
parties prior to the handshake, so you can mix it in before other
secret keys.  But for patterns that transmit identities, it would make
more sense for the PSK to be a pairwise value that only gets mixed in
once the parties learn each other's identity, and can lookup the
pairwise PSK from some database.

Concretely, something like WireGuard might want a pattern like:

<- s
...
-> e, es, s, ss
<- e, ee, se, psk

Where the "psk" token means "mix in the PSK now".  You could put the
token earlier, for example at the end of the first message, if you
assume knowledge of the initiator's "s" is sufficient to identify the
correct PSK.  But you might want it later, if something in the first
message's payload is needed to lookup the PSK, or for DoS-resistance
if you want to decrypt the first message's payload without consulting
the PSK database.  So having a "psk" token gives flexibilty for those
decisions.

Some questions pop up:

(1) How do we name this?  It seems like we're moving towards a naming
syntax of having modifiers within the pattern field, like "XXhfs" or
"XXfallback+sig+hfs", so we should probably align with that, instead
of the current special-case syntax of "NoisePSK_XX".  We'd probably
like the name to indicate PSK placement.  I'll argue the most likely
PSK placements are at the beginning of the handshake, or at the end of
a message:
 * At the beginning of a handshake, we should still probably put it
after "e" since the spec currently assumes message patterns start with
""e"
 * At the end of a message means it will come after any "s" tokens in
that message, and keeps the patterns easy to read.  So we could name
things like:

Noise_IKpsk0:
<- s
...
-> e, psk, es, s, ss
<- e, ee, se

Noise_IKpsk1:
<- s
...
-> e, es, s, ss, psk
<- e, ee, se

Noise_IKpsk2:
<- s
...
-> e, es, s, ss
<- e, ee, se, psk

This doesn't rule out other placements, it just means we might need to
extend the naming scheme down the road.


(2) What does this actually do?  I think it should apply the rules
from Section 7 regarding MixKey(e), i.e. since we're use a non-DH key,
we should ensure there is a non-DH source of randomization.  Then we'd
like to turn the 2nd bullet (or something like it) into a token.

This isn't trivial, because the 2nd bullet current specifies:

ck, temp = HKDF(ck, psk)
MixHash(temp)

Which doesn't affect k, because it assumes the following MixKey(e)
will affect k.  But if we turn this into a token, we can't make that
assumption anymore.

Jason suggested allowing a 3rd output from HKDF, something like:

MixKeyAndHash(psk):
  ck, k, temp = HKDF(ck, psk)
  MixHash(temp)

We could simplify further, and consider just MixKey(psk), but then the
PSK doesn't immediately affect the "h" value, and it would be nice it
we maintain the invariant that "h" binds always everything that
happened previously.

This sounds reasonable to me, and like it's worth adding to the
revision 32 draft.

We haven't broken compatibility since 2015, so this would require
updates for existing libraries.  That's unfortunate but this does seem
like a more thoughtful and flexible approach, which would see
real-world use.  I'd like to hear what the library developers think.
Luckily, I don't think PSK had gotten much use outside of WireGuard,
which is willing to change.

Trevor