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

[Peter Todd <pete@petertodd.org>]

[-- Attachment #1: Type: text/plain, Size: 10907 bytes --]

On Sat, Dec 21, 2024 at 03:16:09PM +0100, Yuval Kogman wrote:

I've been reviewing Wasabi and other coinjoin implementations lately and
I believe that your focus on lite clients with regard to Wasabi is
incorrect. Let's go through the issues:


# Sybil Attacks In General

Let's get this out of the way first. As AdamISZ correctly noted in his
Jan 7th reply¹ to you, sybil attacks in general are impossible to
entirely prevent in any coinjoin protocol where participation is done
anonymously. It is always possible for an adversary to simply flood the
mechanism with coinjoin requests to the point where they are the only
counterparty.

What we can do is make sybil attacks costly. In general, Wasabi's
current usage with user-settable centralized coordinators does that
pretty well: typical coinjoin rounds on the most popular coordinator,
https://coinjoin.kruw.io, are transactions close to the standard size
limits, with hundreds of inputs and outputs, mixing millions of USD
dollars worth of BTC per round. A trivial sybil flood attacker would
have to spend a lot of money and hold a lot of coins to simulate that.


# Attacks via Failed Rounds

Secondly, there's a potential class of attacks via failed rounds;
attacks via failed rounds are potentially cheap/free attacks, as no
transaction fees are actually spent. A Wabisabi coordinator gets desired
inputs and outputs from clients, which would allow them to learn
something about which inputs are linked to each other, and which outputs
were desired by the owner of those inputs, if the coordinator
succesfully "sybil" attacks the client.

This class of attack might be interesting if Wasabi reused outputs after
rounds failed, in subsequent rounds. I have not verified whether or not
this is actually true; AdamISZ did confirm to me that JoinMarket does
*not* do this, resulting in large gaps between used outputs in typical
operation (it's normal for a high % of rounds to fail). This is an
implementation issue due to gap-limits in HD wallet implementations;
Silent Payment-like functionality may be a way around this problem.
Additionally, this class of attack would impact pay-in-coinjoin
functionality, where a payment address is added directly to a coinjoin.


# Attacks via "Successful" Rounds

If the round actually completes, the transaction fees must actually be
paid, and liquidity must be provided. So if the attacker wants to do a
cheaper attack than the "dumb" attack that is always possible, they must
find a way to get other participants to provide that liquidity and pay
those fees.

You keep bringing up lite clients, e.g. in your statement that:

	Unfortunately only full nodes can verify that a coin really is unspent.
	If a user has configured Wasabi to use a full node this is ideal but
	probably would not be the norm.
	-https://github.com/WalletWasabi/WalletWasabi/issues/5533

Your focus is mistaken. In fact, it's irrelevant whether or not a txin
in a proposed coinjoin round is spending a coin that exists or not. The
reason is there are two possible situations:

1) The coin is either spent, or never existed at all. The round will
   fail as the transaction is invalid, meaning we're actually dealing with
   a form of Attack via Failed Round. As described above, these aren't
   particularly interesting attacks.
 
2) The coin is unspent, and the round succeeds. Whether or not a
   reduced-cost sybil was successful depends on round identity
   consistency.

Clients do *not* need to validate coins in coinjoin rounds. Whether or
not they're real is irrelevant, as the Bitcoin consensus itself
validates this for you.


## Consistency of Round Identity

As you mention, here we have a form of MITM attack, leveraged to perform
a sybil attack: if Alice and Bob are coinjoining at the same time, from
Alice's perspective, if the coordinator can pretend to be Bob, the
coordinator can run two simultaneous "rounds" that are actually creating
the same transactions. Thus the coordinator is re-using Bob's liquidity
and fees to sybil attack Alice. This type of sybil even works with N
participants: for each participant the coordinator can create a round
with N-1 other fake participants, MITM attacking each simultaneously.

Since Wasabi already has coin ownership proofs and distributes them, I
believe we can easily validate the round ID consistency of a coinjoin
transaction after it's fully signed and confirmed by simply validating
that the signatures on the inputs were in fact signed by the pubkeys of
the corresponding coin ownership and round ID proof. Wasabi already
evaluates the anonymity score of outputs. So performing this check would
simply mean that we're validating that the round was not sybilled, and
the anonymity score is valid.

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.


# References

1) https://groups.google.com/g/bitcoindev/c/CbfbEGozG7c/m/oJTF8wqRDgAJ


> ### WabiSabi
> 
> This affects Wasabi Wallet, and Ginger Wallet which is a fork of
> Wasabi. Trezor Suite was also affected, but has subsequently removed
> support for coinjoins[^18]. They too were made aware of various issues
> and chose to ignore them, despite contributing the limited (read:
> purely theater for privacy, only addressing hardware wallet specific
> theft scenario) ownership proof verification.
> 
> Here the issue is more complex, but ultimately reduces to key
> consistency as well.
> 
> In the protocol clients register their Bitcoin UTXOs independently. A
> valid input registration request includes a BIP-322 ownership proof,
> which commits to the so called *Round ID*. This in turn is a hash
> commitment to the parameters of the round, including the server's
> anonymous credential issuance parameters (analogous to a public key).
> 
> The parameters are obtained by polling the server for information
> about active rounds. If inconsistent round IDs are given to clients,
> this effectively partitions them, allowing deanonymization.
> 
> Although clients obtain the ownership proofs of other clients and
> seemingly verify them, BIP-322 proofs verification requires knowledge
> of the spent outputs `scriptPubKey` which light clients cannot obtain
> on their own. This public key is included alongside the ownership
> proofs, which makes their verification non-binding, the server can
> generate unrelated public keys, and create ownership proofs with those
> keys that commit to the per-client round IDs, which the client will
> accept as valid.
> 
> This issue was described before the initial release[^7] but never
> addressed. Although subsequently ownership proofs were given to
> clients[^8], this change only addressed the use of ownership proofs to
> identify a wallet's own inputs in a stateless signing device, without
> addressing the consistency issues. Because the server provides the
> public key against which unknown inputs ownership proofs must be
> verified, that places them under adversarial control.
> 
> Related issues and comments I have posted over the years:
> 
> - unimplemented consistency check that does not depend on prevout also
> not implemented[^9]
> - no commitment to coordinator address in the round parameters[^10],
> although this was temporarily fixed the fix was reverted[^11]
> - additional missing fields in the round parameter commitments, and
> rationale addressing tagging attacks[^12]
> - initial description of blind signature based protocol, which
> predates my collaboration and design of the anonymous credential based
> protocol which also addresses this explicitly[^13]
> 
> Finally, although not in scope I will also note that poor coin
> selection (bad randomization and de-randomization), improper
> randomization of input registration timing, and tor circuit management
> increase the probability of the success of such an attack, by making
> it easier to target specific users. Additional concerns exist for
> alternative clients due to use of JSON and HTTP in the protocol, in
> the C# implementation serialization by a 3rd party JSON library, which
> may canonicalize JSON differently (e.g. ordering of properties in JSON
> objects), etc. Additionally, although designed with coordination fees
> in mind, the anonymous credential mechanism did not enforce that
> coordination fees are fair or incentive compatible (nor can it with
> non-binding ownership proofs, though the main privacy concern there is
> the coordinator lying about the values of other clients' prevouts
> leading to poor amount decomposition), resulting in thefts of user
> funds[^14][^15], but this has now been removed[^16].
> 
> Again a version of this with some preliminaries is also on github.[^17]
> 
> [^7]: https://github.com/WalletWasabi/WalletWasabi/issues/5533
> [^8]: https://github.com/WalletWasabi/WalletWasabi/pull/8708
> [^9]: https://github.com/WalletWasabi/WalletWasabi/issues/6394#issuecomment-920225648
> [^10]: https://github.com/WalletWasabi/WalletWasabi/issues/5992
> [^11]: https://github.com/WalletWasabi/WalletWasabi/pull/8708/files#diff-04b849802b4adf5b34756a49b498f2ac97247cbb64424e5a69ee64c28a7033bcR120
> [^12]: https://github.com/WalletWasabi/WalletWasabi/issues/5439
> [^13]: https://gist.github.com/nothingmuch/61968fde675a596758bffd4c278ac096
> [^14]: https://github.com/WalletWasabi/WalletWasabi/discussions/13249
> [^15]: https://bitcointalk.org/index.php?topic=5499439.msg64309927#msg64309927
> [^16]: https://archive.is/xFRHO
> [^17]: https://gist.github.com/nothingmuch/4d717e12e451ff4ce43474972e41c6ba
> [^18]: https://blog.trezor.io/important-update-transitioning-from-coinjoin-in-trezor-suite-9dfc63d2662f
> 
> -- 
> 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 bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/CAAQdECCdRVV%2B3ZoJhOotKEvmUV4yrV7EYWE8SOWCE1CF9tZ6Yg%40mail.gmail.com.

-- 
https://petertodd.org 'peter'[:-1]@petertodd.org

-- 
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 bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/Z5JtilN2k7HwRRXt%40petertodd.org.

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]