Linux & Open-Source Training Linux Laptops news&links company Info

Randomness shouldn't be left to chance - Howto

© John Gilbert

Good crypto depends on good entropy, and bad crypto can kill you!

Linux 2.6.x and Hardware Random Number Generators : A mini-howto to get hw_random working (with supported hardware)By John Gilbert

Part 0. Introduction to chaos, or why is this important?

Good Random Number Generation is a key component to modern cryptography, statistical problem solving techniques, communication security, stock market prediction, etc., but is extremely difficult to implement on deterministic machines like modern computers. There is a large library of "Psuedo-Random" algorithms that have been written to generate "random like" number sequences, but given the same starting values or "seeds", they will produce exactly the same sequence. This predictability makes them ideal for some types of problems (see Perlin Noise for a great example), but an extreme liability for other uses.

A truly random (completely unpredictable, and statistically sound) number generator needs a true chaotic randomness source feeding it. One of the best sources of statistically sound randomness is from quantum effects, such as radioactive decay, electron vibration noise, etc.  It just so happens that there's a measurable quantum mechanical effect on silicon, and both Intel and AMD have been nice enough to put device hook to this into some of their hardware.

I'll show you how to make this work.

Part 1. The hw_random module.

First, build a 2.6.X kernel with hw_random configured as a module.
     (I'm assuming you already have module-init-tools, and know how to do this.)

Device Drivers-> Character devices ->  Intel/AMD/VIA HW Random Number Generator support set to <M>. On saving your kernel, if you 'grep RANDOM .config' it should answer CONFIG_HW_RANDOM=m Go ahead and build the kernel and modules, fix grub/lilo, boot from new kernel, Check to see if hardware is supported. Do a 'modprobe hw_random'. If successful you should see hw_random when you run 'lsmod', and 'dmesg |grep random' should return something like:

hw_random: AMD768 system management I/O registers at 0x8000. hw_random hardware driver 1.0.0 loaded

If this fails, this means that ether your hardware is not supported yet, or you don't have a hardware random number generator. You'll have to find another system where this works. Sorry. Read Kernel-Source/hw_random.txt and the source to see what hardware is supported.

Part 2. The devices nodes.

Ok, you got the module working, now how to talk to it.. If you are using /devfs, you can skip ahead a bit.
As root, cd to /dev/ and run
mknod /dev/hwrandom c 10 183
To load hw_random when the device is used, do the following.
echo "alias char-major-10-183 hw_random" >> /etc/modules.conf
/PATH-TO-MIT-TOOLS/module-init-tools-3.0/generate-modprobe.conf
>/etc/modprobe.conf
depmod -ae
hw_module should now show up as soon as its used.

Part 3. The daemon and test software.

You need to download the rng-tools-1.1.tar.gz package from http://sourceforge.net/projects/gkernel/
unpack it into your source directory (/usr/local/src is a good choice),
configure
make
make install
This makes two programs, plus the man pages. In /usr/local/sbin/ is a file called rngd, the random number generator daemon.
go ahead and run this. It's job is to take randomness info from /dev/hwrandom, and feed it as seeds to /dev/random. The second program is /usr/local/bin/rngtest. Try the following...
cat /dev/random | rngtest -c 1000
The output should look something like this (remember, it's random!)...
rngtest: rngtest 1.1 starting up...
rngtest: bits received from input: 20000032
rngtest: FIPS 140-2 successes: 999
rngtest: FIPS 140-2 failures: 1
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 1
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=1.206; avg=118.273;
max=1518.642)Kibits/s
rngtest: FIPS tests speed: (min=30.566; avg=64.671; max=65.998)Mibits/s
rngtest: Program run time: 165442321 microseconds
If it detects lots of runs or patterns, you're randomness is broken, DON'T USE IT!
Another kind of neat thing to try is
xxd /dev/random |more
(xxd is part of the vim software packages)

Part 4. The finish, and other fun stuff.

If you feel you can trust your randomness, that is rngtest seems happy, you'll want to put rngd in a startup script.
To learn more about why randomness is important, check out the following resources:

The Code Book: The Science of Secrecy from Ancient Egypt to Quantum Cryptography by Simon Singh (Author)
    A great intro to crypto, how it works, its uses, and its misuses (many mistakes were made).
Too bad that the code challenge in the back of the book was broken so fast. Very good coverage of the breaking of Linear B and Egyptian Hieroglyphics.

Secrets, Lies, and Atomic Spies
http://www.pbs.org/wgbh/nova/venona/     A TV program that takes a very scary look at the cold war crypto activity, the mistakes that the USSR made in their use of one-time-keys, and how the NSA broke a handful of messages. The scariest part is that the KGB knew we broke their codes fifty years before the general American public was allowed to know. That, and that Ethel Rosenberg was probably innocent.

The Codebreakers : The Comprehensive History of Secret Communication from Ancient Times to the Internet by David Kahn (Author)      Another great book on Crypto, with a stronger focus on 20th Century WWI Zimmerman Note, the WWII code talkers, enigma, etc.

LavaRND www.LavaRND.org
    A cool website where they use lava lamps to generate truly crytographically sound random numbers. If your hardware doesn't support hw_random (or vice versa), this would be a good alternative.
Not to be confused with LavaRand, the earlier SGI version.

Perlin Noise
http://freespace.virgin.net/hugo.elias/models/m_perlin.htm
http://mrl.nyu.edu/~perlin/doc/oscar.html

    Ken Perlin worked on the movie "Tron", then went on to create this noise generator that has some useful properties, including winning an Academy Award for Ken Perlin.

Paketto Phentropy
http://www.doxpara.com/read.php/code/paketto.html

    Part of this TCP/IP analysis toolkit is a 3D data visualization package. At the bottom of this web page are some example movies of how bad randomness can allow TCP sequence numbers to give away OS versions, and possibly allow spoofing hacks.

Part 5. Conclusion.

Please remember that history is full of examples of good crypto used poorly. One-time-pads rely on good random number generators and that the pads only being used once to be secure.

Use randomness carefully!

If you're able to get some use out of this Mini-HowTo, send your spare Lava-Lamps and a postcard to John Gilbert, care of LinuxCertified, 1072 S. De Anza Blvd., Suite A107-19, San Jose, CA 95129


Please provide any feedback, corrections etc on above article to articles@linuxcertified.com

Receive Announcements & Linux Tips

info@linuxcertified.com
Linux is a registered trademark of Linus Torvalds.