© 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
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
