[noise] multi algorithm handshakes - alternative formulation (was Re: "sig" modifier (was: Extension spec: Static-Static Pattern Modifiers))

[Justin Cormack]

The discussion https://moderncrypto.org/mail-archive/noise/2018/001793.html
is the most up to date
formulation of multi algorithm handshakes. We need these for complex
signature use cases and for
PQ use cases, and quite likely other things in future. The proposed
notation is not terribly readable,
in particular the use of i and r for initiator and responder
modifications. I wanted to propose a
possible alternative formualtion of these that is I think more general.

Using a simple signature example from above post, where we modify
initiator but not responder.

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

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

An alternative formulation for this is in terms of

NK:
  <- s
  ...
  -> e, es
  <- e, ee

XN:
  -> e
  <- e, ee
  -> s, se

XNsig:
  -> e
  <- e, ee
  -> s, sig

NK+XNsig:
  <- s
  ...
  -> e, es
  <- e, ee
  -> s1, sig1

In this case the last line could be written as s, sig but in more
complex cases the numbers are helpful.

I think this is a cleaner notation, as it avoids the "1" and "i"
modifiers, but it is also more general.
The rules for composition are fairly obvious, though clearly they need
writing down. Identical ephemerals
are coalesced (this means that NN is the identity for the standard
patterns). There are some potential
tweaks, such as moving additional ephemerals after the first
encryption, rather than the obvious conjunction
which is to order things interleaved as per the pattern derivation rules.

With other examples from that, here is doubling:

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

This one needs some slightly different primitives.

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

NN:
  -> e
  <- e, ee

NNekem:
  -> e1
  <- ekem
Note this is applying the ekem rule to NN, but we rename to e1 now to
make it clear this is a different type of e.
This pattern could perhaps be called NNkem.

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

Another example:

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

This is just the basic symmetric sig pattern with explicit deferral. s
is a different
type to e so we use the "1" modifier. Because we use N patterns for
creating mixed types
we never need to mark explicit initiator and reposnder on modifiers.

XK1sig:
  <- s1
  ...
  -> e
  <- e, ee, sig1
  -> s1, sig1

We basically use the "1" as a type, it might be better to use
consistent types, so nothing
is always standard DH keys, "1" could be signatures, "2" New Hope but
not sure if this is more
or less confusing.

Another doublign example from above:

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

this is composed as

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

X1K:
  <- s
  ...
  -> e, es
  <- e, ee
  -> s
  <- se

X1Kskem:
  <- s1
  ...
  -> e, skem1
  <- e, ee
  -> s1
  <- skem1

NNekem:
  -> e1
  <- ekem

XK+NNekem
  <- s
  ...
  -> e, e1, es
  <- e, ee, ekem1
  -> s, se

XK+NNekem+X1Kskem: (or maybe called XK+NNkem+X1Kkem as the e and s are implicit)
  <- s, s1
  ...
  -> e, e1, es, skem1
  <- e, ee, ekem1
  -> s, s1, se
  <- skem1

Note that a canonical ordering for composition might be a good idea.