Two Fast Methods of Generating True Random Numbers on the Arduino

[bloc97]

We present two novel and fast methods on generating True Random Numbers on the Arduino.

https://gist.github.com/bloc97/b55f684d17edd8f50df8e918cbc00f94


Any commentary and criticism is greatly appreciated.
The validation part is still missing but extensive testing (Diehard and TestU01) are coming soon.


Thank you for your time and happy holidays.

[pert]

The Arduino microcontroller is a cheap and versatile chip

I really don't like this first sentence. Arduino is not a microcontroller or chip. The term "Arduino" as it refers to commercially available hardware products means a PCB with a primary microcontroller and the necessary support circuitry for that microcontroller. Various microcontrollers are used on the different Arduino boards and none of those microcontrollers are manufactured by Arduino.

[bloc97]

I've changed it to "AVR series microcontroller", it was an oversight on our part.

[el_supremo]

GigaHerts -> GigaHertz

Pete

[bloc97]

Typo fixed, and we updated the article with better experimental data.

[TonyWilk]

Hi,
Interesting article but I'm not exactly sure what target use cases you have in mind.

The abstract states:

One major problem for some hobbists is the lack of secure random number generation on the Arduino platform.

and

In this article we will explore two better methods to generate true random numbers from the Arduino that are both fast, less predictable and less prone to external attack

Unfortunately both methods are really easy to circumvent (short analog input to ground, max. out the accelerometer or spoof it with a replacement I2C source), so it is hardly secure.

Having had some experience with all sorts of RNG's over the years (my company developed gaming equipment, now part of Playtech plc), I think that trying to source entropy from any uncharacterized source is doomed to failure. A 'floating' analog input on the Arduino's processor is susceptible to the system environment it is in, the period or magnitude of any signal is not knowable for any arbitrary case.

By all means, use these (and any other) sources to accumulate entropy to seed and/or adjust an internal PRNG, but if you want 'true' random generation you really need to add some noise source hardware.

For fast generation of pseudo-random numbers, I have always found the Additive number generator  from Knuth's The Art of Computer Programming Vol.2 Seminumerical Algorithms to be excellent. Churning this based on whatever entropy you have is very little overhead.


At the very least, with the methods you currently propose, your library should include some function which attempts to provide a 'secure' random number... i.e. run the algorithm(s) and do some stats to gain a level of confidence that the sources are not compromised, then return a result.

Yours,
  TonyWilk

[bloc97]

The abstract states:
Unfortunately both methods are really easy to circumvent (short analog input to ground, max. out the accelerometer or spoof it with a replacement I2C source), so it is hardly secure.

Yes, of course, if the intruder has direct electrical access to the board, nothing can stop him except a secure hardware random number generator.

However, I do think this is better for projects that are enclosed and/or attached. While it cannot guarantee security, it does require a lot of work to break the RNG, while by using direct sampling or the Von Neumann extractor alone you can do a quick side channel attack by using a device that can generate charge, put it near the board and it will affect the analog pins.

Since this method reseeds the RNG at each step, it is harder to guess the next value since the current value is affected by all previous generated values.

The main reason for building the first method was to conduct a statistical test and proving the feasibility of fast TRNG on the Arduino as a proof of concept. Generation by direct sampling will fail the Diehard tests, and the Von Neumann extractor method will take 20 days to generate the 10MB necessary for the Diehard tests. The first method only took us 3 hours to generate 10MB of data, which is as fast as Direct sampling while also passing the Diehard test.

As you said, the second method will require more testing, and we will update the results of our findings. Also, you proposed an interesting idea. We could try to only output the random values if they pass some kind of test, effectively blocking the program if an attack is detected.

[udoklein]

In my opinion this is a bad approach. In addtion to the reasons already mentioned: if the manufactor should for any reason improve its manufacturing process and deliver chips with less entropy in the output then the scheme will break down.  You seem to assume that this will not happen, but why? Changes in manufacturing are not uncommon. The design might be improved to deliver less noise. Or the design may be optimized for a cheaper build in AD converter.

In addition you did not check how the entropy might be reduced by external influences (e.g. periodic noise in the power supply, vibrations etc.).


The first question is: why do I need a hardware RNG in the first place? Often security reasons spring to mind. Then the second question is: what might be reasonable attack vectors? This is not even considered for this approach.

[robtillaart]

Wether or not it is the ideal random solution, you guys did a serious effort to prove the quality of your generator.
And I really appreciate that, thank you.