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

Zusammenfassung

Blind signatures allow the issuing of signatures on messages chosen by the user so that they ensure blindness of the message against the signer. Moreover, a malicious user cannot output `+1 signatures while only finishing ` signing sessions. This notion, called one-more unforgeability, comes in two flavors supporting either sequential or concurrent sessions. In this paper, we investigate the security of a class of blind signatures constructed from Sigma-protocols with small challenge space CΣ (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 polynomial-time attack that breaks one-more unforgeability for any ` ≥ k concurrent sessions in time O(k · |CΣ|). 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 ≤ k, our attack works for ` = k t in time O( k t · |CΣ| 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 |CΣ| = 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.