Subject: Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks

From: waxwing/ AdamISZ <[email-masked]>
Date: Fri, 24 Jan 2025 08:38:47 -0800 (PST)

> The only question left for this technique is a cryptography one: 

> Is it possible to create an alternate pubkey p', that such that a valid 
signature s signed by arbitrary pubkey p for message m, also validates 
for p' for signature s and message m? I believe the answer is no for 
schnorr. But I'm not a cryptography expert, and I may have missed 
something. 

I've been thinking about this (to some extent digging up old analyses from 
a few years back). I'm pretty sure that because of Schnorr's key-prefixing, 
it is indeed not possible to do this: (specifically: given a tuple (m, 
(R,s), P) that exists and for which the signature is valid, create a *new* 
pubkey P2 s.t. (m, (R, s), P2) is valid. Notice this is not quite the same 
as the definition of strong unforgeability (in which we analyze a specific 
given key), which is an established property of Schnorr under the ROM. 
Still, my argument would be that: a new P2 for which this is valid 
satisfies: sG = R + e' P2, where e'=H(R,P2,m) and we previously had sG = R 
+ eP, so that we require P2 = e/e' * P, but e' = H(R,P2,m) so that this 
equation is insoluble under the preimage resistance of the hash function.

Does this same argument apply to ECDSA? No, definitely not  because ECDSA 
does not fix the pubkey into the hashing (which is of course why pubkey 
recovery is possible in ECDSA, for example). From just looking at the 
verification equation sR = H(m)G + R_x P, though, I guess that we cannot 
actually create a new P2 for the same (R,s),m tuple, but for different 
reasons: while a negation of s is still valid, that is not the issue. If we 
cannot change R or s or m, we cannot change P. Apparently it's debatable 
how important the ECDSA case will be, but, it's for sure interesting!

Regards,
AdamISZ/waxwing

-- 
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to [email-masked].
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/5fcbe15c-2793-44a7-88d1-e708c224f2fdn%40googlegroups.com.