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

Richard Barnes <rlb@ipv.sx> Mon, 04 February 2019 23:28 UTC

Return-Path: <rlb@ipv.sx>
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 284D412870E for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 15:28:33 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -0.052
X-Spam-Level:
X-Spam-Status: No, score=-0.052 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, DKIMWL_WL_MED=-0.142, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, HTML_MESSAGE=0.001, HTTPS_HTTP_MISMATCH=1.989, RCVD_IN_DNSWL_NONE=-0.0001] autolearn=ham autolearn_force=no
Authentication-Results: ietfa.amsl.com (amavisd-new); dkim=pass (2048-bit key) header.d=ipv-sx.20150623.gappssmtp.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 Ay4kv55vDjry for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 15:28:30 -0800 (PST)
Received: from mail-ot1-x342.google.com (mail-ot1-x342.google.com [IPv6:2607:f8b0:4864:20::342]) (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 6E56A12426E for <cfrg@irtf.org>; Mon, 4 Feb 2019 15:28:30 -0800 (PST)
Received: by mail-ot1-x342.google.com with SMTP id 32so2788535ota.12 for <cfrg@irtf.org>; Mon, 04 Feb 2019 15:28:30 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc; bh=zzC+OMIoY4SrcgCOlAe7dPAgyqKKDFHgSm8pFa5h6+4=; b=Q8GhkG943ZqZF+y72Nh8LlgyX59QcIsSDoxl1zUIFW6ULfaWOOdR4G8K6Bdm1DMgbG 86akfTcr53+nVqNp3YaIfbHqdr+d5iwtarUlrFY+zPLsFgsdgx6I6asCElPNeEt/bRbH tfV/nxBWWVbMwiHY/qhmN1KXoy/IqikMSrdXwzXiTAtoNpwkO/G9zVVMyBjjfUnU/X9y 8e26v8tlrYTU+tUwNcX06K8wcpYGkPBEZOyP2Kgb+GcR0M3H2PXOcsBqx2X0gOUe3qlB Y2cJd5CvUlol6W+nasPwCyKkkO7sOWVlT4ukdRImePO8dQaWQbs12FkmYcyfPNsvyPLd ES4A==
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=zzC+OMIoY4SrcgCOlAe7dPAgyqKKDFHgSm8pFa5h6+4=; b=JPW75+/WbtuV39cT4Jfl+4FSvIBdrAN8NEFjMyqGgjtjXiww0edDVnsHCV8eObHHP4 01Qa7LdCXC20/9qQMN7C5HIgHeIWShakuM0ZSMaCYq9E+b21EQCSgO8sHYTd3qGG0joY t5VROLuHAIpxRYufiXEzDFSFC4M+yWgrwmo1BAlxStpi+UKgcXt4HZ3FWB6Z9+W+yZWg gfW0qB6aFtF8i1K4mKDdgdai1pUKCq4c+6uVtFulXSprY1bKdAGb0UHVbk4UgI80LlW3 hNclrnc8DDZmYaugKhhPrd2W6C/REOxzFKVSLIykJ16XNPHSBCUz3RXHyaDTM1ccdam4 dtBQ==
X-Gm-Message-State: AHQUAuaSU+HlhLDqUkBthmby6PrENoZMK6AA7ySNerwqnLiTs6I0Rd8v 1qO7VFeK8AiUP4djUjz3KpS5CKxmmML0Y5rI5jedxQQHLT0=
X-Google-Smtp-Source: AHgI3IZGs9Py/eEAqaeUO3bZekoatezZJ0Lwo5RwIVKbY1+x4gUxe/QBKIs/X+LbIjzIezAm5TcSAdLPetFIqaA3VKM=
X-Received: by 2002:aca:f18:: with SMTP id 24mr954338oip.310.1549322909651; Mon, 04 Feb 2019 15:28:29 -0800 (PST)
MIME-Version: 1.0
References: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com> <CAHOTMV+oPWYew0-SF7fFwPnMXyu8aHBMvARv2ZNRma9sTnqvvA@mail.gmail.com>
In-Reply-To: <CAHOTMV+oPWYew0-SF7fFwPnMXyu8aHBMvARv2ZNRma9sTnqvvA@mail.gmail.com>
From: Richard Barnes <rlb@ipv.sx>
Date: Mon, 4 Feb 2019 18:28:11 -0500
Message-ID: <CAL02cgSkk0Y8g-kdqzjL2wp37n1Fg6fXe3QEL0tki7U8V+PG1A@mail.gmail.com>
To: Tony Arcieri <bascule@gmail.com>
Cc: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000ac2dff058119d9c6"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/w71T7ZBg1pspgdVrfA-AJNsHy5k>
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:28:33 -0000

Thanks, Tony.  In parallel, George Tankersley pointed me toward the
ristretto work as well.  There is an Internet-Draft now:

https://datatracker.ietf.org/doc/draft-hdevalence-cfrg-ristretto/

Given all this, seems like it could be something worthwhile for this group
to look at!

--Richard

On Mon, Feb 4, 2019 at 6:23 PM Tony Arcieri <bascule@gmail.com> wrote:

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