University of Birmingham > Talks@bham > Computer Security Seminars > Backdoors in Pseudorandom Number Generators: Possibility and Impossibility Results

Backdoors in Pseudorandom Number Generators: Possibility and Impossibility Results

Add to your list(s) Download to your calendar using vCal

If you have a question about this talk, please contact Andreea Radu.

Inspired by the Dual EC DBRG incident, Dodis et al. (Eurocrypt 2015) initiated the formal study of backdoored PRGs, showing that backdoored PRGs are equivalent to public key encryption schemes, giving constructions for backdoored PRGs (BPRGs), and showing how BPR Gs can be ``immunised’’ by careful post-processing of their outputs. In this paper, we continue the foundational line of work initiated by Dodis et al., providing both positive and negative results.

We first revisit the backdoored PRG setting of Dodis et al., showing that PRGs can be more strongly backdoored than was previously envisaged. Specifically, we give efficient constructions of BPR Gs for which, given a single generator output, Big Brother can recover the initial state and, therefore, all outputs of the BPRG . Moreover, our constructions are forward-secure in the traditional sense for a PRG , resolving an open question of Dodis et al. in the negative.

We then turn to the question of the effectiveness of backdoors in robust PRN Gs with input (c.f. Dodis et al., ACM -CCS 2013): generators in which the state can be regularly refreshed using an entropy source, and in which, provided sufficient entropy has been made available since the last refresh, the outputs will appear pseudorandom. The presence of a refresh procedure might suggest that Big Brother could be defeated, since he would not be able to predict the values of the PRNG state backwards or forwards through the high-entropy refreshes. Unfortunately, we show that this intuition is not correct: we are also able to construct robust PRN Gs with input that are backdoored in a backwards sense. Namely, given a single output, Big Brother is able to rewind through a number of refresh operations to earlier ``phases’’, and recover all the generator’s outputs in those earlier phases.

Finally, and ending on a positive note, we give an impossibility result: we provide a bound on the number of previous phases that Big Brother can compromise as a function of the state-size of the generator: smaller states provide more limited backdooring opportunities for Big Brother.

This talk is part of the Computer Security Seminars series.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.


Talks@bham, University of Birmingham. Contact Us | Help and Documentation | Privacy and Publicity.
talks@bham is based on from the University of Cambridge.