Paper 2016/306

A Formal Treatment of Backdoored Pseudorandom Generators

Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, and Thomas Ristenpart

Abstract

We provide a formal treatment of backdoored pseudorandom generators (PRGs). Here a saboteur chooses a PRG instance for which she knows a trapdoor that allows prediction of future (and possibly past) generator outputs. This topic was formally studied by Vazirani and Vazirani, but only in a limited form and not in the context of subverting cryptographic protocols. The latter has become increasingly important due to revelations about NIST's backdoored Dual EC PRG and new results about its practical exploitability using a trapdoor. We show that backdoored PRGs are equivalent to public-key encryption schemes with pseudorandom ciphertexts. We use this equivalence to build backdoored PRGs that avoid a well known drawback of the Dual EC PRG, namely biases in outputs that an attacker can exploit without the trapdoor. Our results also yield a number of new constructions and an explanatory framework for why there are no reported observations in the wild of backdoored PRGs using only symmetric primitives. We also investigate folklore suggestions for countermeasures to backdoored PRGs, which we call {\em immunizers}. We show that simply hashing PRG outputs is not an effective immunizer against an attacker that knows the hash function in use. Salting the hash, however, does yield a secure immunizer, a fact we prove using a surprisingly subtle proof in the random oracle model. We also give a proof in the standard model under the assumption that the hash function is a universal computational extractor (a recent notion introduced by Bellare, Tung, and Keelveedhi).

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published by the IACR in EUROCRYPT 2015
DOI
10.1007/978-3-662-46800-5_5
Keywords
pseudorandomnesssubversionpseudorandom generatorpublic-key encryption
Contact author(s)
chaya ganesh @ gmail com
History
2016-03-18: received
Short URL
https://ia.cr/2016/306
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/306,
      author = {Yevgeniy Dodis and Chaya Ganesh and Alexander Golovnev and Ari Juels and Thomas Ristenpart},
      title = {A Formal Treatment of Backdoored Pseudorandom Generators},
      howpublished = {Cryptology ePrint Archive, Paper 2016/306},
      year = {2016},
      doi = {10.1007/978-3-662-46800-5_5},
      note = {\url{https://eprint.iacr.org/2016/306}},
      url = {https://eprint.iacr.org/2016/306}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.