4 ms·

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

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.

littlestymaar 7y ago
“you can't be safe from all attacks” doesn't means you should not attempt to protect yourself from the obvious ones.
- Jasper_ 7y ago
  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.
  - littlestymaar 7y ago
    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…
  - pdpi 7y ago
    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.
  - tialaramex 7y ago
    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.
    - mnw21cam 7y ago
      > 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.
      - cwzwarich 7y ago
        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.
        jlokier 7y ago
        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.
  - cesarb 7y ago
    > 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.
    - pbhjpbhj 7y ago
      CodeArtisan posted upstream, https://news.ycombinator.com/item?id=21979268 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??
      - saagarjha 7y ago
        Detecting backdoored random number generators is quite difficult.
        littlestymaar 7y ago
        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).
      - imtringued 7y ago
        >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.
  - CJefferson 7y ago
    There have been bugs in RDRAND, AMD processors would keeping returning 0 in some cases.
    - saagarjha 7y ago
      0xffffffff: https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/ https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd...
  - imtringued 7y ago
    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.
cesarb 7y ago
> 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.
feanaro 7y ago
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.
- tytso 7y ago
  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.
  - throwaway2048 7y ago
    The blocking CRNG (besides the necessary early seeding) is an entirely artificial problem however..

littlestymaar 7y ago

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

Jasper_ 7y ago
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.
- littlestymaar 7y ago
  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…
- pdpi 7y ago
  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.
- tialaramex 7y ago
  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.
  - mnw21cam 7y ago
    > 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.
    - cwzwarich 7y ago
      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.
      - jlokier 7y ago
        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.
- cesarb 7y ago
  > 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.
  - pbhjpbhj 7y ago
    CodeArtisan posted upstream, https://news.ycombinator.com/item?id=21979268 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??
    - saagarjha 7y ago
      Detecting backdoored random number generators is quite difficult.
      - littlestymaar 7y ago
        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).
    - imtringued 7y ago
      >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.
- CJefferson 7y ago
  There have been bugs in RDRAND, AMD processors would keeping returning 0 in some cases.
  - saagarjha 7y ago
    0xffffffff: https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd-microcode-bug-destroyed-my-weekend/ https://arstechnica.com/gadgets/2019/10/how-a-months-old-amd...
- imtringued 7y ago
  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.

cesarb 7y ago

> 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.

feanaro 7y ago

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.

tytso 7y ago
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.
- throwaway2048 7y ago
  The blocking CRNG (besides the necessary early seeding) is an entirely artificial problem however..