Nicholas Mc Guire, OpenTech EDV Research GmbH, Bullendorf, Austria

Generating random numbers by traditional means, that is harvesting asynchronous events from peripheral devices via interrupts, is limited on may embedded systems and for some even completely impossible. This not only raises security issues, but it increasingly is also a problem for algorithms that depend on unbiased random numbers (e.g. monte carlo methods). For these deeply embedded systems the solution has typically been to used ”good” pseudo random number generators and hope (in the security case) that the adversary will not be  able to figure out the seed and the PRNG algorithm and thus not be able to predict sequences. The alternative was a relatively expensive TRNG hardware extension.

In the past decades computer science has extensively studied the jitter and latency properties of computer systems. A generally observable trend is for the jitter/latency distribution to manifest it self as distribution rather than as discrete peaks in the spectrum. These distributions are only in part due to peripherals active or the asynchronous nature of co-processors (e.g. DMA,GPUs, etc.) a significant part of the distribution must be attributed to the inherent non-determinism of modern super-scalar CPUs them selves. Pairing this inherent non-determinism, that does not depend on peripheral activities, with methods for harvesting entropy seems a natural option for deeply embedded systems to provide reliable random number generation - including use in cryptographic applications.

The concept of generating random numbers by using ”non-deterministic” software constructs is it self not new - attempts to utilize the undeterminedness of wakeup order from a semaphore have been published in the past - the overall literature on the issue is though scant. In the past years we have developed three different entropy extractors. All of them have one thing in common - the method used is actually trivial and thus we dub this class of random number generators Embarrassingly Simple Random Number Generators (ESRNGs). The three concepts that have been implemented to date are:

• 1st ESRNG (x86 only): was based on the reading of the TSC being physically non-deterministic, even with disable interrupts and cache-hot code, the variance was very small though an extraction was never the less possible. This ESRNG though mandated operation with disabled interrupts to ensure that it was not possible to induce patterns on the bit extraction.
• 2nd ESRNG: The second ESRNG approach was to use a general race condition, a simple unprotected global variable and count the occurrence of a race as a 1 and a non-occurrence as a 0. The outcome would depend on the length of the trial loop and this trial loop was then used to dynamically adjust the ESRNG to varying load situations. While this works we have, to date, not been able to auto-calibrate the parameters needed for the control loop.
• 3ed ESRNG: One of the drawbacks of the 2nd ESRNG was the complexity of the control loop and the fact that the entropy harvested was very limited as it was based on a single bit per race trial (some experimental extensions did show that more could be extracted but that does not remedy the principle limitations of the approach) so for the 3ed ESRNG we tried to model not a single bit ”ball on the nail” type RNG but extended this to logically form a Galton board - that is a state preserving (or partially state preserving) approach.

In this presentation we will not only outline the principles behind the entropy extraction mechanism and present currently available (while still limited) data but also introduce the actual code that is currently undergoing testing for the 3ed ESRNG, on a set of platforms ranging from uniprocessors running a 2.4.X kernel to 8 core systems running the latest 3.X kernels and 3.4.X preempt-rt kernels. this still limited spectrum of hardware and kernels never the less gives us the confidence that the approach is suitable and potentially can be generalized. The prime goal of the presentation is to present the methodology and the design of these random number generators and discuss in what form this could be integrated at kernel level to provide reliable random number generation for deeply embedded systems.