* [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
@ 2024-12-21 14:16 Yuval Kogman
2025-01-06 13:07 ` Sjors Provoost
2025-01-23 16:25 ` Peter Todd
0 siblings, 2 replies; 10+ messages in thread
From: Yuval Kogman @ 2024-12-21 14:16 UTC (permalink / raw)
To: Bitcoin Development Mailing List
Following the recent Wasabi & GingerWallet vulnerability report[^1]
and its "fix", I would like to bring up (reiterate, but for the first
time on the mailing lists) some broader deanonymization issues with
both Wasabi / GingerWallet and Samourai wallet's CoinJoin protocols.
These vulnerabilities were never truly discovered and consequentially
not disclosed, responsibly or otherwise, because they had always been
in the protocols. Neither team seems capable of addressing these for a
variety of reasons.
Personal disclosure: I was involved in the design of WabiSabi, as well
as its implementation but left in protest before its release. I
maintain that this software is not fit for purpose and should not be
used unless users trust the coordinators with their privacy.
Furthermore, I allege that rent seeking behavior explains the apparent
incompetence and willful ignorance, and caution against applying
Hanlon's razor too charitibly.
In regards to Wasabi/GingerWallet, especially in light of the various
"community" WabiSabi protocol coordinators, it's important to make
users aware of the degree of trust they place in these services.
Wasabi developers are still claiming that these issues are not
fixable, which is incorrect to say the least, especially considering
that when I was contributing to the project and taking for granted
that these issues would be addressed I got no pushback, nor any
indication that they did not understand the issue at the time.
Whirlpool is now defunct, but Samourai proponents are claiming that
their developers have warned about the Wasabi vulnerability, despite
the Whirlpool protocol having a more blatant and easily exploitable
version of the same category of attack, so it's worth setting the
record straight. The whirlpool client code was included in Sparrow
wallet until v1.9.0 when it was removed following the shutdown of the
whirlpool service.
[^1]: https://bitcoinops.org/en/newsletters/2024/12/13/#deanonymization-vulnerability-affecting-wasabi-and-related-software
## Preliminaries
Both protocols facilitate multiparty transaction construction,
ostensibly utilizing cryptography for privacy preserving denial of
service protection. TxOut addition requires authorization tokens, an
unblinded signature in Whirlpool's case, or an anonymous credential in
WabiSabi's, that is supposed to not be linkable to any of the client's
added TxIns.
In both protocols a malicious coordinator can trick the existing
client implementations into making fully deanonymized requests. In
Whirlpool this means a TxOut is linkable to a TxIn. In WabiSabi this
means that the set of TxOuts is linkable to the set of TxIns of a
single client.
### Whirlpool
This is a trivial deanonymization attack reliant on the fact that the
client completely trusts the server with regards to the consistency of
the blind signing key.
In Whirlpool, the server's blind signing key is obtained by the client
by extracting it from the response to the input registration
request.[^2]
Subsequently, this key is used to make blind signing requests during
the confirmation phase.[^3]
After a blind signature is given to the client the unblinded signature
is used to request an output registration.[^4]
Because the key is not announced a priori, nor is it signed by the
participants' spending keys before output registration or signing[^5],
the server can provide each input with a unique RSA key. Since the
unblinded signatures are made by different keys, the server can learn
the mapping from inputs to outputs.
This description along with some preliminaries is also posted on github.[^6].
[^2]: https://github.com/Archive-Samourai-Wallet/whirlpool-client/blob/99c1acc101f53fef21fbcc5d23cb05eafb7324e9/src/main/java/com/samourai/whirlpool/client/mix/MixProcess.java#L140-L141
[^3]: https://github.com/Archive-Samourai-Wallet/whirlpool-client/blob/99c1acc101f53fef21fbcc5d23cb05eafb7324e9/src/main/java/com/samourai/whirlpool/client/mix/MixProcess.java#L146
[^4]: https://github.com/Archive-Samourai-Wallet/whirlpool-client/blob/99c1acc101f53fef21fbcc5d23cb05eafb7324e9/src/main/java/com/samourai/whirlpool/client/mix/MixProcess.java#L185
[^5]: https://github.com/Archive-Samourai-Wallet/whirlpool-client/blob/99c1acc101f53fef21fbcc5d23cb05eafb7324e9/src/main/java/com/samourai/whirlpool/client/mix/MixProcess.java#L216
[^6]: https://gist.github.com/nothingmuch/74d0b0bd63a2d663efce5e8a82d32bca
### 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.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2024-12-21 14:16 [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks Yuval Kogman
@ 2025-01-06 13:07 ` Sjors Provoost
2025-01-06 14:30 ` Yuval Kogman
2025-01-23 16:25 ` Peter Todd
1 sibling, 1 reply; 10+ messages in thread
From: Sjors Provoost @ 2025-01-06 13:07 UTC (permalink / raw)
To: Bitcoin Development Mailing List; +Cc: Yuval Kogman
Thanks for the write-up.
I’m curious to learn if any of these attacks happened in practice,
and if there are methods to find out retroactively.
> In Whirlpool, the server's blind signing key is obtained by the client
> by extracting it from the response to the input registration
> request.[^2]
> Because the key is not announced a priori, nor is it signed by the
> participants' spending keys before output registration or signing[^5],
> the server can provide each input with a unique RSA key. Since the
> unblinded signatures are made by different keys, the server can learn
> the mapping from inputs to outputs.
Do we know based on observations or published server-side code whether
this key was:
1) the same for all time; or
2) unique for each round; or
3) unique for each registration request
In case of (1) and (2) it would have been possible to detect a targeted* attack,
of course only if you were on the lookout.
Perhaps if the app kept sufficient logs, it would still be possible to retroactively
check this.
> ### WabiSabi
>
> 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.
Are these round IDs logged by clients?
* = I’m thinking of an active attacker who wants to track specific UTXOs.
They could preemptively “persuade” the coordinator server to provide
a different RSA key or round ID if they ever try to join a round.
- Sjors
--
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/E26BEB3C-1345-487D-A98C-2A7E17494B5E%40sprovoost.nl.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2025-01-06 13:07 ` Sjors Provoost
@ 2025-01-06 14:30 ` Yuval Kogman
2025-01-07 15:56 ` waxwing/ AdamISZ
0 siblings, 1 reply; 10+ messages in thread
From: Yuval Kogman @ 2025-01-06 14:30 UTC (permalink / raw)
To: Sjors Provoost; +Cc: Bitcoin Development Mailing List
On Mon, 6 Jan 2025 at 14:08, Sjors Provoost <sjors@sprovoost•nl> wrote:
> Do we know based on observations or published server-side code whether
> this key was:
> 1) the same for all time; or
> 2) unique for each round; or
> 3) unique for each registration request
>
> In case of (1) and (2) it would have been possible to detect a targeted* attack,
> of course only if you were on the lookout.
Only (2) would be correct behavior. If (3) was performed, then that is
just the tagging attack. If (1) was done, then that would have allowed
clients to stockpile blind signatures in earlier rounds, and register
excess outputs during the output registration phase of later ones to
disrupt them (wasabi 1 had this bug FWIW).
if the archived code is considered reliable, then it seems (2) was the
implemented behavior:
https://github.com/Archive-Samourai-Wallet/whirlpool-server/blob/develop/src/main/java/com/samourai/whirlpool/server/beans/Mix.java#L67
> Perhaps if the app kept sufficient logs, it would still be possible to retroactively
> check this.
I'm not aware of any such observation efforts. They would require
modifying the client, at least with the archived version that I saw
the `blindingParams` member is not used that way (there are other
debug logs in the whirlpool client, but not with this data).
However, since the public key is only given in response to input
registration, i.e. after the server has learned of the intended UTXO,
and because in many cases an xpub linking that coin may have also been
revealed to the server, and the server controls the grouping of coins
into sets of 5, it seems to me that if it was controlled by a rational
attacker it would not use the overt key tagging attack when covert
ways of deanonymizing are available and just as effective.
> * = I’m thinking of an active attacker who wants to track specific UTXOs.
> They could preemptively “persuade” the coordinator server to provide
> a different RSA key or round ID if they ever try to join a round.
While this is certainly possible, maintaining plausible deniability is
easier if the server merely maliciously control the placement of
UTXOs, ensuring that targeted UTXOs end up only with xpub-revealed
and/or adversary controlled peers.
> Are these round IDs logged by clients?
In the case of wasabi, both my recollection and a cursory search
indicates that yes:
https://github.com/WalletWasabi/WalletWasabi/blob/42e7963d7fffc7f8f37fd9b6e8973235859ee7fb/WalletWasabi/WabiSabi/LoggerTools.cs#L36
I did not check in detail where this information is logged, and I
don't think a list of all published round IDs is logged.
I would not encourage users to share such logs, or their data, without
careful considerations. Even if logs were scrubbed, revealing a/the
set of rounds in which a user participated can significantly harm
privacy, especially since participation in rounds and coin selection
does not take into account history intersection attacks. See also
these issues re log scrubbing
https://github.com/WalletWasabi/WalletWasabi/issues/6770
https://github.com/WalletWasabi/WalletWasabi/issues/6670 (first was
closed without fixing, deemed duplicate of 2nd - i'd say it isn't -
which is still open...).
One of the developers still working on wasabi indicated that there
will finally be some efforts to mitigate this class of attack:
1. redundant queries from isolated tor circuits of the round status
information where round IDs are published, and consistency checks for
the data returned
2. use of deterministic shuffling in the transaction, ensuring that
signatures can only be aggregated in the absence of equivocation
(assuming the corresponding Lehmer code has enough bits of entropy)
Since round IDs are published ahead of time in the status requests,
and clients explicitly choose which round to join before revealing any
of their intended inputs, the first mitigation is straightforward and
would present a significant barrier.
--
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/CAAQdECCq5n7zkRJboVwjLMWkGUP7-G2U7tK4Ekf5M9NqLypLQA%40mail.gmail.com.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2025-01-06 14:30 ` Yuval Kogman
@ 2025-01-07 15:56 ` waxwing/ AdamISZ
2025-01-07 21:33 ` Yuval Kogman
0 siblings, 1 reply; 10+ messages in thread
From: waxwing/ AdamISZ @ 2025-01-07 15:56 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 10429 bytes --]
Hello nothingmuch, Sjors, list,
Thanks nothingmuch for the writeup on coinjoins with coordinators.
This general topic is rarely covered and while people like me know about
it, we (well, I) are/am too lazy to get into the details of what kinds of
problems exist.
I think there are two distinct categories of weakness here:
1/ the ability of the coordinator to Sybil a targeted user by *not*
including other unknown-to-coordinator entities in the join. This can be
done by blocking access of those other entities, and/or Sybilling by adding
their own entities.
This first weakness is absolutely fundamental for all participants *except*
the coordinator; you can't code/algorithm/crypto your way around it.
Justification of that: the essence of this coordination is that it must be
anonymous for the participants, that is the whole point. Therefore the
ability to distinguish between Sybils and non-Sybils cannot exist, in pure
form. However:
The weakness is ameliorated, but not removed, by using decentralization of
having oneself be the coordinator for a join. I say "not removed" because
the Sybil risk still exists, but the bar is set much higher for the
attacker, since they have to Sybil the whole ecosystem, i.e. they have no
control over who else takes part. It is also ameliorated, but not removed,
by cost imposition (see Joinmarket fidelity bonds e.g.).
What's clear is that this risk is far worse with a static central
coordinator for all joins rather than the "each new participant
coordinates" model. Also to correct a common imprecision (so not ofc
addressed to you nothingmuch, but to the reader): the taker-maker model is
*not* incompatible with coordinator blinding.
2/ the ability of the coordinator to tag a targeted user by shenanigans
with the blinding key, roundID etc.
The story you tell on this is interesting. In short, as per the
"fundamental weakness" paragraph above, it's the nature of these systems
that the user is anonymous and ephemeral and therefore the only "identity"
they have is the coin they bring to the join. Given that, attestations
being verifiable requires blockchain access as the ground truth. For
similar things in Joinmarket's protocol (and rest assured, we had the same
requirement, basically), we never had to bat an eye, because we could make
calls on the utxo set at any time, since we *force* users to use full
nodes. But as you say, it *should* still be fully possible with various
kinds of light client ... so I am wondering why the people working on the
Wasabi project didn't consider this a sine-qua-non. Why even bother with
blinding if you're not going to give the client a surety that the blinding
is actually doing anything?
On reflection, I can see at least one counter-argument: suppose user2 is
looking at user1's signature on the context of the round, and they are
given key P for user1's signature and just told "trust me" by the
coordinator, and they go ahead, because user2 only has a light client and
no merkle proofs. Well, if the coordinator lies about P, the user2 can find
out later that day, using a full node or block explorer to check user1's
utxo. Now, if the coordinator's message is *signed* so as to be
non-repudiable, then user2 can prove to the world that the coordinator
lied. Conditional on that signing, I think this counter-argument is strong;
in the absence of signing, with repudiable messages instead, then I think
it's weak.
I guess all this comes into particularly sharp focus now that we have
various different Wasabi coordinators. They should all be assumed to be run
by the Feds, so to speak, and analyzed from that perspective. (not that
that wasn't true with only 1, just that it's more true, now).
A few more specific Qs/comments:
On the Samourai issue:
> Because the key is not announced a priori, nor is it signed by the
participants' spending keys before output registration or signing[^5], the
server can provide each input with a unique RSA key. Since the unblinded
signatures are made by different keys, the server can learn the mapping
from inputs to outputs.
My gut reaction is to do "permanent key tweaked with context" here, so the
client could easily verify, based on remembering the permanent key, that
the correct (hash of date plus round number plus whatever) had been
applied. But that works in Schnorr family, I don't know if a key tweak can
be applied to RSA? Perhaps this question is academic, but I want to know
how easily this could have been fixed in practice. (I don't know why they
were using RSA, but I could imagine various practical reasons; there were
after all known attacks on Schnorr blinded signing).
> 2. use of deterministic shuffling in the transaction, ensuring that
signatures can only be aggregated in the absence of equivocation (assuming
the corresponding Lehmer code has enough bits of entropy)
That's an elegant idea; I presume it depends on tx size being large enough
(yeah, bits of entropy), but that certainly isn't an issue for the
Wa(bi)sabi design. Couldn't a similar trick be played with the
coordinator's receiving address (assuming that wasabi still works like
that, with a coordinator fee address in the tx)?
> it seems to me that if it was controlled by a rational attacker it would
not use the overt key tagging attack when covert ways of deanonymizing are
available and just as effective.
It seems I missed something, here. What covert attacks are possible except
for Sybilling, excluding other users from the round? - which is only at
best semi-covert. Maybe stuff like timing and tor?
Cheers,
waxwing/AdamISZ
On Monday, January 6, 2025 at 8:31:34 AM UTC-6 Yuval Kogman wrote:
> On Mon, 6 Jan 2025 at 14:08, Sjors Provoost <sj...@sprovoost•nl> wrote:
>
> > Do we know based on observations or published server-side code whether
> > this key was:
>
> > 1) the same for all time; or
> > 2) unique for each round; or
> > 3) unique for each registration request
> >
> > In case of (1) and (2) it would have been possible to detect a targeted*
> attack,
> > of course only if you were on the lookout.
>
> Only (2) would be correct behavior. If (3) was performed, then that is
> just the tagging attack. If (1) was done, then that would have allowed
> clients to stockpile blind signatures in earlier rounds, and register
> excess outputs during the output registration phase of later ones to
> disrupt them (wasabi 1 had this bug FWIW).
>
> if the archived code is considered reliable, then it seems (2) was the
> implemented behavior:
>
>
> https://github.com/Archive-Samourai-Wallet/whirlpool-server/blob/develop/src/main/java/com/samourai/whirlpool/server/beans/Mix.java#L67
>
> > Perhaps if the app kept sufficient logs, it would still be possible to
> retroactively
> > check this.
>
> I'm not aware of any such observation efforts. They would require
> modifying the client, at least with the archived version that I saw
> the `blindingParams` member is not used that way (there are other
> debug logs in the whirlpool client, but not with this data).
>
> However, since the public key is only given in response to input
> registration, i.e. after the server has learned of the intended UTXO,
> and because in many cases an xpub linking that coin may have also been
> revealed to the server, and the server controls the grouping of coins
> into sets of 5, it seems to me that if it was controlled by a rational
> attacker it would not use the overt key tagging attack when covert
> ways of deanonymizing are available and just as effective.
>
> > * = I’m thinking of an active attacker who wants to track specific UTXOs.
> > They could preemptively “persuade” the coordinator server to provide
> > a different RSA key or round ID if they ever try to join a round.
>
> While this is certainly possible, maintaining plausible deniability is
> easier if the server merely maliciously control the placement of
> UTXOs, ensuring that targeted UTXOs end up only with xpub-revealed
> and/or adversary controlled peers.
>
> > Are these round IDs logged by clients?
>
> In the case of wasabi, both my recollection and a cursory search
> indicates that yes:
>
>
> https://github.com/WalletWasabi/WalletWasabi/blob/42e7963d7fffc7f8f37fd9b6e8973235859ee7fb/WalletWasabi/WabiSabi/LoggerTools.cs#L36
>
> I did not check in detail where this information is logged, and I
> don't think a list of all published round IDs is logged.
>
> I would not encourage users to share such logs, or their data, without
> careful considerations. Even if logs were scrubbed, revealing a/the
> set of rounds in which a user participated can significantly harm
> privacy, especially since participation in rounds and coin selection
> does not take into account history intersection attacks. See also
> these issues re log scrubbing
> https://github.com/WalletWasabi/WalletWasabi/issues/6770
> https://github.com/WalletWasabi/WalletWasabi/issues/6670 (first was
> closed without fixing, deemed duplicate of 2nd - i'd say it isn't -
> which is still open...).
>
> One of the developers still working on wasabi indicated that there
> will finally be some efforts to mitigate this class of attack:
>
> 1. redundant queries from isolated tor circuits of the round status
> information where round IDs are published, and consistency checks for
> the data returned
> 2. use of deterministic shuffling in the transaction, ensuring that
> signatures can only be aggregated in the absence of equivocation
> (assuming the corresponding Lehmer code has enough bits of entropy)
>
> Since round IDs are published ahead of time in the status requests,
> and clients explicitly choose which round to join before revealing any
> of their intended inputs, the first mitigation is straightforward and
> would present a significant barrier.
>
--
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/6a5ac106-6f8d-480d-91f6-0b9796977554n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 12752 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2025-01-07 15:56 ` waxwing/ AdamISZ
@ 2025-01-07 21:33 ` Yuval Kogman
0 siblings, 0 replies; 10+ messages in thread
From: Yuval Kogman @ 2025-01-07 21:33 UTC (permalink / raw)
To: waxwing/ AdamISZ; +Cc: Bitcoin Development Mailing List
On Tue, 7 Jan 2025 at 16:59, waxwing/ AdamISZ <ekaggata@gmail•com> wrote:
> What's clear is that this risk is far worse with a static central coordinator for all joins rather than the "each new participant coordinates" model. Also to correct a common imprecision (so not ofc addressed to you nothingmuch, but to the reader): the taker-maker model is *not* incompatible with coordinator blinding.
Nor is it even limited to a centralized coordinator (e.g. if
instantiated with a threshold issuance scheme). Another misconception
is that such a mechanism helps privacy, when all it can do is provide
denial of service resistance potentially without undermining privacy,
but does nothing to actually improve it directly. The misconception is
not accidental, as often wabisabi credentials are portrayed as privacy
enhancing.
> 2/ the ability of the coordinator to tag a targeted user by shenanigans with the blinding key, roundID etc.
>
> The story you tell on this is interesting. In short, as per the "fundamental weakness" paragraph above, it's the nature of these systems that the user is anonymous and ephemeral and therefore the only "identity" they have is the coin they bring to the join. Given that, attestations being verifiable requires blockchain access as the ground truth. For similar things in Joinmarket's protocol (and rest assured, we had the same requirement, basically), we never had to bat an eye, because we could make calls on the utxo set at any time, since we *force* users to use full nodes. But as you say, it *should* still be fully possible with various kinds of light client ...
Indeed. Wasabi has optional full node support, and yet this check was
never implemented. For light clients various reduced soundness
mitigation are possible that would still make it significantly harder
to do this successfully.
> so I am wondering why the people working on the Wasabi project didn't consider this a sine-qua-non.
Well, FWIW I was, it came up repeatedly and I always assumed that it
was supposed to be essential (see the footnote links in initial email
for lots of supporting evidence). The oldest instance I found of me
explicitly mentioning such consistency issues dates back to before the
wabisabi design was in place, and I would think a company with "zk" in
the name and which repeatedly used phrases like "can't be evil" and
"trustless" to describe its service would care, but alas it did not
work out that way. This is especially concerning since everyone
involved knew there was a good chance that alternative coordinators
are very likely in the future.
> Why even bother with blinding if you're not going to give the client a surety that the blinding is actually doing anything?
Ostensibly denial of service protection. If being cynical, DoS
protection only for the coordinator and not the users. But even that
is empirically unmotivated given that the first 3 wasabi protocols had
cryptographic flaws in the denial of service protection, but when DoS
attacks finally arrived they exploited misconfiguration of digital
ocean firewall (no datacenter level firewall was configured) and the
recourse was enabling cloudflare with SSL termination.
The simpler explanation is that it's an affinity scam, and regrettably
I was tricked and exploited into effectively becoming a rubber stamp
of approval with the intent of deceiving non-technical users to pay
the coordination fees. Just one supporting example, note how how an
audit of the code was announced
https://github.com/orgs/WalletWasabi/discussions/7262 but it fails
fails to mention that the audit only accounts for protocol security
that protects the coordinator against malicious users, and that the
non cryptographic but privacy sensitive code protecting clients was
not audited.
> On reflection, I can see at least one counter-argument: suppose user2 is looking at user1's signature on the context of the round, and they are given key P for user1's signature and just told "trust me" by the coordinator, and they go ahead, because user2 only has a light client and no merkle proofs. Well, if the coordinator lies about P, the user2 can find out later that day, using a full node or block explorer to check user1's utxo. Now, if the coordinator's message is *signed* so as to be non-repudiable, then user2 can prove to the world that the coordinator lied. Conditional on that signing, I think this counter-argument is strong; in the absence of signing, with repudiable messages instead, then I think it's weak.
Yep, publishing such signatures would have been a significant
mitigation of the various tagging concerns. i don't remember if
something like this was brought after they decided not to provide
clients with the ownership proofs at all in the initial release.
Ownership proofs were later included, but only covering the threat
model for stateless signers
https://github.com/WalletWasabi/WalletWasabi/pull/8708. Also note how
this commit reverts a fix in the original PR, restoring dummy data in
lieu of a meaningful commitment to the coordinator address, presumably
with this rationale:
https://github.com/WalletWasabi/WalletWasabi/issues/5992#issuecomment-1538230320
i.e. it's already broken and released so it's too late to fix
anything).
> I guess all this comes into particularly sharp focus now that we have various different Wasabi coordinators. They should all be assumed to be run by the Feds, so to speak, and analyzed from that perspective. (not that that wasn't true with only 1, just that it's more true, now).
Yep... The most popular coordinator still in use is described by its
operator as "free" and "trustless", and has publicly admitted to be
incapable of understanding these issues. As usual, there is a profit
motive at play, see liquisabi.com for revenue estimates.
> My gut reaction is to do "permanent key tweaked with context" here, so the client could easily verify, based on remembering the permanent key, that the correct (hash of date plus round number plus whatever) had been applied. But that works in Schnorr family, I don't know if a key tweak can be applied to RSA? Perhaps this question is academic, but I want to know how easily this could have been fixed in practice. (I don't know why they were using RSA, but I could imagine various practical reasons; there were after all known attacks on Schnorr blinded signing).>
Afaik RSA was just the obvious choice at the time for both (nopara is
on the public record admitting he copied the RSA blind signing code
from stack overflow... no clue about whirlpool's stated design
rationale). In hindsight, this is arguably better than blind Schnorr,
since Wagner attack mitigation is rather complex though not impossible
(wasabi also had a nonce reuse issue with the blind signing key in the
1st iteration of blind introduced in this PR Schnorr
https://github.com/WalletWasabi/WalletWasabi/pull/1006 and Wagner
attack only became relevant after that)
A tweaked key would indeed work very well for this kind of mitigation,
as the untweaked key could have even been hard coded in the client,
and the client could locally tweak it with the round ID as the
committed data. This should also be possible with blind DH e-cash /
privacy pass tokens, and the wabisabi issuer parameters, which are
just an n-tuple of ECC public keys and similarly amenable to TR style
commitments.
> > 2. use of deterministic shuffling in the transaction, ensuring that signatures can only be aggregated in the absence of equivocation (assuming the corresponding Lehmer code has enough bits of entropy)
>
> That's an elegant idea; I presume it depends on tx size being large enough (yeah, bits of entropy), but that certainly isn't an issue for the Wa(bi)sabi design. Couldn't a similar trick be played with the coordinator's receiving address (assuming that wasabi still works like that, with a coordinator fee address in the tx)?
Yes. It could be an OP_RETURN of course, and not a very costly one. It
could be a pay to contract, if the coordinator is willing to risk not
losing these transcripts, but if published that should not be a
concern, just complexity in the coordinator's wallet. If the
coordinator consolidates any inputs, it could be sign to contract,
eliminating that risk. That said, coordinator fee support has been
removed recently, partly because the fees were never enforced using
the anonymous credential mechanism and client side determination of
the effective values of inputs after deducting such fees, what has led
to abusive coordinators siphoning user funds.
Successfully equivocating transcripts reduces to a multi-collision
attack. For the easiest case, that of a 2-collision to single out
exactly one target user, two transcripts would need to be found such
that the hashes encoded in the order collide. Even if n-1 users are
honest, and the parameters were fully then this is still not a 2nd
preimage attack, since nothing prevents a malicious coordinator from
contributing the last input, and grinding ownership proofs on it to
collide with the transcript observed by the targetted user. log2(40!)
is ~159, just shy of standard NIST recommendations for collision
resistance, note that this is for one list, but inputs and outputs are
two separate ones, so log2(24!) ~= 79, would have cryptographic
soundness if there are least 25 inputs and 25 outputs. The main
benefit of this approach is that it saves a round trip, all clients
can just sort the transaction locally and contribute signatures
knowing the transaction would go through only if they all agree, but
this round trip elimination comes with the liability of divulging to
the potentially malicious coordinator what a client had intended to
do.
That said, partitioning all clients is an n-collision, so harder to do
than just finding a 2 collision, and doing "just" 2^80 work in between
learning the final output set and signature aggregation is very
generous to the adversary, but either way the assumption was there'd
be on the order of 100 inputs as a starting condition (in practice
that figure is even higher), so much so that even the current sorting
by amount is retained, just shuffling equivalent valued outputs would
suffice for Lehmer coding a hash image with security level 2^160 (e.g.
~40 equivalence classes of 4 outputs each).
> > it seems to me that if it was controlled by a rational attacker it would not use the overt key tagging attack when covert ways of deanonymizing are available and just as effective.
Absolutely, and also note that using any kind of
commit-to-the-transcript-in-the-transaction approach does not
guarantee the coordinator will be caught unless users independently
coordinate to check for consistency after the fact, nor does it
prevent any privacy leaks arising from coin selection, or the choice
of outputs.
> It seems I missed something, here. What covert attacks are possible except for Sybilling, excluding other users from the round? - which is only at best semi-covert. Maybe stuff like timing and tor?
You didn't miss anything, I only described the long standing active
attacker concern, which I had described before the release due to the
recent "vulnerability" and subsequent "fix": GingerWallet's round ID
hash preimage validation was inexplicably lost in a refactor, and then
restored. They claimed that this active adversary concern was a new
attack, and that it was fully mitigated, neither of which is true.
Usually when I criticized Wasabi in the past, not here, it was over
these passive deanonymization concerns, which IMO are much more severe
than the active ones for precisely the reasoning you gave above.
1. "optimistic" (ugh) approach to coin selection (first select coins,
then try to register, high probability that not all can be registered
due to abrupt cutoff, then figure out how to decompose the resulting
balance), and some ad-hoc tweaks that de-randomize it in order to deal
with some of the fragmentation issues that poor amount decomposition
resulted is a major concern, especially since there's no accounting
whatsoever for history intersection. if the adversary has some
fore-knowledge of a wallet's cluster, then this informs the adversary
of likely output value choices, and subsequent coinjoins or payment
transactions can confirm and further undermine this through history
intersection.
2. initially the tor circuit management was highly problematic, more
recently it has been partly mitigated, but there are still potential
timing leaks especially considering that the guard node will be fixed
for a given client's circuits, reducing total variance for circuits.
before they switched to clearnet coordinator w/ cloudflare + SSL
termination as a trusted middleman this was more severe, due to the 2x
factor in # of circuits required for hidden services.
3. the use of HTTP and JSON at the protocol level, neither of which is
sufficiently rigid to be canonical, and reliance on *varying* 3rd
party implementations of both (i.e.
https://github.com/WalletWasabi/WalletWasabi/pull/13339) between
different versions of the client presents another set of semantic
leaks...
These independent (i.e. potentially compounding) leaks can
additionally be covertly amplified delaying or dropping coordinator
responses (this in particular exploits the lack of request timing
randomization during reissuance or output registration requests, by
delaying responses to credential reissuance requests, if only one
client is actually able to register an output when the first output
registration is received, that's a deterministic link, for example).
If such leaks are insufficient for the adversary to conclude that the
a posteriori outcome is deanonymizable, then it can of course just
disrupt the session forcing a blame round with plausible deniability.
There's some discussions of some of these concerns e.g. here
https://github.com/WalletWasabi/WabiSabi/issues/83
Part of what's so frustrating about my experience is that in addition
to my criticisms seeming like a gish gallop simply because there are
so many flaws, the "rebuttals" against these privacy leaks this were
always in the spirit of "oh yeah? so why don't you deanonymize this
transaction? oh you can't?", which is morally bankrupt given the
profit motive and vulnerable and misinformed users' lives potentially
being be at risk. More generally, it is well known e.g. from the
mixnet literature that attackers generally have exponential advantage
in every marginal bit of leak information, nevermind the fact that
these concerns are specifically about a malicious coordinator not a
3rd party observer (there the concerns about balance decomposition and
coin selection are still relevant FWIW), which is why in privacy
enhancing technologies usually the burden of proof rests with the
defender, not the attacker.
--
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/CAAQdECAg5W4a9_386FeGWBZnv7zje4gmXtAMcC8scWq_o2dEwg%40mail.gmail.com.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2024-12-21 14:16 [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks Yuval Kogman
2025-01-06 13:07 ` Sjors Provoost
@ 2025-01-23 16:25 ` Peter Todd
2025-01-24 16:00 ` Peter Todd
` (2 more replies)
1 sibling, 3 replies; 10+ messages in thread
From: Peter Todd @ 2025-01-23 16:25 UTC (permalink / raw)
To: Yuval Kogman; +Cc: Bitcoin Development Mailing List
[-- 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 --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2025-01-23 16:25 ` Peter Todd
@ 2025-01-24 16:00 ` Peter Todd
2025-01-24 16:38 ` waxwing/ AdamISZ
2025-02-04 14:02 ` Yuval Kogman
2 siblings, 0 replies; 10+ messages in thread
From: Peter Todd @ 2025-01-24 16:00 UTC (permalink / raw)
To: Yuval Kogman; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 1264 bytes --]
On Thu, Jan 23, 2025 at 04:25:46PM +0000, Peter Todd wrote:
> 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.
Sorry, I forgot one condition in that paragraph. Here's what it should
have said:
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, *and* also validates 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.
--
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/Z5O5HGWyM597drg3%40petertodd.org.
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2025-01-23 16:25 ` Peter Todd
2025-01-24 16:00 ` Peter Todd
@ 2025-01-24 16:38 ` waxwing/ AdamISZ
2025-02-04 14:02 ` Yuval Kogman
2 siblings, 0 replies; 10+ messages in thread
From: waxwing/ AdamISZ @ 2025-01-24 16:38 UTC (permalink / raw)
To: Bitcoin Development Mailing List
[-- Attachment #1.1: Type: text/plain, Size: 2176 bytes --]
> 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 bitcoindev+unsubscribe@googlegroups•com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/5fcbe15c-2793-44a7-88d1-e708c224f2fdn%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 2699 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2025-01-23 16:25 ` Peter Todd
2025-01-24 16:00 ` Peter Todd
2025-01-24 16:38 ` waxwing/ AdamISZ
@ 2025-02-04 14:02 ` Yuval Kogman
2025-02-04 22:22 ` Peter Todd
2 siblings, 1 reply; 10+ messages in thread
From: Yuval Kogman @ 2025-02-04 14:02 UTC (permalink / raw)
Cc: Bitcoin Development Mailing List
This subject of this is about the possibility of active tagging
deanonymization attacks by a malicious coordinator, so I will address
the claims pertaining to that first, and the rest of the claims in
order of relevance.
There's also an important correction, due to Sjors: I overlooked a
relevant detail of BIP 341 and misremembered the related behavior when
I did consider it. The implication is that transactions that spend at
least one P2TR input partially mitigates the simplest form of this
attack, but as detailed below it's not a sufficient mitigation.
A brief summary:
1. Your proposed mitigation for the tagging attack is inadequate and
is redundant when P2TR inputs are spent.
2. Your unsubstantiated minimization of issues relating to input-input
link disclosure, in failed rounds and otherwise, can be dismissed by 3
separate lines of argument. such leaks are *very* relevant for this
attack.
3. Your account of sybil resistance ignores important nuances, but at
any rate that isn't really relevant to the subject.
4. You neglect to disclose a relevant conflict of interest which is
relevant context re (2).
Note:
At the request of the moderators I have edited out some of the additional
context I initially provided, as it is not directly related to the technical
matter at hand. While I understand why this forum is perhaps not the
appropriate one to bring that up, I stand by what I said and personally still
feel that *is* relevant, due to misinformation about the services and software
offered by for profit privacy vendors. If anyone is interested in the full
message, I have posted it publicly. Feel free to reply off list if you'd like
to read it and are having trouble finding it.
On Thu, 23 Jan 2025 at 17:25, Peter Todd <pete@petertodd•org> wrote:
# Tagging Attack by Active Adversary
> As you mention, here we have a form of MITM attack, leveraged to perform
> a sybil attack
While it's nice to see that you're acknowledging that the attack is
indeed possible, i.e. that the protocol is not trustless, your account
of how it works is somewhat misleading. The idiosyncratic use of
"sybil" is pretty common, but you go a bit further than just using it
as a convenient shorthand in your framing, confusing different attack
scenarios. This is a distraction. While sybil attacks are relevant to
deanonymization, that's qualitatively different and using "sybil"
attacks to refer to deanonymization attacks more generally obscures
the concern raised here.
So to be clear, this is not a sybil attack, where by definition the
attacker controls many apparent users. This attack is by a malicious
coordinator, and does not require it to control any of the coins used
as inputs. n-1 deanonymization attacks can be executed by means of
sybil attack, so often sybil attacks refer to n-1 deanonymization
attacks in this context, but sybils are not at all the mechanism
involved in this attack on anonymity.
## Attack Overview and Adversary Capabilities
Here's a more detailed and accurate description of how the attack is
performed, which at Sjors' request includes more details and
preliminaries about the transport layer. Note that not all steps need
to be executed for this to be an attack, see the details below for the
choices available.
1. n honest (i.e. not sybil) clients query round information from a
malicious coordinator. The coordinator responds to each request with a
unique round ID.
2. Each client then registers its inputs using isolated tor circuits,
but with respect to the maliciously chosen round ID, which links all
of these requests to the initial status request.
3. The coordinator terminates the connection confirmation phase for
each round, and misleads clients into thinking the n-1 other clients
are also participating in the same round.
4. Clients register their desired outputs, and again clients are
partitioned with each output registration uniquely identifying which
client it belongs to using the per client round ID.
5. The coordinator terminates the output registration phase, providing
clients with the unsigned transaction, and they submit their
signatures.
## Tor Circuits & Connections
As background, it's important to distinguish between circuits and
connections made over these circuits. Circuits are multi hop, onion
routed end to end encrypted channels utilizing the tor relay protocol,
between a client node and a tor relay. The client directly
communicates (TCP + TLS) with its guard node (1st hop), which is
directly connected to the 2nd relay to which the client's onion
encrypted messages are forwarded, and the 2nd relay is similarly
connected to the 3rd relay, which is used as an exit node. There
are/were 1500-2000 exit nodes in operation since Wasabi 2 was released
(https://metrics.torproject.org/relayflags.html). Hidden service
connections are no longer relevant for Wasabi (or its derivatives,
e.g. gingerwallet and to a lesser extent the btcpay plugin) so will
not be discussed here, but they were relevant at the time of launch.
Once a circuit is established to an exit node, the client can ask it
to make connections - which are full duplex streams analogous to TCP
connections - to the coordinator over clearnet. These connections
(called "streams" in the relay protocol documentation
https://spec.torproject.org/tor-spec/) are multiplexed over a circuit,
and circuits are multiplexed over the underlying TCP connections to
and between relays, but over clearnet map 1:1 to TCP connections made
by the exit node on behalf of the client. TLS is employed, so the exit
node can't MITM traffic, but cloudflare with SSL termination was used
for the zksnacks coordinator and is still used for kruw's coordinator,
so thinking of "the coordinator" as adversarial includes cloudflare,
they effectively MITM all connections, and see all unencrypted
traffic.
Wasabi uses SOCKS to connect to the local Tor daemon. Tor daemon
treats any SOCKS authentication credentials (which are always
accepted) as isolation IDs: connections associated with differing IDs
may never share a circuit. The same ID may end up being mapped to
multiple circuits as necessary, as circuits are a dynamic resource.
Wasabi then uses HTTP to make requests over these connections.
Previously a bespoke HTTP 1.1 client was used, with keep-alive
explicitly requested, but now the standard dot net HTTP client is
used, with HTTP 1.1 still being preferred, and IIUC keep alive is also
used by default with this implementation.
https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/WebClients/Wasabi/WasabiHttpClientFactory.cs#L130
Initiating multiple SOCKS connections with distinct isolation IDs in
quick succession will not result in Tor building circuits
concurrently, but sequentially. Any failures in allocating circuits or
opening connections can appear as increased latency from the point of
view of the SOCKS interface, or as a dropped connection depending on
whether the failure occurs before or after stream data was sent to the
intended endpoint. The time to first byte can be on the order of tens
of seconds even on success during bursty activity.
Wasabi uses distinct isolation IDs for input registration, reissuance
and output registration requests, and a long lived one for status
polling. Wasabi also randomizes the timing of requests, but
inadequately.
## Step 1
The `GetStatus` API is repeatedly polled to obtain data about in
progress rounds, including `MultipartyTransactionState`, essentially
an event log. This includes registered inputs, the ownership proofs
and previous transaction outputs, and outputs. When I refer to the
"transcript" I mean this ordered log of events, including hashes of
all credential requests associated with the events.
These requests use the same isolation ID throughout
https://github.com/WalletWasabi/WalletWasabi/blob/b49e69d48e6f599235cc3c518c2cf8e3e9206571/WalletWasabi/WabiSabi/Client/WabiSabiHttpApiClient.cs#L16
For each round the client knows about it asks the server to only
respond with whose index is greater than a given checkpoint. When
input registration events are observed by the client, it verifies the
ownership against the scriptPubKey also included in the event data,
and ensures that the ownership proof commitment data includes the
expected round id.
The index (which is under the coordinator's control given it chooses
how many events to return in reply to each request), and the
connection & request patterns all makes it relatively straightforward
for the coordinator to maintain different views for different clients.
Furthermore, the client respects the precedence order of rounds, so
divulging other clients' round IDs as necessary is not an issue for a
coordinator attempting to cause a client to register inputs for a
specific round ID.
An initial request from a client that has no checkpoints and comes
from an isolated tor circuit at a random time can be anonymous, as it
does not reveal any linking information to the client (apart from the
potential HTTP related client version fingerprints which I will ignore
henceforth).
## Step 2
During this step the full mapping of input-input links is revealed,
because all input registration requests from a particular client will
be sent with respect to the round ID that uniquely identifies that
client. As of today, the client software does not mitigate or even
detect this at any step. This is a serious concern, see the section on
input-input linking below for discussion of why. In this section I
will focus on the how.
Since round initiation time is not known, clients repeatedly confirm
their input registration, until a final confirmation request that
issues credentials.
A malicious coordinator can affect coin selection criteria
(constraints and suggestions). In particular, by flooding more than
one round per client and offering relatively disjoint valid selections
a coordinator can ellicit information about the preferences of the
client, on top of common ownership clusters, can aid it in optimizing
for higher rates of wallet clustering by repeated disclosure attacks
(e.g. by aborting rounds). The coin selection code has no memory of
the adversarial inputs or its own selections. Deliberate
de-randomization with ad-hoc rules makes this algorithm more
susceptible to harmful choices, for example the bias towards larger
valued coins interacts with the maximum allowed and suggested values.
- https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/WabiSabi/Client/CoinJoin/Client/CoinJoinClient.cs#L179-L181
- https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/WabiSabi/Client/CoinJoin/Client/CoinJoinCoinSelector.cs#L50-L303
Unlike the common input ownership heuristic applied as applied to
confirmed transactions this can be iterated by the attacker. The
iterative nature and cluster revelation bears some resembles the
privacy leaks in BIP 37 filters discovered by Jonas Nick
(https://www.research-collection.ethz.ch/bitstream/handle/20.500.11850/155286/eth-48205-01.pdf),
as well as this more recent work which investigates clustering using
unconfirmed transactions (https://arxiv.org/pdf/2303.01012).
Qualitatively it seems to me that this is more harmful, given the
nature of the coins that are meant to be selected into privacy
enhancing transactions. The client's leniency makes focusing on input
clustering only a costless and practically covert attack, even though
technically it's an active one, so the client need not trust the
coordinator not to do it.
## Step 3
Only at this step are the input registration events published by the
server, but note that this apparent phase change can be different for
each adversarially constructed round. Although the initial input set
is finalized at once, this is represented as many discrete events in
the log, which if clients are sharing the same round ID (see step 5
for why), which affords the coordinator a tagging vector (manipulating
the checkpoint index). In addition to there being sufficiently many
indexes to identify each input uniquely, the order of these events is
not constrained, since nowhere is the transcript (see above) actually
committed to.
After this no additional inputs are allowed (incidentally this is a
perverse incentive to de-randomize input registration timing). From an
adversarial point of view this mean given a set of inputs whose real
ownership proofs commit to distinct round IDs, it can choose for each
input cluster what subset of other forged inputs it can see, and which
input (clusters) to reject, for example by aborting with "not enough
participants" or "load balancing" conditions, which are considered
normal (but are at least logged).
For an adversarially chosen input set, which can contain entirely made
up coins with arbitrary values, real ones controlled by the adversary
if the coordinator is also doing a sybil attack, chosen in order to
influence output registration decisions, there is no restriction on
the same set of outpoints to be used unless the coordinator wishes to
also obtain output registrations or signatures.
## Step 4
Here the client reveals its intended output registrations, linking
them to the already linked inputs (i.e. the full sub-transaction of
that client). Inputs signal their readiness to sign. When all inputs
have signalled, the output registration phase terminates. Here too
there is room for partitioning clients in a more covert variation,
since all individual clients know is how many of their inputs have
signalled readiness to sign. This information is not included in the
`MultipartyTransactionState` event log, but should be part of the
transcript.
## Step 5
At this stage the client calculates the final transaction by sorting
the inputs and outputs from the event log, first by amount then
outpoint or scriptPubKey.
The coordinator can freely ignore/censor certain signatures (valid or
invalid ones), and trigger a blame round. In blame rounds the allowed
outpoints must be a subset of the previous round's outpoints. By
equivocating the `BlameOf` field of the round parameters in
conjunction with the other tagging vectors (i.e. not unique round
IDs), clients can be misled into believing the same blame round ID is
associated with more than one previous round ID, because his field is
not hashed when deriving round IDs:
https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/WabiSabi/Crypto/RoundHasher.cs#L13-L32
P2WPKH inputs sign according to BIP 143, where each signature commits
to the list of outpoints. P2TR outputs sign according to BIP 341,
which also commits to the scriptPubKeys and amounts, which are taken
the event log. This means that taproot inputs will not produce valid
signatures if they observe equivocated ownership proofs. Thanks to
Sjors for this correction, I misremembered this as only committing to
the values of the coins. No such restriction exists for P2WPKH
outputs. This restricts a malicious coordinator ability to tag using
equivocated round IDs when P2TR inputs are spent, but this does not
preclude tagging those outputs by other means (i.e. checkpoint leak,
differential timing as discussed in more detail here
https://github.com/WalletWasabi/WabiSabi/issues/83 and exploiting soft
aborts to allow unbounded iteration of these attacks) nor the
interaction with the `BlameOf` field in the round ID derivation, see
below for details.
In other words even though taproot signing prevents equivocated
ownership proofs from being used to successfully tag a fully signed
transaction if it contains at least one P2TR input, it's possible to
use tagging to reveal the input clusters, and then restrict subsequent
blame rounds to only the already tagged inputs, and only permit
transactions which the adversary is confident sufficiently link the
outputs to the input clusters to succeed.
## Issues with Peter's Mitigation
> 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.
This mitigation, which is redundant with BIP 341 signing, is strictly
inferior to the 4 possible mitigations already mentioned in this
thread, none of which were implemented:
1. redundant queries of round information over isolated tor circuits
2. best effort validation of ownership proofs under SPV assumptions
3. deterministic shuffling of transaction data seeded by transcript hash
4. have the coordinator publicly sign the transcript before signatures
are submitted
Unlike (1) and (2) this check is not done before proceeding with the
protocol, and unlike (3) and (4) it is not done before aggregating
signatures, and so does not prevent going through with a maliciously
constructed transaction. The victim pays for the attack (mining fees
and optionally contributing to coordinator revenue), and only
discovers it occurred after the fact. See below for some additional
consequences of this flaw.
Unlike (3) and (4), which can confirm the full transcript, this only
checks consistency of the round ID. That makes sense for (1) and (2),
but not for a check done after the fact.
Unlike (4), a public signature is non-repudiable making it possible to
prove that a malicious coordinator equivocated. With the aid of a 3rd
party, something analogous to (1) can be used to prove equivocation,
assuming the 3rd party is trusted by the verifier of that claim
(something like TLS notary). a variant of this was considered during
the design, but without taking into account waxwing/AdamISZ's insight
about the non-repudiation property.
Finally, as mentioned above for P2TR outputs this mitigation is
already redundant with the hashing specified in BIP 341. That has an
effect similar (3) but unfortunately does *not* commit to the full
transcript but only the set of ownership proofs. Like mitigation (3)
this happens too late in the protocol, and without additionally
implementing mitigations (1) and/or (2), is insufficient.
(1) and (2) are not protocol breaking changes. I previously
erroneously described a weak form of (3) as possible, because I
misremembered this as only performing a stable sort by amount, but
that is not the case as they are explicitly sorted by outpoint /
script, so unfortunately that makes mitigation (3) a protocol breaking
change.
> The only question left for this technique is a cryptography one:
No. The question, and far from the only one, is why were none of the
stronger and fully described (before mainnet release) mitigations
implemented at launch or at any subsequent point, despite repeated
claims of the protocol being trustless?
- https://web.archive.org/web/20240521010051/https://blog.wasabiwallet.io/wasabi2-0-released/#:~:text=that%20implements%20trustless%20WabiSabi%20coinjoin%20over%20the%20Tor%20anonymity%20network.
- https://archive.is/dtPd9
- https://archive.is/Vi46a
- https://archive.is/vexOP
- https://archive.is/l5Qko (two lies in one tweet, cloudflare was a
trusted 3rd party and still is with kruw's coordinator)
- https://bitcointalk.org/index.php?topic=5482818.msg64055886#msg64055886
Why were the concessions with regards to section 7.2.2 of the paper
not justified? Why did two of the named authors not not disown or
retract the paper if they don't stand by its contents? Especially as
they were representatives of a for profit coordinator?
https://eprint.iacr.org/2021/206.pdf
At least I agree with the framing of this as an essentially solved
problem, just with respect to the proper mitigations, which just makes
their omission from the implementation even more baffling.
> 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?
Malleability of the signature or public key under weak fiat shamir
(i.e. ECDSA) is irrelevant, as waxwing points out in his reply the
commitment data is strongly bound by the challenge hash. The public
keys bind that commitment to an unforgeably costly resource (UTXOs),
and for all relevant output types this key is still strongly bound by
the scriptPubKey (P2{W,}PKH) and so also made available in the
ownership proof data (since BIP 322 proofs have the same format as
transaction signatures) and the final signature data.
Waiting for confirmation merely proves that either this was consensus
valid, or that the attacker was willing to expend PoW on it although
that too is irrelevant since Wasabi doesn't actually validate
difficulty / chain work unless it is configured to check against a
trusted node, in which case mitigation (2) would provide complete
certainty.
# Input-Input Linking, Consequences for On Chain Privacy
> 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.
This is only true if one ignores *all* aspects of the protocol apart
from liveness, which the coordinator is trusted with anyway (which is
OK, unlike trusting it with respect to privacy, "semi honest" threat
model) and security against theft which excluding the concern for
stateless signers (which if the ownership proofs are faked, a
stateless signer would not recognize as its own) is at least verified
by clients. See below on the topic of light clients.
However, this does not follow with regards to privacy. You write:
> 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.
Intersection attacks, first introduced in the context of mixnets, have
been considered in the context of coinjoins since at least 2014
(https://people.cs.umass.edu/~gbiss/mixing.pdf) and applied to
coinjoins and wallet clustering since 2017
(https://petsymposium.org/popets/2018/popets-2018-0038.pdf). This work
is not explicitly cited in the wabisabi paper as the on-chain aspects
were considered out of scope in the paper, which is only concerned
with the KVAC DoS control mechanism and its privacy consequences. That
you don't find it interesting without any further justification is,
most charitably, a reflection of the depth of your research into this
subject.
Concerns about intersection attacks, especially as described in the
cookie meets the blockchain paper (i.e. use of out of band leaks that
can't be accounted for in anonymity set estimates based only on
on-chain data) are justified if the coordinator is only considered
semi-honest (trusted with liveness, not with privacy).
As a concept, intersection attacks are also taken for granted in the
code when estimating anonymity set sizes:
https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/Blockchain/Analysis/BlockchainAnalyzer.cs#L161-L183
Of course, as the cookie meets the blockchain paper discusses,
intersection attacks are part of a broader family of clustering
attacks. Note especially the caveats in the paper about limitations of
the result when clusters are disjoint, making the input-input links
particularly relevant for an attacker attempting to cluster coinjoin
outputs. Intersection attacks both rely on and are amplified by other
wallet clustering techniques. The Wang et al paper linked above, which
discusses clustering based on unconfirmed transactions, includes a
useful and fairly up to date survey of these techniques. Other recent
notable work is the cited Kappos et al
(https://www.usenix.org/system/files/sec22-kappos.pdf) and Moser &
Narayanan's recent work (https://arxiv.org/pdf/2107.05749) both of
which improve clustering by utilizing wallet fingerprinting.
Fingerprinting is another subject that has seen recent progress
recently (https://ishaana.com/blog/wallet_fingerprinting/).
Given the adversarial control over aborts, the more minor tagging
vectors, the lack of binding of the `BlameOf` field and the gamable
coin selection a strategic malicious coordinator can manipulate
clients into only completing successful rounds when it is able to
successfully cluster the outputs even if reliant on the round ID
equivocation mechanism, as must be the case for taproot inputs.
So to put it bluntly, because there is no other way to put it, your
theory of "anonymity set size" as calculated by wasabi is simplistic,
and ignores the vast literature on privacy such as work on mixnets,
and the entropic anonymity set perspective (the way deanonymization
attacks generally compound typically resulting in an exponential decay
of privacy). This all has been well understood for more than 2
decades, and applies doubly so in Bitcoin's case due to the
transparent and highly replicated nature of the transaction graph, as
demonstrated by the small selection of papers I've shared here.
Secondly, there's the matter of what was specified. Leaking
information about input-input links is discussed in the wabisabi
paper, mainly discussed in section 7.2.1 and mentioned several times
throughout. Just two quotes for your consideration:
>> In order to maintain privacy clients must isolate registration requests
>> using unique network identities. A single network identity must not expose
>> more than one input or output, or more than one set of requested or
>> presented credentials.
...
>> Since every registration request is only associated with a single input
>> or output, the only information that would need to be broadcast publicly on
>> the blockchain if the protocol succeeds is revealed directly.
If this is justifiably not "interesting", then again, why are two
named co-authors of the paper evidently unable to justify lack of
consideration for this subject when it was time to implement the
protocol they are supposed to understand? Throughout all of the
references I provided, including the paper, there is not one
substantiated counter argument to *anything* of what I said: no
serious errors, no arguments against the assumptions, no refutation or
even discussion of the prior work which I had studied to substantiate
my claims.
That this was included in the threat model is again supported by the
code, which as we know uses a distinct isolation ID for each input
registration request. This is a rather expensive (in terms of latency,
failure rates, etc) implementation choice, and one which is seemingly
important (though not enough to merit an investigation how tor
circuits actually work, as can be seen here
https://github.com/WalletWasabi/WalletWasabi/issues/8420). The fact
that isolating circuits is insufficient to prevent leaks is clearly a
bug, otherwise a single isolation ID would have been considered.
Thirdly, it has been claimed by support staff and the official account
that the coordinator *can't* learn this information:
- https://archive.is/dtPd9
- https://archive.is/8xtLW
- https://archive.is/pyyuu
- https://archive.is/rpRIo
So even though you don't find it "interesting", apparently they seemed
to think that paying customers of the service do.
In other words there are 3 separate reasons to dismiss your claim that
this is not interesting:
- published and well cited research on this concern (with supporting
evidence in the code that this is in scope for wasabi's threat model)
- claims made in the wabisabi paper (again, the code agrees up to
implementation flaws)
- marketing and support claims made to paying users
And just to reiterate, the adversary isn't just the coordinator
operators, but also cloudflare, which as mentioned above, since as a
MITM it can surveil and censor any traffic between the coordinator and
the client.
# Ownership Proofs w.r.t Light Clients
Returning to light clients, not that it's that important but mainly
because you misconstrue and/or misrepresent my views and past
statements on this.
> 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.
...
> You keep bringing up lite clients, e.g. in your statement that:
...
> 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:
Your framing of my "focus" being "incorrect" is, apart from being
unsubstantiated, also disingenuous.
Wasabi is a light client, except when used in the aforementioned
hybrid mode where it's configured to query certain information from a
trusted full node. The quote you gave is explicitly talking about the
difficulty of validating ownership proof *before* the round commences,
to avoid disclosing any actions to a malicious coordinator. It was
made under the assumption that at least wasabi clients configured to
use a full node would protect against these issues. They don't, with
no reasonable explanation given other than that the full node
integration is "not real", which for reasons I'm yet to understand
allows making some RPC requests but precludes others (which the
backend is able to make
https://github.com/WalletWasabi/WalletWasabi/blob/d8d792d339d3e467ea36eedd45f392de5ea716df/WalletWasabi/WabiSabi/Backend/Rounds/Arena.Partial.cs#L345C33-L345C46).
When I said what you quoted out of context I was working under the
assumption that one of the most basic aspects of trustlessness, namely
lack of mitigation against tagging attacks which are the subject of
this thread, would be addressed before the release. I don't know why
you seem to insist it's my "focus", when it's just a constraint
imposed by the project. Perhaps the reason is that you're confused
about what the ownership proofs actually were meant to provide
assurances against. Let's recap.
Note the opening paragraph of the issue you quote from, emphasis added here:
>> Clients need to verify ownership proofs to ensure *uniform credential
>> issuer parameters for all round participants (otherwise they might be subject
>> to tagging attacks)*, and to prevent denial of service by a malicious
>> coordinator (being tricked into creating invalid coinjoins that can't be
>> broadcast, *but which may leak information about intended outputs*).
This is separate from the concern of the coordinator validating user's
ownership proofs to protect against denial of service attacks by
malicious users, attacks on stateless signing devices (as I already
mentioned, the only reason ownership proofs were eventually given to
clients: at the time of the mainnet release only the coordinator saw
them, precluding even consistency mitigations reliant on the use of
more than one input per client) as described here
https://gnusha.org/pi/bitcoindev/CAB3F3Dv1kuJdu8veNUHa4b58TvWy=BT6zfxdhqEPBQ8rjDfWtA@mail.gmail.com/
However, as alluded to by the 2nd emphasis a primary concern with the
ownership proofs in addition to consistency of the round parameters
and transcript, is that prevout amounts are critical information for
making choices about the choices of output values. Poor output
denomination choices are a potentially catastrophic privacy leak
especially in conjunction with input-input links (addressed above)
under the sub-transaction model
(https://www.comsys.rwth-aachen.de/fileadmin/papers/2017/2017-maurer-trustcom-coinjoin.pdf)
when considering P_{O,O}, P_{I,O} values associated with a particular
output. In ginger wallet not only are these apparent prevout values
potentially under adversarial control, the coordinator simply
explicitly tells the client which denominations to use, another
unnecessary trust assumption.
This is elaborated on in this issue from which I will quote some more:
https://github.com/WalletWasabi/WalletWasabi/issues/5945
>> Clients must opportunistically verify as many ownership as possible with
>> already available blocks, and additionally verify at least one or two
>> random ownership proofs, ideally more. Full nodes can verify all ownership
>> proofs trivially, with spend status validation as well, but light clients
>> with no full node integration enabled can only check for inclusion in a
>> block (see #5533).
..
>> With some verification the confidence that the amounts given by the
>> coordinator is valid increases, but is not certain without, so it is still
>> possible for a coordinator to partition users and hide some inputs from some
>> users to bias their actions.
Without knowing the set of other users' input values, the wallet's
balance may be decomposed into a combination of output values that is
not underdetermined in the sub-transaction model, as I mention here:
https://github.com/WalletWasabi/WalletWasabi/pull/5994#issuecomment-924105739
Also note that this follows discussion of mitigations (1) and (2) and
the lack of header validation are discussed here with no substantive
defense of the lack of such mitigations, and what exactly is assured
in the light client security model (but thank you for explaining it as
though i'm confused).
# Sybil Attacks
> # Sybil Attacks In General
>
> Let's get this out of the way first.
This is also addressed in the paper, section 7.2.2. Have you read it?
> 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.
waxwing brought up *targetted* attacks in relation to the
coordinator's ability to censor honest parties, a distinction which
you are glossing over here.
> 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.
Targeted attacks are inherently cheaper. In this setting the
coordinator can try to influence the targeted user in the numerous
ways described above, and only let the transaction go through if
circumstances favor deanonymization. You yourself mention the failure
rate for rounds is high, though it's not clear if you referred to
JoinMarket or wasabi. In wasabi's case, they are much higher than they
need to be for reasons described in previous messages. There are also
incentive incompatibilities inherent in the protocol design (e.g.
https://github.com/WalletWasabi/WalletWasabi/pull/6654) that make it
rational for honest users to defect under some circumstances, and
indeed the client implements defection behavior in places that could
be prevented before comitting to a round
https://github.com/WalletWasabi/WalletWasabi/pull/7216
Secondly, coordinator revenues also need to be considered (also
discussed in the paper) in the context of sybil attacks. Notably,
kruw's coordinator earns revenues despite being advertised as "free",
and with mining fees being low recently the mining fee cost is about
as low as it can be, so really the liquidity requirement is the only
deterrence under these circumstances even for non-targeted attacks.
Bolstering this deterrent significantly is straightforward (verifiably
randomization of selected inputs), but that too was rejected by the
wasabi team, despite discussions about the value and simplicity of
this approach and its benefits over samourai's 'trust me bro it's
random" input selection. This was not fully documented, but is
mentioned in passing here (discount mechanism to incentivize honest,
low time preference users to impose a higher liquidity requirement by
earning discounts, no negative externalities to honest high time
preference users)
https://github.com/WalletWasabi/WalletWasabi/issues/5439
# Address reuse avoidance
Anyway, the final technical thing you brought up, the address gap:
> I have not verified whether or not
> this is actually true;
Wasabi uses a non standard address gap limit (114 by default), and
retains information in persistent storage about the state of keys (see
KeyState enum).
This is problematic with recovering from seed, because upon recovery
the last key used on chain will determine the next index to use. The
last key used in a failed round is not known.
> This is an
> implementation issue due to gap-limits in HD wallet implementations;
This is a privacy issue due to the dependence on off-chain state and
the inability to restore it when recovering from seed.
> 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.
With silent payments avoiding this reuse can be done statelessly under
the assumption that input sets never repeat (which they shouldn't if
the coordinator is honest and is very unlikely even if it isn't). This
does not require full receiver support at the cost of a linear scan of
the wallet's full transaction history upon recovery, discovering root
transactions starting from keys (e.g. from a normal external address
chain), if the silent payments derivation is only used for self spend
outputs.
This assumes the private scanning key is accessible (which it should
be) but requires no protocol modifications (whereas sending to 3rd
parties, or more generally without knowledge of the private scanning
key, requires cooperation of the other parties and requires blinding
to preserve privacy). With the private scanning key self spend
addresses can be computed using silent payment derivations using the
public spending keys obtained from the ownership proofs, allowing the
script pubkeys to be known for output registration.
Unfortunately this can lead to unspendable outputs, because without
strong validation of ownership proofs: if the final transaction does
not match the keys in the ownership proof then the data required for
computing the tweak is not available from the confirmed transaction.
As discussed above, if P2TR inputs are spent into the transaction
consensus validation protects against this, but P2WPKH only ones would
not, nor would their owners know their self spend tweaked outputs are
safe (spendable using only BIP 32 seed & BIP 352 scanning rules) at
the time of signing.
Under the active tagging scenario, either the tweaked private key or
the malicious ownership proofs need to be durably persisted in order
to maintain access to funds. This is not a viable solution without
validating the consistency of the ownership proofs *before* signing,
which your proposed mitigation fails to account for (but which
mitigation (3) protects against for all input types, and mitigation
(4) also protects against with the additional assumption that other
clients are honest, in both cases an honest coordinator that refuses
to accept signatures that don't match the ownership proofs eliminates
this issue).
# Conflict of Interest
It would have been appropriate for you to disclose that your review is
paid for by an interested party as a direct response to accusations I
have made:
- https://archive.is/cbffL
- https://archive.is/BJCNG
Kruw has described his service as "free" and "trustless", despite earning
revenues and despite the issues described here. Supporting evidence for
this is in the unedited version of this reply.
--
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/CAAQdECC0FG7xhxygAPEL0XD4umU%2BzH84rK-P-UDKMLaZhr1HBw%40mail.gmail.com.
^ permalink raw reply [flat|nested] 10+ messages in thread
* Re: [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
2025-02-04 14:02 ` Yuval Kogman
@ 2025-02-04 22:22 ` Peter Todd
0 siblings, 0 replies; 10+ messages in thread
From: Peter Todd @ 2025-02-04 22:22 UTC (permalink / raw)
To: Yuval Kogman; +Cc: Bitcoin Development Mailing List
[-- Attachment #1: Type: text/plain, Size: 3670 bytes --]
On Tue, Feb 04, 2025 at 03:02:01PM +0100, Yuval Kogman wrote:
I'm going to split this off because this kind of thing isn't relevant to
the actual technical details of interest to readers of their mailing
list, and I'll make it easy for the mods to decide whether or not to let
this part of the discussion through.
> # Conflict of Interest
>
> It would have been appropriate for you to disclose that your review is
> paid for by an interested party as a direct response to accusations I
> have made:
The supermajority of the people posting on this mailing list are being
paid for their work. It would be silly to pre-face every single email
with "sponsored by Foo"; what you are replying to is just an email, not
my actual review publication, which I have not completed yet.
You yourself appear to be paid to work on the topic of on-chain privacy
via your employment at Spiral; I don't see you putting disclaimers about
that.
https://x.com/spiralbtc/status/1704905217974665340
For actual public publications I've made, in recent years I've generally
said who paid for them and under what terms:
https://petertodd.org/2024/one-shot-replace-by-fee-rate
https://petertodd.org/2024/covenant-dependent-layer-2-review
https://petertodd.org/2023/v3-transactions-review
https://petertodd.org/2023/drivechains#backstory
There's some other material on that blog where payment really isn't
clear to me and not discussed. E.g. material I (partly) wrote in one
form for a client and then reworked on my own time to be a blog post.
And obviously, everything I write is arguably commercial: my full-time
employment is Bitcoin-related consulting, and publishing is one of the
main ways I get work.
> - https://archive.is/cbffL
> - https://archive.is/BJCNG
>
> Kruw has described his service as "free" and "trustless", despite earning
> revenues and despite the issues described here. Supporting evidence for
> this is in the unedited version of this reply.
Wasabi set the coordinator fee limit to 0% by default in the Jun 2024
release:
https://github.com/WalletWasabi/WalletWasabi/releases/tag/v2.0.8.1
Kruw's coordinator does not charge a coordinator fee.
Due to how Wasabi coinjoins work, coinjoins will almost always have some
small amount of sats left over that didn't decompose into standard
denominations after the transaction fee is paid. Those sats go to the
coordinator. The amounts involved are tiny, always less than the
transaction fee, as you can easily see on https://liquisabi.com/
For example, b4daaefbd53dd255a4d1507889df52fe1adcc970b5edaea1d9fc2b1c840f7367,
had 31,407sats of leftovers that went to the coordinator, out of
5,459,668,967 sats of outputs and a 104,289 sat transaction fee.
31,407 / 5,459,668,967 = 0.0006%
I'll let others decide whether or not you're being dishonest by not
mentioning the tiny amounts involved, while simultanously claiming I'm
being dishonest by not mentioning in my email that (as usual) I'm
getting paid to work on this stuff.
In particular, remember that that fees are part of the coinjoin security
model: we *need* transactions to be costly enough to prevent sybil
attacks. If anyone with access to coins can just do infinite coinjoin
transactions at zero cost, we have a potential sybil attack problem.
--
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/Z6KTD2vvdfsCpVDN%40petertodd.org.
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 833 bytes --]
^ permalink raw reply [flat|nested] 10+ messages in thread
end of thread, other threads:[~2025-02-04 22:32 UTC | newest]
Thread overview: 10+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2024-12-21 14:16 [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks Yuval Kogman
2025-01-06 13:07 ` Sjors Provoost
2025-01-06 14:30 ` Yuval Kogman
2025-01-07 15:56 ` waxwing/ AdamISZ
2025-01-07 21:33 ` Yuval Kogman
2025-01-23 16:25 ` Peter Todd
2025-01-24 16:00 ` Peter Todd
2025-01-24 16:38 ` waxwing/ AdamISZ
2025-02-04 14:02 ` Yuval Kogman
2025-02-04 22:22 ` Peter Todd
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox