My next class:

A Random Diary

Published: 2013-09-17. Last Updated: 2013-09-17 13:59:24 UTC
by Johannes Ullrich (Version: 1)
10 comment(s)

The current discussion about breaking encryption algorithm has one common thread: random number generators. No matter the encryption algorithm, if your encryption keys are not random, the algorithm can be brute forced much easier then theoretically predicted based on the strength of the algorithm. All encryption algorithms depend on good random keys and generating good random numbers has long been a problem.

In Unix systems for example, you will have two random devices: /dev/random and /dev/urandom. "random" usually produces random numbers based on some source of entropy. In Linux, parameters like mouse movements, disk activity and interrupts are used. Older versions of the random number generator used network activity, but since the attacker may be able to affect network activity, this parameter is no longer used. The Linux random number generator was found to be not particularly well implemented, in particular on disk less systems and systems with little user activity, like for example routers [1] .

Recently, some implementations of Linux like OpenWRT where found vulnerable if they are used on MIPS based hardware. The random number generator on these systems uses the number of CPU cycles since reboot as a seed. However, the respective function always returns 0, not the actual number of cycles on MIPS. [2]

Are there better ways to collect random numbers? One of the challenges is to increase the amount of entropy (random events) collected. There are some good attempts to use microphones, cameras and other hard ware devices to improve the pool of entropy. Sadly, there are no simple "standardized" solutions to implement these techniques.

Here are a couple pointers to projects that may help you implement better random number generators:

Using the camera in Windows : http://wcrnd.sourceforge.net
using the sound card in Windows: http://sourceforge.net/projects/trng
Linux camera based random number generator: http://sourceforge.net/projects/lavarnd/
Linux sound card random source: http://code.google.com/p/snd-egd/

testing random number generators: http://www.leidinger.net/FreeBSD/dox/dev_rndtest/html/df/d2a/rndtest_8c_source.html (look for "rndtest" in your Linux distro)

Got any other tips to create good random numbers (cheaply)?

[1] http://www.pinkas.net/PAPERS/gpr06.pdf
[2] https://lists.openwrt.org/pipermail/openwrt-devel/2013-September/021318.html

------
Johannes B. Ullrich, Ph.D.
SANS Technology Institute
Twitter

Keywords:
10 comment(s)
My next class:

Comments

Havege is also used :

http://www.issihosts.com/haveged/

Cpu interrruption as entropy source

G.

Anonymous

Sep 17th 2013
1 decade ago

I have seen suggestions that one can use radioactive decay of something as a basis for truly random numbers. The radiation levels wouldn't need to be high - it really depends on how many random bits per day you really need.

There are homebrew projects where people have taken a home smoke detector (which has a small sample of Am-241) and adapt it to be a random number generator.

Anonymous

Sep 17th 2013
1 decade ago

" Got any other tips to create good random numbers (cheaply)? "

It's very doable to get a sequence of outputs that has all the mathematical properties that random numbers have; without needing to resort to physics. So the question may to broad.... how do you define "good"; good enough for what? What's the fundamental qualifier? :)

Math::RANDOM::ISAAC comes to mind.
http://www.burtleburtle.net/bob/rand/isaacafa.html

Oh I don't know... grab a copy of the isc.sans.edu homepage's HTML; concatenate it with the current text of the front page of 100 internet news sites and blogs around the internet, include some twitter searches; crawl at a pseudorandom hourly offset. After 10000 crawls are appended, encrypt that huge blob of text using a block cipher, with a secret key. Take a SHA512 hash of that encrypted result, and seed the ISAAC algorithm using the bits in the hash.

for $i (0..$hashtext) { $seeds[0] += ord(substr($hashtext,$i,1)) }
my $rng = Math::Random::ISAAC->new(@seeds);

Use the seeded algorithm to generate a new 256-bit symmetric key.

Anonymous

Sep 17th 2013
1 decade ago

The problem with a lot of these methods is that they are only for user workstations. Embedded systems often don't have keyboards, mice, sound, camera's, or even background network traffic. So in the "Internet of things" many systems need self-contained crypto quality RPNGs. Virtual hosted systems have similar problems.

Anonymous

Sep 17th 2013
1 decade ago

Intel has some things built into the chip for DRNG.

http://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide

Anonymous

Sep 17th 2013
1 decade ago

In the hardware world, we used to use a diode junction forward biased with a weak current. A carbon resistor can provide thermal noise. Alpha decay can be a random source, as alluded to by the smoke detector approach noted in an earlier post. Shot noise can be a source of random numbers in a vacuum tube biased almost at cutoff. A radio dectector in the low end of the HF band can be used to detect "atmospherics" -- noise from electrical discharges from lightning. I am not sure what kind of bit rate one can get out of these approaches, so it would depend upon how many random bits you needed over a given interval of time.

Anonymous

Sep 17th 2013
1 decade ago

@Anonymous
Intel RNG in the chip? .....bad timing mate ;)
https://www.schneier.com/blog/archives/2013/09/surreptitiously.html

Anonymous

Sep 18th 2013
1 decade ago

Great find, and great comments on the article. Curious as to what Intel's response to this is as the strategy seems to be differentiate with features on the chip like their manageability engine and other things that allow you to store keys, run code and things like that.

Anonymous

Sep 18th 2013
1 decade ago

How about a cheap radio receiver that tunes in to cosmic noise, and base the seed on that output?

Anonymous

Sep 18th 2013
1 decade ago

http://www.entropykey.co.uk

A USB device that supplies lots of fresh entropy to /dev/random, available for any opensource flavor os.
Can be shared over a network aswell.

Anonymous

Sep 20th 2013
1 decade ago

Login here to join the discussion.


Top of page
Diary Archives