OT: TRNG vs PRNG (was Re: [ILUG] serious Debian/Ubuntu security hole found)

[Ivan Griffin]

Actually, a useful discussion on this topic is available at 
http://en.wikipedia.org/wiki/Hardware_random_number_generator



On Fri, 16 May 2008, Ivan Griffin wrote:

>
> This discussion is interesting, but probably going completely off topic. In 
> way of apology for continuing it, I've changed the subject line slightly.
>
>
> However, I think it is worth pointing out that in the semiconductor industry, 
> the state-of-the-art in consumer electronics crypto probably is considered to 
> be the use a "true" RNG (TRNG) constructed from some hardware process (pair 
> of ring oscillators, etc) as an initial seed, feeding into a well 
> characterised encryption engine. There are other aspects, such as ensuring 
> the keys are not visible to software directly, but only to a hardware crypto 
> offload engine.
>
> PRNGs are not considered best practice.  This isn't my personal opinion - it 
> is a viewpoint that is strongly enforced by many of the industry incumbants 
> when licensing, for instance, their DRM specifications. I work for a company 
> that has recently included an analog TRNG macro into our new chip design 
> specifically for this specific purpose.
>
> Quoting John von Neumann, "Anyone who considers arithmetical methods of 
> producing random digits is, of course, in a state of sin."
>
>
> In Applied Cryptography, the crypto bible by Bruce Schneier, the requirements 
> for a RNG are defined as:
> * the output appears to be random (i.e. passes all statistical approximation 
> tests of randomness that can be found, auto-correlation, cross-correlation 
> etc);
> * it must be computational infeasible to predict next random bit;
> * it cannot be reliably reproduced - given same inputs, the generator should 
> generate two complete unrelated and random sequences.
>
> Depending on the use of the RNG, it may satisfy one or more of these 
> requirements.  PRNGs are usually considered only to satisfy Schneier's first 
> requirement, whereas good HW-based TRNGs are considered capable of satisfying 
> all three. Their output does not depend on any previously produced bits, 
> unless the deterministic behaviour of the PRNG.
>
> There are many techniques for TRNGs:
> * electrical noise (e.g. Johnson noise, Shot Noise, Flicker noise - all of 
> which have had their noise distributions characterised.)
> * Quantum properties of Photons (quantum theory predicts the choice of path 
> by a photon is truly random)
> * Radioactivity - unstable isotope decay
>
> As a consequence, I don't think it is fair to state that theoretical 
> mathematical functions which appear pseudo random are better understood than 
> the quantum effects which generate noise.
>
> I also don't think it is correct to say that there are no tests available for 
> randomness. There are many tests that attempt to determine randomness through 
> pattern identification - for example, NIST have their "Statistical Test Suite 
> for Random and Pseudorandom Number Generators for Cryptographic 
> Applications", the Chi-squared test is useful, as is the DIEHARD test suite. 
> Obviously, entrophy estimation is theoretically impossible, but it is 
> possible to get a feeling for random failures in certain limited runs with 
> appropriate assumptions.
>
> One of the properties of a good encryption engine is that small changes in 
> the input are reflected in disproportionate changes in the output - i.e it 
> has good spread across the output space. AES/Rijndael is an example of a good 
> crypto algorithm where a sequentially incrementing counter will generate very 
> good output. Using the TRNG input as an initial seed, coupled with other 
> mechanisms for gathering entropy, into such a crypto block will generate you 
> a pretty unique sequence of keys.
>
> I think this is well summarised in a presentation by Laszlo Hars ("Random 
> Topics" - http://www.hars.us/Papers/RandomTopics-SummerCon.ppt) :
> "Do Random Numbers exist? Mathematically: yes ... but no algorithm generates 
> them ... Physically: maybe"
>
> Best Regards,
> Ivan
>
> On Fri, 16 May 2008, Timothy Murphy wrote:
>
>> On Thursday 15 May 2008 02:40:10 pm paul at clubi.ie wrote:
>> 
>>> If we can't determine randonmess, why should trust the output of a
>>> man-made algorithm that /seems/ random over measurements of physical
>>> processes that we apparently have good reason to believe /are/
>>> random?**
>> 
>> Because we know far more about mathematical functions
>> than we do about the physical processes you are talking about.
>> 
>> Take the time distribution of emissions from radioactive material,
>> which is often taken as a model of a random process.
>> 
>> There are any number of reasons why this might not in fact be random,
>> eg the measuring apparatus might be defective,
>> there may be cosmic ray emissions from a completely different source,
>> the rate of emission may not be independent of the temperature,
>> the direction of the magnetic field may affect the result,
>> etc, etc.
>> 
>> 
>> 
>> -- 
>> Timothy Murphy
>> e-mail: gayleard /at/ eircom.net
>> tel: +353-86-2336090, +353-1-2842366
>> s-mail: School of Mathematics, Trinity College, Dublin 2, Ireland
>> -- 
>> Irish Linux Users' Group mailing list
>> About this list : http://mail.linux.ie/mailman/listinfo/ilug
>> Who we are : http://www.linux.ie/
>> Where we are : http://www.linux.ie/map/
>> 
>> 
> -- 
> Irish Linux Users' Group mailing list
> About this list : http://mail.linux.ie/mailman/listinfo/ilug
> Who we are : http://www.linux.ie/
> Where we are : http://www.linux.ie/map/
>
>