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

Tony Arcieri <bascule@gmail.com> Mon, 04 February 2019 23:23 UTC

Return-Path: <bascule@gmail.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 1CAA612870E for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 15:23:59 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level:
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: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=gmail.com
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 ghlSn_xH8xSA for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 15:23:56 -0800 (PST)
Received: from mail-ot1-x343.google.com (mail-ot1-x343.google.com [IPv6:2607:f8b0:4864:20::343]) (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 88BAE12426E for <cfrg@irtf.org>; Mon, 4 Feb 2019 15:23:56 -0800 (PST)
Received: by mail-ot1-x343.google.com with SMTP id g16so2787587otg.11 for <cfrg@irtf.org>; Mon, 04 Feb 2019 15:23:56 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; 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; d=1e100.net; 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: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com>
In-Reply-To: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com>
From: Tony Arcieri <bascule@gmail.com>
Date: Mon, 4 Feb 2019 15:23:44 -0800
Message-ID: <CAHOTMV+oPWYew0-SF7fFwPnMXyu8aHBMvARv2ZNRma9sTnqvvA@mail.gmail.com>
To: Richard Barnes <rlb@ipv.sx>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000596c00058119c9c7"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JMvzxKsE6YAcKf7112OeRQuWxMo>
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: Mon, 04 Feb 2019 23:23:59 -0000

On Mon, Feb 4, 2019 at 2:21 PM Richard Barnes <rlb@ipv.sx> 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!

https://mailarchive.ietf.org/arch/msg/cfrg/lM1ix9R-0tVzhZorQhQlKvi4wpA

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:

https://trac.torproject.org/projects/tor/ticket/8106

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:

https://forum.web3.foundation/t/key-recovery-attack-on-bip32-ed25519/44

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:

https://ristretto.group/


> 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 moderncrypto.org cert is expired, how ironic):

https://web.archive.org/web/20180904062814/https://moderncrypto.org/mail-archive/curves/2017/000858.html


> 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
protocol".

Some more discussion here (unfortunately this link isn't in archive.org):

https://moderncrypto.org/mail-archive/curves/2017/000891.html

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