Eurocrypt 2015: Backdoored PRNGs

Since truly random bits are often hard to come by, many cryptographic protocols use a small amount of true randomness to seed a pseudorandom number generator (PRNG) whose outputs ought to be indistinguishable from truly random strings. If one can predict the future outputs of such generators then one can often subvert the larger protocol built on top. So security of PRNGs is crucial in the design of secure protocols.

The trouble is, it may be that a PRNG that appears secure to a typical user actually contains a backdoor rendering it totally insecure; some information may exist, unknown to most users, the knowledge of which enables one to recover the internal state of the PRNG and hence predict its future (or maybe past) outputs. This is a highly topical subject given the recent accusations that the NSA purposely introduced a backdoor in the NIST Dual EC PRNG: it is claimed that the NSA knew some underlying information about the parameters suggested by NIST that is infeasible for ordinary users to determine, and armed with this knowledge, one can use a single output of the PRNG to predict all future outputs. In particular, it would be possible to decrypt TLS sessions using this trapdoor information.

This morning Chaya Ganesh presented a formal model for backdoored PRNGs, in joint work with Yevgeniy Dodis, Alexander Golovnev, Ari Juels, and Thomas Ristenpart. They say that in a backdoored PRNG, the parameter generation algorithm outputs a set of public parameters called the public key and a trapdoor called the secret key. The generation algorithm takes a public key and the current state of the generator and outputs some bits that should be indistinguishable from random to any party with just the public key. A party with the secret key can easily distinguish PRNG outputs from random strings and possibly predict future outputs.

The authors prove that a backdoored PRNG whose outputs are indistinguishable from random without the secret key is equivalent to a public key encryption scheme whose ciphertexts are indistinguishable from random. They also consider possible countermeasures against backdoors, called immunisations, and give a negative result in the so-called public immuniser security model where the immunisation function is decided upon before the PRNG is designed: they show that a saboteur can always design a PRNG that will bypass the immuniser, no matter what it is. On the other hand, in the semi-private immuniser model, where the immuniser's randomness is known to the party using the backdoor but unknown to the PRNG designer, the authors give a positive result. They use the immuniser's randomness as a salt to a hash function and prove that the outputs of this scheme are indistinguishable from random bits, even for an attacker in position of the trapdoor secret key and the salt from the immuniser.

This was an interesting talk, combining elegant formalism with a hugely important and topical issue in security. The full paper is online here.