[MLS] A different way to do key exchange

[Phillip Hallam-Baker <[e-mail]>]

Traditional TLS uses RSA Encryption and RSA signature to perform a key
exchange. Then we do a Diffie Hellman exchange. And if we want client side
authentication, well blerghhh


Why not just to a DH exchange?

let Alice's {private, public} key be {a, A}, Bob's be {b, B} etc.

A = g^a mod p
B = g^b mod p
etc

Assume we have a directory that maps Alice->A, Bob->B etc.

So using straight DH with mutual authentication, the mutually agreed key is
g^ab mod p. We calculate that as A^b mod p or B^a mod p.

[From this point on, I will drop the mod p]

This works, but it is not great because now all messages Alice sends to Bob
are encrypted under a single key. Yuk. We also have the problem that they
can be decrypted using Alice's key which she might not want.

If Alice doesn't need to authenticate herself to Bob, she can just generate
a per-message ephemeral {x, X} and use that instead. The mutual agreed key
is now g^xb. Alice uses a different x each time. And she can only decrypt
the message if she decides to explicitly create a decryption blob for
herself.

We could use this last exchange plus a HKDF key derivation for TLS with the
same properties as the original RSA exchange but more simply. It does not
give us PFS though, What if we want to get that with one exchange?


To get PFS, we are going to need to introduce some sort of nonce or
blinding factor on Bob's side. So lets generate another keypair {y, Y} and
this time we are going to ADD it to Bob's key so that the key agreement
value is g^x(b+y).

Alice knows x and calculates B^x . Y^x
Bob knows b, y and calculates either X^(b+y) or X^b . X^y

At this point we are applying Torben Pedersen's Distributed key generation
scheme. And it has wondrous properties. We can perform all the operations
on b in a HSM and perform the blinding factor calculation at the
application level. We can even split the private key between MULTIPLE HSMs.

[OK I did elide something here, you can add b+y in modular arithmetic, yes.
But it is modulo the subgroup size not the prime. This is p-1 for DH and
(p-1)/8 for our CFRG curves.]


OK so now what if we want to perform client side authentication and involve
Alice's credential {a, A} ?

Easy, the key agreement value is now g^(a+x)(b+y)


So here we have one key agreement function that lets us add in or remove
PFS according to whether or not we require it for a particular set of
messages. We can even turn PFS on in the middle of an existing conversation
or turn it off just by dropping the blinding factor out of the mix (or not).

Want three way key agreement?  g^(a+x)(b+y)(c+z)

Want it in ECC? yes, it all works in Ed25519 or Ed448. It will also work in
Curve 25519 and Curve 448 if someone can point me to a routine to perform
addition of two Montgomery points in the compressed representation.


The HSM compartmentalization could be a way to defeat the Spectre and
Meltdown attacks. I showed some of this in a preview of my RSA talk on this.

All I need is for the CPU manufacturer to provide us with an isolated core
to perform x25519 and x448 operations. The information from that core can
then be used to apply a blinding factor to crypto operations at the
application level.


There is a simple proof that this approach is secure if the underlying DH
scheme is.