Re: [Cfrg] Curve25519 lacks private/public homomorphism?

Dan Brown <danibrown@blackberry.com> Tue, 05 February 2019 17:20 UTC

Return-Path: <danibrown@blackberry.com>
X-Original-To: cfrg@ietfa.amsl.com
Delivered-To: cfrg@ietfa.amsl.com
Received: from localhost (localhost [127.0.0.1]) by ietfa.amsl.com (Postfix) with ESMTP id A0066124BAA for <cfrg@ietfa.amsl.com>; Tue, 5 Feb 2019 09:20:24 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.61
X-Spam-Level:
X-Spam-Status: No, score=-0.61 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=1.989, RCVD_IN_DNSWL_LOW=-0.7, SPF_PASS=-0.001, URIBL_BLOCKED=0.001] autolearn=ham autolearn_force=no
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 94qbvq60ud9z for <cfrg@ietfa.amsl.com>; Tue, 5 Feb 2019 09:20:22 -0800 (PST)
Received: from smtp-p02.blackberry.com (smtp-p02.blackberry.com [208.65.78.89]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ietfa.amsl.com (Postfix) with ESMTPS id DAE04130E92 for <cfrg@irtf.org>; Tue, 5 Feb 2019 09:20:21 -0800 (PST)
Received: from xct107cnc.rim.net ([10.65.161.207]) by mhs215cnc.rim.net with ESMTP/TLS/DHE-RSA-AES256-SHA; 05 Feb 2019 12:20:14 -0500
Received: from XCT198YKF.rim.net (10.2.25.6) by XCT107CNC.rim.net (10.65.161.207) with Microsoft SMTP Server (TLS) id 14.3.408.0; Tue, 5 Feb 2019 12:20:14 -0500
Received: from XMB116CNC.rim.net ([fe80::45d:f4fe:6277:5d1b]) by XCT198YKF.rim.net ([fe80::59f9:6b62:c489:7f43%13]) with mapi id 14.03.0415.000; Tue, 5 Feb 2019 12:20:13 -0500
From: Dan Brown <danibrown@blackberry.com>
To: Richard Barnes <rlb@ipv.sx>, CFRG <cfrg@irtf.org>
Thread-Topic: [Cfrg] Curve25519 lacks private/public homomorphism?
Thread-Index: AQHUvNgOFwu3M9YoVUKwftYRZJ/N2qXRccEw
Date: Tue, 5 Feb 2019 17:20:12 +0000
Message-ID: <810C31990B57ED40B2062BA10D43FBF501D8AAC1@XMB116CNC.rim.net>
References: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com>
In-Reply-To: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com>
Accept-Language: en-US, en-CA
Content-Language: en-US
X-MS-Has-Attach: yes
X-MS-TNEF-Correlator:
x-originating-ip: [10.65.160.251]
Content-Type: multipart/signed; protocol="application/x-pkcs7-signature"; micalg=SHA1; boundary="----=_NextPart_000_0167_01D4BD4D.23A22F70"
MIME-Version: 1.0
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/vzwFIYGpCBATOF3_WXHi3wRAbXs>
Subject: Re: [Cfrg] Curve25519 lacks private/public homomorphism?
X-BeenThere: cfrg@irtf.org
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <cfrg.irtf.org>
List-Unsubscribe: <https://www.irtf.org/mailman/options/cfrg>, <mailto:cfrg-request@irtf.org?subject=unsubscribe>
List-Archive: <https://mailarchive.ietf.org/arch/browse/cfrg/>
List-Post: <mailto:cfrg@irtf.org>
List-Help: <mailto:cfrg-request@irtf.org?subject=help>
List-Subscribe: <https://www.irtf.org/mailman/listinfo/cfrg>, <mailto:cfrg-request@irtf.org?subject=subscribe>
X-List-Received-Date: Tue, 05 Feb 2019 17:20:25 -0000

Hi Richard,

 

Could you not just add delta to the private key (instead of multiplying the private key)?  (Add [delta]G to the public key.)  

 

This seems to meet your four bullet points, though I did no follow-up reading.

 

Adding delta is certainly NOT a morphism of the DH group, though it is a morphism of the curve, etc., etc.  Maybe you need the group morphism property for a sophisticated reason that you forgot to list?

 

Anyway, if delta is small enough, say delta<2^200, there is little chance of disturbing the top bit.  (If some bottom bits are fixed, set the few bottom bits of delta to zero.)

 

By the way, it is not yet clear to me why these key “updates” would be “useful”.  (Either added or multiplied).

 

Best regards,

 

Dan

 

From: Cfrg <cfrg-bounces@irtf.org> On Behalf Of Richard Barnes
Sent: Monday, February 4, 2019 5:21 PM
To: CFRG <cfrg@irtf.org>
Subject: [Cfrg] Curve25519 lacks private/public homomorphism?

 

Hi CFRG,

 

I'm trying to work through whether the MLS working group can use Curve25519 in a particular way, and was wondering if folks here had any insights.

 

MLS has a case where it would be useful to be able to be able to implement the following:

 

- Given a DH key pair whose private key is held by one set of parties and public key by another

- Have a third party (holding only the public key) be able to generate a "delta" such that:

  - The holders the private key can use the delta to update the private key to a new value

  - The holders of the public key can use the delta to compute the corresponding new public key

 

That is, we're looking to use a certain homomorphism in the DH group action that translates a change in private key to a change in public key.  For example, with traditional ECDH, you could generate a random number that the private key holders could multiply with the private key, and the public key holders could just do a DH operation to multiply the public key by the delta.  (A sketch in Go here [1].)

 

When you try to do this with Curve25519 (or Curve448), however, you run into a problem: `k_list[31] |= 64`.  The X25519 function in RFC 7748 [2] ensures that the second-most-significant bit of a scalar private key is always set, but this bit is not necessarily set in the product of two such scalars.  In other words, there are scalars `ab` such that you can arrive at `abG` as the result of a DH computation, but never abG will never be a public key (since `X25519(ab, 9) != abG`).  The mapping from private keys to public keys is not a homomorphism with regard to addition or multiplication.

 

This means we're out of luck with regard to our delta scheme.  If the delta happens to result in a new private key with its penultimate bit unset, then it can't actually be used as a private key -- and there's no way for the delta-generating party to know this.

 

Is this surprising to people?  Is it a consequence of some property of Curve25519 that is good for security, or is it just collateral damage?  (Why does the penultimate bit need to be set?)  Do folks have other ideas for a "homomorphic" construction such as the above that would accommodate this quirk of Curve25519?

 

Thanks a lot,

--Richard

 

 

[1] https://play.golang.org/p/nyiRcJUDT-p <https://urldefense.proofpoint.com/v2/url?u=https-3A__play.golang.org_p_nyiRcJUDT-2Dp&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=hnuASub6WZC2yU-gN0ugWh-Kr8Pkiu8X95Nhs3Reebc&s=AO4-p_x3NlAk3S64sOFbVecbdF_UeI2GKxro-5gM2GM&e=> 

[2] https://tools.ietf.org/html/rfc7748#section-5 <https://urldefense.proofpoint.com/v2/url?u=https-3A__tools.ietf.org_html_rfc7748-23section-2D5&d=DwMFaQ&c=yzoHOc_ZK-sxl-kfGNSEvlJYanssXN3q-lhj0sp26wE&r=qkpbVDRj7zlSRVql-UonsW647lYqnsrbXizKI6MgkEw&m=hnuASub6WZC2yU-gN0ugWh-Kr8Pkiu8X95Nhs3Reebc&s=BXy82rs-JetAjAhHvyYL8QEgrl8r9nHj4f2ItnvPhWw&e=>