Comment by walterbell | Hacker News Reader

Comment by walterbell | Hacker News Reader

On the subject of TRNG, John Denker wrote a 2005 paper for using soundcard data as a source of randomness, http://www.av8n.com/turbid/

> We discuss how to configure and use turbid, which is a Hardware Random Number Generator (HRNG), also called a True Random Generator (TRNG). It is suitable for a wide range of applications, from the simplest benign applications to the most demanding high-stakes adversarial applications, including cryptography and gaming. It relies on a combination of physical process and cryptological algorithms, rather than either of those separately. It harvests randomness from physical processes, and uses that randomness efficiently. The hash saturation principle is used to distill the data, so that the output is virtually 100% random for all practical purposes. This is calculated based on physical properties of the inputs, not merely estimated by looking at the statistics of the outputs. In contrast to a Pseudo-Random Generator, it has no internal state to worry about. In particular, we describe a low-cost high-performance implementation, using the computer’s audio I/O system.

On randomness, http://www.av8n.com/turbid/paper/turbid.htm#sec-raw-randomne...

> Understanding turbid requires some interdisciplinary skills. It requires physics, analog electronics, and cryptography.

This is one of these approaches that are for all practical purposes completely useless.

There's basically only three problems generating good randomness: 1. Very early during boot you don't have a lot of good sources. 2. On very constrained devices you have limited external input. 3. Bugs in the implementation.

Randomness from soundcards doesn't help with any of these. They probably aren't yet initialized at the point in time where it matters most, they don't exist for the most problematic devices and bugs are bugs, no matter what your source of randomness.

> Randomness from soundcards doesn't help with any of these.

"Randomness from soundcards" is also spectacularly unlikely to help on the cloud. Pretty sure they don't fit SoundBlaster16s to EC2 instances or Digital Ocean Droplets...

Given that these instances are typically virtualized I wouldn't be surprised if you could extract a decent amount of entropy just by using the system timings (interrupts, RTC sampling etc...) given that they would be affected by the other running systems. And of course there's always the network card.

In my experience it's not usually super difficult to get a decent amount of entropy on complex desktop or servers, it's only a real issue on simple embedded hardware where you might have no way to sample the environment and all the timings are ultra-deterministic. In this case I've resorted to using temperature measurements and fan speed as a source of entropy during early boot, which isn't ideal.

It would seem quite helpful if these virtual machines provided a virtual device that gives random numbers provided by the host device.

> given that they would be affected by the other running systems

Philosophically, does that make it more or less random? The whole category of side-channels suggests that there are problems with sharing a system like this.

There's also the philosophical question of how cryptographically secure a fully virtual system can be when the host has full inspection and control capability. If you're running in the cloud you need to think carefully about how to delegate this to the platform if at all possible.

I want a cloud version of Dr. Sbaitso!

It could potentially help with 1 if you have some early bootstrap code to configure the sound card and get some samples. I agree with your general point however.

I probably don’t know enough about computers, but wouldn’t there be a way to use e.g. the digital outputs of a DAC directly even in the earliest part of boot? Is there a good reason why CPUs aren’t doing this already?

Well, if you have one, and if the thing it's listening to is sufficiently random - both of which are in question here.

This is sort of the problem the CPU random number generator is intended to solve, but see the discussion on trust.

Reminds me of Cloudflares wall of lava lamps[1], discussed here: https://news.ycombinator.com/item?id=16041295

[1] https://www.cloudflare.com/learning/ssl/lava-lamp-encryption...

How long does the lava lamp system take to start from a cold boot?

About half an hour to get a solid glob going for mine, too long and you tend to end up with a large bias towards the top. I looked into this because I wanted to pre warm my lava lamp because it’s depressing to wake up to cold blobs.

CPUs already have a physics-based random number generator.

https://en.wikipedia.org/wiki/RDRAND

Which has concerns that it may be backdoored by intelligence agencies: https://github.com/torvalds/linux/blob/6398b9fc818eea79dcd6e...

I'm a lot less worried about an NSA backdoor than I am that Intel (or mediatek, or whatever cheap ARM license is in my router) just fucked up the implementation

First generation AMD Zen CPUs returned all 1s for RDRAND instructions for instance

https://dilbert.com/strip/2001-10-25

What's stopping the NSA from inserting a backdoor to recognize it's running kernel randomness code and change the results too? If you don't trust your CPU, you can't trust anything it does. Expecting the backdoor to show up in one solely instruction is hopelessly naive.

“you can't be safe from all attacks” doesn't means you should not attempt to protect yourself from the obvious ones.

If you expect RDRAND to change its behavior to be nefarious, also expect ADD and MUL to do the same. The RDRAND conspiracy theory is bizarre because underneath lies a core belief that a malicious entity would go so far as to insert a backdoor, but put it strictly in a simple and easily avoidable place? So they're malicious entities, but can only touch certain instructions?

Malicious entities don't play by made up rules. RDRAND being a convenient scapegoat seems like exactly the thing they'd want, too.

I don't get your point. Should we assume there is no backdoor at all just because we can't predict all kind of backdoors that can be?

Being defensive against RDRAND is just one (relatively easy) way to defend oneself against a (relatively easy to implement) backdoor. Yes, this defense isn't perfect, because there can be other (more difficult to escape) backdoors, but that's not a compelling reason not to avoid the “easy” ones…

There's a reasonable argument to be made that limiting the backdoor to very specific instructions that specifically target the domains you care about makes it less likely that your backdoor will be triggered by accident. Escaping detection is just as important here.

The concern for RDRAND was really that it might be used to exfiltrate data.

Imagine a parallel universe where everybody happily just uses RDRAND to get random numbers. For example when you connect to an HTTPS server, as part of the TLS protcol it sends you a whole bunch of random bytes (these are crucial to making TLS work, similar approaches happen in other modern protocols). But in that universe those bytes came directly from RDRAND, after all it's random...

Except, if RDRAND is actually an exfiltration route, what you've just done is carve a big hole in your security perimeter to let RDRAND's owners export whatever they want.

XORing RDRAND into an apparently random bitstream is thus safe because the bitstream is now random if either RDRAND works as intended OR your apparently random bitstream is indeed random.

> XORing RDRAND into an apparently random bitstream is thus safe because the bitstream is now random if either RDRAND works as intended OR your apparently random bitstream is indeed random.

That's making assumptions. For instance, it wouldn't be beyond the realms of possibility for the compromised CPU to also track which registers contain a result produced from RDRAND, and make (X XOR RDRAND) produce a predictable result. After all, RDRAND is already an undefined number, so the system can legitimately decide later what it would like it to be. Yes, it would require more silicon in the registers, re-ordering and dispatch system, and ALU, but it would be feasible.

A change that large (probably requiring new custom RAMs and modifications to fairly timing-constrained register renaming logic) doesn't seem feasible for somebody to insert below the RTL level without being noticed. It would be much easier to just make RDRAND somehow less random, while still passing whatever randomness test is used for qualification.

I don't see how the RDRAND change would be gotten away with either, if someone else is looking at the silicon design.

To modify RDRAND so that it is less random in a way that's useful for an attacker, yet passes statistical randomness testing by the OS and other software, would require RDRAND to implement something cryptographic, so that only the attacker, knowing a secret, can "undo" the not-really-randomness.

A new crypto block would surely be very noticable at the RTL level.

Another comment[1] gave a link to an existing implementation of such backdoor using only doping. It doesn't implement a cryptographic scheme but weakens the randomness in a way that still pass NIST test suite.

[1]: https://news.ycombinator.com/item?id=21979268

Wouldn't require different RAM, and wouldn't really require any different register renaming logic. It would however require an extra bit on each register to flag the value as originating from RDRAND, and a different ALU that uses that flag and changes the outcome for certain operations.

Obviously, if you store the result of RDRAND to main RAM and read it back in later, this would defeat the system as the flag wouldn't be preserved. But I'm guessing most code won't do that for performance reasons.

The simpler option of just making RDRAND predictable is less powerful, because then the operating system can compensate with randomness obtained from elsewhere. The attack above allows the CPU to actually compromise the operating system's own randomness source.

> If you expect RDRAND to change its behavior to be nefarious, also expect ADD and MUL to do the same.

There's a very important difference: ADD and MUL are deterministic, while the output of RDRAND is random. If ADD or MUL or FDIV return incorrect results, that can be detected (as the Pentium has shown). If RDRAND returns backdoored values, it cannot be detected by only looking at its output; you have to check the circuit.

CodeArtisan posted upstream, https://news.ycombinator.com/item?id=21979268, about a method of doping that effectively makes a side-channel (crazy!).

Surely you can check the output and see if it's random? Don't these attacks rely on perturbing the RNG do it's no longer a TRNG, isn't output the only way to tell??

Detecting backdoored random number generators is quite difficult.

Or even impossible: if the not-so-random value comes from an AES stream (or any encryption method actually), it's impossible to prove as long as AES is not broken (proving that an AES stream can be distinguished from random is a sufficient definition of “broken” in the crypto community).

>Surely you can check the output and see if it's random?

No you can't. That's an inherent property of randomness. If you're lucky you can win the lottery 10 times in a row. The only thing you can verify is that the random number generator is not obviously broken (see AMD's RDRAND bug) but you can't verify that it's truly random.

> isn't output the only way to tell??

Looking at the implementation is the only way to tell.

Let's say I generate a list of one million random numbers through a trustworthy source. Now I build a random number generator that does nothing but just return numbers from the list.

There is an impractical way of verifying a random number generator that is only useful in theory. Remember how you can flip a coin and take 1000 samples and you get roughly 1/2 probability for each side? The number of samples you have to take grows with the number of outcomes. If your RNG returns a 64 bit number you can take 2^64*x samples where x is a very large number (the larger the better). x = 1 is already impractical (50 years @ 3 billion RDRAND/s) but to be really sure you would probably need x > 10000. Nobody on earth has that much time. Especially not CPU manufacturers that release new chips every year.

> but you can't verify that it's truly random.

Even if you cannot be 100% sure that something is not really random, there are plenty of statistical measurements that can be used to assess the quality of the output (in terms of entropy).

> Let's say I generate a list of one million random numbers through a trustworthy source. Now I build a random number generator that does nothing but just return numbers from the list.

In less than a second your generator would be stalled which is a pretty obvious flaw to see.

The real issue is cryptographic algorithms because they are designed to simulate randomness, and they are adversarially improving when statistic methods of studies become more powerful. At every single point in time, state of the art cryptography is going to be able to produce fake random that the current state of the art cryptanalysis cannot prove as not random.

> At every single point in time, state of the art cryptography is going to be able to produce fake random that the current state of the art cryptanalysis cannot prove as not random.

That may not be true. (As in, I'm not sure it is.)

For many useful crypto algorithms where we give a nominal security measure (in bits), there is a theoretical attack that requires several fewer bits but is still infeasible.

For example, we might say a crypto block takes a 128-bit key and needs an order of magnitude 2^128 attempts to brute force the key.

The crypto block remains useful when academic papers reveal how they could crake it in about 2^123 attempts.

The difference between 2^128 and 2^123 is irrelevant in practice as long as we can't approach that many calculations. But it does represent a significant bias away from "looks random if you don't know the key".

It seems plausible to me that a difference like that would manifest in statistical analysis that state of the art cryptanalysis could prove as not random by practical means, while still unable to crack (as in obtain inputs) by practical means.

That makes sense. I stand corrected.

There have been bugs in RDRAND, AMD processors would keeping returning 0 in some cases.

0xffffffff: https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd...

Because obtaining a seed is the only non deterministic part of a RNG. Once you have the seed you can trivially predict the next numbers. Since random numbers are used to generate encryption keys, being able to manipulate random numbers also allows you to defeat encryption. The way the RDRAND backdoor would work is pretty simple. When it is activated (system wide) it simply needs to return numbers based on a deterministic RNG (with a seed known to the owners of the backdoor). To an observer it would still work as intended and there is no way to prove that there is a backdoor.

Verifying an ADD instruction is very easy and if it were to return wrong results then it would be obvious that it is buggy. Programs would cease to work. Alternatively it would have to be incredibly smart and detect the currently executed program and exfiltrate the encryption key during the execution of the encryption function.

The first backdoor scales to millions of potential targets. The second is a carefully targeted attack against a known enemy. Targeted attacks have cheaper alternatives than silicon back doors.

> What's stopping the NSA from inserting a backdoor to recognize it's running kernel randomness code and change the results too?

It's much much harder. They'd have to insert something on the frontend (where the instruction decoder is) or on the L1 instruction cache to recognize when it's running that specific piece of code; both parts are very critical for the processor performance, so every gate of delay counts. And that's before considering that the Linux kernel code changes unpredictably depending on the compiler, kernel configuration options, and kernel release. Oh, and you have to be very precise in detecting that code, to make sure nothing else misbehaves or even gets slower (some people count cycles on parts of their code, so an unexpected slowness would get noticed).

Contrast with RDRAND, an instruction which is defined to return an unpredictable value; it would be simple to make its output depend on a counter mixed with a serial number and a couple of bits of real randomness, instead of being fully random. It's not even on the performance-critical part of the chip; it's isolated on its own block, so adding a backdoor to it would cause no performance problems, and would break no other software.

Why does anyone even continue to bother arguing this?

There are ways of mixing RDRAND into the entropy pool safely and this can be done easily. Why would you deliberately choose to not mix RDRAND and use it directly instead? You wouldn't. It makes no sense. Therefore, RDRAND should be mixed into the pool, it is being mixed into the pool and there is no more reason to debate this.

Yes, and Linux has done it for years. The problem is whether or not RDRAND should be trusted in the absence of sufficient estimated entropy that it should be used to unblock the CRNG during the boot process. This is what CONFIG_RANDOM_TRUST_CPU or the random.trust_cpu=on on the boot command is all about. Should RDRAND be trusted in isolation? And I'm not going to answer that for you; a cypherpunk and someone working at the NSA might have different answers to that question. And it's fundamentally a social, not a technical question.

The blocking CRNG (besides the necessary early seeding) is an entirely artificial problem however..

An implementation that is not good by itself. Not least because on some AMD cpus the CPU takes the XKCD approach [1] [2].

[1] https://www.xkcd.com/221/ [2] https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd...

https://sharps.org/wp-content/uploads/BECKER-CHES.pdf

This paper demonstrates that by adding a small amount of dopant[1] to the RDRAND circuitry, you can weaken it enough while it still pass NIST suite. And the modification is undetectable.

In this paper we introduced a new type of sub-transistor level hardware Trojan that only requires modification of the dopant masks. No additional transistors or gates are added and no other layout mask needs to be modified. Since only changes to the metal, polysilicion or active area can be reliably detected with optical inspection, our dopant Trojans are immune to optical inspection, one of the most important Trojan detection mechanism. Also, without the ability to use optical inspection to distinguish Trojan-free from Trojan designs, it is very difficult to find a chip that can serve as a golden chip, which is needed by most post-manufacturing Trojan detection mechanisms. To demonstrate the feasibility of these Trojans in a real world scenario and to show that they can also defeat functional testing, we presented two case studies. The first case study targeted a design based on Intel’s secure RNG design. The Trojan enabled the owner of the Trojan to break any key generated by this RNG. Nevertheless, the Trojan passes the functional testing procedure recommended by Intel for its RNG design as well as the NIST random number test suite.This shows that the dopant Trojan can be used to compromise the security of a meaningful real-world target while avoiding detection by functional testing as well as Trojan detection mechanisms. To demonstrate the versatility of dopant Trojans, we also showed how they can be used to establish a hidden side-channel in an otherwise side-channel resistant design. The introduced Trojan does not change the logic value of any gate, but instead changes only the power profile of two gates. An evaluator who is not aware of the Trojan cannot attack the Trojan design using common side-channel attacks. The owner of the Trojan however can use his knowledge of the Trojan power model to establish a hidden side-channel that reliably leaks out secret keys.

[1] https://en.wikipedia.org/wiki/Doping_(semiconductor)

Amazing!

Reply on news.ycombinator.com