feature article
Subscribe Now

The Secret Secret to Secrets

Generating Random Numbers is Harder Than it Looks

“Rage, rage against the dying of the light.” – Dylan Thomas

I’m no expert in computer security. But I know some people who are.

Crypto-weenies (as they love to be called) occupy an interesting niche in the engineering ecosystem. Normally, engineering is a clearly understood, aboveboard kind of endeavor. We operate by well-understood laws of physics. Ohm’s Law applies to everyone. We tend to share information, expertise, tips, and tricks. Heck, open-source software is all about sharing and disbursing information and exposing all of your code’s inner workings.

Yet crypto-engineers aren’t like that. They thrive on secrecy, myth, and legend. Their techniques are deliberately obscure. Their very success often depends on other engineers not understanding how their stuff works. So it’s a bit difficult to glean useful information about cryptography circuits or techniques, even during long conversations with normally gregarious developers. There are some things you’re just not supposed to know.

Chief among these is how a computer generates and checks security keys. By this I mean the passwords, checksums, hashes and whatnot that are either intended to verify that a user or a program is who or what you think it is, or that are used to encrypt important data. When you download a firmware update, how do you know that it’s the actual approved code from the vendor and not some hacked or spoofed version? When you store payment or password information, how to prevent someone else from reading that file?

Cryptography involves secrets, by definition. There’s the secret you’re trying to keep (passwords, for example), and then there’s the secret that keeps that secret a secret. You can try to keep the location of the password file a secret (“security by obscurity”), or you can encrypt the file in some way. Paradoxically, most encryption algorithms are publicly known and well understood. So if the encryption algorithm itself isn’t a secret, how does it generate secrets?

By “seeding” the algorithm with a secret number, that’s how. Even if the bad guys know exactly how you encrypted your secret file (and they will), they still can’t crack it if they don’t know how you seeded it. That seed number becomes the real secret.

You can pick a seed number yourself, but that’s only fun for the first half-dozen times. It gets tedious after that. It’s also not as secure as it seems, because humans tend to be lousy at picking random numbers. It’s too tempting to pick a birth date or your locker combination from high school. We also have a weird tendency to pick the number 17 when we’re thinking of random numbers.

The right way to do it is to have a computer generate the seed numbers randomly. But that presents a different problem. Computers do what they’re told (usually), so how do you tell a computer to pick something at random? Randomizing a decidedly deterministic and nonrandom machine is a paradox in itself. Thus, we have a whole subgenre of engineering dedicated to creating and testing true random-number generators (TRNGs).

Random numbers must meet four criteria. They must be unpredictable (duh), they must be uniformly distributed across the whole number space (e.g., between 0 and 1, or between 1 and 1000, etc.), and they must be utterly independent of any outside influence. That third criterion is remarkably difficult to achieve. For instance, a TRNG can’t use any part of the computer’s real-time clock as a randomizer because that would mean you’d get the same numbers at the same time of day. Lastly, but perhaps most obviously, random seed numbers must be kept secret. No matter how beautifully random your number is, it loses all of its value the second it’s known.

This is all tough to do. We’re not good at judging randomness, and “hard to guess” isn’t a valid test. The NIST actually has standards for randomness as well as tests you can run to see if your RNG is truly a TRNG and not just a PRNG.

Peeling the onion a bit further, how do you get a computer to cough up truly random numbers? Ah, that’s where it gets secretive and the engineers start looking at their shoes. There are all sorts of circuits involving shift registers and loopbacks that can do strange and unnatural things to a seed number, but how do you generate that seed? Where does the real randomness enter the picture?

Cryptography experts call that “the source of entropy.” Your entropy determines the quality of your TRNG, to a large extent. And entropy can come from a lot of places, most of them pretty poorly understood. We’ve already eliminated the RTC as a source of entropy; it’s too predictable. It also fails the “independence” test because there would be too much correlation between the time of day and the resulting random number. Sure, it would be hard to guess, but not hard to duplicate. We also can’t use other seemingly random events like the time it takes a human operator to press a key on a keyboard, because that’s also tied to an outside, observable (and theoretically repeatable) event.

How about internal sources of entropy? Some designers have used the random contents of uninitialized RAM cells as a big binary number, but blank DRAMs aren’t actually as random as we like to think. Some chipmakers use random manufacturing variations in their circuit designs, like the capacitance of a certain area of polysilicon or the resistance of a given trace. Others design circuits with deliberate race conditions. Those are all pretty uncontrollable (see here) and unrepeatable, so they make good sources of entropy. They’re also hard for outside hackers to observe – right up until they decapitate the chip and examine it with a microscope. Really dedicated security thieves have no qualms about doing that. Some chipmakers include physically unclonable functions (PUFs), although those are more for identification than for seeding TRNGs.

Manufacturing variations have the advantage of being a natural (unintentional, actually) byproduct of normal semiconductor processing. It comes for free, in a sense. But it’s also wholly unpredictable, which is… good? Or is it bad, because you can’t ever be sure those defects will continue from wafer to wafer, or from process node to process node? It’s so secret even the developer doesn’t know how it works!

And as arcane as these tricks are, they’re also discoverable if you try hard enough. After all, if the circuit’s RC behavior is detectable by the TRNG, it must also be detectable to outside instruments. That means it can be probed, with the right equipment. All it takes is time, money, and talent to crack your security. Pick any two.

The current state of the art involves a multipronged approach. First, use random manufacturing variations as your source of entropy. Then bury the relevant circuits under other layers of metal and polysilicon so they’re not easily probed from the top without damaging the rest of the chip. Next, “whiten” the TRNG by masking its behavior while it operates. A lot of seemingly impossible side-channel attacks have been successful by monitoring the power consumption, RF emissions, propagation times, or temperature variations of a chip that was otherwise secure. Whitening the circuit with random noise masks its behavior and prevents (we think) such attacks. Then keep all of that information a secret. 

2 thoughts on “The Secret Secret to Secrets”

  1. Dear friends,

    Generating Random Numbers has been my Diploma Thesis, published in 1961. See
    http://www.fpl.uni-kl.de/staff/hartenstein/lot/ER-1961.pdf
    (sorry, in German language)

    A sensor (scintillation counter) received input from radioative radiation. The logic design of a decimal digit counter was done with transistors not yet on the market – sponsored by the German Philips. Its components: a Flipflop followed by a flap-flep-flip-flop-flup circuit having 5 states (figure 4).

    Best regards,
    Reiner

Leave a Reply

featured blogs
Oct 18, 2018
The IC6.1.8 and ICADVM18.1 production releases are now available for download at Cadence Downloads . IC6.1.8 ICADVM18.1 For information on supported platforms, compatibility with other Cadence tools, and details of key issues reported by our early access partners that have be...
Oct 17, 2018
Samtec offers one of the industry'€™s largest and most flexible lines of two-piece, pin-and-socket board-stacking interconnects. To say it another way, we have more ways to stack two or more boards together than any other connector company.  Also, you can specify a cust...
Oct 16, 2018
  IC Insights has just published the September Update to The 2018 McClean Report, and one figure (reproduced below) puts yet another nail into the coffin for poor old Moore'€™s Law. Now please take care. There'€™s a vertical line between the 200mm wafers on the left ...
Oct 12, 2018
At the end of the day, your products are only as good as their in-the-field performance. It doesn'€™t matter how well they performed in a controlled environment....