[MLS] A different way to do key exchange

Phillip Hallam-Baker <phill@hallambaker.com> Wed, 28 February 2018 22:50 UTC

Return-Path: <hallam@gmail.com>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost []) by ietfa.amsl.com (Postfix) with ESMTP id E9E1E126FDC for <mls@ietfa.amsl.com>; Wed, 28 Feb 2018 14:50:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Status: No, score=-2.099 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] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
Received: from mail.ietf.org ([]) by localhost (ietfa.amsl.com []) (amavisd-new, port 10024) with ESMTP id GcLmvoTiSOtr for <mls@ietfa.amsl.com>; Wed, 28 Feb 2018 14:50:21 -0800 (PST)
Received: from mail-oi0-x230.google.com (mail-oi0-x230.google.com [IPv6:2607:f8b0:4003:c06::230]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 71459126FB3 for <mls@ietf.org>; Wed, 28 Feb 2018 14:50:21 -0800 (PST)
Received: by mail-oi0-x230.google.com with SMTP id b8so3062112oib.11 for <mls@ietf.org>; Wed, 28 Feb 2018 14:50:21 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:from:date:message-id:subject:to; bh=XarE2ci7Pp+WS8iTiS+mQAPQ4d3aWcB6YIZYDkcJ7Tw=; b=NdVXWa5kUWxcD/n3L3wduysjZMN3krlSC2WiwbMcLXjofiosQLDZYzbD7RGalK+Gb/ +/xP08f/4n5u42QZDOQFIjvfqPxYytkqqtUUcJhe7cgy43TuXyBaJYcu5MpawufqhiDU 9rJAHE4E5eHUzehKQPutkW163IsXXYa+qB6y9iIEG84waGN8KPCjTrwpXO7uhH5fWTMU 41pybrnN38o++bJSvRD3XGKxVVOfWx8c39DzWMjSPi3xHvyc+I2qQ9p8oHraigrUrq4h JAEUrPp/FTvc3yiAdS/h9zH82S40JXVhgiT+kRmP5JVnVuMtVGmfArvWlxpz2RDlSacE ww/g==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:from:date:message-id:subject :to; bh=XarE2ci7Pp+WS8iTiS+mQAPQ4d3aWcB6YIZYDkcJ7Tw=; b=RmdvG5sX8v0iv5+0jMlCmZaej2hf7Rzac2gSu07YV7R7r+NmDLstBia883vyT0ktR7 u5DFp/6bqjcoz+6p1zLqsJPNg2j52ES/xjv9yV3UgFnpmoqx4OcT6JXDUh5IjBoI1DbC WOJVvENRjoCwk3/7y/CwF5rDYr01aiK6VvtdCcOqpAvQsvU6K4QrHx3TGKKkDv7F7n8p 8Mc7DEz8tTk6JCpSquMyChC6FypfQ9lq74/CacE10NAQZ99WJ7Ecy9u7OJ/xWuJy36/E XDVrZmq6781XilvluzzUOUtWDNl+f1d63VJkxDeV8TQrogIAETcNehfecJIQH7BAlWri 6+oA==
X-Gm-Message-State: APf1xPA8yz390XOZ6HGKz8dY86nwxP+TxHJFLgyAUx2ctkouGz3rwi0v UZ4pdhtPgZYTYpe1H1jRRS956NubT8hPnY++UZz1zg==
X-Google-Smtp-Source: AG47ELu2HkUSmwZPwwBqWl04bOM85Jx9y5b7jV3hyzTv7BZq5yxBaDm8qXRd1+W/gfBRzrGRZLKo6nOCkxiV5sCy4aU=
X-Received: by with SMTP id b11mr11112089oif.36.1519858220188; Wed, 28 Feb 2018 14:50:20 -0800 (PST)
MIME-Version: 1.0
Sender: hallam@gmail.com
Received: by with HTTP; Wed, 28 Feb 2018 14:50:19 -0800 (PST)
From: Phillip Hallam-Baker <phill@hallambaker.com>
Date: Wed, 28 Feb 2018 17:50:19 -0500
X-Google-Sender-Auth: mlSesIudOBnJjxH7vA0YKhtPGdw
Message-ID: <CAMm+Lwi3ojHHnWT4DDk+F-+3Mjmryg=-UBzGaE1Drt1tg2rrKw@mail.gmail.com>
To: mls@ietf.org
Content-Type: multipart/alternative; boundary="001a113cd28452d04d05664d9118"
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/ttJuzR3qXRA8kE3MnmODwM2Rb-8>
Subject: [MLS] A different way to do key exchange
X-BeenThere: mls@ietf.org
X-Mailman-Version: 2.1.22
Precedence: list
List-Id: Messaging Layer Security <mls.ietf.org>
List-Unsubscribe: <https://www.ietf.org/mailman/options/mls>, <mailto:mls-request@ietf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/mls/>
List-Post: <mailto:mls@ietf.org>
List-Help: <mailto:mls-request@ietf.org?subject=help>
List-Subscribe: <https://www.ietf.org/mailman/listinfo/mls>, <mailto:mls-request@ietf.org?subject=subscribe>
X-List-Received-Date: Wed, 28 Feb 2018 22:50:25 -0000

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

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

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.