[noise] Multi-algorithm handshakes (a sketch)

[Trevor Perrin]

Hi all,

One motivation for deferred patterns in rev34 was to add more
flexibility for replacing the DH-based auth tokens (se, es) with
signature and KEM tokens.

This would mean moving beyond Noise handshakes based on a single DH
algorithm towards "multi-algorithm" handshakes which might use
different DH, signature, and KEM algorithms within a single handshake.

This would be a lot of work, and add a lot of complexity, but also
some benefits:

 * Clients and servers could reuse existing long-term signing keys, in
some cases.

 * Using signing keys instead of DH keys is sometimes more flexible;
because you can sign things, and both parties aren't restricted to the
same public-key algorithm.

 * Signatures can be used to sign the initial message, giving a
"0-RTT" authentication with different security properties (more
resilient to server compromise, i.e. KCI-resistance).

 * By allowing "hybrid" or "doubled" use of post-quantum KEM and
signature algorithms in combination with conventional algorithms, we
can add postquantum resistance without loss of conventional security.

 * We could potentially support "wildcard" algorithms whose type is
transmitted during the handshake (instead of being part of the pattern
name), gaining even more flexibility at the cost of run-time
complexity.


I think this is a direction we should pursue, because we have a lot of
powerful machinery for dealing with patterns, and this would let us
apply it to a wider range of protocols.

So I'd like to brainstorm the tokens and modifiers we'd need for a
"multi-algorithm" Noise extension.  I took an earlier stab at it [1],
but I think the below is better.

Roughly, the idea is that you declare multiple algorithm types in the
pattern name as ALG+ALG1+ALG2+ALG3+etc, and then tokens can be
annotated with the type number.  Modifiers are also annotated with the
type number, so that when they replace or double an existing token
with a new token, the new token will refer to that type.

This is a long way from working, and probably unclear and buggy - but
maybe it starts down a useful direction (or encourages someone to come
up with something better!)


Tokens
-------
Signature and KEM tokens:
  sig : Signature from static key over h
  ekem : KEM ciphertext encrypted to recipient's e
  skem : KEM ciphertext encrypted to recipient's s

Numbered tokens (N is a number from 1...9)
  sN : public key of type N
  eN : public key of type N
  eeN : DH between keys of type N
  seN : " "
  esN : " "
  ssN : " "
  sigN : Signature from static key of type N
  ekemN : KEM ciphertext encrypted to ephemeral key of type N
  skemN : KEM ciphertext encrypted to static key of type N


Modifiers
----------
Replacement modifiers (N is a number from 1...9, or absent)
  sigNi : Replace initiator's s with sN and se with sigN
  sigNr : Replace responder's s with sN and es with sigN
  skemNi : Replace initiator's s with sN and es with skemN
  skemNr : Replace responder's s with sN and se with skemN
  ekemN : Replace first e with eN and delete second e; replace ee with ekemN

Doubled modifiers (N is a number from 1...9)
  sigNid: Append sN following initiator s if not already present;
append sigN following se, deferring to the next line if necessary
  sigNrd: Append sN following responder s if not already present;
append sigN following es, deferring to the next line if necessary

  ekemNd : Append eN following first e if not already present; append
ekemN following ee
  skemNid : Append sN following initiator s if not already present;
append skem following es, deferring to the next line if necessary
  skemNrd : Append sN following responder s if not already present;
append skem following se, deferring to the next line if necessary

  eeNd : Append eN following e if not already present; append eeN following ee
  seNd : Append sN following initiator s if not already present;
append eN following responder e if not already present; append seN
following se
  esNd : Append sN following responder s if not already present;
append eN following initiator e if not already present; append esN
following es
  ssNd : Append sN following s if not already present; append ssN following ss

(Note that if using replacement modifiers you should use deferred
patterns as needed, so the modifier won't need to defer things; but if
using doubled modifiers you might end up with auth tokens in both the
original and deferred location, thus the modifier has to be capable of
deferring)


Examples
---------
XK:
  <- s
  ...
  -> e, es
  <- e, ee
  -> s, se

XKekem1d (e.g. XKekem1d_25519+NewHope) # hybrid forward-secrecy
  <- s
  ...
  -> e, e1, es
  <- e, ee, ekem1
  -> s, se

XKsig1i (e.g. XKsig1_25519+RSA2048) # rsa sig
  <- s
  ...
  -> e, es
  <- e, ee
  -> s1, sig1

XKskem1r (e.g. XKskem1_25519+RSA2048) # rsa enc
  <- s1
  ...
  -> e, skem1
  <- e, ee
  -> s, se

XKsig1i+skem1r (e.g. XKsig1i+skem1r_25519+RSA2048) # rsa sig+enc
  <- s1
  ...
  -> e, skem1
  <- e, ee
  -> s1, sig1

XKekem+sig1i+skemr (e.g. XKekem+sig1i+skemr_Kyber+RSA2048)
  <- s
  ...
  -> e, skem
  <- ekem
  -> s1, sig1

XK1sig1i+sig1r (e.g. X1sig1+sig1r_25519+Ed25519) # deferred pattern, EC sig
  <- s1
  ...
  -> e
  <- e, ee, sig1
  -> s1, sig1

X1Kskem1i+skem1r (e.g. X1Kskem1i+skem1r_25519+RSA2048) # deferred
pattern, RSA enc
  <- s1
  ...
  -> e, skem1
  <- e, ee
  -> s
  <- skem1

XKekem+sig1i+skem2r (e.g. XKekem+sig1i+skem2r_Kyber+Ed25519+RSA2048)
  <- s2
  ...
  -> e, skem2
  <- ekem
  -> s1, sig1

# doubles everything, and defers initiator auth:

XKekem1d+skem1id+skem1rd (e.g. XKekem1d+skem1id+skem1rd_25519+Kyber)
  <- s, s1
  ...
  -> e, e1, es, skem1
  <- e, ee, ekem1
  -> s, s1, se
  <- skem1


Trevor