public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed

* [bitcoindev] Reiterating centralized coinjoin (Wasabi & Samourai) deanonymization attacks
@ 2024-12-21 14:16 Yuval Kogman
  2025-01-06 13:07 ` Sjors Provoost
  0 siblings, 1 reply; 5+ 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] 5+ 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
    0 siblings, 1 reply; 5+ 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] 5+ 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; 5+ 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] 5+ 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; 5+ 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] 5+ 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; 5+ 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] 5+ messages in thread

end of thread, other threads:[~2025-01-07 21:40 UTC | newest]

Thread overview: 5+ 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

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox