Date: Thu, 11 Feb 2021 14:38:57 +0000
To: Pieter Wuille <bitcoin-dev@wuille.net>
From: Dr Maxim Orlovsky <orlovsky@protonmail.com>
Reply-To: Dr Maxim Orlovsky <orlovsky@protonmail.com>
Message-ID: <5096768E-3A77-4CD8-AC22-105CA63152A7@protonmail.com>
In-Reply-To: <mCGqNxZZgiKEO8gbRcHFUxcU5fGBMWMfkJdapM2Nuhe0gemmqXRfnyqqaRY70UFea1udvQe0LIYt9Ps3lsgDArVHlfeMOWacXqZ7ZiGzMTU=@wuille.net>
References: <D962F4E0-E10F-433D-BFC9-3462A8A9CF7A@protonmail.com>
 <mCGqNxZZgiKEO8gbRcHFUxcU5fGBMWMfkJdapM2Nuhe0gemmqXRfnyqqaRY70UFea1udvQe0LIYt9Ps3lsgDArVHlfeMOWacXqZ7ZiGzMTU=@wuille.net>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures &
	decentralized identity
Precedence: list

Hi Pieter,

... and sorry for misspelling your name in my first e-mail :(

Thank you very much for all the clarifications; it=E2=80=99s good to have t=
hem sorted out and clearly structured. From what you wrote it follows that =
we still need to reserve a dedicated purpose (with new BIP) for BIP340 sign=
atures to avoid key reuse, am I right?

Kind regards,
Maxim

> On Feb 6, 2021, at 02:15, Pieter Wuille <bitcoin-dev@wuille.net> wrote:
>=20
>=20
> On Friday, February 5, 2021 9:51 AM, Dr Maxim Orlovsky via bitcoin-dev <b=
itcoin-dev@lists.linuxfoundation.org> wrote:
>=20
>> Hi,
>>=20
>> Background
>>=20
>> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
>>=20
>> Had a discussion last night in Bitcoin Core IRC with Peter Wuille on dif=
ferent topics regarding key derivations, security, key tweaks in context of=
 Schnorr signatures & Taproot. Would like to share some action points and p=
lans that emerged from there:
>>=20
>> 1.  There is a real need for BIP-43 based new BIP with a new purpose fie=
ld for keys used in Schnorr signatures. Peter will not do it (he is not ver=
y much interested in spending his time on wallet-level stuff), so someone e=
lse should.
>> 2.  Keys used in Schnorr signatures MUST NEVER BE used in ECDSA signatur=
es, otherwise there is a risk of private key leak via correlation attack. T=
his is rationale behind N1.
>=20
> Hi Maxim,
>=20
> thanks for bringing up this discussion here. I'd like to clarify a few th=
ings though, as I think the above is formulated far too strongly.
>=20
> There are two issues here: (1) reasons to avoid reusing the same key for =
privacy reasons, and (2) reasons to avoid using related keys for cryptograp=
hic reasons. And in practice, solutions to the first (which we already need=
, unrelated to Taproot/Schnorr) mean the second is largely moot.
>=20
>=20
> # Don't reuse keys for privacy/organizational reasons.
>=20
> Reusing the same key in Bitcoin scripts - for use in distinct signature s=
chemes or not - should always be avoided. It has obvious privacy implicatio=
ns; I don't think this is controversial, and it's a problem that exists tod=
ay, unrelated to Taproot. E.g. you don't want to reuse the same keys as bot=
h single-sig and participation in multisig.
>=20
> My personal view here is that distinct standard derivation paths help wit=
h this in the simple cases, but they're not a full solution in the most gen=
eral case. E.g. if you want to use one seed/root to participate in multiple=
 sets of multisig policies, you'll need some kind of index to assign to eac=
h anyway. For this reason in general I prefer solutions that explicitly tra=
ck what path is used for what.
>=20
>=20
> # Don't use related keys for cryptographic reasons
>=20
> There are some concerns to address here, but I want to make it clear ther=
e are no known attacks against usage of related keys across ECDSA and Schno=
rr, and I don't expect there will be. However, there is probably no proof f=
or this, and creating one may be tricky. On the other hand, the ecosystem (=
Bitcoin, but also many other applications) has accepted ECDSA long ago, whi=
le it had no security proofs whatsoever (and even the ones that exist now r=
ely on fairly unusual assumption; a proof for security of mixed Schnorr/ECD=
SA usage would inherently need equally unusual assumptions too).
>=20
> Now, as soon as a hardened derivation separates different uses there is n=
o concern at all. So any solution for avoiding key reuse (section above) th=
at works by assigning (implicitly or explicitly) different hardened derivat=
ion paths (as BIP43 etc. do) to different uses implies there is never any c=
oncern about related keys across Schnorr/ECDSA.
>=20
> If the keys are not separated by a hardened step, it's more complicated. =
Looking at the different cases:
>=20
> (1) Signing with related ECDSA keys (e.g. two unhardened child keys from =
the same xpub)
>=20
> - This is very common on BIP32 usage today, so hopefully it is secure! Ti=
m 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 actual=
ly secure, but I don't know under what assumptions. Note that the comment t=
here about Schnorr not having this property does not apply to BIP340, becau=
se it uses key-prefixed Schnorr.
>=20
> (2) Signing with related Schnorr keys.
>=20
> - I believe this is secure simply because BIP340 challenges commit to the=
 pubkey (key prefixing), and thus a signature on one shouldn't teach you an=
ything about others. A formal proof is probably a bit longer, but still tri=
vial to construct.
>=20
> (3) The real question: signing with a Schnorr key that is related to an E=
CDSA key.
>=20
> - I don't expect that this is easy to prove, but I have a very hard time =
imagining how it could be exploitable, given the use of domain-separated ha=
shes. Aspects such as BIP340's key prefixing and the fact that Bitcoin sigh=
ashes indirectly commit to the (set of) signing pubkeys make it even harder=
.
>=20
>=20
> # TL;DR
>=20
> * For privacy reasons, you should use separate keys/derivation branches f=
or different uses in all circumstances (duh).
> * To stay within the realm of provably security it's advisable to make su=
re 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=
 had about unhardened BIP32 ECDSA keys before a proof was known (which I th=
ink most people aren't even aware of).
>=20
> Cheers,
>=20
> --
> Pieter