12

What is the best method to get a truly (as opposed to pseudo) random number in Arduino, or at least the best possible approximation? From my understanding, the function randomSeed(analogRead(x)) it's not random enough.

If possible the method should leverage the basic Arduino setup alone (no additional sensors). Solutions with external sensors are welcome if they improve significantly the randomness over the basic setup.

  • What is the application? Must it be cryptographically secure? What are you doing with the randomness then? Then without an external chip implementing a TRNG from a physical entropy source, you're out of luck. You could also implement a determenistic RNG like a HMAC DRBG and seed it from something static plus a low-quality entropy source, but that still won't be cryptographically secure. – Maximilian Gerhardt Mar 12 '18 at 18:09
  • Yes, I need random numbers for cryptographically secure applications. – Rexcirus Mar 12 '18 at 18:57
10

The Entropy library uses:

the watchdog timer's natural jitter to produce a reliable stream of true random numbers

I like this solution because it doesn't use up any pins of your microcontroller and doesn't require any external circuitry. This also makes it less subject to external failures.

In addition to a library, they also provide a sketch that demonstrates the use of the same technique used to generate a random seed for the microcontroller's PRNG without the library: https://sites.google.com/site/astudyofentropy/project-definition/timer-jitter-entropy-sources/entropy-library/arduino-random-seed

7

randomSeed(analogRead(x)) will only produce 255 sequences of numbers, which makes it trivial to try all combos and produce an oracle that can couple to your output stream, predicting all the output 100%. You are on the right track however, it's just a numbers game, and you need a LOT more of them. For example, taking 100 analog reads from 4 ADCs, summing them all, and feeding that to randomSeed would be much better. For max security, you need both unpredictable input and non-deterministic mixing.

I'm not a cryptographer, but I've spent thousands of hours researching and building hardware and software random generators, so let me share some of what I've learned:

Unpredictable Input:

  • analogRead() (on floating pins)
  • GetTemp()

Potentially Unpredictable Input:

  • micros() (w/ a non-deterministic sample period)
  • clock jitter (low-bandwidth, but usable)
  • readVCC() (if not battery-powered)

External Unpredictable Input:

  • temp, humidity, and pressure sensors
  • microphones
  • LDR voltage dividers
  • reverse-bias transistor noise
  • compass/acceleration jitter
  • esp8266 wifi hotspot scan (ssid, db, etc)
  • esp8266 timing (the background wifi tasks make scheduled micros() fetches indeterminate)
  • esp8266 HWRNG - RANDOM_REG32 -extremely fast and unpredictable, a 1-stop

collecting The last thing you want to do is spit out entropy as is comes along. It's easier to guess a coin flip than a bucket of coins. Summing is good. unsigned long bank; then later bank+= thisSample; is good; it will roll-over. bank[32] is even better, read on. You want to collect at least 8 samples of input for each chunk of output, ideally much more.

Guarding against poisoning If heating the board causes a certain max clock jitter, that's an attack vector. Same with blasting RFI towards the analogRead() inputs. Another common attack simply unplugging the unit thus dumping all the accumulated entropy. You should not output numbers until you know it's safe to do so, even at the cost of speed.

This is why you want to keep some entropy around long-term, using EEPROM, SD, etc. Look into the Fortuna PRNG, which uses 32 banks, each one updated half as often as the one before it. That makes it difficult to attack all 32 banks in a reasonable amount of time.

Processing Once you collect "entropy", you have to clean it up and divorce it from the input in a hard-to-reverse way. SHA/1/256 is good for this. You can use SHA1 (or even MD5 really) for speed since you don't have a plaintext vulnerability. To harvest, never use the full entopy bank, and ALWAYS ALWAYS add a "salt" to the output that's different each time to prevent identical outputs given no entropy bank changes: output = sha1( String(micros()) + String(bank[0]) + [...] ); The sha function both conceals inputs and whitens output, protecting against weak seeds, low accumulated ent, and other common issues.

To use timer inputs, you need to make them indeterministic. This is a simple as delayMicroseconds(lastSample % 255); which pauses an unpredictable amount of time, making "successive" clock reads non-uniform in difference. Do that semi-regularly, like if(analogRead(A1)>200){...}, provided A1 is noisy or hooked to a dynamic input. Making each fork of your flow rather difficult to determine will prevent cryptoanalysis on decompiled/ripped output.

Real security is when the attacker knows your whole system and is still helpless to overcome it.

Lastly, check your work. Run your output through ENT.EXE (also available for nix/mac) and see if it's any good. Most important is the chi square distribution, which should usually be between 33% and 66%. If you get 1.43% or 99.999% or something edgy like that, more than one test in a row, your random is crap. You also want the entropy ENT reports as close to 8 bits per byte as possible, > 7.9 for sure.

TLDR: The simplest fool-proof way is to the uthe ESP8266's HWRNG. It's fast, uniform, and unpredictable. Run something like this on an ESP8266 running the Ardunio core, and use serial to talk to the AVR:

// ESP8266 Arduino core code:
void setup(){
 Serial.begin(9600); // or whatever
}

void loop() {
  // Serial.write((char)(RANDOM_REG32 % 256)); // "bin"
  Serial.print( String(RANDOM_REG32, HEX).substring(1)); // "hex"
}

** edit

here is a bare-board HWRNG sketch I wrote a while back, operating as a not just a collector, but a whole CSPRNG spitting out of the serial port. It's built for a pro-mini but should be easily adaptable to other boards. You can use just floating analog pins, but it's better to add stuff to them, prefereably different things. Like microphones, LDRs, thermistors (trimmed to max spread around room temp), and even long wires. It does pretty well in ENT if you have even moderate noise.

The sketch integrates several notions I've mentioned in my answer and follow-up comments: accumulating entropy, stretching by over-sampling less-than-ideal entropy (von neumann said it's cool), and hashing to uniformity. It forgoes entropy quality estimation in favor of "gimme anything possibly dynamic" and mixing using a cryptographic primitive.

// AVR (ardunio) HWRNG by dandavis. released to public domain by author.
#include <Hash.h> 

unsigned long read[8] = {0, 0, 0, 0, 0, 0, 0, 0};
const int pincount = 9; // adjust down for non pro-mini boards
int pins[9] = {A0, A1, A2, A3, A4, A5, A6, A7, A0}; // adjust for board, name analog inputs to be sampled
unsigned int ticks = 0;
String buff = ""; // holds one round of derivation tokens to be hashed.
String cache; // the last read hash



void harvest() { // String() slows down the processing, making micros() calls harder to recreate
  unsigned long tot = 0; // the total of all analog reads
  buff = String(random(2147483647)) + String(millis() % 999);
  int seed =  random(256) + (micros() % 32);
  int offset =  random(2147483647) % 256;

  for (int i = 0; i < 8; i++) {
    buff += String( seed + read[i] + i + (ticks % 65), HEX );
    buff += String(random(2147483647), HEX);
    tot += read[i];
  }//next i

  buff += String( (micros() + ticks + offset) % 99999, HEX);
  if (random(10) < 3) randomSeed(tot + random(2147483647) + micros()); 
  buff = sha1( String(random(2147483647)) + buff + (micros()%64) + cache); // used hash to uniform output and waste time
  Serial.print( buff ); // output the hash
  cache = buff;
  spin();
}//end harvest()


void spin() { // add entropy and mix
  ticks++;
  int sample = 128;
  for (int i = 0; i < 8; i++) { // update ~6/8 banks 8 times
    read[ read[i] % 8] += (micros() % 128);
    sample = analogRead(  pins[i] ); // a read from each analog pin
    read[ micros() % 8] += ( read[i] % 64 ); // mix timing and 6LSBs from read
    read[i] += sample; // mix whole raw sample
    read[(i + 1) % 8] += random(2147483647) % 1024; // mix prng
    read[ticks % 8] += sample % 16; // mix the best nibble of the read
    read[sample % 8] += read[ticks % 8] % 2147483647; // intra-mix banks
  }

}//end spin()



void setup() {
  Serial.begin(9600);
  delay(222);
  int mx = 2028 + ((analogRead(A0)  + analogRead(A1) + analogRead(A2)  + analogRead(A3)) % 256);  
  while (ticks < mx) {
    spin();
    delay(1);
    randomSeed(read[2] + read[1] + read[0] + micros() + random(4096) + ticks);
  }// wend
}// end setup()



void loop() {
  spin();
  delayMicroseconds((read[ micros() % 8] %  2048) + 333  );
  delay(random(10));
  //if (millis() < 500) return;
  if ((ticks % 16) == (millis() % 16) ) harvest();
}// end loop()
  • (I’m short on characters here, sorry.) Good overview! I would suggest to use a counter for the salt; micros() is a waste of bits because it may jump by several steps between calls. Avoid the high bits in analogue inputs, restrict to the lowest one or two bits. Even with a targeted attack those are hard to pin down (unless you can put a wire on the Input). "Non-deterministic mixing" is not something you can do in software. SHA-1 mixing is standardised: crypto.stackexchange.com/a/6232. The indet. timer you propose is only as random as the source you already have is. Not much gain here. – Jonas Schäfer Mar 13 '18 at 7:07
  • sha simplifies and protects, so that you don't have to worry about how many bits to grab from an analog input for example. a few inches of wire connected to an analog (or a serpentine pcb trace) will swing it more than a few bits. the mixing is non-deterministic by virtue of the unsaved and unknown salt fed to the hash with a subsample of accumulated values. micros() is harder to replay than a counter, esp when fired at non-deterministic intervals. – dandavis Mar 13 '18 at 10:46
  • 1
    I have a question. You said that taking 100 measures is better. But isn't taking lots of measures a sort of "average" that limits the effectiveness of taking these "random" data? I mean, usually you average to get less noisy (so less "random") measurements... – frarugi87 Mar 14 '18 at 16:56
  • well I recommend constant sampling, i was just saying 100 is better than 1 since it offers more combinations. An accumulation model like Yarrow/Fortuna is still vastly better. Consider concatenating (not summing) those 100 analog samples before hashing; stronger because it makes sample order important, and being one char off yields a whole different hash. So, even though one could average the samples to get less noise, an attacker would have to verbatim recite all values or no match... My main point is "accumulate, mix, and verify" more than advocating a specific noise source. – dandavis Mar 14 '18 at 20:02
4

From my experience, analogRead() on a floating pin has very low entropy. Maybe one or two bits of randomness per call. You definitely want something better. The watchdog timer's jitter, as proposed in per1234's answer, is a good alternative. However, it generates entropy at a pretty slow rate, which can be an issue if you need it right when the program starts. dandavis has quite a few good suggestions, but they generally require either an ESP8266 or external hardware.

There is one interesting entropy source that has not been mentioned yet: the contents of the uninitialized RAM. When the MCU is powered up, some of its RAM bits (those that happen to have the most symmetrical transistors) start up in a random state. As discussed in this hackaday article, this can be used as an entropy source. It is only available on a cold boot, so you can use it to fill an initial entropy pool, which you would then periodically replenish from another, potentially slow source. This way your program can start its work without having to wait for the pool to slowly fill up.

Here is a example of how this could be harvested on an AVR-based Arduino. The code snippet below XORs the whole RAM in order to build a seed that it later feeds to srandom(). The tricky part is that the harvesting has to be done before the C runtime initializes the .data and .bss memory sections, and then the seed has to be saved in a place the C runtime will not overwrite. This is done by using specific memory sections.

uint32_t __attribute__((section(".noinit"))) random_seed;

void __attribute__((naked, section(".init3"))) seed_from_ram()
{
    const uint32_t * const ramstart = (uint32_t *) RAMSTART;
    const uint32_t * const ramend   = (uint32_t *) RAMEND;
    uint32_t seed = 0;
    for (const uint32_t *p = ramstart; p <= ramend; p++)
        seed ^= *p;
    random_seed = seed;
}

void setup()
{
    srandom(random_seed);
}

Note that, on a warm reset, the SRAM is preserved, so it still has the whole contents of you entropy pool. This same code can then be used to preserve the collected entropy across a reset.

Edit: fixed an issue in my initial version of seed_from_ram() that worked on the global random_seed instead of using a local seed. This could lead to the seed being XORed with itself, destroying all the entropy harvested so far.

  • Nice work! can I steal? re: pins: one or two bits of unknown is enough if utilized right; that would only limit the output speed of perfect secrecy (yuck), but not the computational secrecy we need... – dandavis Mar 15 '18 at 2:41
  • 1
    @dandavis: Yes, you can reuse, sure. You are right about analogRead() being usable if you know what you are doing. You just have to be careful not to overestimate its randomness when updating an estimate of your pool's entropy. My point about analogRead() is mostly meant as a criticism of a poor yet often repeated “recipe”: randomSeed(analogRead(0)) just once in setup() and assume it's enough. – Edgar Bonet Mar 15 '18 at 8:44
  • If analogRead(0) has 1 bit of entropy per call, then calling it repeatedly will yield 10000/8 = 1.25 KBytes/sec of entropy, 150 times as much as the Entropy library. – Dmitry Grigoryev Jun 26 at 8:07
0

If you don't really need entropy and simply want to get a different sequence of pseudo-random numbers on every startup, you can use EEPROM to iterate through consecutive seeds. Technically the process will completely deterministic, but in practical terms it's much better than randomSeed(analogRead(0)) on an unconnected pin, which will often make you start with the same seed of either 0 or 1023. Saving the next seed in EEPROM will guarantee that you start with a different seed each time.

#include <EEPROM.h>

const int seed_addr = 0;
unsigned long seed;

void setup() {
    seed = EEPROM.read(seed_addr);
    EEPROM.write(seed_addr, seed+1);
    randomSeed(seed);
}

If you need real entropy, you can collect it either from clock drift, or by amplifying external noise. And if you need a lot of entropy, external noise is the only viable option. Zener diode is a popular choice, especially if you have a voltage source above 5-6V (it will work with 5V too with an appropriate Zener diode, but will produce less entropy):

enter image description here

(source).

The amplifier output has to be connected to an analog pin, which will produce several bits of entropy with each analogRead() up to tens of MHz (faster than Arduino can sample).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.