Trust Samourai and their childish shills to blow this out of proportion.
Summary
-------
This report is intended as a disclosure of 2 vulnerabilities found in Wasabi Wallet. We suspect that these vulnerabilites have existed for a long time (since the inception of Wasabi?) and we think they're serious enough to deserve a proper responsible disclosure.
Context of these findings
-------------------------
In late July, we were working on an analysis of bitcoin flows related to the Twitter hack. This study was done in the context of our work for OXT Research.
As it was reported by multiple articles, a part of these funds has entered the Wasabi mixer. That led us to work on an analysis of mixes related to these funds.
Our first action was to gather a set of information by analyzing the main peel chain of toxic changes generated by these mixes. Nothing new here.
After that, we decided to check if we could identify idiosyncrasies of Wasabi Wallet allowing us to weaken the anonsets of some mixed outputs potentially controlled by the hacker. The approach used here is similar to the one used for the Toxic Recall Attack previously described for Joinmarket as it leverages additional information based on the coinjoin algorithm.
So, we've started to review the code of the client and of the coordinator, looking for such idiosyncrasies. This is how we have identified the first vulnerability.
Vulnerability 1
---------------
Review of the code led us to the conclusion that there is no randomness introduced by the client or by the coordinator during the selection of TXOs that will participate in a given mix.
Client side, the unique random factor that we were able to find is related to the switch between "lazy mode"/"non lazy mode" (https://github.com/zkSNACKs/WalletWasabi/blob/07b0a5cf6245724c68a86dfc9a9535b0164ca864/WalletWasabi/CoinJoin/Client/Rounds/ClientState.cs#L238) but this mechanism provides a weak protection considering that it will only occur if the selection of a single TXO or of a low number of TXOs has previously failed.
This lack of strong randomness consistently introduced by the client and/or the coordinator means that the system is acting as a deterministic automaton.
For instance, the client can be modeled as an automaton composed of:
- a Table of Instructions that is the set of coin selection rules mainly defined in ClientState.GetRegistrableCoinsNoLock(),
- a State Register storing the set of TXOs controlled by the wallet,
- a Tape composed of cells storing events related to the mixing process ("input registration of round N starts", "input registration of round N ends", "confirmation of tx associated to round N", etc).
The main consequence of this lack of strong endogenous randomness is that an observer having knowledge of events related to the mixing process and of the composition of the targeted wallet at a given step N, is able to predict which TXOs of the wallet will be selected for each round of mixing after step N, hence cancelling the benefits of the previous mixes.
Specifically, this means that:
- We are able to use the coin selection algorithm to isolate remixed UTXOs based on the coin selection rules. As a result, the anonset of the previous mix(es) does not contribute to the actual anonset. For instance, if round N generates a 0.1 mixed output A that is itself remixed by round N+1 into TXO B, then anonset(B) is equal to anonset(round_N+1) and not to anonset(A) - 1 + anonset(round_N+1) as it's expected by the user.
- Anonsets of TXOs that weren't selected for a given round may also be decreased thanks to this attack.
For instance, if we know that:
- a mixed output A controlled by the target wallet and created by round M wasn't selected for round N,
- a TXO B also created by round M and with the same denomination as A, was selected as an input of round N
then we can infer that B isn't controlled by the target wallet. This inference allows for a decrease of the anonset of A.
In summary, the lack of consistent randomnness introduced in the coin selection process negates the privacy gained by previous mixes, reducing the actual privacy to that of the most recent mix.
The role of exogeneous randomness
---------------------------------
So far, we've excluded the case of exogeneous randomness that may decrease the reliability of results provided by an attack based on this first vulnerability.
Here, it's important to note that exogeneous randomness may have different sources. Thus, we're going to use the following typology that will allow us to define a typology of attackers in the next section:
- 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 anonset 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)
Typology of attackers
---------------------
Here we propose the following typology of attackers:
- Type A: 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.
Type A attackers are subject to Type A exogeneous randomness but aren't concerned by Type B (knowledge of coordinator logs).
Type B attackers are potentially subject to both types of exogenous randomness but they should be able to deal with some occurences of Type B randomness. For instance, the analysis of mix transactions stored on the blockchain should allow such an attacker to detect if the rejection of unconfirmed TXOs has been activated by the coordinator.
Vulnerability 2
---------------
In order to mitigate the effects of exogenous randomness, both types of attackers can leverage a second vulnerability that is based on the existence of peel chains composed of toxic change outputs propagating across the mixes.
Here, the idea is that these toxic change outputs can be viewed as:
- "beacons of certainty" because it's possible to identify which mixes have spent the toxic changes.
- "expected checkpoints" that can be predicted to occur at a given round in absence of any exogenous randomness.
Thus, when an expected checkpoint doesn't match with the mixes generated by Wasabi, an attacker knows that there was an occurence of exogenous randomness and he can start to investigate concurrent hypotheses of exogeneous randomness that may lead to the observed results.
On our side, we were able to confirm this approach during some of our tests. In one case, we were expecting the mix of a toxic change output after the first two rounds of mixing, but it didn't happen after a few hours. After further analysis, it appeared that this TXO was repeatedly rejected by the coordinator because it was unconfirmed (like others TXOs controlled by the wallet). Mixing resumed as expected after the transactions associated to the first two rounds were confirmed a few hours later.
This second vulnerability can be used by both types of attackers but we suspect that it's especially effective when used by Type A Attackers in order to mitigate the effect of Type A randomness (the main reason being that users are humans and humans suck at generating strong randomness).
Test of the attack in the wild
------------------------------
* Summmary
In early August, we completed a series of tests. These tests have allowed us to confirm that the coin selection algorithm implemented by the client is indeed deterministic and selected the inputs as predicted.
From our observations, the main source of exogenous randomness during these tests seemed related to temporary scalability issues encountered by the coordinator and leading to TXOs failing to participate to mix rounds (see PRs 4133, 4134, 4135, 4136, 4137).
While technical issues like these ones make the interpretation of results more challenging for Type B attackers, they don't affect Type A attackers (a failure during a registration phase or during the signing phase is part of information available to the Coordinator). Moreover, we can expect that issues like these ones get fixed, decreasing de facto the randomness experienced by Type B Attackers.
* Principle of the test
Test simulated 2 actors:
- Alice:
- Alice simulates the Wasabi user targeted by the attack.
- She runs a vanilla Wasabi client.
- She sends ~0.4BTC (single UTXO) to her Wasabi wallet and enqueues this UTXO for mixing with a 120 anonset target.
- Eve:
- Eve simulates an attacker tracking the funds controlled by Alice and leading to Wasabi mixes.
- She acts as a "low-level" Type B attacker.
- She eavesdrops the Wasabi coordinator but doesn't participate to mixes.
- For this, she runs a slightly modified Wasabi client that logs the details of mix rounds and if rounds failed or succeeded (modifications made in ClientState.UpdateRoundsByStates()) .
* Sample test illustrating the attack
The spreadsheet "analysis.ods" provides a sample of a test illustrating how this attack can be used to decreases the anonset provided by multiple rounds of mixing.
- First sheet lists the first mixes and TXOs related to Alice's activity during the test (plus the related bitcoin addresses and private keys) .
- Second sheet is a timeline of events built by Eve thanks to data gathered thanks to her Wasabi client.
- Third sheet is the different stages of the State Register (Alice's wallet) as predicted by Eve when running a deterministic automaton simulating Alice's Wallet.
For the sake of clarity and simplicity, the first spreadsheet is organized as follows:
- Bold green cells identify elements modified by each step.
- In the context of this specific test, the deterministic coins selection algo can be reduced to the following heuristic: "Select the first available TXO covering the required funds with TXOs sorted by confirmation status, increasing anonset and decreasing amount" (this order corresponds to the order defined for the selection of a single TXO).
- Comments in the last column try to make explicit the details of the heuristic for each step.
As predicted by our model of the attack, we can observe that:
- remix of [9e01:81] by [79bc] leads to a first weakening of anonsets:
- [9e01:81]: Ajusted anonset is 4 instead of expected anonset of 10,
- [79bc:33]: Ajusted anonset is 4 instead of expected anonset of 13,
- [79bc:46]: Ajusted anonset is 81 instead of expected anonset of 90,
- remix of [79bc:46] by [3de0] leads to a second weakening of anonsets:
- [79bc:33]: Ajusted anonset is 2 instead of expected anonset of 13 (2 TXOs with same amount as [79bc:33] are inputs of [3de0]),
- [79bc:46]: Ajusted anonset is 2 instead of expected anonset of 90,
- [3de0:45]: Ajusted anonset is 53 instead of expected anonset of 142.
Severity
--------
In our opinion, these vulnerabilities should be considered as High/Critical for the following reasons:
- in the case of a mixed output being remixed, these vulnerabilities break the Zerolink guarantee for the previous mix and cancel the benefits provided by the previous mix.
- these vulnerabilities break the global guarantees provided to users by the mixer. Indeed, an effective attack against the user of a mixer doesn't require the deanonymization of all user's postmix TXOs. Deanonymizing a single TXO is often enough. Thus, the last mix a user participates in is their effective anonset. For users participating in a final low liquidity mix (e.g. 105d84ad09a11e91b406cbde6ae220ad8dc74d718427080721b0048f18a4f55c or 9035306130415c91b7144e977097a7abe150aaf554046390ec48a8e61d051c9c), their desired/expected and actual privacy can be off by an order of magnitude.
- Considering that these vulnerabilities have existed for a long time, it's our belief that if we were able to detect them, it's more than likely that they were already detected by someone else and perhaps already exploited in the wild.
Potential mitigations / fixes
-----------------------------
As it was shown in previous sections, the unique protection currently available to users against these two vulnerabilities is the occurrence of exogenous randomness. Obviously, this can't be considered as a satisfying solution, because:
- protection should be consistent and verifiable and shouldn't rely on external factors which aren't under the control of users or operators of the mixer.
- it offers a weak protection against Type A attackers.
In our opinion, the best fix against these two vulnerabilities is the introduction of consistent randomness in client code (i.e. in ClientState.GetRegistrableCoinsNoLock()).
We understand that prioritizing the selection of some TXOs over others TXOs might be an important factor for Wasabi operations and we believe that it's still possible to do that while introducing randomness only known by the client.The principle of such a solution would be to replace the current selection process based on a strong ordering of TXOs, by a random selection of a Coingroup, with an unequal probability of being selected depending on the factors currently used for the ordering.
For instance, the stong ordering of TXOs by anonset and amount (https://github.com/zkSNACKs/WalletWasabi/blob/07b0a5cf6245724c68a86dfc9a9535b0164ca864/WalletWasabi/CoinJoin/Client/Rounds/ClientState.cs#L242) may be replaced by:
- the computation for each CoinGroup of a metric f(anonset(CG1), amount(CG1)).
- the computation for each CoinGroup of a probability of being selected: P(CG1) = metric(CG1) / sum_over_CGn(metric_CGn).
Schedule for a public disclosure
--------------------------------
Considering the severity of these vulnerabilities and the likelyhood this is already being exploited by less ethical parties but also keeping in mind the time that may be required for implementing and testing a fix, a tradeoff has to be found. Thus, we are offering the following approach:
- Within 48 Hours of the delivery of this disclosure Wasabi Wallet / Zk Snacks Ltd should release a statement on their public channels (twitter, reddit, website, etc...) alerting and warning users to the fact that a vulnerability has been reported and a solution is being worked on.
- Within 15 Days of the delivery of this disclosure Wasabi Wallet / Zk Snacks Ltd should release a tested patch to the public that mitigates the concerns in this disclosure.
Provided these two conditions are met, we will not disclose this publicly until after the 15 days have elapsed and a fix can be implemented by your team.
If Wasabi Wallet / Zk Snacks Ltd fails to release a statement within 48 hours we will be forced to conclude that the team does not consider this a serious issue and we will begin the process of a responsible public disclosure immediately.
The only (cmiiw) way the attackers can get enough wallet state info is if someone puts a large amount of BTC in as one UTXO and then queues all of it for remix. Stick with small sizes, should be fine.
