[noise] Tokens and modifiers for signatures/KEMs

[Trevor Perrin]

Some recent ideas would move us closer to handling signature and KEM algorithms.

In particular:  The "deferred" patterns (below) would give us options
for authenticating a party using either a message they send or
receive; in the former case, the DH can be replaced with a signature,
in the latter case with a KEM.

https://moderncrypto.org/mail-archive/noise/2018/001474.html


Signature and KEM algorithms might be hardcoded for some hash
algorithm (e.g. Ed25519 signatures are hardcoded to SHA512).
Alternatively, algorithms might receive their hash functionality via
an interface to Noise, and we have ideas to explore there:

https://moderncrypto.org/mail-archive/noise/2018/001494.html


A separate set of questions is how to handle patterns and names when we have:

 - Different classes of algorithms (signature, DH, KEM) that could be
used with a single key (e.g. a 25519 key could support DH and
signatures (e.g. XEd25519 signing); an RSA key might be used with KEM
or signatures).

 - Different algorithms of the same class that could be used with a
single key (e.g. RSA-PKCS1 vs RSA-PSS signatures)

 - Different types of keys (e.g. the initiator and responder might
each have a different type of static key)

 - Hybrid protocols where a party has multiple static or ephemeral
keys, e.g. combining PQ algorithms with non-PQ algorithms.


Here's a sketch of how we could handle the names and patterns.

(Nailing this down is less important until we've specified all the
deferred patterns and hashing stuff, but I think this shows a
direction we should head in, and that there's no insurmountable
obstacles).


Public-key algorithms
======================
Instead of a Noise protocol taking a single DH algorithm, we can
consider it taking a list of public-key algorithms.  Each algorithm
name refers to some type of key and some specific DH, KEM, or
signature algorithm.  E.g. "25519" refers to an X25519 key and X25519
DH.

In a Noise protocol name, these algorithms would be separated with
plus signs.  Additionally, if an algorithm requires a different type
of public key than the preceding algorithm, they are separated by the
numbers "1", "2", etc:

25519+XEd25519
25519+1+Ed25519
25519+1+Ed25519+2+NewHope
25519+1+448
RSAKEM+RSAPSS+1+NewHope
25519+1+RSAPSS+RSASIGPKCS1

Each algorithm will be associated with a suffix of the form:
"", "a", "b", "c", "1a", "1b", "2", "2a", "3", "4", "4a", etc.

These suffixes will be added to tokens to indicate which algorithm
they refer to.  The number refers to the key type, and the letter
refers to alternate algorithms for the key type.  For example:

25519+XEd25519  (""=25519, "a"=XEd25519)
25519+1+Ed25519 (""=25519, "1"=Ed25519)
RSAKEM+RSAPSS+1+NewHope (""=RSAKEM, "a"=RSAPSS, "1"=NewHope)
25519+1+RSAPSS+RSASIGPKCS1 (""=25519, "1"=RSAPSS, "1a"=RSASIGPKCS1)

Tokens
=======
"sig"
 - can replace "se" (from initiator) or "es" (from responder)
 - adds a signature over the h value from the sender's static key
 - transmitted under encryption if applicable (if k exists)

"skem"
 - can replace "es" (from initiator) or "se" (from responder)
 - adds a KEM ciphertext based on the other party's static key
 - calls MixKey() on the output
 - not encrypted (?)

"ekem"
 - can replace "ee"
 - adds a KEM ciphertext based on the other party's ephemeral key
 - calls MixKey() on the output
 - if the second "e" in the pattern becomes unused, it can be deleted
 - not encrypted (?)

Suffixes can be added to above tokens to associate them to public-key
algorithms.


Modifiers
==========
Pattern modifiers are processed sequentially.  They modify tokens by
replacing the default DH operations with sig and ekem / skem tokens
pointing to the appropriate algorithm via a suffix.  These modifiers
can only be used if the changes they describe result in a valid
pattern.  For example: if a pattern contains an "es" from the
initiator, the "sig" modifier can't be applied.

sig: replaces all "se" and "es" with "sig"
sigi: replaces all "se" with "sig"
sigr: replaces all "es" with "sig"
skem: replaces all "se" and "es" with "skem"
skemi: replaces all "se" with "skem"
skemr: replaces all "es" with "skem"
ekem: replaces all "ee" with "ekem"

DH modifiers are also introduced (ee, se, es).  They aren't no-ops,
because the above replacements can also change the suffix to refer to
a different algorithm, and a protocol might use multiple DH
algorithms.

The initial suffix is "".  The suffix is appended onto the new token,
and also appended to any keys used as inputs to the new token.

The suffix is updated as follows:
 - The current algorithm class is initialized to DH, and is changed to
KEM or signature (or back to DH) by the above modifiers.
 - When a modifier uses a different class of algorithm, then the
suffix is changed to "a" if the suffix is currently empty or doesn't
end with a letter, otherwise the letter is incremented (a->b, b->c,
etc).
 - A special case is if the default DH algorithm is completely
replaced, in which case the letters are shifted down ("a" -> "",
"b"->"a").

The following modifiers explicitly switch to a new key type and reset
the suffix to a number:

ca:
 - Stands for change to a new algorithm, only needed when switching to
a new algorithm using the same key and of the same algorithm class.
 - Increments the suffix letter.

c1, c1, c3, etc:
 - Stands for "change to a new key type".
 - Sets the suffix to the number.
 - Numbers have to be used sequentially.

d1, d2, d3:
 - Stands for change to a new key type and "double".
 - Sets the suffix to the number.
 - The above modifiers are re-interpreted to "double" the underlying
token by adding a new token after it, instead of replacing it.


EXAMPLES
=========
Below we show only the pattern and algorithm parts of the protocol
name, and we use placeholder algorithm names (DH, SIG, KEM).

A signature can be added using the same public-key type (XXsig), using
a different key type (XXc1+sig), or doubling the authentication with a
different key type (XXd1+sig).


XX_DH
  -> e
  <- e, ee, s, es
  -> s, se

XXsig_DH+SIG
  -> e
  <- e, ee, s, siga
  -> s, siga

XXc1+sig_DH+1+SIG
  -> e
  <- e, ee, s1, sig1
  -> s1, sig1

XXd1+sig_DH+1+SIG
  -> e
  <- e, ee, s, s1, es, sig1
  -> s, s1, se, sig1


Similarly with KEMs:


X1X1_DH
  -> e
  <- e, ee, s
  -> es, s
  <- se

X1X1skem_DH+KEM
  -> e
  <- e, ee, s
  -> skem, s
  <- skem

X1X1c1_skem_DH+1+KEM
  -> e
  <- e, ee, s1
  -> skem1, s1
  <- skem1

X1X1d1_skem_DH+1+KEM
  -> e
  <- e, ee, s, s1
  -> es, skem1, s, s1
  <- se, skem1


The initiator and responder can use different signature algorithms:


XK1(s, rs):
  <- s
  ...
  -> e
  <- e, ee, es
  -> s, se


XK1+c1+sigi+c2+sigr_DH+1+SIG+2+SIG
  <- s2
  ...
  -> e
  <- e, ee, sig2
  -> s1, sig1



Sigs, KEMS, and DH can all be used together:

XK_DH
  <- s
  ...
  -> e, es
  <- e, ee
  -> s, se

XK+c1+sigi+c2+skemr_DH+1+SIG+2+KEM
  <- s2
  ...
  -> e, skem2
  <- e, ee
  -> s1, sig1


Adding hybrid PQ forward secrecy just means "doubling" with an ephemeral PQ KEM:


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

IK+d1+ekem_DH+1+KEM
  <- s
  ...
  -> e, e1, es, s, ss
  <- e, ee, ekem1, se


But you could also switch to KEMs entirely:


NK_DH
  <- s
  ...
  -> e, es
  <- e, ee

NKkem_KEM
  <- s
  ...
  -> e, skem
  <- ekem


Trevor