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

Tony Arcieri <bascule@gmail.com> Tue, 05 February 2019 20:05 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 4AA5013120B for <cfrg@ietfa.amsl.com>; Tue, 5 Feb 2019 12:05:20 -0800 (PST)
X-Virus-Scanned: amavisd-new at amsl.com
X-Spam-Flag: NO
X-Spam-Score: -1.998
X-Spam-Level:
X-Spam-Status: No, score=-1.998 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, URIBL_BLOCKED=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 J_j6kHGXatnK for <cfrg@ietfa.amsl.com>; Tue, 5 Feb 2019 12:05:18 -0800 (PST)
Received: from mail-ot1-x32e.google.com (mail-ot1-x32e.google.com [IPv6:2607:f8b0:4864:20::32e]) (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 007E4130EEC for <cfrg@irtf.org>; Tue, 5 Feb 2019 12:05:17 -0800 (PST)
Received: by mail-ot1-x32e.google.com with SMTP id v23so7924339otk.9 for <cfrg@irtf.org>; Tue, 05 Feb 2019 12:05:17 -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=/w3hUrJ0cmuMu9ysem8LjzgwZ7vLf3ljjTpE16OsxTU=; b=uZD724QBaEsD6ll8ue0igJ0jROwugAKNBXvSkveNSPWAEDUB7dRBSMRKk/xsSKBlEO KeCY03T7Yfo2jJgzNVuNpbqSs2zYpg7D4CickkF5C6iTEQaJmcKQqkskhd1XNeVzAk15 VSqAEW+LnFSpdLpH5lwBugB6hIuD55rTx2FhZu4CEyTv7RK6+EA6UdofOdrLS6onhCoA n3nWhmWyW06WumUIYT9Sn2+L/13tkwKN9GK61vu3+UaBqiF9TXTN/2m4yk6CzrrJ5lwT en4Umqt1iB94DJjpcF6k6nW1z3dci514rmZyERoPdwptTidjxHHlHb3jFBtlcgHsrLFx YbWg==
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=/w3hUrJ0cmuMu9ysem8LjzgwZ7vLf3ljjTpE16OsxTU=; b=jSYOhHlWRP8JN7t/qIhOPVJF2Fa928XxKRArUHWQbiIFJMjN0kn52i+gjnjfgHyiIr bS+IiEQyvei/6VKwctRVGl0zYa9BWNXxxbWrJVuEcD4tcUMJJzt3PfJaDF7Dqcp+yEHe mbWt0LKPRKizpF764XNHFYdcyBvAjj2FBIylzVQ1Z7q1JuN8myGvOD2opG9BzW4IaQ8M e2md/AjnkC7/Qilp+6pErqFB/rdGr/cACPJWB0g1gOn5fyyAEx4PZrFZUPRd5EAJN3NU YqBUkW0d4HtzmN5VWz6mopn9zvvjsa4GomM5/5v0nNPjOtZ8U8dQo13fHm6tp9Ww0Jz0 3XYA==
X-Gm-Message-State: AHQUAuaKjkyR7d0grLzGvb+9if/o7aXJfcc1XmARWfJgYdipsKuNvt5T NW7vfS8gvE4nKe+69bG2+DwxtKG3m3Er6FJaQo8=
X-Google-Smtp-Source: AHgI3IYNXuSEPCBTBsIx97YStRnaGXx/ydYtU9/RELdo0/lI3tYUUmCtD1U35Q5Zv+4G4INMOsKbdU8+jZnzOeyWjTw=
X-Received: by 2002:aca:ba02:: with SMTP id k2mr3659158oif.177.1549397116710; Tue, 05 Feb 2019 12:05:16 -0800 (PST)
MIME-Version: 1.0
References: <CAL02cgT3ZdpkH6otptjXavDMhXrJFGWAD5DqL1+nJeheWsmQgw@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF501D8AAC1@XMB116CNC.rim.net> <CAHOTMVJCecMBeXfag6h9Ag2ZhkF43HC5Sa3k6J+TGmSCFWj9nw@mail.gmail.com> <810C31990B57ED40B2062BA10D43FBF501D8AB74@XMB116CNC.rim.net>
In-Reply-To: <810C31990B57ED40B2062BA10D43FBF501D8AB74@XMB116CNC.rim.net>
From: Tony Arcieri <bascule@gmail.com>
Date: Tue, 5 Feb 2019 12:05:03 -0800
Message-ID: <CAHOTMV+hTWi81ahecQytpsoqnK8tQSAB1r5_rjDCfemr-qhDuA@mail.gmail.com>
To: Dan Brown <danibrown@blackberry.com>
Cc: Richard Barnes <rlb@ipv.sx>, CFRG <cfrg@irtf.org>
Content-Type: multipart/alternative; boundary="000000000000c1f7b405812b20b3"
Archived-At: <https://mailarchive.ietf.org/arch/msg/cfrg/9nolzhBEE_7hs09zKjn0Xkjut5U>
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 20:05:20 -0000

On Tue, Feb 5, 2019 at 11:38 AM Dan Brown <danibrown@blackberry.com> wrote:

> Hmm, I thought that this question was about X25519, but now it seems to be
> about EdDSA (Ed25519)?
>

Correct, where the original question was about D-H (X25519), Ed25519-BIP32
describes a similar scheme based on addition instead of scalar
multiplication, but in this case, for the purpose of signatures.

The basic idea is the same though, and underneath both schemes are
"Curve25519", with Ed25519-BIP32 using the "edwards25519" (RFC 8032
terminology) form. You could implement an Ed25519-BIP32 like scheme in
terms of X25519, or vice versa, but you will encounter the same problems.


> I see that BIP32 talks about updating the “after hash” private key? Is
> such modification the key generation generally considered compliant to CFRG
> spec RFC 8032?
>

This is indeed a big problem. I'm not going to attempt to play RFC lawyer,
but rather just say that in practice no Ed25519 library provides any of
this in the public API. In practice what I've seen, over and over again in
codebases where people try to extend Ed25519 with these features, is they
take the code from ed25519.c/go/etc, make the private APIs public, and muck
around with it at an extremely low level, sometimes just naively removing
clamping ("what is this for?"), or clamping repeatedly and therefore losing
key strength.

Without something like Ristretto, I'm not sure it's *possible* to define a
safe API that would allow an RFC 8032-compliant Ed25519 signer to derive a
unique private scalar based upon some agreed upon protocol which the
verifier can also do offline without coordination from the signer, in such
a way that is *misuse resistant* and "pluggable", i.e. not coupled to a
particular key derivation / blinding scheme.

Even if it were possible, I still don't think it's a good idea, and that's
kind of a shame, because it means Ed25519 signatures aren't composable in a
way, say, ECDSA signatures over a curve of prime order are, such as in the
original "BIP32" (which is used in conjunction with secp256k1).

-- 
Tony Arcieri