Further Attacks on the Micali-Schnorr Pseudorandom Generator

The Micali-Schnorr pseudorandom generator has been in use since its inception in 1990. However, serious concerns about the possibility of a backdoor have been raised since its security is not tightly coupled to the RSA problem. The main contributions include: extending the state of the art in small state attacks by uncovering a new range of vulnerable parameter choices, with accompanying implementation that proves practical and theoretical viability of the extended attack; existence of vulnerable exponents, with an algorithm to generate such exponents for any moduli; development of a framework to using only an exponent's public moduli to detect backdoors and malicious constructions. The main implications of our findings are practical attacks towards non-standard implementations and progress towards a full break; we thus need to be vigilant around niche and inadvertent usage of such a generator.