An Analysis and Disclosure Regarding the Deterministic Nature of the Wasabi Wallet CoinJoin Algorithm
Introduction
The mid-July Twitter Hack thrust bitcoin back into public awareness. After reports of inflows of coins scammed by the Twitter Hacker into Wasabi Wallet, we began an analysis of these flows to put together a new OXT Research Report.
In late July 2020 we began to review the code of both the Wasabi Wallet client and the Wasabi CoinJoin coordinator looking for idiosyncrasies in the CoinJoin implementation that could possibly be exploited by a malicious actor to de-anonymize mix transactions. During these reviews the OXT Research team found (2) vulnerabilities in the Wasabi Wallet client and coordinator code.
On August 17, 2020 we confirmed these vulnerabilities were able to be reproduced "in the wild". We marked these vulnerabilities as critical and began the process of private responsible disclosure with ZkSnacks Ltd. (Wasabi Wallet operating entity.)
On August 19, 2020 we were made aware that the Wasabi Wallet team did not accept the results in this disclosure, but have not provided any further details at this time.
Lack of randomness
Our researchers have discovered that there is no randomness introduced when the wallet selects which TXOs are registered for an inclusion in a mix transaction.
This translates into a situation where an adversarial observer is able to determine which TXOs of the wallet will be selected for each round of future mixing, cancelling out the benefit of each previous mix.
Coins are posted to each coinjoin round by the wallet using a deterministic coin selection algorithim. An external attacker without knowledge of the coordinator logs stored by ZkSnacks Ltd. would need to monitor the coinjoin network timeline (registration, close, confirmations) and combine that with the coin selection algorithim to exploit this vulnerability.
Alternatively, an attacker with knowledge of the Wasabi coordinator logs would be more easily able to exploit this vulnerability.
How does Wasabi Work?
- The user selects a target anonymity Set
- The user enqueues unspent transaction outputs to be mixed in an upcoming mixing round
- The wallet will then process the mixes automatically until the target anonymity set is reached or the user manually stops the process.
The concept of Anonymity Set in Wasabi
In a Wasabi mix transaction, the amount of other TXOs that share an equal value as your TXO is equal to your anonymity set. The idea being that this is the size of the crowd that your coins belong to and are indistinguishable from. The larger the crowd the better is the general rule for anonymity sets.
Remixing
Remixing is a widely recommended best practice and users of most coinjoin platforms are encouraged to remix their TXOs for an increase in the overall anonymity set of the remixed outputs.
When remixing, the expectation is that you are taking the obtained anonymity set from the prior mixes (subtracting 1, since your 1 TXO is being consumed) and adding the anonymity set obtained in the second mix transaction.
If we were to remix our previously mentioned initial TXO in an additional CoinJoin transaction that obtained a further 50 anonymity set, we would expect a total score of 99 ( 50-1 + 50 )
Impact of the first vulnerability
If it can be predicted that the first mix output will be remixed by a given round of mixing, it means that initial TXO is 1 of the mixed outputs of the second mix.
With this knowledge the other mixed outputs are false positives. As a consequence, the anonymity set after remix becomes 50 instead of the expected and reported 99.
"But 50 seems fine!"
Privacy enhancing tools shouldn't produce results that are a lottery. A good mixer should provide constant and predictable outcomes. In the case of Wasabi, the guarantees given by the codebase allows for anonymity sets somewhere between 2 and 100 for a mix.
"But most Wasabi mixes have an anonymity set far larger than 2!"
While this might be true, average/median performance doesn't matter when talking about privacy. The privacy of your bitcoin is only as good as the privacy of your weakest TXO. For example, the recent Twitter Hacker was caught and arrested not due to their entire wallet being deanonymized, but rather a single transfer of bitcoin to an exchange.
Additionally there are examples [9035...1c9c] , [105d...f55c] of fairly atypical low anonymity set mix transactions.
Exogenous randomness as a mitigation/protection against the attack
Additionally to the original description of this vulnerability, our team has proposed a first analysis of external factors that may act as sources of external randomness and somewhat mitigate the effectiveness of the attack.
This analysis led us to the description of a typology of exogenous randomness (Randomness that derives its source external to the system)
| Type A |
Randomness introduced by the user and for which the attacker has no prior knowledge. (e.g.: new funds unknown to the attacker are enqueued, user temporarily stops her client and resumes the mixing later, custom target anonymity set value set by the user, etc…). |
|---|---|
| Type B |
Randomness introduced by events independent from the user. (e.g.: unconfirmed TXOs are rejected by the coordinator, connection failure, etc...). |
This further led us to a definition of a typology of attackers
| Type A Attacker |
Attacker having the same knowledge as the coordinator (i.e. attackers with knowledge of the technical logs of the coordinator). |
|---|---|
| Type B |
Attacker with no access to coordinator's technical logs but able to eavesdrop the Wasabi and Bitcoin network and, optionally, to participate in each round in order to gather additional information about the mixes. |
These 2 typologies have allowed us to refine the threat models:
- (Type A) Attackers
- Subject to the limitations imposed by Type A exogenous randomness but aren't concerned by Type B exogenous randomness.
- (Type B) Attackers
- Potentially subject to both types of exogenous randomness but they should be able to deal with some occurrences of Type B randomness.
Finally, our team has presented a second vulnerability, based on the existence of peel chains composed of toxic change outputs, that can be leveraged by an attacker to mitigate the effects of exogenous randomness.
Tests
A series of tests simulating a "low-level" Type B attacker were run in early August. Conditions during these tests were adversarial for an attacker (mempool filled with a high number of transactions, temporary overload of server running the coordinator) but we were nonetheless able to validate our description of the two vulnerabilities and have a first evaluation of their effectiveness.
A sample of a test was provided with the original disclosure as an example illustrating the process that might be applied by an attacker.
Rationale of our disclosure
The form of our disclosure was based on multiple elements:
The lack of consistent randomness introduced in the selection of coins used for a mixin is a well-understood threat documented in the many published academic papers.
For an example of existing research exploring the importance of randomness in the selection of "mixins" within Monero transactions, and how a subtle weakness was exploited to attack the monero blockchain see An Empirical Analysis of Traceability in the Monero Blockchain.
Exogenous randomness may partially mitigate the attack. However, evaluating the full scope of its "effectiveness" is a complex task because of the multiple externalities involved (e.g.: what is the typical behavior of a Wasabi user? Do Wasabi users actively use the multiwallets feature allowing a compartmentalization of their mixing activity ? Who is the attacker and what are its capabilities in term of analysis of premix activity? etc...).
External factors which are outside the control of users and operators of a mixer and which may greatly vary in time, can hardly be considered as a satisfying solution.
Conclusions
The best solution is obviously to introduce consistent randomness into the coin selection process and, considering that implementing such a solution is possible, it should be a priority.
Absent the implementation of a solution, users of Wasabi Wallet should be aware that the anonymity set of their postmix output may potentially be as low as the anonymity set provided by the last mix of the associated TXO. Users should act accordingly, depending on the specifics of the last mix and depending on their own threat model.
Without implementing a solution ZkSnacks Ltd should be aware that the technical logs of the coordinator may potentially be used as a resource to weaken the privacy provided by the service and they should, in our opinion consider these logs as a critical resource.
