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

Phillip Hallam-Baker <> Thu, 01 March 2018 13:16 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 8B21112E86D for <>; Thu, 1 Mar 2018 05:16:00 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, FREEMAIL_FORGED_FROMDOMAIN=0.25, FREEMAIL_FROM=0.001, HEADER_FROM_DIFFERENT_DOMAINS=0.25, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
Authentication-Results: (amavisd-new); dkim=pass (2048-bit key)
Received: from ([]) by localhost ( []) (amavisd-new, port 10024) with ESMTP id SivsHjLcYqKj for <>; Thu, 1 Mar 2018 05:15:57 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4003:c06::22f]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id C8FDF127735 for <>; Thu, 1 Mar 2018 05:15:54 -0800 (PST)
Received: by with SMTP id c18so4406720oiy.9 for <>; Thu, 01 Mar 2018 05:15:54 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc; bh=l/E0mdD3DBfJEUq57ORLTI0/akUTggDmWWruqt17SeE=; b=rH8VJFKierZ1oTdgfZoMGsuFkSu2gClZcZtRuPbanpsaPb8ikvgFWTSd+bnZt5+oQt ChUTDHTCwa/05ShPx14VfncI6VrAEXq1sETLOJkfFqd+yLyrnCsZMKsQI/u/T9YIzto1 2Tx6NvMTwCMMNYqADompcfeojFXVM4PlsSmghXIvklirOIvhdI10vCZ368xGKDUruhR5 dp3/M93EWwDZ2zNIabN7fNDBIy1vSdRuweEJr38WZLedaPioA4Be/31NE8dLahZ7htOx GmMuscavfLg2VFbCjQ8B60X+wGuyaRIon67ErCUfoGbbOIPir/uJyaeLFt2zTzdvHDLw T0AQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc; bh=l/E0mdD3DBfJEUq57ORLTI0/akUTggDmWWruqt17SeE=; b=RntGfe9bHFUq/IYpieG/MjoPtWEc9B0gEDVrvCuV7Z0TYPirYYYxdNesrwLa0utgzU eF8eupysQNBSt0uLUk6uPIRl1W2ODk0wPqe40/bfseJmXrsuk6f4Xd7p3QpWb6wwe2Ol RkuJ1paxA9lsmKxNrRmA34cmJndKsQru2HWZlgzMF+ux/siloQNGNBdRXdAerH9rAGga 9fJdBki6xwwYNVnmfzfJvgV/z57rWD8Wbe1BpQ4ZH7MZfV/MUKJehwpxvKjfmKTMasAr SD3HgwvhcTQ1ppqAJWREDmk1RM1Q43Uy2grmTK/ctjnIhBi3EcFt79dMCKiT5UVOW8LM FNmg==
X-Gm-Message-State: AElRT7EqcGy756JB+/3qaOz5RMy3RcUokA/kOgT2Dr3TAg40Ufu7HZB5 yro/psipWHToU2Dx53qF89WWMNeIowBavqDlXp4=
X-Google-Smtp-Source: AG47ELt2y4O3vPBjOoswpHhYSNWVloKa/d1t40CQENv3TTdLIqc+sioYyiBbjR81nqHvWYtKTA0xwPv2MSoYiQ/oxcQ=
X-Received: by with SMTP id n125mr1186933oia.26.1519910153744; Thu, 01 Mar 2018 05:15:53 -0800 (PST)
MIME-Version: 1.0
Received: by with HTTP; Thu, 1 Mar 2018 05:15:52 -0800 (PST)
In-Reply-To: <>
References: <> <>
From: Phillip Hallam-Baker <>
Date: Thu, 1 Mar 2018 08:15:52 -0500
X-Google-Sender-Auth: 4FS_Skw2ckZh1CSEqLQUdRM1rKE
Message-ID: <>
To: Katriel Cohn-Gordon <>
Content-Type: multipart/alternative; boundary="001a113de014cdf64b056659a8b3"
Archived-At: <>
Subject: Re: [MLS] A different way to do key exchange
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Messaging Layer Security <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Thu, 01 Mar 2018 13:16:03 -0000

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 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 <>

> 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