Wasabi Wallet - Hardfork release fixed vulnerability

On 2020 May 10, Ondřej Vejpustek from TREZOR team sent a PGP encrypted message to the team of Wasabi wallet, a Bitcoin privacy wallet, containing a detailed explanation about a possible CoinJoin denial of service vulnerability, in complete accordance to their responsible security disclosure policy.  In this article, the Wasabi developers explain the timeline and actions taken until the resolution of the issue. You may read the technical explanation by Ondřej, himself, at the bottom of the post.

The vulnerability has been fixed and can no longer be exploited by a potential attacker.

Who's affected?

Before the v4 Hard Fork, an attacker could have exploited the vulnerability to perform a DoS (denial-of-service) attack, in such a way that it was difficult to identify the attacker itself. Denial of Service means that the attacker would halt the entire CoinJoin process for all other participants and Wasabi rounds would no longer work. Given the fact that we have not observed any DoS attempts thus far, we assume that no Wasabi user has been affected by the vulnerability.

It is important to specify that the attacker could neither steal users' funds nor deanonymize anyone. What they could have done was to prevent the completion of the CoinJoin process.

User Action

If you have already downloaded Wasabi Wallet v1.1.12, released on August 5th, 2020, then you are ready to take full advantage of the v4 Hard Fork; which fixed this vulnerability. In this case no user action is needed.

If you have not yet upgraded Wasabi to v1.1.12 version, then we urge you to do so; as the Hard Fork breaks the compatibility with older software.

Timeline

• 2020, May 10: Ondřej  discloses the vulnerability to the Wasabi team.
• 2020, May 11: Wasabi team confirms the existence of the vulnerability.
• 2020, May 12: Wasabi team pays out a Bitcoin reward for the findings.
• 2020, May 14: Wasabi team starts working on fixing the issue.
• 2020, June 04: Wasabi team finalizes and then plans the deployment of the fix.
• 2020, Aug 05: Wasabi Wallet v1.1.12 is released with the client side fix.
• 2020, Sept 03: Wasabi Wallet v4 hard fork is deployed.

Closing Thoughts

Finally we'd like to thank you Ondřej and we hope your actions set the example for responsible review, notification and resolution of vulnerabilities.

Responsible Disclosure

Dear Adam,

I found a severe security issue in your implementation of the coinjoin
coordinator. An attacker can exploit the vulnerability to perform a
denial-of-service attack such that it's extremely difficult to identify
the attacker.

This paragraph summarizes how blind Schnorr signatures are used in your
implementation. At the beginning of each round a fresh blind Schnorr
signature key pair is generated for every round level. In the input
registration phase a participant of the coinjoin registers unspent
outputs in their possession as inputs to the coinjoin transaction and
one or more blinded addresses as outputs of the coinjoin transaction. In
the connection confirmation phase the coordinator determines how many
levels the participant has funds to participate in, and returns them the
corresponding number of blinded addresses signed with the corresponding
level keys. In the output registration phase the participant (under a
different identity) reveals their (unblinded) outputs with the
(unblinded) signatures that are verified by the coordinator.

A nonce that is used in blind Schnorr signatures is supposed to be
generated freshly for every signature. If a signer generates two
signatures using the same nonce, it's easy to determine their private
key as same as the private part of the nonce.

The problem is that the nonce in your implementation is part of the key
pair. As a consequence the nonce is the same for all outputs registered
on the same level. That means that a participant that registers at least
two outputs on the same level is able to determine the signer's private key.

Suppose h is a blinded message to be signed, d is the coordinator's
private key and r is the private part of the nonce.
The signature of the blinded message is r - d * h modulo the order of
the group that is used (secp256k1 in our case). Suppose an attacker has
signatures s1 and s2 of distinct messages h1 and h2 signed with the same
private key and nonce. Then the following holds:
(s1 - s2) / (h2 - h1) = ((r - d * h1) - (r - d * h2)) / (h2 - h1)
  = d * (h2 - h1) / (h2 - h1) = d
s1 + h1 * d = (r - d * h1) + h1 * d = r

An attacker that knows the signer's private key can generate a valid
signature for every message. Therefore, they are able to register an
output that was never blind signed by the coordinator. What are the
consequences? As long as the implementation of the client is sound, the
attacker can neither steal a decent amount of coins nor deanonymize
anyone. What they can do is prevent the completion of the coinjoin, in
other words denial-of-service attack. I've got the following ideas:
  * The attacker registers (in the output registration phase) both their
real outputs and one or more fake outputs. Consequently, there are one
or more participants that aren't allowed to register their outputs since
the output registration phase ends when there are as many registered
outputs as returned blinded signatures in the connection confirmation
phase. These participants naturally refuse to sign the conjoin
transaction. As a result, their unspent output registered as inputs to
the coinjoin are banned.
  * The attacker registers only one of two of their real outputs. Beside
that, they register one fake output on a higher level. Because they
registered as many outputs as they have been given blinded signatures,
other participants can register their outputs. After that, the
coordinator builds a transaction that can't be valid, since the sum of
all inputs is less than the sum of all outputs. I didn't investigate
what happens next.

What are the possible fixes for this bug?
  * The coordinator on request generates nonce pair, remembers both
private and public part, and returns the public one. A participant that
registers their unspent outputs and blinded addresses uses the nonce to
blind the addresses and sends the nonce in his request. The coordinator
finds the corresponding private nonce, blind signs the addresses, and
forgets the nonce pair, so it's not used repeatedly.
  * Replace Schnorr blind signatures with RSA blind signatures, since
RSA signature doesn't require nonce. I think you used RSA before.
Nevertheless, I don't like this approach because RSA in contrasts with
elliptic-curve cryptography isn't so widespread in the bitcoin community.

I hope you appreciate this report!

Best regards,
Ondřej Vejpustek