The Two Component Random Number Generator

attiny10

[Karl] was in need of a hardware random number generator, but is needs had a few caveats: it needed to be cheap, and sufficiently random. Random number generation can get quite crazy with Geiger tubes, lava lamps, and radioactive decay, but a much smaller solution was found in an 8 pin AVR microcontroller.

The solution uses AVRentropy, a library that uses the watchdog timer’s jitter in AVR microcontrollers to provide cryptographically secure random numbers. Setting up the circuit was easy – an ATtiny45 microcontroller was connected to a cheap chinese USB to serial converter. Three wires, and the circuit is complete. The code was simple as well; it’s just a call to initialize the entropy and write the bits to the serial port.

There are a few drawbacks to this build. Because the entropy library must wait until enough entropy is gathered, it can only produce about two 32-bit numbers per second. That’s all [Karl] needed for his application, though, and with an enclosure made from a wine cork and marble, he has the prettiest and smallest random number generator around.

41 thoughts on “The Two Component Random Number Generator

    1. Yes, they are secure. The dongle is only sending out random numbers generated by the MCU, and the code is simple enough to be read by almost anybody.

      After Snowden, almost everyone distrusts everything related to crypto, but if you don’t believe those numbers are secure, at least state why.

      1. It is not absolutely secure, but for most purposes it is good enough. It is easier to put a back door in the program these random numbers are going to be used for than it is to hack this device, especially because it is a custom device.

        Of course, for most purposes, a simple software random generator on a PC using freely available entropy is also good enough in nearly all the cases.

        1. I think in this case the ‘security’ element refers to the generation of the random numbers themselves (is the sequence genuinely random and unpredictable? generating truly random sequences is much harder than it might appear at first sight) rather than the way in which the generated numbers are then treated.

          1. The generated numbers are probably not genuinely random and unpredictable. The RC oscillator that drives the watchdog is not completely independent from the environment, and will respond to temperature/voltage fluctuations which an attacker may control or read out. Also, with sufficiently sensitive equipment, the RF emissions may be detected from some distance.

            I realize that people tend to focus on only a single part of the whole security network (the random number generator), but a complete secure system has many more elements. There’s is no sense in worrying about perfectly random and unpredictable numbers, if they are going to be used in a system with easier weaknesses.

          2. Trui is right, another example I saw of this using an FPGA was able to be biased by heating it up or letting it heat itself up with hard usage. I would also say there should be a level of de-skewing going on before those numbers are used, and perhaps, that’s part of the reason there is a delay. I prefer the Geiger method or the amplifier noise method (http://hackaday.com/2012/09/12/generating-random-numbers-from-white-noise/) on the theory side.

        2. Trui, as the author of the library in question, I can assure you that the library has been shown to produce cryptographically secure and truly random (uniform distribution) numbers. The security is largely dependant upon physical implementation, though, so as the end user one is reponsible for not only maintaining that, but regularly checking to ensure that the security hasn’t been compromised.

          1. Ah, but did you check the compiler to see if it recognizes that you’re building the library, and inserts a back door in your object files ? (not so far fetched as you may think, as this has been done before).

          2. Again, “The security is largely dependant upon physical implementation, though, so as the end user one is reponsible for not only maintaining that, but regularly checking to ensure that the security hasn’t been compromised.”

          3. Right. So the end user is still required to verify everything from end to end, including the library itself, the toolchain, the USB interface, the PC, and the details of the watchdog clock hardware that aren’t easily accessible to inspection, as well as making sure the attacker doesn’t have any way to monitor or manipulate relevant external influences. Since nobody does all those things, we cannot assume it is “absolutely secure”. Of course, we can agree it is “secure enough” for most typical purposes. But then again, the same can be said for /dev/random.

          4. Yes, Trudi if a person wants security they are required to ensure it for anything that might be compromised… Nothing new there.

            Of course, unless the NSA is after you (or you fear it is) then the OP’s device will likely proove fine as is. Even more so if they simply use it on a variety of different computers and hence don’t have to worry too much about that end of things.

            And not everyone is running a OS that has /dev/random… and of those who do, this library and user created device is far easier for that user to perform the verification described above than it would be for most users to verify that /dev/random hasn’t been compromised…

            And of course, this tech doesn’t actually need a computer at all if the task can be handled with a couple of microcontrollers.

    2. “True random generators” are not “cryptographically secure random generators” because with a “true random generator” there is a chance to get 0, 0, 0, 0, 0, 0, .. 0 at it’s output and you don’t want that for crypto.

  1. Been there, done that .The only thing that still puzzles me is the code distribution from a straight forward implementation (using wdt and an 8 MHz crystal): http://abload.de/img/200kphasenoisehist2rq8x.png (200k 8bit values collected and binned).
    I’ve added a few lines to ensure even code distribution (needless to say that this measure doesn’t increase randomness). Will have to take a closer look at AVREntropy.

    1. Maybe, maybe not. For most purposes, it might be sufficiently random, but for a cryptographically secure random number generator, the distribution must also be random, and it should ideally be impossible to influence the random number generator externally.

      I think your proposal more or less means it’s a opamp amplifying the signal from a poorly tuned circuit (as opposed to a highly selective RF receiver); this means it would probably be possible to influence the output by illuminating the circuit with a strong RF signal.

      It’s fairly easy to come up with a circuit that might work; it’s mighty difficult to prove any given circuit actually does work as a secure random number generator.

      1. Op-amp in a Faraday cage? With an optical output?

        Isn’t there still plenty of good entropy in the old fashioned “please hit lots of keys” method and measuring the time down to the microsecond?

  2. How is this “The Two Component Random Number Generator” if there are way more than 2 components. Dont try to write that the PCB (USB to UART) is one component because then you can make this all in 1 pcb and call it a 1 component random… so … any thoughts on that?

    1. It’s a UART output RNG. The two components are the microcontroller and its bypass cap. The USB to UART is just an adapter. Though its low speed is indeed almost useless – just digitizing an unused analog audio input and using the LSBs gets you 96kbps or more. For that matter, I suppose a real one component RNG would be a zener diode built inside a 3.5mm plug, which is then plugged into the microphone input of a PC or other device.

      That said, I have used zener noise successfully for generating random numbers. Combined with a LFSR to debias it, it will even pass randomness tests.
      http://dangerousprototypes.com/forum/viewtopic.php?f=62&t=4632

      If you need very high speed generation of cryptographic random numbers, your best bet is to use a high speed ADC to digitize noise, discard some of the MSBs, and use cryptographic encryption and/or hashes to further debias it. As a matter of fact, some encryption algorithms like AES are really just CSPRNGs. Their output is unpredictable as long as the key remains secret.

    1. I haven’t looked at the design but it is fully possible to generate true random numbers from a clock source. The idea isn’t to use the clock as such but to extract the jitter which depends on misc. things like thermal noise. One “just” have to make sure to filter out deterministic components to get a proper random source.

  3. Please at least run the data through the diehard or dieharder tests before claiming it’s cryptographically secure. e.g. LFSRs produce fantastically good-looking mean / autocorrelation / whiteness / histograms and yet are awful PRNGs.

    1. The basic tests were used as a screen, since the early reports on jitter noise produce entropy for the AVR series indicated that some types of chips have issues. The more detailed tests require multiple independent samples of the entropy stream and are much more complicated to present the results from. diehard needs 10MB of data for each sample and dieharder needs about 300mb for each sample. The nature of true random number generators (as opposed to the PRNG’s for which the tests above are designed) is that it WILL fail some of the test components SOME of the time. It requires multiple sample and statistical analysis to determine if those failures are significant… Not something easily conveyed or written upon on a Wiki page… I am still running tests on the data, and it hasn’t failed yet…

    2. ++

      Also, the Nist STS is another good resource for would-be RNG implementors. While neither of these tools will tell you your RNG is secure, they can certainly tell you that your RNG is busted.

  4. BTW, at only 2 32-bit ints per second of entropy, the two devices I have that have been running this for about 16 months have only produced a abou 320 MB of entropy each. Or enough for one sample run through die-harder… Can’t even combine the tests for multiple samples, since it isn’t really valid to test the validity of a single source that way.

    1. If you can find a way to remove the glass without ruining the CCD, you’ll get a lot more “speckles”. Glass stops the alpha particles, so it’s the gamma radiation from further down in the decay chain that makes it work at all.

  5. It should be expected that Diehard, ent, rngtest, and other random number test tools show some number of failures with a true random number generator. If you are seeing 100% passes with a long sequence then you should suspect that the sequence is pseudorandom or is being filtered to get rid of these cases. For example, one of the tests is for a long string of 0’s or 1’s. This becomes statistically likely to have these strings given a large enough block of random numbers.

    There is a comparison of hardware random number generators on Wikipedia:
    https://en.wikipedia.org/wiki/Comparison_of_hardware_random_number_generators

Leave a Reply to Walter AndersonCancel reply

Please be kind and respectful to help make the comments section excellent. (Comment Policy)

This site uses Akismet to reduce spam. Learn how your comment data is processed.