Paper 2023/440

On the Possibility of a Backdoor in the Micali-Schnorr Generator

Hannah Davis, University of California, San Diego
Matthew Green, Johns Hopkins University
Nadia Heninger, University of California, San Diego
Keegan Ryan, University of California, San Diego
Adam Suhl, University of California, San Diego
Abstract

In this paper, we study both the implications and potential impact of backdoored parameters for two RSA-based pseudorandom number generators: the ISO-standardized Micali-Schnorr generator and a closely related design, the RSA PRG. We observe, contrary to common understanding, that the security of the Micali-Schnorr PRG is not tightly bound to the difficulty of inverting RSA. We show that the Micali-Schnorr construction remains secure even if one replaces RSA with a publicly evaluatable PRG, or a function modeled as an efficiently invertible random permutation. This implies that any cryptographic backdoor must somehow exploit the algebraic structure of RSA, rather than an attacker's ability to invert RSA or the presence of secret keys. We exhibit two such backdoors in related constructions: a family of exploitable parameters for the RSA PRG, and a second vulnerable construction for a finite-field variant of Micali-Schnorr. We also observe that the parameters allowed by the ISO standard are incompletely specified, and allow insecure choices of exponent. Several of our backdoor constructions make use of lattice techniques, in particular multivariate versions of Coppersmith's method for finding small solutions to polynomials modulo integers.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
Preprint.
Keywords
Micali-SchnorrstandardsCoppersmith's method
Contact author(s)
hdavis @ ucsd edu
mgreen @ cs jhu edu
nadiah @ cs ucsd edu
kryan @ ucsd edu
asuhl @ ucsd edu
History
2023-03-27: approved
2023-03-26: received
See all versions
Short URL
https://ia.cr/2023/440
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/440,
      author = {Hannah Davis and Matthew Green and Nadia Heninger and Keegan Ryan and Adam Suhl},
      title = {On the Possibility of a Backdoor in the Micali-Schnorr Generator},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/440},
      year = {2023},
      url = {https://eprint.iacr.org/2023/440}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.