Return-Path: <bitcoin-dev@wuille.net>
Received: from fraxinus.osuosl.org (smtp4.osuosl.org [140.211.166.137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 62F93C013A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  6 Feb 2021 01:15:25 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by fraxinus.osuosl.org (Postfix) with ESMTP id 4AD9586C20
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  6 Feb 2021 01:15:25 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
Received: from fraxinus.osuosl.org ([127.0.0.1])
 by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id nA_MoF66bIFO
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  6 Feb 2021 01:15:23 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.7.6
Received: from mail-40133.protonmail.ch (mail-40133.protonmail.ch
 [185.70.40.133])
 by fraxinus.osuosl.org (Postfix) with ESMTPS id 116A786B96
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  6 Feb 2021 01:15:23 +0000 (UTC)
Date: Sat, 06 Feb 2021 01:15:12 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=wuille.net;
 s=protonmail2; t=1612574119;
 bh=64l8ZtPA1+AupHARZELB8uTTI6P/wbFOc2+YyQ4qhUw=;
 h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From;
 b=EClJQtDFVFgeIWxu5KnXi1boDiPx629WnHZ0dqnmY6y253xC/iPxOcjd5b4tLqQa7
 YhBCIYe+s+nYglqGpE0fE1CdZyK8aUhEgsXZquTr7ML1ZvqA3NMjDoOUjn8bvDZwDN
 1XhEfFgJ3hGT4gPzRkN87mnpdPxsgQQPEJs9G3X8nwFq/NH0UIIupMTybOQUy37yrl
 Szl+ywCTtFIjcEcOxQTa05jnoScM4/loy9CWXrCY/DCU7YX8AGqbIj9bdIJEdK/mRU
 UE0WfK9aloAlQ8A9BT0ce1Izz86cMBDVmIcM8uLwa6JSKjHTKylpr5BDmNQkDK0VjU
 +CaQhJWxELnxQ==
To: Dr Maxim Orlovsky <orlovsky@protonmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: Pieter Wuille <bitcoin-dev@wuille.net>
Reply-To: Pieter Wuille <bitcoin-dev@wuille.net>
Message-ID: <mCGqNxZZgiKEO8gbRcHFUxcU5fGBMWMfkJdapM2Nuhe0gemmqXRfnyqqaRY70UFea1udvQe0LIYt9Ps3lsgDArVHlfeMOWacXqZ7ZiGzMTU=@wuille.net>
In-Reply-To: <D962F4E0-E10F-433D-BFC9-3462A8A9CF7A@protonmail.com>
References: <D962F4E0-E10F-433D-BFC9-3462A8A9CF7A@protonmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures &
	decentralized identity
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Sat, 06 Feb 2021 01:15:25 -0000

On Friday, February 5, 2021 9:51 AM, Dr Maxim Orlovsky via bitcoin-dev <bit=
coin-dev@lists.linuxfoundation.org> wrote:

> Hi,
>
> Background
>
> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>
> Had a discussion last night in Bitcoin Core IRC with Peter Wuille on diff=
erent topics regarding key derivations, security, key tweaks in context of =
Schnorr signatures & Taproot. Would like to share some action points and pl=
ans that emerged from there:
>
> 1.  There is a real need for BIP-43 based new BIP with a new purpose fiel=
d for keys used in Schnorr signatures. Peter will not do it (he is not very=
 much interested in spending his time on wallet-level stuff), so someone el=
se should.
> 2.  Keys used in Schnorr signatures MUST NEVER BE used in ECDSA signature=
s, otherwise there is a risk of private key leak via correlation attack. Th=
is is rationale behind N1.

Hi Maxim,

thanks for bringing up this discussion here. I'd like to clarify a few thin=
gs though, as I think the above is formulated far too strongly.

There are two issues here: (1) reasons to avoid reusing the same key for pr=
ivacy reasons, and (2) reasons to avoid using related keys for cryptographi=
c reasons. And in practice, solutions to the first (which we already need, =
unrelated to Taproot/Schnorr) mean the second is largely moot.


# Don't reuse keys for privacy/organizational reasons.

Reusing the same key in Bitcoin scripts - for use in distinct signature sch=
emes or not - should always be avoided. It has obvious privacy implications=
; I don't think this is controversial, and it's a problem that exists today=
, unrelated to Taproot. E.g. you don't want to reuse the same keys as both =
single-sig and participation in multisig.

My personal view here is that distinct standard derivation paths help with =
this in the simple cases, but they're not a full solution in the most gener=
al case. E.g. if you want to use one seed/root to participate in multiple s=
ets of multisig policies, you'll need some kind of index to assign to each =
anyway. For this reason in general I prefer solutions that explicitly track=
 what path is used for what.


# Don't use related keys for cryptographic reasons

There are some concerns to address here, but I want to make it clear there =
are no known attacks against usage of related keys across ECDSA and Schnorr=
, and I don't expect there will be. However, there is probably no proof for=
 this, and creating one may be tricky. On the other hand, the ecosystem (Bi=
tcoin, but also many other applications) has accepted ECDSA long ago, while=
 it had no security proofs whatsoever (and even the ones that exist now rel=
y on fairly unusual assumption; a proof for security of mixed Schnorr/ECDSA=
 usage would inherently need equally unusual assumptions too).

Now, as soon as a hardened derivation separates different uses there is no =
concern at all. So any solution for avoiding key reuse (section above) that=
 works by assigning (implicitly or explicitly) different hardened derivatio=
n paths (as BIP43 etc. do) to different uses implies there is never any con=
cern about related keys across Schnorr/ECDSA.

If the keys are not separated by a hardened step, it's more complicated. Lo=
oking at the different cases:

(1) Signing with related ECDSA keys (e.g. two unhardened child keys from th=
e same xpub)

- This is very common on BIP32 usage today, so hopefully it is secure! Tim =
Ruffing pointed me today to https://link.springer.com/chapter/10.1007/978-3=
-030-36938-5_8 whose abstract seems to indicate they prove this is actually=
 secure, but I don't know under what assumptions. Note that the comment the=
re about Schnorr not having this property does not apply to BIP340, because=
 it uses key-prefixed Schnorr.

(2) Signing with related Schnorr keys.

- I believe this is secure simply because BIP340 challenges commit to the p=
ubkey (key prefixing), and thus a signature on one shouldn't teach you anyt=
hing about others. A formal proof is probably a bit longer, but still trivi=
al to construct.

(3) The real question: signing with a Schnorr key that is related to an ECD=
SA key.

- I don't expect that this is easy to prove, but I have a very hard time im=
agining how it could be exploitable, given the use of domain-separated hash=
es. Aspects such as BIP340's key prefixing and the fact that Bitcoin sighas=
hes indirectly commit to the (set of) signing pubkeys make it even harder.


# TL;DR

* For privacy reasons, you should use separate keys/derivation branches for=
 different uses in all circumstances (duh).
* To stay within the realm of provably security it's advisable to make sure=
 ECDSA key and Schnorr keys use distinct hardened derivation steps.
* Even if you don't, you're really just back to the level of assurance we h=
ad about unhardened BIP32 ECDSA keys before a proof was known (which I thin=
k most people aren't even aware of).

Cheers,

--
Pieter