Whenever you read a (good) cryptography book they discuss the difficulty in generating truly random numbers. The standard “random” numbers thay you get from things like the C rand() function is actually a psudo-random number — it is deterministically generated by applying a function (often a hash) to an input seed. The seed usually generated from some external source, such as the interval between packets arriving on the Ethernet interface, keyboard timing, etc. The better pusudo-random number generators (PNRG) continue to feed external entropy data into the system to try and increase the randomness of the data.
While it may be hard to do, lots of cryptography requires very good (unpredicatable) random data — as a recent example, take the recent CVE-2008-0166 vulnerability. The short version (longer, better written version here) is that valgrind (a debugging tool that, amongst other thing, checks to make sure that you are not reading garbage from uninitialized memory) was complaining that OpenSSL was reading some uninitialzed memeory and using that data. Someone got annoyed with the warning and without completly undertanding the function that was doing this, simply commented it out (actually, he did try and figure out the reason, checked with the OpenSSL list, etc), and so stopped valgrind complaining. Unfortunatly, the uninitialized data that valgrind was complaining about was used as entropy to the PRNG function and so the amount of entropy was decreased (and you thought it took work to decrease entropy!). The proctial upshot of this is that the PRNG was no longer as random and SSH keys generated form this ended up being predictable — there were only 32,768 different keys that would be generated. Thils means that you could simply generate all of the possible keys and try them sequentially until the system let you in — and hilarity ensued. The importance of true randomness (and the difficulty in generating it) for various applications even lead the Rand Corporation to publish a book full of randomness — for only USD $90 you too can purchase “A Million Random Digits with 100,000 Normal Deviates“
In order to make the output of your PRNG as random as possible, you should pour more entropy into the pool — there are various hardware devices for doing this, such as thermal noise, avalanche (or Zener breakdown) noise from a diode, shot noise, etc.
Intel used to make a motherboard chipset (i810) that included a good hardware number generator, but unfortunately have taken this out of newer chipsets. There have been some cute random number generation systems, such as SGI’s lavarnd, which basically involved pointing a webcam at a lava lamp. A similar project (that stole the name) is LavaRnd which uses the chaotic noise from a CCD in darkness, but the ultimate source (and the one that all of hte textbooks use) is radioactive decay.
While all of the textbooks mention radioactive half-live as a great source of entropy, you don’t often see this implemented — so, this seemed like a fun project to do.
The basic plan is to take an old Geiger counter and point it at a source of radiation — like the small Americium 241 pellet in an ionising smoke detector. I will then take the (audio) output of the Geiger counter and feed it to an interface that will connect to the serial port on a PC and watch the interval between “clicks”. If the most recent interval is greater than the previous interval I’ll count that as a 1, if less I will count it as a 0, and if equal, I’ll just drop the current interval.
I have some Gieger counters that were originally designed for civil defence (back during the heady days when Russian nuclear attack was imminent) and just need to design an RS-232 interface. I m currently planning on using an OpAmp as a high impedance amplifier and driving an opto-isolator that will be connected to the CTS pin.
Oh! No page on PRNGs would be complete without mentioning the Blum Blum Shub PRNG — I don’t have anything useful so say about it, but, with a name like that, how could I NOT mention it?! In fact, I am going to try squirrel away a reference to it on every page from now on…
. The following weekend I traveled to Stockholm for IETF75 which gave me a few uninterrupted hours on the plane to read through the General material as well. I got back to VA late on Saturday and went to the West Friendship, MD hamfest on Sunday morning. I wasn’t expecting there to be quite so many people taking the exam so I didn’t arrive as early as I should have. I took the General Exam and waited for what felt like hours while to was graded. I passed that and thanks to some quick grading by the Laurel VEC team I managed to take and pass the Extra class exam in the last 15 minutes before they closed.
