Re: [bitcoin-dev] BIP32/43-based standard for Schnorr signatures & decentralized identity

[Dr Maxim Orlovsky <orlovsky@protonmail.com>]

Hi Pieter,

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

Thank you very much for all the clarifications; it’s good to have them 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 signatures to avoid key reuse, am I right?

Kind regards,
Maxim

> On Feb 6, 2021, at 02:15, Pieter Wuille <bitcoin-dev@wuille.net> wrote:
> 
> 
> On Friday, February 5, 2021 9:51 AM, Dr Maxim Orlovsky via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrote:
> 
>> Hi,
>> 
>> Background
>> 
>> ====================
>> 
>> Had a discussion last night in Bitcoin Core IRC with Peter Wuille on different topics regarding key derivations, security, key tweaks in context of Schnorr signatures & Taproot. Would like to share some action points and plans that emerged from there:
>> 
>> 1.  There is a real need for BIP-43 based new BIP with a new purpose field 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 else should.
>> 2.  Keys used in Schnorr signatures MUST NEVER BE used in ECDSA signatures, otherwise there is a risk of private key leak via correlation attack. This is rationale behind N1.
> 
> Hi Maxim,
> 
> thanks for bringing up this discussion here. I'd like to clarify a few things 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 privacy reasons, and (2) reasons to avoid using related keys for cryptographic 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 schemes 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 general 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 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 (Bitcoin, but also many other applications) has accepted ECDSA long ago, while it had no security proofs whatsoever (and even the ones that exist now rely 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 derivation paths (as BIP43 etc. do) to different uses implies there is never any concern about related keys across Schnorr/ECDSA.
> 
> If the keys are not separated by a hardened step, it's more complicated. Looking at the different cases:
> 
> (1) Signing with related ECDSA keys (e.g. two unhardened child keys from the 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 there 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 pubkey (key prefixing), and thus a signature on one shouldn't teach you anything about others. A formal proof is probably a bit longer, but still trivial to construct.
> 
> (3) The real question: signing with a Schnorr key that is related to an ECDSA key.
> 
> - 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 hashes. Aspects such as BIP340's key prefixing and the fact that Bitcoin sighashes 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 had about unhardened BIP32 ECDSA keys before a proof was known (which I think most people aren't even aware of).
> 
> Cheers,
> 
> --
> Pieter