Welcome to the resource topic for 2023/1588
Title:
M&M’S: Mix and Match Attacks on Schnorr-type Blind Signatures with Repetition
Authors: Khue Do, Lucjan Hanzlik, Eugenio Paracucchi
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 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.
ePrint: https://eprint.iacr.org/2023/1588
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .