If you are using your Arduino’s PRNG (Pseudo-Random Number Generator) for anything more serious than flashing random lights for your Christmas decorations, there’s a chance you might run into some unexpected issues, as the random() function in Arduino seems to be somewhat broken.

Why? Let me explain.

Background

Most basic random number generators in programming libraries and platforms are based on what is called a “Linear Congruential Generator” (LCG), and I have discussed them before here in my blog. As with any PRNG, the output of the algorithm ends up being a sequence of numbers “seemingly” selected at random, starting from a “seed”.

Given the basic structure of an LCG, after you have drawn X numbers from the generator, you’ll start getting the same sequence again. This is called the “period” of the LCG, and is one of the things you should know about the PRNG you are using (again, if you are serious about your random numbers, or you need a controlled, predictable and stable behavior).

Arguably, you should always know the weakness and strengths of the PRNG you are going to use, before even using it, as to avoid any potential pitfall and/or limitation (and that’s why it’s normally not a good idea to use the default implementation of a random generator in any language; For the most of it you don’t know what you are getting).

The Problem

Mark; a clever guy I follow on twitter, recently published an intriguing discovery, from a rather simple experiment. He wrote a Sketch that picks the third of the first 3 numbers generated by Arduino’s random() function, and starts counting the number of iterations it takes for the PRNG to give the same number again. As it’s supposed to be using GCC’s default PRNG, the expected answer for that is 2^31-1 (0x7FFFFFFF) iterations, but instead, after only 2^31-3 (0x7FFFFFFD) calls (2 iterations sooner) the algorithm started repeating itself.

• Was this weird result related to the fact that he used the third number and not the first one?
• Does that mean that Arduino’s PRNG break after you go over the full set without reseeding it?
• Would anything change if you were to select the 10th number instead? Or pick a different seed?

I do not know for sure, to be honest. Since his experiment takes more than 2 days (55.3 hours, actually) to run on the real hardware, it’s not something I’m interested in playing with a lot (If you repeat the experiment with different seeds and/or different offsets please let me know!). I did, however, run his same sketch almost verbatim (just added a global time counter) to verify that it wasn’t just an accidental hiccup in his setup that caused his unusual result. And no, it was not; I got the same period of 0x7FFFFFFD instead of 0x7FFFFFFF.

Would there be a problem if it’s always 0x7FFFFFFD? Depending on your needs that might not be an issue, but the thing is that it’s such a weird unexpected value, that even if you look into the code behind the PRNG you will end up having no clue of where that value is coming from. There’s something odd about it and it looks to me like their PRNG is not operating properly.

Is this a big of deal? Yes and no. If you don’t need any kind of predictable periodicity in your stream of random numbers, and don’t care about the long time it takes the default PRNG to run, then you can ignore this issue entirely. Otherwise you’ll need to explore alternatives.

The Simplest Solution

I’ll assume here that you are not trying to implement a top-secret high-security encryption scheme on Arduino, but you still want to have a stable, well-behaved and predictable PRNG you can rely on. Based on Mark’s sketch, I repeated his test, but using the simplest, most straightforward “textbook” implementation of LCG, with the parameters used by glibc, which give a LCG model with a theoretical period of 0x7FFFFFFF.

unsigned long lcg_seed = 0x50000L; // Could be any value

unsigned long rand2(){
  lcg_seed = (lcg_seed * 1103515245L + 12345L) % 2147483648L;
  return lcg_seed;
}

You can find the full test sketch on my GitHub. This implementation not only is more straightforward than Arduino’s random(); it’s also faster (takes only 28.7 hours to sweep the full set, instead of ~55) and it behaves in a predictable and consistent manner, giving you the expected period of 0x7FFFFFFF.

Is an LCG a good solution for your cryptographic needs? If you are serious about security; no. But for most applications where you need random numbers and a LCG would suffice, rolling your own implementation (e.g: with the code above) seems to be the way to go; You get a reliable and predictable PRNG, that is twice as fast as the default random() function and won’t fail unexpectedly due to odd behavior.