• FOSDEM 2016
• /
• Schedule
• /
• Speakers
• /
• Nicholas Mc Guire

The speaker description is potentially outdated as it is from a previous FOSDEM edition.

The problem of generating reliable and "good" random numbers is a long standing problem in general and especially in embedded systems. For many systems it is not an option to include a special purpose (back-door-ed ?) true Random Number Generator (RNG) be it for cost reasons or because the systems are actually already deployed and modifications non-trivial. Software solutions for RNGs generally are considered to be pseudo RNGs (PRNGs), that is they provide "good" random streams provided the seeds and internal state are kept secret. For cryptographic means as well as for probabilistic algorithms a good source of random numbers is needed, in this paper we present a possible alternative solution called Embarrassingly Simple Random Number Generators (ESRNG). Although these results have not yet been confirmed by an independent entity, our tests using the NIST Statistic Test Suit gives strong evidence for this alternative RNG approach passing the NIST sts-2.1.1 on more than 80 platforms from single core to many-core and virtual systems.

In this presentation we introduce the code concept and the actual implementation along with the current state of testing.

The sources of ESRNG are released under the GNU General Public License Version 2 as published by the Free Software Foundation (www.gnu.org), this paper is released under FDL V1.2.

It is not uncommon for embedded systems to simply ignore issues of random number generation or use anything from weak ad-hoc methods to "all boards using the same secure key"...

One reason for this is that the entropy extraction methods in operating systems that are based on software, build on asynchronous external events,
e.g. interrupts as the entropy source. For deeply embedded systems such sources are often not available or simply insufficient. This can be because they are to deterministic, e.g. CAN or too slow (serial lines) to keep the entropy pool filled.

Generating reliable keys needs significant amounts of entropy, even desk-top systems commonly run out of entropy during generation of keys, or may take a
very long time to complete key generation (very long being tens of minutes).

At the same time we have witnessed the integration of many non-deterministic optimizations in contemporary CPUs. Out of order instructions, pLRU cache-replacement, asynchronous logic in cache-controllers, "random" retries on memory-transactions as well as CPI values that are not constant even
with disabled interrupts and cache hot instruction sequences. There is more than enough entropy in a modern CPU - in fact we would claim that a modern CPU (even single core) is a excellent true entropy source - all that is needed is a harvester for this entropy source.

Surprisingly it turned out that the harvester for this system inherent entropy is truly trivial - in its simplest form amounting to a a few dozen lines of C-code, running as unprivileged low-priority process in user-space.. hence we named it Embarrassingly Simple Random Number Generator (ESRNG). While the final code is truly trivial, it took five versions (until now) to reach
the current state. ESRNG5 now achieves performance in the range of 1kbit/s (raspberry Pi) to 35kbit/s (Core Duo Quad) thus well suited to satisfy most of the demands on RNGs in embedded systems.

The model behind this is simply harvesting of micro-timing differences at the instruction level. This is achieved by implementing different types of race-conditions that lead to biased random sequences and then using different methods for un-biasing --- explicit, e.g. VanNeuman/Peres or implicit, e.g. by coalescing inverse processes.

This report will focus on ESRNG5 which is a multi-threaded RNG based on implicit unbiassing. With all the skepticism that "pure software" solutions most likely will encounter, we hope that presenting the internals of the
approach will help uncover any potential flaws and ultimately lead to a reliable software based TRNG suitable for embedded systems.

Keywords: embedded,SW-TRNG,system entropy

Events