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
May 21, 2022
May is Asian American and Pacific Islander (AAPI) Heritage Month. We would like to spotlight some of our incredible AAPI-identifying employees to celebrate. We recognize the important influence that... ...
May 20, 2022
I'm very happy with my new OMTech 40W CO2 laser engraver/cutter, but only because the folks from Makers Local 256 helped me get it up and running....
May 19, 2022
Learn about the AI chip design breakthroughs and case studies discussed at SNUG Silicon Valley 2022, including autonomous PPA optimization using DSO.ai. The post Key Highlights from SNUG 2022: AI Is Fast Forwarding Chip Design appeared first on From Silicon To Software....
May 12, 2022
By Shelly Stalnaker Every year, the editors of Elektronik in Germany compile a list of the most interesting and innovative… ...

featured video

Building safer robots with computer vision & AI

Sponsored by Texas Instruments

Watch TI's demo to see how Jacinto™ 7 processors fuse deep learning and traditional computer vision to enable safer autonomous mobile robots.

Watch demo

featured paper

Introducing new dynamic features for exterior automotive lights with DLP® technology

Sponsored by Texas Instruments

Exterior lighting, primarily used to illuminate ground areas near the vehicle door, can now be transformed into a projection system used for both vehicle communication and unique styling features. A small lighting module that utilizes automotive-grade digital micromirror devices, such as the DLP2021-Q1 or DLP3021-Q1, can display an endless number of patterns in any color imaginable as well as communicate warnings and alerts to drivers and other vehicles.

Click to read more

featured chalk talk

Enabling the Flow of Data in the World of IoT

Sponsored by Mouser Electronics and YAGEO Group

At the heart of our growing IoT ecosystem are high performance semiconductors, but integrated circuits alone cannot make a successful IoT system. In this episode of Chalk Talk, Amelia Dalton chats with Peter Blais from KEMET and Ryan Wenzelman from Pulse about how passive components are crucial to the development of successful IoT frameworks. They take a closer look at RF, wired and power distribution aspects of IoT system development and investigate how YAGEO Group is advancing innovation in the world of IoT with a wide selection of passive components.

Click here for more information about Pulse Electronics World of IoT