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/>>
Maintained by the ILUG website team. The aim of Linux.ie is to
support and help commercial and private users of Linux in Ireland. You can
display ILUG news in your own webpages, read backend
information to find out how. Networking services kindly provided by HEAnet, server kindly donated by
Dell. Linux is a trademark of Linus Torvalds,
used with permission. No penguins were harmed in the production or maintenance
of this highly praised website. Looking for the
Indian Linux Users' Group? Try here. If you've read all this and aren't a lawyer: you should be!
