Paper 2023/1588
M&M'S: Mix and Match Attacks on Schnorrtype Blind Signatures with Repetition
Abstract
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 Sigmaprotocols 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 isogenybased scheme CSIOtter (Crypto'23), as well as potential blind signatures designed from assumptions with the wellknown Sigmaprotocol for the graphisomorphism problem (e.g., Lattice Isomorphism Problem). For this class of blind signatures, we show a $\mathit{polynomial}$$\mathit{time}$ attack that breaks onemore 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 tradeoff, 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 CSIOtter ($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.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Keywords
 Blind SignaturesSigma ProtocolsGroup ActionsCryptanalysis
 Contact author(s)

khue do @ cispa de
hanzlik @ cispa de
eugenio paracucchi @ cispa de  History
 20231013: revised
 20231013: received
 See all versions
 Short URL
 https://ia.cr/2023/1588
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/1588, author = {Khue Do and Lucjan Hanzlik and Eugenio Paracucchi}, title = {M&M'S: Mix and Match Attacks on Schnorrtype Blind Signatures with Repetition}, howpublished = {Cryptology ePrint Archive, Paper 2023/1588}, year = {2023}, note = {\url{https://eprint.iacr.org/2023/1588}}, url = {https://eprint.iacr.org/2023/1588} }