M&M'S: Mix and Match Attacks on Schnorr-Type Blind Signatures with Repetition

Blind signatures allow the issuing of signatures on messages chosen by the user so that they ensure $\mathit{blindness}$ of the message against the signer. Moreover, a malicious user cannot output $\ell+1$ signatures while only finishing $\ell$ signing sessions. This notion, called $\mathit{one}$-$\mathit{more}$ unforgeability, comes in two flavors supporting either $\mathit{sequential}$ or $\mathit{concurrent}$ sessions.

In this paper, we investigate the security of a class of blind signatures constructed from Sigma-protocols with small challenge space $\mathcal{C}_{\Sigma}$ (i.e., polynomial in the security parameter), using $k$ repetitions of the protocol to decrease the chances of a cheating prover. This class of schemes includes, among others, the Schnorr blind signature scheme with bit challenges and the recently proposed isogeny-based scheme CSI-Otter (Crypto'23), as well as potential blind signatures designed from assumptions with the well-known Sigma-protocol for the graph-isomorphism problem (e.g., Lattice Isomorphism Problem).

For this class of blind signatures, we show a $\mathit{polynomial}$-$\mathit{time}$ attack that breaks one-more unforgeability for any $\ell \geq k$ concurrent sessions in time $O(k \cdot |\mathcal{C}_{\Sigma}|)$. Contrary to the ROS attack, ours is generic and does not require any particular algebraic structure. We also propose a computational trade-off, where, for any $t \leq k$, our attack works for $\ell = \frac{k}{t}$ in time $O(\frac{k}{t} \cdot |\mathcal{C}_{\Sigma}|^t)$.

The consequences of our attack are as follows. Schemes in the investigated class of blind signatures should not be used concurrently without applying specific transformations to boost the security to support more signing sessions. Moreover, for the parameters proposed for CSI-Otter ($k=128$ and $|\mathcal{C}_{\Sigma}|=2$), the scheme becomes forgeable after 128 concurrent signing sessions for the basic attack and with only eight sessions in our optimized attack. We also show that for those parameters, it is even possible to compute two signatures in around 10 minutes with just one signing session using the computation power of the Bitcoin network. Thus, we show that, for sequential security, the parameter $k$ must be at least doubled in the security parameter for any of the investigated schemes.