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
Jan 19, 2021
If you know someone who has a birthday or anniversary or some other occasion coming up, you may consider presenting their present in a Prank-O gift box....
Jan 19, 2021
As promised, we'€™re back with some more of the big improvements that are part of the QIR2 update release of 17.4 (HotFix 013). This time, everything is specific to our Allegro ® Package Designer... [[ Click on the title to access the full blog on the Cadence Communit...
Jan 19, 2021
I'€™ve been reading year-end and upcoming year lists about the future trends affecting technology and electronics. Topics run the gamut from expanding technologies like 5G, AI, electric vehicles, and various realities (XR, VR, MR), to external pressures like increased gover...
Jan 14, 2021
Learn how electronic design automation (EDA) tools & silicon-proven IP enable today's most influential smart tech, including ADAS, 5G, IoT, and Cloud services. The post 5 Key Innovations that Are Making Everything Smarter appeared first on From Silicon To Software....

featured paper

Overcoming Signal Integrity Challenges of 112G Connections on PCB

Sponsored by Cadence Design Systems

One big challenge with 112G SerDes is handling signal integrity (SI) issues. By the time the signal winds its way from the transmitter on one chip to packages, across traces on PCBs, through connectors or cables, and arrives at the receiver, the signal is very distorted, making it a challenge to recover the clock and data-bits of the information being transferred. Learn how to handle SI issues and ensure that data is faithfully transmitted with a very low bit error rate (BER).

Click here to download the whitepaper

featured chalk talk

RF Interconnect for 12G-SDI Broadcast Applications

Sponsored by Mouser Electronics and Amphenol RF

Today’s 4K and emerging 8K video standards require an enormous amount of bandwidth. And, with all that bandwidth, there are new demands on our interconnects. In this episode of Chalk Talk, Amelia Dalton chats with Mike Comer and Ron Orban of Amphenol RF about the evolution of broadcast technology and the latest interconnect solutions that are required to meet these new demands.

Click here for more information about Amphenol RF Adapters & Cable Assemblies for Broadcast