This post is going to be my recap of a small portion of Dan Kaminsky’s Derbycon 2012 talk, “Black Ops.” The part of his talk this writing will reflect on the importance of random number generation and details a couple methods for adding entropy.
One of the biggest keys to information security and especially cryptography is the ability of computers to produce random numbers. Random numbers form the backbone of encryption. Most systems today try to add entropy to their random values by measuring and quantifying several unpredictable variables such as mouse and keyboard inputs or the effect of the environment on the hard drive’s ability to spin. These methods don’t bode well for servers without HDDs.
Kaminsky suggested two ways to make random numbers more random. One method works directly with the hardware, the other method is a purely application-level software approach. The hardware method will be described first and the software approach second.
In any system with multiple clocks (which is basically all of them) random bits can be generated by measuring the difference between a fast clock and a slow clock. The idea is simple and brilliant: Have a process attached to a fast clock increment a count variable in a tightly-looping incrementing function. Have a second process attached to a slow clock fire off an interrupt to the first process every nth cycle. In the interrupt function, flush the first processes count variable to a buffer, shuffle the bits, hash them, truncate the result and push it into the random number pool.
The software approach is likewise novel. Instead of using different clocks, it employs firing off multiple threads and causing a race condition. This method is a simple from an algorithmic standpoint, but the concept is the important part; any number of algorithms could be designed around the theory of racing threads or measuring the time they take to return. The idea Kaminsky set up requires at least three threads: One thread holds an integer variable; a second thread increments the variable; a third thread decrements the variable. The idea is to fire the first thread then fire the second two simultaneously and see which, if any, got blocked. The best thing about this approach is that it doesn’t rely on human input devices to increase entropy meaning servers can benefit from it greatly.