[Cfrg] Curve25519 lacks private/public homomorphism?

Richard Barnes <rlb@ipv.sx> Mon, 04 February 2019 22:21 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 3F632127598 for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 14:21:47 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -2.041
X-Spam-Level:
X-Spam-Status: No, score=-2.041 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, 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 8yn127jITNW2 for <cfrg@ietfa.amsl.com>; Mon, 4 Feb 2019 14:21:44 -0800 (PST)
Received: from mail-ot1-x32a.google.com (mail-ot1-x32a.google.com [IPv6:2607:f8b0:4864:20::32a]) (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 84E0C1200D7 for <cfrg@irtf.org>; Mon, 4 Feb 2019 14:21:44 -0800 (PST)
Received: by mail-ot1-x32a.google.com with SMTP id n8so2602384otl.6 for <cfrg@irtf.org>; Mon, 04 Feb 2019 14:21:44 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=ipv-sx.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=C9XCl0a8Jw14E8kh4yKA4glpGI+I9rt52Khb947m2UM=; b=TdBA3Bxnj+WQ5TFBj4XTOSY8kM9dG1dcaJ5ttC8uFWyxQQmaFtBud5MIGzSryKqF+o sp8vzqqOrlXxt64ggNZGj+BuMjGj/B0jYcubjy2EMM8UsGjDfhtGLpoDmJG0h9lf+P+B /ZFRTl0oOr/O/02Gch/njNFAKXIAlsx4GJYxt0OlmU9ECCETflo3VhdI0UCt5Qk2uX6F t6ycGddAgFFpL2h+mZ65yCokQgAxlZetwaEjQ8u52KkSxGTBSb3UKRq4cuy0ws9m5BZi vFQaLfEQ21/bVk9uHvn56MbQYlVwjpsm5pSJqrVmaZMol7ukTQ89R2xqB7SKxBmEz4AE 0wKw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=C9XCl0a8Jw14E8kh4yKA4glpGI+I9rt52Khb947m2UM=; b=US7QzOphhvmzxEBWjYM3zm1BkJEYE1+WPBsf+GtQfpKacf64yNvyYcA+xbclAB754+ ujA57SwDrULPAX3n96131yPr0N2RMFSpyESUJCj596TBMkvJyUSnhAR0VZ7gLOUGZXFg xHEMoLuQFKnTHl/IxEqzbK7L4C+eB6uu50IxzRg1nTF2TsDZ4kjsfgNRmROnp0F/eOqL 5cRFZDbCSqGSyP5JKUKeVJsu0+wXaesI1h6jTVNuY3D9MJI1P2sJD3jW4t9R6Muyzp6W /M67pOgpyOcTNheQG0/350xL/lHJMQ+eKkJJs3GDFz8vayxoxt8h5JJIMjJb9Z/IMi3X QXZg==
X-Gm-Message-State: AHQUAuYR36f7OJuxARUyjC5QOPlSp8nJSZqeJv1n7iuE10gji9iXEE/G p1ivmlqm1RFvy3Y9VB7rw+jx/W63Avr2O+P4oswZwy23JPs=
X-Google-Smtp-Source: AHgI3IZlED+Wf82lItrQvVw9dIiXrBpztSLtjoDCTUx/Xz4isH7rPV113jKXdyVQNYdW9fegAB8Vh8qpzQfe9MUOI44=
X-Received: by 2002:a9d:3f34:: with SMTP id m49mr875459otc.23.1549318903499; Mon, 04 Feb 2019 14:21:43 -0800 (PST)
MIME-Version: 1.0
From: Richard Barnes <rlb@ipv.sx>
Date: Mon, 4 Feb 2019 17:21:24 -0500
Message-ID: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com>
To: CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000e32852058118ea75"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/JVg30dldjr4pcwZ1perpA1k-OGQ>
Subject: [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 22:21:47 -0000

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
[2] https://tools.ietf.org/html/rfc7748#section-5