* [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