Backdoors in Pseudorandom Number Generators : Possibility and Impossibility Results. / Degabriele, Jean; Paterson, Kenneth; Schuldt, Jacob; Woodage, Joanne.

Advances in Cryptology – CRYPTO 2016: 36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I. ed. / Matthew Robshaw; Jonathan Katz. Vol. 9814 Springer Berlin / Heidelberg, 2016. p. 403-432 (Lecture Notes in Computer Science ; Vol. 9814).

Research output: Chapter in Book/Report/Conference proceedingChapter

E-pub ahead of print

Documents

Links

Abstract

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 BPRGs 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 BPRGs 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 PRNGs 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 PRNGs 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.
Original languageEnglish
Title of host publicationAdvances in Cryptology – CRYPTO 2016
Subtitle of host publication36th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 14-18, 2016, Proceedings, Part I
EditorsMatthew Robshaw, Jonathan Katz
PublisherSpringer Berlin / Heidelberg
Pages403-432
Number of pages30
Volume9814
ISBN (Electronic)978-3-662-53018-4
ISBN (Print)978-3-662-53017-7
DOIs
Publication statusE-pub ahead of print - 21 Jul 2016

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume9814
This open access research output is licenced under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.

ID: 26604789