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
Apr 18, 2021
https://youtu.be/afv9_fRCrq8 Made at Target Oakridge (camera Ziyue Zhang) Monday: "Targeting" the Open Compute Project Tuesday: NUMECA, Computational Fluid Dynamics...and the America's... [[ Click on the title to access the full blog on the Cadence Community s...
Apr 16, 2021
Spring is in the air and summer is just around the corner. It is time to get out the Old Farmers Almanac and check on the planting schedule as you plan out your garden.  If you are unfamiliar with a Farmers Almanac, it is a publication containing weather forecasts, plantin...
Apr 15, 2021
Explore the history of FPGA prototyping in the SoC design/verification process and learn about HAPS-100, a new prototyping system for complex AI & HPC SoCs. The post Scaling FPGA-Based Prototyping to Meet Verification Demands of Complex SoCs appeared first on From Silic...
Apr 14, 2021
By Simon Favre If you're not using critical area analysis and design for manufacturing to… The post DFM: Still a really good thing to do! appeared first on Design with Calibre....

featured video

The Verification World We Know is About to be Revolutionized

Sponsored by Cadence Design Systems

Designs and software are growing in complexity. With verification, you need the right tool at the right time. Cadence® Palladium® Z2 emulation and Protium™ X2 prototyping dynamic duo address challenges of advanced applications from mobile to consumer and hyperscale computing. With a seamlessly integrated flow, unified debug, common interfaces, and testbench content across the systems, the dynamic duo offers rapid design migration and testing from emulation to prototyping. See them in action.

Click here for more information

featured paper

Understanding Functional Safety FIT Base Failure Rate Estimates per IEC 62380 and SN 29500

Sponsored by Texas Instruments

Functional safety standards such as IEC 61508 and ISO 26262 require semiconductor device manufacturers to address both systematic and random hardware failures. Base failure rates (BFR) quantify the intrinsic reliability of the semiconductor component while operating under normal environmental conditions. Download our white paper which focuses on two widely accepted techniques to estimate the BFR for semiconductor components; estimates per IEC Technical Report 62380 and SN 29500 respectively.

Click here to download the whitepaper

featured chalk talk

Maxim's Ultra-High CMTI Isolated Gate Drivers

Sponsored by Mouser Electronics and Maxim Integrated

Recent advances in wide-bandgap materials such as silicon carbide and gallium nitride are transforming gate driver technology, bringing higher power efficiency and a host of other follow-on benefits. In this episode of Chalk Talk, Amelia Dalton chats with Suravi Karmacharya of Maxim Integrated about Maxim’s MAX22700-MAX22702 family of single-channel isolated gate drivers.

Click here for more information about Maxim Integrated MAX22700–MAX22702 Isolated Gate Drivers