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

"Katriel Cohn-Gordon" <me@katriel.co.uk> Thu, 01 March 2018 10:42 UTC

Return-Path: <me@katriel.co.uk>
X-Original-To: mls@ietfa.amsl.com
Delivered-To: mls@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id 979FC12DA4F for <mls@ietfa.amsl.com>; Thu, 1 Mar 2018 02:42:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.699
X-Spam-Level:
X-Spam-Status: No, score=-2.699 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, 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: ietfa.amsl.com (amavisd-new); dkim=pass (1024-bit key) header.d=katriel.co.uk header.b=c69EN/Sy; dkim=pass (2048-bit key) header.d=messagingengine.com header.b=QDtWa1aN
Received: from mail.ietf.org ([4.31.198.44]) by localhost (ietfa.amsl.com [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id bsRUwGc8PF4W for <mls@ietfa.amsl.com>; Thu, 1 Mar 2018 02:42:17 -0800 (PST)
Received: from out5-smtp.messagingengine.com (out5-smtp.messagingengine.com [66.111.4.29]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id 7E0AC1276AF for <mls@ietf.org>; Thu, 1 Mar 2018 02:42:17 -0800 (PST)
Received: from compute6.internal (compute6.nyi.internal [10.202.2.46]) by mailout.nyi.internal (Postfix) with ESMTP id 9703B20D4E; Thu, 1 Mar 2018 05:42:16 -0500 (EST)
Received: from web3 ([10.202.2.213]) by compute6.internal (MEProxy); Thu, 01 Mar 2018 05:42:16 -0500
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=katriel.co.uk; h=content-transfer-encoding:content-type:date:from:in-reply-to :message-id:mime-version:references:subject:to:x-me-sender :x-me-sender:x-sasl-enc; s=mesmtp; bh=/n96+g5AbWEMrOnJbp1jrTTccG 2iQ2W4ngj9KG3pQHs=; b=c69EN/Syu5ogIwqxSYZVIgYoU58POBHp25FOU+Hq3I a5CMl5RkwyPKi1/35xQDfQaEl2K6Cz+qvVCdE8kprkUhQcKU9OzAJjyOTI5WmltG tO2uf+orokIWFKi3j3uf6mcytWESSJQMLflzLRPx7dBq/X62nspt3nVP0e2VwTRh Y=
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=content-transfer-encoding:content-type :date:from:in-reply-to:message-id:mime-version:references :subject:to:x-me-sender:x-me-sender:x-sasl-enc; s=fm2; bh=/n96+g 5AbWEMrOnJbp1jrTTccG2iQ2W4ngj9KG3pQHs=; b=QDtWa1aNYc3R4xC6H8DHy/ f/1XJGA6a3CB7x210OohNOG6KDChmp9wvAGoOGOXy8W181pscrrnuapmawcxZZXy c/jI7tBy4Ji/PgbzhVdzhujnx+addmC5H7IjD2UDIDm5JjRSTWZpASU/9YAidJsS Jlf4CI2m9aNaKDJUyjBHEwI3X1eq/k4eAdpqPBtWi8zLA0FoM8UJfW/8h4Fd7Ugl hGveAGXTcLF34VJzRNBjFvLFnqpjyuqzC4W+PM1BF6THKGML595KQmSydBBd9sgL Dq5Tdnv+z0t1cd2kkpD7dkw2vy+9osEIfN2mWgjI0s4RcoV2xzzpXe5OQOOclSLQ ==
X-ME-Sender: <xms:CNmXWpC2CZyo-dLgfHYCzhoooUn3Pz3P8jUjuSEEAp2Xry_so3o1JQ>
Received: by mailuser.nyi.internal (Postfix, from userid 99) id 696469E4E4; Thu, 1 Mar 2018 05:42:16 -0500 (EST)
Message-Id: <1519900936.1252177.1287608280.18488F31@webmail.messagingengine.com>
From: Katriel Cohn-Gordon <me@katriel.co.uk>
To: Phillip Hallam-Baker <phill@hallambaker.com>, mls@ietf.org
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: multipart/alternative; boundary="_----------=_151990093612521770"
X-Mailer: MessagingEngine.com Webmail Interface - ajax-b08ff009
In-Reply-To: <CAMm+Lwi3ojHHnWT4DDk+F-+3Mjmryg=-UBzGaE1Drt1tg2rrKw@mail.gmail.com>
Date: Thu, 01 Mar 2018 10:42:16 +0000
References: <CAMm+Lwi3ojHHnWT4DDk+F-+3Mjmryg=-UBzGaE1Drt1tg2rrKw@mail.gmail.com>
Archived-At: <https://mailarchive.ietf.org/arch/msg/mls/s21DDDUtk8AZvn7I64wthUegxwM>
Subject: Re: [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: Thu, 01 Mar 2018 10:42:21 -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
> MLS@ietf.org
> https://www.ietf.org/mailman/listinfo/mls