40
\$\begingroup\$

A small microcontroller (8-bit Atmel) controls a number of lights in order to present a light show with many fancy randomized light sequences.

A suitable pseudo-RNG does its job nicely, but I'm looking for a good seed for it. A seed will be necessary because if someone turns multiple such devices on at the same time, it won't look good if they all generated the same sequences of effects until they slowly drift apart due to the tiny differences in their individual clock sources.

A very good method to seed a pseudo-RNG, which I often used, is possible in case of a device which has to be started with the press of a button or flip of a switch. As soon as the µc is powered on, a very fast timer can be started, and the value of this timer seeds the RNG as soon as the button is pressed for the first time.

The problem is, in this scenario, there are no buttons. The program has to start as soon as the device is powered on.

The place on the PCB is extremely limited (nothing more than a few of the very smallest SMD parts might fit), so I'm looking for the smallest and simplest possible solution. Therefore I'll rule out fancy solutions like true RNG hardware, radio receivers, etc.

All I have is a 16 bit timer-counter in the CPU, and an unused portpin which has access to an ADC.

My current solution is to just use a resistor (as inaccurate as possible) to provide approximately half the supply voltage to the ADC pin, and seed the RNG with the first AD conversion value. However, nowadays most 10% resistors have an inaccuracy well under 1% (it would be fun to imagine the face of a supplier when I tell them we want the worst quality SMD resistors they can find), so there is a very high chance of multiple units starting with the same seed.

A better alternative would be to make multiple conversions and build a value out of the least significant bits of these measurements. However, I used the ADC of this µc type before and I know it's very accurate. Running the ADC at the fastest possible speed might help here.

Does anyone have a better suggestion? The seed is not required to be perfectly uniformly distributed, but the more uniform the distribution is, the better. A 16 bit seed with a perfectly uniform distribution would be a dream too good to be true, but I think a halfway decent distribution over 5 or 6 bits might be sufficient.

\$\endgroup\$
  • 12
    \$\begingroup\$ "it would be fun to imagine the face of a supplier when I tell them we want the worst quality SMD resistors they can find" - it would be even funnier to let the value of this resistor be undefined in the circuit diagram, and telling the people in production that this one part must be soldered manually after the pcb comes out of the placement machine, out of a bin where we mixed together every resistor value we have. - Because it's not a RNG I'm looking for, but a seed. So if it generates the same value almost every time it's not that bad, it's more important to be different across devices. \$\endgroup\$ – vsz Sep 2 '15 at 16:34
  • 8
    \$\begingroup\$ Why not write a random value to EEPROM storage during production programming? This way, you could use the fanciest RNG you like as it'll only be in the production programmer(s) and not the end devices. (Credit to @immibis: your 'slightly different software file' gave me the idea.) \$\endgroup\$ – Calrion Sep 3 '15 at 9:02
  • 2
    \$\begingroup\$ So just to be %100 clear, the problem is that they might start out on the same sequence, not that they might drift apart over time, correct? \$\endgroup\$ – wedstrom Sep 3 '15 at 22:27
  • 2
    \$\begingroup\$ The choice of your RNG matters: some need good quality seeds, others don't. For example, for Xorshift, any seed other than 0 will work and will work equally well. Even a tiny difference in the initial seed will result in a very different starting position in the RNG's cycle. \$\endgroup\$ – curiousdannii Sep 4 '15 at 3:43
  • 3
    \$\begingroup\$ You can combine all the ADC answers with statistics and timing for even more randomness. For example, measure how many processor ticks it takes until you take N samples where the lower 3 LSBs are 101, and M samples where the lower 3 LSBs are 110. Expand this concept as desired. \$\endgroup\$ – wjl Sep 5 '15 at 6:06

10 Answers 10

24
\$\begingroup\$

Put a parallel resistor and capacitor between the A/D pin and ground. Make the resistor fairly high, preferably well above the input signal impedance requirement for the A/D. Make the RC time constant maybe around 10 µs. For example, 100 kΩ and 100 pF sounds like a good combination.

To get a value with some randomness, drive the pin high for a while, then set it to high impedance and take a A/D reading a few µs later. Particularly if you properly abuse the A/D acquisition time, the voltage it will see will be dependent on the R and C values, the pin leakage current, other nearby noise, and temperature.

Grab the low bit or the low two bits and repeat as necessary to get any number of random bits.

For a more random pattern, perform this procedure occasionally and inject the low bit of the A/D result into the random number generator you are already using.

\$\endgroup\$
  • \$\begingroup\$ This sounds good. Be sure to check the input impedance on the ADC - the Atmega8 series have an analog input impedance of 100Meg which makes Olin's resistor value a bit low. \$\endgroup\$ – stefandz Sep 2 '15 at 23:09
  • 3
    \$\begingroup\$ @stef: Input impedance and the signal impedance required for correct conversion are two different things. Yes, the input impedance is very high due to it being CMOS. However, there is a maximum impedance limit on the signal to enable it to charge the sample and hold cap within the specified time, and to overcome whatever leakage the pin may have. \$\endgroup\$ – Olin Lathrop Sep 3 '15 at 10:37
  • 2
    \$\begingroup\$ sorry, from your answer I thought you were referencing the input impedance as opposed to the source impedance spec. 10k is the Atmega8's specified maximum source impedance, so your answer is spot on. For reference, the S/H cap inside is 14pF, in case anyone was interested. \$\endgroup\$ – stefandz Sep 3 '15 at 10:48
  • 2
    \$\begingroup\$ @stef: I edited the answer to make this more clear. \$\endgroup\$ – Olin Lathrop Sep 3 '15 at 10:52
  • \$\begingroup\$ You missed Lunar phase & bank holidays. Also hand waving a useful addition, especially if low C and not well shielded. \$\endgroup\$ – Russell McMahon Sep 9 '15 at 13:06
23
\$\begingroup\$

Some possible options:

  1. Pre-program a unique serial address for each device. If you have a good enough RNG algorithm, then even a sequential list of serial addresses will produce wildly different results.

  2. Depending on your MCU/setup, you might have two different clock sources available for the system clock and the watchdog timer/timer counter input. If one/both of these have significant variance, you can use this to generate a suitably different seed. Here is an example I wrote which uses an Arduino's internal watchdog timer and an external XTAL system clock.

  3. Use a BJT transistor and build a highly beta dependent amplifier. This can be read from an ADC for the seed.

  4. Capacitors/inductors are typically specified to a much worse tolerance than resistors. You could build some kind of filter circuit (RC, RL, LC) with these and measure the output with the ADC.

\$\endgroup\$
  • 5
    \$\begingroup\$ I vote for option 1, it is a zero part count solution that will result in the sequences never having to match. The serial number and RND generator can say 16 bits making any devices have a negligible chance of mimicking another's pattern. \$\endgroup\$ – KalleMP Sep 2 '15 at 18:18
  • 1
    \$\begingroup\$ I also like the solution one. If you use a simple hashing algorithm you should be fine even if you have sequential serial numbers. \$\endgroup\$ – magu_ Sep 2 '15 at 21:22
  • 6
    \$\begingroup\$ A nice thing about option 1 is that some devices come with built-in serial numbers (usually network/RF related micros) so you don't even need a separate step to burn the serial numbers \$\endgroup\$ – slebetman Sep 3 '15 at 0:34
  • 3
    \$\begingroup\$ Even a garbage RNG like an LCG will "produce wildly different results for a sequential list of serial addresses". I vote for 1 also. \$\endgroup\$ – BlueRaja - Danny Pflughoeft Sep 3 '15 at 0:41
  • 3
    \$\begingroup\$ If you have a time source then using that as a base for your switch on seed would help offset things between runs. Combine this with a serial address/number or the MAC address if your device has one and you will fix the inter-device matching too. I have seen some software that persistently stores some or every random number generated for use as the seed, even after a reboot. If your devices have different operating times, they should drift apart. \$\endgroup\$ – TafT Sep 3 '15 at 10:24
8
\$\begingroup\$

Uninitialized memory

You could try to use the uninitialized memory in the micro controller. The trick is to find the bits that have the most 'balanced' flip-flops, and are actually random. The procedure is to read all the memory, reset, and repeat a few times to measure which bits are truly random. Then you use this map to read out enough random bits to seed your PRNG or LFSR!

This method should give you random seeds, even with identical hardware, more details (and links) are available in this hack-a-day article

I like this method because it doesn't require any additional circuitry or pins; your AVR already has ram, you just need to find the unstable (random) bits. Also the mapping procedure could be automated; you can apply the same code and procedure to each device, and have truly random results!

\$\endgroup\$
  • 1
    \$\begingroup\$ You don't really need to figure out which bits are random. XOR-ing all bytes will give you a random outcome even if just 8 bits are random. And as the picture shows, the actual values may not be random in a temporal sense, they're unique enough - which is exactly what we need here. \$\endgroup\$ – MSalters Sep 3 '15 at 23:07
  • 1
    \$\begingroup\$ If you can find a PRNG that allows you to "mix in" entropy, then that could be even better than the XOR-then-seed option. Iterate through the uninitialised memory and mix in the bytes to the PRNG. E.g. see my simplerandom C library—mix function. \$\endgroup\$ – Craig McQueen Sep 4 '15 at 6:30
  • \$\begingroup\$ This will not give you crypto-quality randomness. \$\endgroup\$ – user17592 Sep 5 '15 at 8:20
  • \$\begingroup\$ @CamilStaps of course it won't. \$\endgroup\$ – Navin Sep 5 '15 at 18:30
  • 1
    \$\begingroup\$ This will not work. Uninitialized memory is undefined behavior if I have an operating system and I don't have any control over which part of memory will be assigned to my program and what was there before. On a microcontroller without an OS this is not the case. Especially with AVR, because there all the RAM will be zero if enough time has passed for the capacitors to be emptied by the current consumption in brownout. \$\endgroup\$ – vsz Sep 5 '15 at 18:38
7
\$\begingroup\$

What I did for a MP3 player with random capability is to just use a different sequential seed at every power on. I started at 1 and stored this in the EEPROM so that at the next power cycle I used 2 etc. This was on an ATMEGA168. As helloworld922 noted even a simple sequential seed will generate completely different pseudo random sequences.

I used one of the linear congruent random sequence generators, this gives a uniform distribution.

int i;
seed = seed * 2053 + 13849;
i = (seed % max) + 1;  // max is the maximum value I want out of the function

Of course if you want multiple units to have different sequences even though they may have had the same number of power cycles then you need something to start out randomly.

This could be done by any of the methods proposed by the other posters - One method I can think of could use the AC zero crossing going into the processor if you have it (for lamp phase control for example)? This could be used to sample the timer on the first crossing following power-up and then used as the seed.

Are there any push-buttons on the unit to select mode etc? If so you can sample the counter the very first time the button is pushed after the MCU is programmed you can generate a random seed initially and store it in EEPROM. Every Power-up after this point would use the stored seed.

\$\endgroup\$
5
\$\begingroup\$

An ADC is a very good source for randomness.

You do not need to rely on resistor tolerances. Any resistor will generate thermal noise, and the same physical effect will introduce noise into the ADC when doing all the sampling and conversion steps. (The datasheet will tell you about the amount of noise, and what configuration settings are worst/best.)

You should not leave the ADC pin floating; this might let the voltage float too far, and risks saturating the input.
(Many MCUs allow you to use something like half of the supply voltage as an ADC input, for calibration. This saves the external resistor, and still gives you noise. Again, see the datasheet for the worst/best configuration.)

You do not need to rely on a single ADC measurement; you can combine multiple measurements with a simple hash or checksum function (CRC would suffice). If you need to start using the RNG immediately, you can later combine the ADC result with the current RNG seed.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'm not sure Johnson noise is a suitable in this application; At STP a 10Meg resistor over a 10kHz bandwidth has 40uV of Johnson noise. You would need a >14 bit ADC or an amplifier circuit to reasonably measure this. \$\endgroup\$ – helloworld922 Sep 2 '15 at 17:17
  • \$\begingroup\$ STP isn't really relevant. The temperature especially could be intentionally raised, but an extra 60 degrees over STP is just 10% extra noise. \$\endgroup\$ – MSalters Sep 3 '15 at 23:30
  • 1
    \$\begingroup\$ A similar approach would be to use the shot noise in a diode. en.wikipedia.org/wiki/Noise_generator#Shot_noise_generators \$\endgroup\$ – teambob Sep 4 '15 at 2:38
2
\$\begingroup\$

Can you save the seed from session to session? If so, is it feasible to turn every unit on for some random time period upon creation? That way all the units will be shipped with preset seeds that are unlikely to be the same.

Another thought: How do you link multiple units together so they turn on simultaneously? If they're in series, add some kind of capacitor so the (n+1)th device starts a few clock cycles after the nth device. Ideally, capacitors would discharge very rapidly on device shutdown, so every start/restart there's a larger gap between the sequences.

If they're in parallel, you could still randomize the start-up time a bit. I assume there's some kind of power filtration using capacitors. If so, fabricating the devices with slightly different filtration circuits would cause each device to start at a slightly different time, causing divergence after several restarts.

A variation on this is to add variance to your clock signals if possible. A 0.1% difference in clock speed might have little impact on the light show, while changing the rate you traverse the PRNG table pretty quickly.

\$\endgroup\$
  • 1
    \$\begingroup\$ perhaps connect a large pour to the analogue in pin and take some readings of "mains hum" to seed the RNG. \$\endgroup\$ – Jasen Sep 3 '15 at 9:07
  • 1
    \$\begingroup\$ @Jasen, all the units connected to the same extension lead will see the same mains hum. \$\endgroup\$ – Ian Ringrose Sep 3 '15 at 14:25
2
\$\begingroup\$

If you running on internal "calibrated" clock source. Could you not save a seed after some time, preferable into the EEPROM. The clock will drift, and it will differ from unit to unit. To save a new value after some time again (maybe each 10 minute or so, or after a time that is short enough to occur within the normal on-time for the device. The longer the device is on, the more likely it will save a "different" value into the EEPROM.

Also take a leap once every now and then (not to often) and reseed while device is on (save this new value in EEPROM).

\$\endgroup\$
2
\$\begingroup\$

What about extendinging your original idea of AD converting based on a varying resistor by adding a LDR or thermistor? (The first would need to be able to "look" outside, I don't know if that's feasible; but the variation in light may be higher than the variation in temperature among devices started at about the same time in about the same place ...)

\$\endgroup\$
  • 1
    \$\begingroup\$ Thermistors come in with another useful property. Several series from most manufacturers have a tremendous variance and inaccuracy. This will further "improve" the outcome. \$\endgroup\$ – Ariser Sep 6 '15 at 8:48
1
\$\begingroup\$

2 potential solutions, both assuming you need a unique seed per unit.

  1. If you flash your units one by one in the factory, The hex file can be programmatically modified by some intermediate script in the programmer. If it is pc controlled, you can overwrite a variable initialisation with the date and time. Guaranteed to be unique for each unit!

  2. Dallas 1 wire devices use only one pin and each come with a unique 64 bit serial number. You can use this as the seed.

\$\endgroup\$
  • 1
    \$\begingroup\$ I like 2, but unfortunately the DS parts all are rather expensive. \$\endgroup\$ – Ariser Sep 3 '15 at 7:26
  • \$\begingroup\$ Don't use production timestamp for crypto-quality randomness, it's predictable. \$\endgroup\$ – user17592 Sep 5 '15 at 8:24
  • 2
    \$\begingroup\$ @CamilStaps For the OP's application, crypto-quality is not required \$\endgroup\$ – Hagen von Eitzen Sep 5 '15 at 16:50
  • 1
    \$\begingroup\$ @HagenvonEitzen true, but others may come to this question searching for crypto-Q randomness, so it's worth mentioning. \$\endgroup\$ – user17592 Sep 5 '15 at 16:55
  • 4
    \$\begingroup\$ @CamilStaps Sigh, it seems you have given up on humanity :) Is it really too demanding to expect from someone who wants to use an answer from electronicsSE for cryptographic purposes that they be at least careful enough to read the question it is supposed to answer? "16bit" or "5 o5 6 bit" seeds are not crypto-Q even if generated by a bunch of Schrödinger cats :) \$\endgroup\$ – Hagen von Eitzen Sep 5 '15 at 18:03
1
\$\begingroup\$

You can leave a floating ADC pin to feed the random number generator (RNG) with captured noise. It should be enough to generate a seed or even use it as the RNG generator.

Don't forget to use the minimum possible conversion time.

The other solution could be a noise generator applied into the ADC pin.

\$\endgroup\$
  • 2
    \$\begingroup\$ I'll make some measurements but if I remember correctly, a floating ADC pin reads 0 or close to 0. I'll check it again to see if that's the case. \$\endgroup\$ – vsz Sep 2 '15 at 16:53
  • 1
    \$\begingroup\$ I am interested, does it read 0 when floating? \$\endgroup\$ – Bence Kaulics Sep 2 '15 at 20:30
  • 2
    \$\begingroup\$ The problem is that this might work on a development board and fail in the final product. \$\endgroup\$ – vsz Sep 5 '15 at 18:40

protected by W5VO Sep 3 '15 at 18:30

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

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