Re: new /dev/random

From: Jean-Luc Cooke (jlcooke_at_engsoc.org)
Date: 10/06/04 

Date: 6 Oct 2004 16:46:18 GMT

I suggest people read this post by Thomas. It is very insighful and I
hope clears things up for many people. Well done.

JLC

Thomas Pornin <pornin@nerim.net> wrote:
> 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
    ... For a proper PRNG, with the assumption that the algorithms are robust, ... is said to contain 40 bits of entropy if I could, ... If I want to attack a stream of 56 bits produced by a PRNG with a seed ... RNG resistance therefore relies on the same two classes of assumptions ...
    (sci.crypt)
  • 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
    ... 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: /dev/random on Linux
    ... things that cryptographers look for when attacking a cipher. ... of the form, "assume that the attack gains access to the pool, but has ... add_timer_randomnessfrom the extract entropy code. ... The only reason why the generic attack ...
    (Linux-Kernel)