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

Tony Arcieri <> Mon, 04 February 2019 23:23 UTC

Return-Path: <>
Received: from localhost (localhost []) by (Postfix) with ESMTP id 1CAA612870E for <>; Mon, 4 Feb 2019 15:23:59 -0800 (PST)
X-Virus-Scanned: amavisd-new at
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, FREEMAIL_FROM=0.001, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-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 ghlSn_xH8xSA for <>; Mon, 4 Feb 2019 15:23:56 -0800 (PST)
Received: from ( [IPv6:2607:f8b0:4864:20::343]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by (Postfix) with ESMTPS id 88BAE12426E for <>; Mon, 4 Feb 2019 15:23:56 -0800 (PST)
Received: by with SMTP id g16so2787587otg.11 for <>; Mon, 04 Feb 2019 15:23:56 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=2s/xjjTJtmg3P6EPQXut1dZDx2M1MSZmN/sImloTRFw=; b=A8z+qWU8gamULZqBR469XhLojuuI7pj3Y+3vpw+za2bBHtR1JilvsoOtW8mAC3C8cg uMZ6J+P9ul+YY+/KufFKuVNm2nJfw8SXExhNvwdXMm8uj9Al94ErkXWJdFo+ZYtoZJWV T3dgj7h735iV0+w0h85mu6KsMb1769ctpcIrIgtinhu+6dOx4pj6puTWvc3G9jX9KsNc DwhQONv5ZKRc7zVLK1xh4xB09/GWw4dAD6yfgFRgsYf+nCoq2vn2lycxRJ3lKfK4Trmd RWoHemsHu9ed5kozlU5lIh3sp3C+ikimd0XOQ7BBCGSS260XpbAFrXaceju0RC+XfrGJ 9EjQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;; s=20161025; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc; bh=2s/xjjTJtmg3P6EPQXut1dZDx2M1MSZmN/sImloTRFw=; b=eUBxGw1Tpdm+Ej4S4cERocQlgHGNcuKRjGTtR4YJrD/docTtzWazm3VhhLt5oUDeqw P1XojYJJ5HIbvLxWpX1jMm/MUZ32vyS/TGuwldmJ89bqUtOzPZiB5Hd/NRiWwX0KIKAV kQxsGXQvJp1QLew1d9SvOIlaAMs4RtlcRN2CipDx7GfLbU6Y3wo/CpLqwOQbxPF3Lv1V kHQlf4hamJdo48B4o711trsRczGBD5QWlzEUK/ceSbTJVfVcL3gp4IttjHAMG+8NB77s 0aD69IHjexZgsYEU8a3Y97IdMbjekmtc7fLyJXaCT7pbKpq2O/U7jaqCETSdFgSWgKg6 5VGg==
X-Gm-Message-State: AHQUAuaqxqevzAUN/rCiIGjvvBJdFEahE+ety9j9KsZLbC/MorLiDUVY xf52vL6F0mwgrPPqvM6atVg38evAcMor34MlWc0=
X-Google-Smtp-Source: AHgI3IYLc90h5H2+3+pbZ/qqDy6Z4ZH1f+YNgEgOIZqqg4g42CWrL9nJjcU6lY4/c/v0SRz5LNa/26dE/iE+Mbz5eK0=
X-Received: by 2002:aca:bd41:: with SMTP id n62mr1013406oif.348.1549322635797; Mon, 04 Feb 2019 15:23:55 -0800 (PST)
MIME-Version: 1.0
References: <>
In-Reply-To: <>
From: Tony Arcieri <>
Date: Mon, 4 Feb 2019 15:23:44 -0800
Message-ID: <>
To: Richard Barnes <>
Cc: CFRG <>
Content-Type: multipart/alternative; boundary="000000000000596c00058119c9c7"
Archived-At: <>
Subject: Re: [Cfrg] Curve25519 lacks private/public homomorphism?
X-Mailman-Version: 2.1.29
Precedence: list
List-Id: Crypto Forum Research Group <>
List-Unsubscribe: <>, <>
List-Archive: <>
List-Post: <>
List-Help: <>
List-Subscribe: <>, <>
X-List-Received-Date: Mon, 04 Feb 2019 23:23:59 -0000

On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <> wrote:

> 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].)

Welcome to the party!

That is to say... this is a thorny problem which keeps coming up. The main
thing you might want to look at for an immediate stopgap is Tor's new V3
.onion addresses / hidden services design:

There have been other schemes proposed to address this problem using
blinding factors ala BIP32 non-hardened derivation. However those schemes
ran afoul of the issue you describe below, despite multiple attempts to
avoid it, and are vulnerable to key recovery attacks:

The explosion of complexity that arises from attempting to handle low order
points at the protocol level, even for such a comparatively simple protocol
as this, is what initially lead me to discover Mike Hamburg's work on Decaf
and vicariously the work of Henry de Valence et al on Ristretto:

> 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 is at least colloquially referred to as "clamping", and yes, the
complexity it glosses over is a huge problem for implementing more advanced
protocols on top of Curve25519. Here's a thread with more background (oh my
the cert is expired, how ironic):

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

It's a fundamental tradeoff of Edwards curves (of your above options I'd
call it "collateral damaged"). As Harry de Valence put it in a recent talk,
"Edwards curves are simpler... but they push complexity upwards into the

Some more discussion here (unfortunately this link isn't in

Per the curve's creator, it's intended for simple protocols like D-H and
signatures only.

(Why does the penultimate bit need to be set?)

My understanding is certain implementations of GF(2^255-19) field
arithmetic (including some of the reference ones, I believe? I don't have a
citation) as well as certain implementations of the Montgomery ladder
require this bit to be set.

> Do folks have other ideas for a "homomorphic" construction such as the
> above that would accommodate this quirk of Curve25519?

Ristretto elegantly solves these problems, and provides a prime order group
abstraction which eliminates the incidental complexity of cofactors / low
order groups which would otherwise get pushed into the protocol layer.

I believe the balls are in motion to publish a draft soon which the CFRG
can potentially select as a working group item.

Tony Arcieri