An architecture for robust pseudo-random generation
and applications to /dev/random
Boaz Barak and Shai Halevi
Abstract
We present a formal model and a simple architecture for
robust pseudorandom generation that ensures resilience in the face of an
observer with partial knowledge (or even partial control) of the
generator's entropy source. Our model and architecture ensure the
following properties:
- Resilience. The generator's output looks random to an
observer with no knowledges of the internal state. This holds even if
that observer has complete control over data that is used to refresh
the internal state.
- Forward security. Past output of the generator looks random
to an observer with no knowledges of the past internal state, even if it
was later able to learn the internal state.
- Backward security/Break-in recovery. Future output of the
generator looks random, even to an observer with knowledge of the current
state, provided that the generator is refreshed with data of sufficient
entropy.
%
Architectures such as above were suggested before. This work differs
from previous attempts in that we present a formal model for robust
pseudo-random generation, and provide a formal proof within this model
for the security of our architecture. To our knowledge, this is the
first attempt at a rigorous model for this problem.
Our formal modeling advocates the separation of the entropy
extraction phase from the output generation phase. We argue
that the former is information-theoretic in nature, and should
therefore rely on combinatorial and statistical tools and not on
cryptography. On the other hand, we show that the latter phase can
be implemented using any standard (non-robust) cryptographic PRG
(which is turn can theoretically be built from any one-way function).
We also discuss the applicability of our architecture as a replacement
for the current implementation of /dev/(u)random in Linux, and
also examine using it as an architecture for pseudorandom generation on
smartcards.
Versions
|