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

Hannah Davis; Matthew Green; Nadia Heninger; Keegan Ryan; Adam Suhl

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-Schnorr standards Coppersmith'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: 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},
      note = {\url{https://eprint.iacr.org/2023/440}},
      url = {https://eprint.iacr.org/2023/440}
}