Walletwasabi: Modular arithmetic in the blind Schnorr signatures

[onvej-sl]

I found a minor vulnerability in the implementation of the blind Schnorr signatures. Someone (for example the coinjoin coordinator) who is presented multiple blind digests and the corresponding unblinded signatures can exploit the vulnerability to find a little connection between the blind digests and the signatures.

Given signer's public key, public nonce and message digest, the blinded digest is computed as follows:

  v = random_scalar()
  w = random_scalar()
  blinded_public_nonce = public_nonce + v * curve.generator + w * signer_public_key
  digest_bytes = sha256(message_digest || blinded_public_nonce.x_coordinate)
  digest = bytes_to_scalar(digest_bytes)
  blinded_digest = digest + (-w)

Both digest and -w on the last line are scalars, that means they are elements of the finite field of the size equal to the order of the secp256k1 curve. All computations in such the field are performed modulo the curve order. Which applies also to the addition on the last line.

In the code, new v and w are generated if the addition on the last line overflows (the curve order).

Let's investigate the consequences. Since blinded_digest is the ordinary sum of two non-negative integers digest and -w, it holds that blinded_digest >= digest. So if someone is given a digest and a blinded digest and the digest is less than the blinded digest, it's clear that these two digests are not connected.

What is the probability that a digest of a message is less than a blinded digest of another message? Let D_1 and D_2 be two independent random variables uniformly distributed on the interval [0, 1). This is a simplification, since in fact digests are uniformly distributed over integers in the interval [0, curve.order). Let B_1 be a random variable uniformly distributed on the interval [D_1, 1). The question is what is the probability of B_1 being less than D_2.

The probability density function of the variable D_1 is

f_D(d) = I([0, 1), d)

where I([a, b), x) is the indicator function of the interval [a, b), meaning I is one for x in the interval [a, b) and zero elsewhere. The joint probability density function of the variables D_1 and B_1 is

f_DB(d, b) = I([0, 1), d) * 1 / (1 - d) * I([d, 1), b)

The marginal probability density function of B_1 is

f_B(b) = integrate(f_DB(d,b), (d, -infinity, infinity)) = integrate(I([0, 1), d) * 1 / (1 - d) * I([d, 1), b), (d, -infinity, infinity)) = integrate(1 / (1 - d), (d, 0, min(b, 1))) = -ln(1 - b) * I([0, 1), b)

For more detailed explanation see for example this or this. Since D_1 and D_2 are independent, B_1 and D_2 are independent too. The probability that B_1 < D_2 is

integrate(f_B(b) * f_D(d), ((b, d) | b < d) = integrate(I([0, 1), d) * (-ln(1 - b)) * I([0, 1), b), ((b, d) | b < d)) = integrate(I([0, 1), b) * integrate(I([0, 1), d) * (-ln(1 - b)), (d, -infinity, b)), (b, -infinity, infinity)) = integrate(-(1 - b) * ln(1 - b), (b, 0, 1)) = 1/4

That means a blinded digest of a message is less than digest of another message with the probability of 1/4. A malicious coordinator that tries to find a coinjoin input that corresponds to a coinjoin output can exclude on average one quarter of inputs, these inputs certainly doesn't correspond to the output.

The fix of this issue is very easy: The condition overflow != 0 must be removed from this line.

[lontivero]

Thank you very much for the detailed report. I will be back we my feedback asap.

[lontivero]

Confirmed and fixed.

[molnard]

@onvej-sl This was again a really in-depth catch! Thank you!