[noise] Multi-algorithm handshakes (a sketch)

[Justin Cormack]

I think it might help to break this up a little into more digestible
pieces, and maybe the notations can
be made cleaner.

signature and KEM are relatively clear as standalone modifiers. I do
wonder about the large number of
different types of signature and formats that are common (inc non
fixed length ones), so there are some
practicalities to consider there. I think splitting these out makes
sense, separately from doubled versions.
I am not sure we technically need the "1" modifiers on the s, kem, and
sig tokens, as you can work out
which they correspond to, but maybe there are some other clearer
notation options.

For doubled cases, I think I would rather if the deferred patterns
were called out explicitly rather than being
implicit. I wonder if it might make sense to define rules for
combining two patterns.

Justin





On 13 July 2018 at 07:08, Trevor Perrin <trevp at trevp.net> wrote:
> 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
> _______________________________________________
> Noise mailing list
> Noise at moderncrypto.org
> https://moderncrypto.org/mailman/listinfo/noise