IACR News item: 18 March 2016
Yevgeniy Dodis, Chaya Ganesh, Alexander Golovnev, Ari Juels, Thomas Ristenpart
ePrint Report
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).
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).
Additional news items may be found on the IACR news page.