On the (In)Security of RSA Signatures
Aris Tentes, NYU
Bellare and Rogaway [ACM CCS ’93] introduced the famous random oracle model as a “paradigm for designing efficient protocols”. This paradigm has led to several highly efficient and widely used in practice constructions, such as the RSA Full Domain Hash signature scheme (RSA-FDH). Unfortunately, little is known about the security of the resulting schemes in the standard model, when the random oracle is replaced by a concrete function. In particular, it is unknown whether we can reduce their (standard model) security to any “natural” assumption.
Prior work has shown several “uninstantiability” results for various abstractions of RSA-based schemes, where the RSA function was replaced by a random permutation. These abstractions, however, do not allow either the reduction or the hash function instantiation to use any algebraic properties of RSA function, such as the multiplicative group structure of Zn*.
In this work we develop new techniques which rule out such algebraic instantiations, focusing specifically on the case of RSA-FDH. We show that it is impossible to reduce the security of RSA-FDH to any natural assumption, provided that the construction and the reduction
treat the multiplicative RSA group Zn* in in a black-box way. To the best of our knowledge, this restriction is satisfied by all positive results for RSA-based signatures, including standard model constructions of Gennaro et al. [EUROCRYPT ’99], Cramer and Shoup [ACM TISS ’00] and Hohenberger and Waters [CRYPTO ’09].
As our main technical (and conceptual) contribution, we show how to adapt the powerful “short description” paradigm of Gennaro and Trevisan [FOCS ’00] to the “generic group” setting. This paradigm is typically used to rule out one-way permutations based reductions, showing that their security proofs would
imply a (provably impossible) way to “compress” a random permutation. In our setting, the reduction has access to a random group G isomorphic to Zn* , and can use the algebraic properties of G. Still, we show that such a reduction must “know” the factorization of n (and, hence, does not “benefit” from the signature forger), since otherwise it can be used to “compress” our group G. We demonstrate the optimality of our negative result, at least in some sense, by showing that the RSA-FDH signatures can be proven secure in the standard model, under the standard RSA assumption, provided the number of signing queries is a-priori bounded.
Joint work with Yevgeniy Dodis and Iftach Haitner.