Tuesday, October 31, 2006


True Random Number Generators are hard and almost impossible to create. Most computer programs use pseudo-Random Number Generators (PRNG) which are, in fact, not random at all. They simply use a mathematical function (most commonly LCG) with a seed based on the system's clock.
For security applications, these simple PRNGs are bad bad bad - they create a giant hole in the security mechanism through which hackers can fairly easily penetrate. So entropy-based RNGs are usually used for cryptographic purposes (for example Window's CryptGenRandom). These RNGs try to collect randomness (actually it's entropy) from as many resources as possible: keyboard events, mouse events, hard-disk events, network events, etc.
Linux also has such an entropy-based RNG, but it has been shown to be weak in some circumstances.
To my knowledge, Windows' counterpart (CryptGenRandom) hasn't yet experienced such a faith...
BTW - an important problem with the cryptographically strong RNGs on a computer is that sometimes they must wait for enough entropy to occur before being able to returning a new random number, causing the application to stall (and making it difficult to generate a large amount of random numbers at short intervals).
Would it be possible to have a really random RNG?
Well, there are various physical phenomena (such as some nuclear processes) that could be used, but it's complicated to incorporate this into every PC :-)
An idea came to my mind - Imagine we had a web service, generating simple random numbers, based on previous calls to the service (and maybe a few other entropy sources). Then each user would get a random number that is influenced by some other user, completely unknown to her. The main idea behind this is that the randomness is aquired from the various independent requests, making it essentially random.
A simulation of such a generator could be easily created by using Blogspot's "Next Blog" link, where you are randomly forwarded to another blog. Take the link you got (or some information inside the blog), hash it somehow (MD5 hasn't been broken yet), and what you get is really random (I checked - a blog doesn't refer twice to the same blog).
This is all very fuzzy, and I'm sure it's flawed in many ways. Yet I think that the principle could be interesting - using user navigation information to provide an RNG service over the web.
And what about performance - having to execute a web request to get one random number isn't very nice!? Well, I didn't say it's perfect, did I? Yet it may (maybe) be extended to return pools of random numbers, thus requiring much less web calls. Also, if you're already running a web site, you may be able to use your own users' information to generate a local RNG only for yourself.

OK, enough babling, ciao!

No comments: