“All science is either physics or stamp collecting.” – Ernest Rutherford
If you think about it, “random” is really just a euphemism for any pattern that we don’t understand. Rolling the dice at a casino table produces a random result, but only because we don’t think about it very hard. We understand the physics of momentum; we know the coefficient of friction of the felt on the table; we can calculate the inertial vectors of the throw. Given enough time, we could accurately predict the outcome of any dice roll. It’s even possible to make a robot arm that throws snake eyes all day long. But absent that real-time information, we treat the outcome as random. Otherwise, there’d be no games of chance.
Our ancestors were baffled by randomness. Why does it rain some days and not others? Why did the river not flood as much as last season? What made the volcano erupt now, just a few months after that strange eclipse? With no understanding of meteorology, microclimates, geology, hydrology, astronomy – or much of anything else, really – our ancestors instead imagined capricious gods impulsively controlling the world for their own inscrutable ends. It wasn’t much of an explanation – it still isn’t – but it satisfies a deep-seated need to impose a sense of order, even if it’s an entirely imaginary one.
At the other extreme, we have digital electronics. No randomness there. It’s all deterministic, predictable, repeatable, and reliable. Digital signaling, unlike messy analog electronics, suffers not from signal degradation. Your bits either get there or they don’t, but they don’t deteriorate or diminish along the way. That’s what makes “audiophile” HDMI cables so hilarious. Dude, it’s digital. Enjoy your gold-plated, oxygen-free 1’s and 0’s.
Okay, sure, underneath it all, everything is really analog, just as everything eventually boils down to physics (or stamp collecting). But at our level of abstraction, it’s all tidy digital bits going about their appointed rounds. We rely on that determinism, that binary nature, to do our jobs as programmers and engineers.
But that very determinism is also what makes it very hard to generate random numbers. Beginning programmers learn that you can’t simply tell a computer to “make up” a random number. And if you tell the machine what number to pick, or even how to pick one, then it’s not really random anymore, is it? So we rely on pseudo-random number generators or lists of pre-generated numbers, or other tricks that aren’t, strictly speaking, truly random, but that nevertheless serve our purposes. After all, “random” just means you can’t see the pattern, right?
That’s all dandy until someone more motivated than you spends quality time figuring out how “pseudo” your pseudo-random number generation really is, and thereby cracks your security. So we have us a dilemma: how do we get unpredictable random numbers from a predictable, deterministic, reliable, digital machine? How do we get Mr. Spock to tell a joke?
We inject some messy unreliability into the equation in order to go quietly off the rails.
Random numbers are important, and not just for gambling. They’re the basis of almost all cryptography and related security measures. Without random numbers, all of your passwords, hashes, keys, and other sensitive information are stored in a reversible, discoverable form. Padlocks aren’t much use if every key fits them. Random numbers provide those differently shaped keys.
The SIM cards used in a million cellphones and ATM cards use keys generated by pseudo-random number generators, which are then stored in on-chip RAM or ROM. Trouble is, those keys can be reverse-engineered, often by X-raying the circuitry. We’ve also seen how keys can be teased out of systems merely by snooping on their radio-frequency emissions or even their power usage. And because SIM cards and the like are mass-produced on the cheap, they all use the same handful of algorithms to create and store their keys. Figuring out how to hack one means you’ve figured out how to hack them all. No, we need something better.
One good way to ameliorate both problems is to include some sort of unique – literally unique in all the world – feature on each chip. If every single stored password relied on something that was different, something that was exclusive to that password or that user alone, then you’d have tougher security. Nobody could figure out your pseudo-random numbering pattern because there’d be no pattern. And hacking one system wouldn’t give any access to the next one, because the unique part would be different every time.
The current state of the art for this technique relies on a physically unclonable function, or PUF. As the name suggests, this is a physical characteristic of the chip, not just a software-defined feature. And it’s unclonable, so you can’t make copies of it, even if you do somehow duplicate the rest of the chip. (Chips are mass-produced, after all, so they’re normally supposed to be clones.) We’ve covered PUFs before (here and here), so the concept isn’t entirely new. But how do you mass-produce chips that are at once identical and yet different?
Well, there are a couple of different ways, but San Jose–based startup QuantumTrace is understandably fond of its own technique. The company uses variations in the chips’ metal layers to introduce totally unique and uncopiable variations into otherwise deterministic and reliable digital devices. The result is a predictable chip with a bit of unpredictability. Like Mr. Spock after a few drinks.
The exact process is a closely guarded secret, of course, but the basics are easy enough. QuantumTrace lays down a thin layer of metal (aren’t they all thin?) and then uses natural imperfections in said metal to feed a voltage-to-digital conversion circuit that converts the blemishes into bits. In the end, you get a 256-bit random number that’s unique to your chip’s particular freckle pattern. And the details of QuantumTrace’s process guarantee that no two chips will ever be the same, no matter how carefully manufactured.
If a 256-bit unique key isn’t enough, the company is happy to have its circuit crank out a 512-bit key, or one that’s thousands or millions of bits long. Go nuts. Longer keys might take longer to generate, but we’re only talking a few milliseconds anyway. What’s the hurry?
One of the delightful charms of QuantumTrace’s process is that it scales well. In fact, the metal’s randomness actually “improves” with smaller feature sizes, so keys get even more random, if that’s possible.
The company operates on an IP-licensing business model. You pay them an up-front license fee for access to the technology, followed by royalties on every chip you make. There are no funny semiconductor processing steps required, so the technique works with pretty much any CMOS device on anybody’s fab line. You pays your money and you makes your keys.
So now you can eliminate random hacks by incorporating randomness in your devices. And you won’t have to pray that nobody figures out your security measures.
An interesting article. My worry about all the methods of producing PUFs is that they might potentially degrade over time, temperature or voltage. For example, metallization is susceptible to electro migration effects which get worse with thin metal. It would be good to understand how this is mitigated – but then QuantumTrace would undoubtedly need an NDA to discuss it…
The PUF is only part of the solution. For example, National Institute of Standards and Technology (NIST) recommends a method of generating cryptographically acceptable random numbers (specification SP800-90A/B/C) that’s suitable for embedding into an FPGA or SoC. I wrote a blog about it if readers want more information: http://embedded-computing.com/articles/dont-let-your-encryption-be-defeated/
In reply to Paul, you can find a paper from HOST 2014 on anti-ageing for SRAM PUFs on our (Intrinsic-ID) website at http://bit.ly/1DbSmnr . Certainly, a lot of research, testing and fine-tuning over several years has gone into ensuring reliable performance over time of PUFs.