Date: Sat, 06 Feb 2021 01:15:12 +0000
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
Precedence: list

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