Saturday, May 9, 2015

CPU jitter for random number generation?

CPU jitter for random number generation?  Here's an interesting paper that claims to present a method for generating random numbers by using the “jitter” caused by various elements of modern CPUs interacting in a complex operating system.  I skimmed the paper, concentrating on section 5, where the author discusses estimating the entropy of the system.  I'm afraid there's too much there that I don't understand for me to make any sort of judgment about the validity of the method.

What the author seems to be asserting is analogous to something anyone can relate to.  Imagine you're driving your car 10 miles in heavy traffic, partly on a highway and partly on city streets.  You can measure your average speed easily enough, and it will be reasonably consistent from one identical trip to another.  However, if you were to measure the instantaneous speed at thousands of points along the way, you'd find lots of variations from the average.  Sometimes a slowpoke in front of you will slow you down.  Sometimes fortune smiles upon you and there's a mile of open, car-free road in front of you.  As you maneuver through traffic, you'll momentarily speed up to pass someone, then slow down to slip back into the traffic pattern.  Similarly, your average direction is the same as that of the road, but there will be lots of momentary variations as you change lanes, bobble about in your lane, etc.  All those minor variations in speed and direction are – the author asserts – random.  There's no pattern to them, and there's no predicting them.  Also importantly, a bad guy can't disrupt the randomness.  These are all good characteristics of a quality random number generator.

Proving that those generated numbers are truly random is another kettle of fish, though.  I'm not sure they've done it.  The current system used by UNIX and a number of other operating systems (and cited in the paper) have been shown to be less than excellent under certain circumstances – most especially on server computers with solid state hard drives.  The problem, it seems, is that timing on such systems is more predictable than with devices that actually move.

Random is hard!

No comments:

Post a Comment