Subject: Re: [MLS] A different way to do key exchange

From: "Katriel Cohn-Gordon" <[email-masked]>
Date: Thu, 01 Mar 2018 10:42:16 +0000

Hi,

Thanks for the comment! The two party protocol you describe is pretty
close to MQV, and the three party version is fairly close to Burmester-
Desmedt though with authentication in the exponent.
The challenge here is that to compute that three-way key in the obvious
manner, you need to do a round robin among all participants: A
broadcasts a value, then B raises it to their private key and
rebroadcasts it, then C and so on. This unfortunately doesn't work if
any party is offline. We tried for a little while to figure out a way to
make BD asynchronous, but without much success. It'd be great if we
could though!
K

On Wed, 28 Feb 2018, at 10:50 PM, Phillip Hallam-Baker wrote:
> 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.> 
> _________________________________________________
> MLS mailing list
> [email-masked]
> https://www.ietf.org/mailman/listinfo/mls

---

From: Phillip Hallam-Baker <[email-masked]>
Date: Thu, 1 Mar 2018 08:15:52 -0500

I see two separate use cases.

What I am currently building is a Confidential Document Control system in
which documents are encrypted under a single encryption key that
corresponds to a group of users. This is equivalent to a security label
TOP-SECRET/NOFORN or a project.

I can apply those static labels to synchronous communications as well. So
if Alice, Bob and Carol are members of the [email-masked] recryption
group, they can all decrypt the messages provided the key-server performs
its part of the key agreement protocol.

My protocol is end to end secure and allows people to be added or removed
from the group at any time. Compromise of the key server does not permit
decryption of any content unless at least one user key is also compromised.

The situation we are discussing here is one in which we do not have a
pre-arranged group. It is an ad hoc collection of people who come and go. I
don't see Round Robin as being impractical in this situation if the number
of participants is 20 or less.

One of the things I have noticed is that the academic literature on crypto
does an awful job of identifying what is a real world requirement and what
is not. And it is not just schemes being proposed that are useless because
they don't meet a real need. There are a lot of really useful approaches
that are dismissed because the academics are insisting on some requirement
that is actually irrelevant.

It is not just the cryptography that has to scale, the protocol has to
scale socially as well. Even IRC has the principle of a channel operator.

On Thu, Mar 1, 2018 at 5:42 AM, Katriel Cohn-Gordon <[email-masked]>
wrote:

> close to MQV, and the three party version is fairly close to
> Burmester-Desmedt though with authentication in the exponent.
>
> manner, you need to do a round robin among all participants: A broadcasts a
> value, then B raises it to their private key and rebroadcasts it, then C
> and so on. This unfortunately doesn't work if any party is offline. We
> tried for a little while to figure out a way to make BD asynchronous, but
> without much success. It'd be great if we could though!
>
> K
>
> exchange. Then we do a Diffie Hellman exchange. And if we want client side
> authentication, well blerghhh
>
>
> 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.
>
> 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.
>
> 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?
>
>
> 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).
>
> 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.
>
> 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.]
>
>
> involve Alice's credential {a, A} ?
>
> 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 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.
>
>
> 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.
>
> *_______________________________________________*
> MLS mailing list
> [email-masked]