CryptoDB
On the possibility of a backdoor in the Micali-Schnorr generator
| Authors: | |
|---|---|
| Download: | |
| Presentation: | Slides |
| Abstract: | Dual EC DRBG is widely believed to have been backdoored by the U.S. National Security Agency. But there was another number theoretic PRG proposed alongside Dual EC that has seen surprisingly little attention: the Micali-Schnorr generator, standardized as MS DRBG, which is based on the hardness of RSA. It appears in early drafts of the ANSI X9.82 standard (but was eventually removed in favor of Dual EC) and the final version of ISO 18031 (alongside Dual EC). The MS DRBG standard follows a pattern eerily reminiscent of Dual EC: it incorporates a series of recommended public parameters that are intended to be used in production as the RSA modulus N. Given the known vulnerabilities in Dual EC and the identical provenance, it is reasonable to ask whether MS DRBG is vulnerable to an analogous attack: Does knowledge of the factors of (or malicious construction of) the recommended moduli imply a practical attack on the MS DRBG generator? Surprisingly, this question is not easy to answer. The security proofs of course do not go through if the factors are known, but all obvious attack strategies fail. In this talk, we give historical background on MS DRBG and describe progress toward finding the backdoor (or proving it doesn't exist). We show that any backdoor must somehow exploit the algebraic structure of RSA, rather than just the attacker's ability to invert the RSA operation. We exhibit two such backdoors in related constructions. Ultimately we were unsuccessful in fully finding a plausible backdoor in MS DRBG (or proving one doesn't exist), but we hope this talk will bring more attention to this interesting open problem with potential real-world impact. |
| Video: | https://youtu.be/608NQdTn39Q?t=2629 |
BibTeX
@misc{rwc-2023-35453,
title={On the possibility of a backdoor in the Micali-Schnorr generator},
note={Video at \url{https://youtu.be/608NQdTn39Q?t=2629}},
howpublished={Talk given at RWC 2023},
author={Hannah Davis and Matthew Green and Nadia Heninger and Keegan Ryan and Adam Suhl},
year=2023
}