Re: new /dev/random

From: Thomas Pornin (pornin_at_nerim.net)
Date: 10/06/04 

Date: Wed, 6 Oct 2004 16:00:02 +0000 (UTC)

According to Guy Macon <http://www.guymacon.com>:
> Is this "undistinguishable" an absolute, or do they really mean
> "very difficult (but possible with infinite resources) to distinguish?"

"Undistinguishable" means "impossible to distinguish". Under which
conditions is specified by appropriate qualifiers. Here, the qualifier
is "computationaly", which means that we speak about the impossibility
for an attacker with tremendous but nonetheless imaginable computing
power, under current or near-future (aka "foreseeable") technology.

For instance, the current record in cipher-breaking by exhaustive search
(i.e., trying all possible keys until one matches) is for a 64-bit key
(for the RC5 block cipher). It took tens of thousands of cooperating
computers (running the program as an "idle" task) during four years. It
is often argued that the current absolute limit for a very motivated big
country government is about 80 bits (for, say, one break each year). My
own estimate is that if all mankind worked primarily towards breaking
a key, something like 100 bits (at most) could be achieved. Breaking a
128-bit key is still about 260000 times more difficult, hence this is
computationaly unbreakable for the time being.

For a proper PRNG, with the assumption that the algorithms are robust,
the most efficient attack is an exhaustive search on either the seed
or the output, whichever is shortest entropy-wise. "Entropy" is a term
improperly borrowed from thermodynamics; in cryptography, it is a log2
measure of the average number of trials an exhaustive search would have
to perform to find the designated data. For instance, a bunch of bytes
is said to contain 40 bits of entropy if I could, given a reliable test
function, find the bytes by calling the test function 2^39 times (on the
average).

If I want to attack a stream of 56 bits produced by a PRNG with a seed
of entropy 128 bits, my best bet is to try the exhaustive search on the
56 bits of output. However, if the PRNG had produced 300 bits, the most
efficient attack would be to try the exhaustive search on the seed.
Hence my statement "shortest entropy-wise".

PRNG resistance to attacks relies on two classes of assumptions, some
on the evolution of computer science (the robustness of the algorithms
used), and some on the evolution of physics (technological improvements
of computers in the foreseeable future).

In a "true RNG", random data is extracted from some measurement of a
physical phenomenon which is believed to be at least partially random.
The randomness of such data, in terms of entropy, is then estimated,
relatively to our current knowledge of how much random the physical
phenomenon is. Then the data is processed through some algorithm which
converts it into some "random bits", but no more bits than the estimated
entropy.

RNG resistance therefore relies on the same two classes of assumptions
than the PRNG: evolution of computer science (the robustness of the
data processing algorithm used) and evolution of physics (how much new
scientific result will make events previously considered as random
predictible to some extent).

The assumptions on computer science made by the RNG are a bit weaker
than those made by the PRNG, mainly because since the RNG is slower
than the PRNG, a much more "heavy" function can be used; also, the RNG
requires only good statistical properties whereas the PRNG needs more
advanced resistance statements.

On the other hand, assumptions made by the RNG on physics are stronger
because, for a given length of random bits requested, the RNG will have
to gather much more entropy than the PRNG (the PRNG needs only, say,
256 entropy bits for its initial seed, whereas the RNG will need at
least 16000 entropy bits if 16000 random bits are required); thus, the
RNG is likely to have to use sources whose randomness is a bit dubious
at best. In short, the PRNG can be more picky and conservative in its
entropy estimates for its initial seed. Moreover, the PRNG works only
on technological improvement, which is mostly industrial and can be
quantified and foreseen to some extent, whereas the RNG assumes things
on hardcore scientific results (or lack thereof), which is in essence
much more uncertain.

In brief, a strength comparison between a PRNG and a "true" RNG is
mostly an assertion about how much smarter are the computer scientists
compared to the physicists. There is no absolute answer here.

The important point is that most of the above is of no practical
relevance. Most usages of randomness are ultimately limited to
computational resistance. For instance, RSA key generation leads only
to a public and private key pair, where the public key can be attacked
with an infinite amount of computing power. A PRNG is quite sufficient
provided that the "cost" of attacking the public key is lower than
the "cost" of attacking the PRNG itself. The same holds for symmetric
session key generation, such as what is used for SSL or SSH. "OTP" is
one of the very few algorithms which may claim some theoretically better
security if a "true" RNG is used, and that only if there is no available
test function on the protected data (if a file is encrypted with an OTP
but a hash of the file is available somewhere, the attacker can attack
the file itself instead of the pad, and thus work on the file entropy
rather than the pad entropy).

Most people, including many programmers involved in the development
of cryptography-related products, do not think along these lines.
They rather formulate thoughts such as "hey, 'random' must be better
than 'urandom', because the man page says so" or even "I want random,
so I use '/dev/random'; now I want to output a nifty sound, where
is '/dev/sound' ?". So much for user freedom and the so-called Unix
"philosophy".

        --Thomas Pornin

Relevant Pages

  • Re: new /dev/random
    ... etc to provide the true random information for the RNG. ... >>into a PRNG for reasons he has failed to convince anyone but himself of. ... with input from "entropy sources" as it goes, ... In the current /dev/random implementation there is an entropy estimator ...
    (sci.crypt)
  • Re: new /dev/random
    ... > is said to contain 40 bits of entropy if I could, ... > efficient attack would be to try the exhaustive search on the seed. ... > than the PRNG: evolution of computer science (the robustness of the ... > because, for a given length of random bits requested, the RNG will have ...
    (sci.crypt)
  • Re: new /dev/random
    ... because the code will insist on grabbing physical entropy at each run. ... SSL needs only a good PRNG, a true RNG is pure overkill. ... -- upon shutdown, 4 KBytes of random data are produced, stored on the ...
    (sci.crypt)
  • Re: Fortuna
    ... > dreaded state-extension attack. ... seed file before boot but can't install any trojans. ... But still, all else being equal, an RNG resistant to a state extension ... What Fortuna tries to do is sidestep the hard problem of entropy ...
    (Linux-Kernel)
  • Re: new /dev/random
    ... ]> PRNG and an RNG and what the definition of infeasible was. ... ] You are talking to cryptographers. ... true RNG while /dev/urandom is supposed to be a PRNG seeded by a limited ...
    (sci.crypt)