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.

Comments

  1. yea, right says:

    “cryptographically secure random numbers”

    • Leonard says:

      Time is probably of the essence.

    • thoriumbr says:

      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.

      • Trui says:

        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.

        • EccentricElectron says:

          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.

          • Trui says:

            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.

          • razor_sparks says:

            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.

        • 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.

          • Trui says:

            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).

          • 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.”

          • Trui says:

            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.

          • 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.

    • yea, right says:

      “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.

  2. hboy007 says:

    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.

  3. fartface says:

    A simple op-amp set to insane gain and then into a digital line input. Makes a great true random number generator.

    • SparkyGSX says:

      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.

    • fonz says:

      maybe, maybe not, it might pick up a local radio station or just oscillate. The usual simple noise source is an amplifier and a zener diode

      • Greenaum says:

        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?

    • It is more complicated than you seem to believe…

      http://code.google.com/p/avr-hardware-random-number-generation/

  4. atomsoft says:

    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?

    • Mike Lu says:

      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.

    • ... says:

      You should ask the HAD ‘editors’, the author never claimed it only had 2 components.

  5. zibri says:
  6. Joshua says:

    Pseudo random…

    • Megol says:

      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.

    • Sorry, but no, it has been tested (and much of that explained in the library link provided)… As the author, I have had two implementations in constant use for over 16 months and it has still not failed.

  7. wardy says:

    Atmel ATSHA204 — an I2C or one wire bus chip that provides numerous authentication and “TRNG” – but it’s llikely to be full of NSA back-doors so use at your own risk :)

  8. rj says:

    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.

    • Megol says:

      If I don’t confuse tests (always a possibility) even running diehard isn’t a guarantee the generator doesn’t have biases that weaken the cryptographic strength.

    • As the author of the library, I can assure you that the generator has been (is still ongoing) tested. On multiple avr chips, by multiple people. I have two implementations that have been producing a random stream for over 16 months. If your curious you can read about it at http://code.google.com/p/avr-hardware-random-number-generation/

    • 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…

    • JGM says:

      ++

      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.

  9. 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.

  10. BobC says:

    This would be ideal on a Digispark, with no need for a USB dongle: http://digistump.com/products/1

  11. Koplin says:

    I made my own true RNG from a radioactive isotope source from a smoke detector and an old webcam.

    I am not the first to do this and I didn’t make a build log, got the idea from this

    http://www.inventgeek.com/Projects/alpharad/overview.aspx

    • Mike Lu says:

      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.

      • Greenaum says:

        Reminds me of the old MIT (I think, back in the day) trick of pointing a camera (before we had webcams) at a lava lamp. Do a bit of maths and you get some randomness out of it.

  12. euler357 says:

    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

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 96,614 other followers