High quality entropy with nothing up its sleeves

The BitBabbler is a hardware True Random Number generator (TRNG). It provides a high bitrate, high quality, constantly verified source of unguessable entropy for any use where a simple pseudorandom sequence is not sufficient or not suitable. It is the culmination of what began as a simple search for an entropy source for our own use that we could believe we might actually be able to have some trust in using for cryptographic key generation and other similar tasks.

Our initial assumption was, like many people before us, that such a thing already existed and we just needed to find the best one. But as our search progressed it became ever more apparent, much to our growing dismay, that we were wrong. So naively wrong that there was only one thing left to do; Start from scratch, learn all that we could from other's mistakes, and see if we could in fact do things better to make a compact, portable and affordable device.

The Problem

Our initial set of requirements didn't seem that onerous:

Minimalist faith

The first two requirements essentially boil down to keep the device as simple as it can be. Ideally it should contain no reprogrammable elements, so no CPU, no FPGA or CPLD, and no onboard memory which could be used to store state for manipulating the output stream. A device which has these things and then locks them to prevent them being read or changed by an attacker only makes the problem worse, since in the hands of a determined attacker, it also prevents you from being able to reverse engineer or disable their exploit.

There is no reason that a good entropy source cannot be built entirely from off the shelf non-programmable components, available from a variety of suppliers, and preferably in a package form which can be replaced on the board by an even moderately equipped home user who has some basic skill with hand soldering. While only the most dedicatedly paranoid people might actually do that, it's the ability for anyone to do it, at any time, which creates the counter-threat of detection to any would-be attacker.

Most TRNG devices that we looked at fell at this first hurdle, though none failed close scrutiny on just this point alone. The more complicated the hardware device is, the more places it has for accidental or deliberately introduced failure, and the more difficult it becomes to detect that. Proprietary firmware makes it worse, but any firmware programmability is a clear liability.

Safety in numbers

The third and fourth requirements mainly relate to serviceability, how fit the device actually is for real world use and how robust it is in the face of either normal or induced failure. A catastrophic RNG failure must be detected immediately, before it has a chance to pollute the system entropy pool, and any long term bias in the raw entropy stream must be detectable during normal operation. Disabling a failed or suspect TRNG should not leave the system starved for other adequate sources of real entropy.

Applying cryptographic whitening to the output is not in itself a bad thing, but that should always be done after the raw stream is subjected to all forms of analysis, since it can easily mask even a complete loss of entropy from the source. A simple counter, providing a completely predictable stream with zero entropy will still appear statistically random if run through a good cryptographic hash – that's precisely the property that makes it a good hash. And sadly, that also makes it a common hack used to hide an otherwise poor entropy source. If the entropy is being used to feed something like the Linux kernel pool, it will already be whitened in this way before use (after mixing with other entropy), so there would seem to be minimal value in doing this to an already good source which is supplying that pool. It cannot increase the entropy of a bad RNG, it can only make the final output stream seem less correlated (to a casual observer) than it really may be.

Predictably unpredictable

The fifth requirement again mostly relates to complexity and robustness of the entropy source. A generator circuit that is inherently unstable, which only operates correctly within a narrow range of conditions, and which requires constant feedback and adjustment to maintain those conditions, seems like a poor choice next to alternative options which do not require that. All feedback loops oscillate to some degree, adding the risk of a secondary predictable resonance to an already naturally biased source. It's probably not impossible to design a satisfactory generator of that form, but it seems harder and more fraught with risk than simply avoiding such designs.

Possibly the only thing worse is designing a TRNG where the only source is an avalanche noise circuit without any such adaptation. The breakdown current which flows in those is highly sensitive to both temperature and voltage fluctuations, and the variation in thresholds between individual components (even from the same manufacturing batch) can be relatively large, particularly when using cheap transistors that were not designed especially for that use. These are easy to make cheaply, but difficult to make reliable for long term use. Since they are also generally quite a slow source of noise, the difficulty is compounded by it taking a very long time to obtain a statistically significant number of samples, limiting the ability to test them well.

Pump up the volume

The sixth was an aspirational requirement. Faster is always better, until it's not. When capturing noise from a broad spectrum source, there is a tradeoff where faster sampling will better capture more of the high frequency noise but it will also reduce the influence of lower frequency noise on adjacent samples. For any such device there will be an optimum sampling rate, above which you start to lose more of the usefully available entropy than you gain from sampling it more often, and correlation between consecutive samples will begin to increase. Beyond a certain point, higher bandwidth circuits also tend to be both more difficult to design and more expensive to produce, which adds a practically limiting factor to how far it is sensible to push this as well. But a TRNG you can't properly test because getting enough bits out of it takes too long is useless too, so this limit had to be pushed …

Wait, what?

The last was perhaps the most initially shocking thing we found in our search, and the one which finally pushed us over the edge to begin building something for ourselves – though armed with the hindsight gained from that effort, it is no longer quite as surprising as it initially was.

It turns out that it is actually quite challenging to build a genuinely good entropy source, and that unless you are extremely diligent, and skeptical, and fully committed to the task of proving that the RNG you have just made is bad, it's very easy to be deceived by the initial results of some simple statistical tests. The often repeated (and wrong) assertion that hardware random number generators aren't supposed to pass such tests probably doesn't help many of the people who've tried to get past that step either. The confirmation bias that is inherent in wanting your project to succeed is powerful. And we'd have probably been sucked in by that after our first trials too if it wasn't for what we'd already seen elsewhere before we began, and what we'd resolved to try to do about it. So we're going to avoid pointing fingers at anyone in particular here. The aim of this project was not to shame people who have genuinely tried their best to Do Good, but to continue to push the state of the art, both for our own use, and for the benefit of everyone who has an interest in this. If we talk about some of the more egregious mistakes elsewhere on this site (which we will), and you think you recognise yourself in those, please don't take that as a personal condemnation. Among people who fly, the philosophy is learn from the mistakes of others, because you won't live long enough to make them all yourself. We think this is a lot like that, so we'd like to assemble a coherent record of them to help people avoid repeating them in future, and we'd likewise encourage people to give us critical feedback on the mistakes they see that we've made too – because however diligent we've tried to be with this, it would still be kind of amazing if there isn't something that we've so far missed somewhere, and it's equally important that we find and fix and warn people about those in no uncertain terms too.

There's a lot of bad information out there about this subject, and if it goes unchallenged and continues being repeated, and continues being naively believed, that doesn't help anyone except the black-hats. We can't take down every site that's spreading it, but we can certainly try our best to avoid perpetuating it, whether it's just sloppy language that is open to misinterpretation, or sloppy understanding that needs to be clarified, if you see it here, please do point it out.

xkcd 538

One thing not explicitly in that original list, which some people may already have noted, is any specific requirement for ongoing physical security. In our original use case, that wasn't going to be a major threat once the integrity and correct operation of the devices were initially established and they were in our possession. If someone could blackbag the site where they were to be used, they could do a whole lot worse than just tamper with or substitute an entropy source. In the more general case of looking to make a device that would be suitable for other uses and other users too, this is perhaps the question with the largest variety of correct but contradictory answers. We look at several of the possible options for that in more detail in the pages describing the BitBabbler design.

Raising the bar for trusted entropy sources

People like to say that it's easy to gripe, though this subject does appear to be something of an exception to that rule. While there are people who have been sensibly challenging many of the more obviously troubling problems and questionable claims of all devices, the general sense we got was that while many people were quick to be suspicious of RDRAND, they seemed equally quick to give just about everything else a nearly free ride. Especially if it used the word Open in a sentence somewhere.

Maybe that's because the failure modes here are subtle – and like with openssl, everyone assumes that someone else is out there doing the due diligence on it. Given the number of people who are still parroting that piping /dev/urandom back into /dev/random is a good way to solve entropy starvation, there does seem to be a rather widespread lack of awareness about what constitutes a good entropy source.

But that's not the immediately important point here … A good set of coherent gripes are the measures and scales of all engineering development, so armed with those to guide us it was time to do some experiments.

All noise, all the time

The first and most important question we needed to answer was, where are we going to sample the noise from? Using a radioactive source was ruled out for practical reasons, and at the other end of the spectrum, mechanical noise was also ruled out for being impractical, inefficient, and too susceptible to external influence. Which left us with just, well … most of the rest of the EM spectrum and all of the things which make it naturally noisy – which didn't really seem too seriously limiting as a starting point.

Having spent many years now designing electronic hardware where noise was our ever present and unstoppable nemesis, and knowing that it comes in a wide variety of flavours and forms with independent causes, made at least one thing seem like a fairly obvious approach to take. We should try to accumulate it from as many of the well understood noise phenomena as we are able to capture together. If strong resilience against any interference from the environment injecting a predictable signal is important (which it is) and if design by proverbs is a thing (which we are less certain of), then don't put all your eggs in one basket seemed like a pretty good starting point to experiment with. If no single perturbation can effect every form of noise that we are integrating, in some way that is a predictable function of the source of interference, then we should have an entropy source which is robust against both natural and deliberate interference. It would still be possible to completely cripple the device (or the computer it is plugged into for that matter), but subtle manipulation which doesn't immediately fail the output sanity checks should become a far more complicated proposition.

It seemed like a plan with some appealing details. To make it work we just needed to turn to the dark side and find a good way to eliminate as much of the signal in a circuit as possible while cultivating every available source of noise into a fully grown, unpredictable, string of zeros and ones … Quick, easy, and seductive, what could possibly go wrong?

White (noise) is the new black

Of course it turns out that getting rid of any trace of a signal is at least as hard as getting rid of the noise in a conventional design. At some point the terms become basically interchanged, the signal we now want is what's left when everything else is told to shut the hell up (which turned out to be an important clue in the end). But we had a plan that looked good on paper, with several sources of pure noise that were theoretically sound if we could tap into them and lift them out of the ruinous signal that would plague them with correlation.

So we designed and built a device. Then we redesigned and built another. And then we iterated through building and testing a few more. At each step we tried as hard as we could to find observable flaws in them. When we couldn't find any more, we tried to find stronger tests which could.

Now we're finally at the stage where we are failing to prove that what we have is broken. Which means it is time to invite more interested people to join in and see if they can find any weakness that we have so far missed. We think we might finally have what we wanted, something with some solid science behind it, that doesn't just rely on saying the word Quantum, trotting out some cliched tropes from security theatre, showing a selected run of Ent, and hoping that nobody who knows what they are looking at will ever stop laughing (or crying) for long enough to bother investigating any of it in depth and call that bluff for what it is. We think it's time to talk about that openly so that more people do understand, or want to understand, and become engaged enough to take us and others to task over anything that is still lacking. We think it's time for the people who care about this to make some noise. Good clean noise.

Comfort eagle

We think we now have something we can begin to trust for our own use. We'd like to think we have something that rivals or beats even the most ridiculously overengineered and expensive devices out there, but the final proof of that really will be in the results of further peer review and analysis. We've currently settled on two TRNG designs that we're aiming to make available to others at a "no excuses" price point, which will make it a no-brainer to use one in any situation where it might be of value, for anyone who is even remotely serious about having a source of good entropy available.

So if you've read this far, and you're even half as excited about this as we now are, you'll probably want to look at the detailed description of how it all works next.