3 ms·

Entropy Attacks

102 points by todsacerdoti 2y ago

commandersaki 2y ago
On the other hand, there's no actual need for this huge pile of random numbers. If you've somehow managed to generate one secure 256-bit key then from that key you can derive all the "random" numbers you'll ever need for every cryptographic protocol—and you can do this derivation in a completely deterministic, auditable, testable way, as illustrated by EdDSA. (If you haven't managed to generate one secure 256-bit key then you have much bigger problems.) This excerpt was the impetus to leave my job working for a company that makes a stupidly expensive high throughput hardware Quantum TRNG.
- jrexilius 2y ago
  Forgive my ignorance on this but does his assertion that a CSPRNG is all you need after an initial truly random seed, hold up against theoretical quantum attacks? If not, then I could see the need for very large/fast sources of entropy for OTP uses and such?
  - hannob 2y ago
    > Forgive my ignorance on this but does his assertion that a CSPRNG is all you need after an initial truly random seed, hold up against theoretical quantum attacks? Yes, if you mean by "theoretical quantum attacks" the stuff we could run if we had a scalable quantum computer. Those impact public key crypto. They do nothing to impact the security of RNGs.
    - Retr0id 2y ago
      It's true that the stream-cipher and/or hash-based CSPRNG constructions that are commonly used are not broken by quantum computing. CRQCs impact more than just public key crypto though, and there's more than one way to design a CSPRNG, so it's not true in the general case that they have "no" impact on RNGs. I believe that Blum Blum Shub, Blum–Micali and Dual_EC_DRBG (backdoor aside) would also be broken by a CRQC.
      - hannob 2y ago
        Technically correct, but the RNGs you're mentioning are essentially RNGs build on public key cryptography. And I don't think they're widely used, simply because they're slow and have no advantage over faster ones (the Dual EC stuff was, as far as I know, the only thing that was somewhat widely used, and, very obviously, nobody should be using that).
    - matthewdgreen 2y ago
      Grover’s algorithm gives a square root speedup on many symmetric algorithms. This isn’t a disaster: it means you have to simply double your key (or hash digest or seed) sizes. But not every symmetric PRG out there is careful about this: some older ones may use 128 bit keys.
- zeven7 2y ago
  Could you expand on that? I understand the idea from the quote, but I don't understand why you left your job. Was it because you assessed there wasn't a need for high throughput quantum random numbers? Or because you thought it was wasteful? Or something else? The concern I would have with relying too much on a source key to derive other keys from would be if one of the keys is leaked, the others would also be exposed. I don't have an application in mind, but assume some could exist where that would be a concern. Maybe you could respond to that concern. I don't know what use cases your company would have been targeting.
  - hannob 2y ago
    His point was that he was working on a product that solves no actual problem. Quantum RNGs are gimmicks that are sold as a solution to a security problem. But they don't solve any security problem. There are real security problems with RNGs, but none of them is solved by a Quantum RNG. They usually come down to implementation errors or not using a secure RNG.
    - GTP 2y ago
      > not using a secure RNG. Wouldn't a quantum RNG solve this issue? I'm aware that there are non-quantum ways to fix this problem, but in my mind quantum is one of the possible solutions, albeit one of the most expensives.
      - hannob 2y ago
        No, a Quantum RNG does not solve the issue that people use an API for insecure random numbers when they should use one for secure random numbers. Every OS already has a secure RNG API. That's a solved problem.
    - kurikuri 2y ago
      No, they aren’t gimmicks. The advantage of a quantum-based entropy sources are that they are often much faster than other hardware based entropy source. They are called ‘quantum’ because they exploit randomness present in particle behaviors described by quantum physics (photon behavior on a beam splitter, etc.). Even ring oscillator based random number generators have quantum effects that contribute to its jitter (think shot noise, as an example), but the analysis of its randomness didn’t require quantum physics to describe it. Quantum RNGs don’t exploit some ‘quantum computing’ property and are strictly limited to a different type of noise from the usual physical noise sources (ring oscillators, phase locked loops, etc.).
- matthewdgreen 2y ago
  On the one hand this is true. Particularly the quantum stuff is mostly pointless. On the other hand, failure to incorporate fresh entropy into systems — turning them deterministic - is one of the rising crypto bug classes. The best solutions will mix the two. Recent example: https://paulmillr.com/posts/deterministic-signatures/ https://paulmillr.com/posts/deterministic-signatures/
thebeardisred 2y ago
(2014).02.05
Retr0id 2y ago
> There are also people asserting that it's important for RNGs to provide "prediction resistance" against attackers who, once upon a time, saw the entire RNG state. At this point we regularly have microarchitectural side-channels that can (with varying speed and reliability) leak kernel memory. It's easy to say "if someone can read kernel memory it's game over", but imho it's better to harden against state compromise than to not.
NoImmatureAdHom 2y ago
"If your system is compromised then you have a problem." ...well, yeah.
172327525 2y ago
I think this attack is less interesting than it sounds, given the specificity of the situation. IF you have a device which can read all the state/secrets on your machine AND the only write access it has to your machine is providing bits to use as an RNG seed, THEN (using this article) you can manipulate the output of the RNG, and exfil some data if you want. I'm struggling to come up with a situation where this would happen.
- sterlind 2y ago
  Low-level supply chain attacks. Like if the Supermicro story had panned out, or if the Intel RDRAND conspiracy theory were true, or you implanted some evil in an HSM.
moralestapia 2y ago
Great article, makes sense, one can reduce entropy, of course.
ex3ndr 2y ago
The most interesting link is broken( does anyone knows how to find source for this link: https://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf https://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf?
- _1tan 2y ago
  https://web.archive.org/web/20220118154838/https://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf https://web.archive.org/web/20220118154838/https://www.isg.r...
eigenform 2y ago
I'm not qualified to say anything about this stuff, but I get the impression this is just a tradeoff: - Collect bits from many "points" in space, but a single "point" in time - Collect bits from a single "point" in space, but many "points" in time In either case, you are not eliminating the possibility that your "random" bits are subject to external influence, you're just moving it into some different domain.

102 points by todsacerdoti 2y ago

On the other hand, there's no actual need for this huge pile of random numbers. If you've somehow managed to generate one secure 256-bit key then from that key you can derive all the "random" numbers you'll ever need for every cryptographic protocol—and you can do this derivation in a completely deterministic, auditable, testable way, as illustrated by EdDSA. (If you haven't managed to generate one secure 256-bit key then you have much bigger problems.) This excerpt was the impetus to leave my job working for a company that makes a stupidly expensive high throughput hardware Quantum TRNG.

jrexilius 2y ago
Forgive my ignorance on this but does his assertion that a CSPRNG is all you need after an initial truly random seed, hold up against theoretical quantum attacks? If not, then I could see the need for very large/fast sources of entropy for OTP uses and such?
- hannob 2y ago
  > Forgive my ignorance on this but does his assertion that a CSPRNG is all you need after an initial truly random seed, hold up against theoretical quantum attacks? Yes, if you mean by "theoretical quantum attacks" the stuff we could run if we had a scalable quantum computer. Those impact public key crypto. They do nothing to impact the security of RNGs.
  - Retr0id 2y ago
    It's true that the stream-cipher and/or hash-based CSPRNG constructions that are commonly used are not broken by quantum computing. CRQCs impact more than just public key crypto though, and there's more than one way to design a CSPRNG, so it's not true in the general case that they have "no" impact on RNGs. I believe that Blum Blum Shub, Blum–Micali and Dual_EC_DRBG (backdoor aside) would also be broken by a CRQC.
    - hannob 2y ago
      Technically correct, but the RNGs you're mentioning are essentially RNGs build on public key cryptography. And I don't think they're widely used, simply because they're slow and have no advantage over faster ones (the Dual EC stuff was, as far as I know, the only thing that was somewhat widely used, and, very obviously, nobody should be using that).
  - matthewdgreen 2y ago
    Grover’s algorithm gives a square root speedup on many symmetric algorithms. This isn’t a disaster: it means you have to simply double your key (or hash digest or seed) sizes. But not every symmetric PRG out there is careful about this: some older ones may use 128 bit keys.
zeven7 2y ago
Could you expand on that? I understand the idea from the quote, but I don't understand why you left your job. Was it because you assessed there wasn't a need for high throughput quantum random numbers? Or because you thought it was wasteful? Or something else? The concern I would have with relying too much on a source key to derive other keys from would be if one of the keys is leaked, the others would also be exposed. I don't have an application in mind, but assume some could exist where that would be a concern. Maybe you could respond to that concern. I don't know what use cases your company would have been targeting.
- hannob 2y ago
  His point was that he was working on a product that solves no actual problem. Quantum RNGs are gimmicks that are sold as a solution to a security problem. But they don't solve any security problem. There are real security problems with RNGs, but none of them is solved by a Quantum RNG. They usually come down to implementation errors or not using a secure RNG.
  - GTP 2y ago
    > not using a secure RNG. Wouldn't a quantum RNG solve this issue? I'm aware that there are non-quantum ways to fix this problem, but in my mind quantum is one of the possible solutions, albeit one of the most expensives.
    - hannob 2y ago
      No, a Quantum RNG does not solve the issue that people use an API for insecure random numbers when they should use one for secure random numbers. Every OS already has a secure RNG API. That's a solved problem.
  - kurikuri 2y ago
    No, they aren’t gimmicks. The advantage of a quantum-based entropy sources are that they are often much faster than other hardware based entropy source. They are called ‘quantum’ because they exploit randomness present in particle behaviors described by quantum physics (photon behavior on a beam splitter, etc.). Even ring oscillator based random number generators have quantum effects that contribute to its jitter (think shot noise, as an example), but the analysis of its randomness didn’t require quantum physics to describe it. Quantum RNGs don’t exploit some ‘quantum computing’ property and are strictly limited to a different type of noise from the usual physical noise sources (ring oscillators, phase locked loops, etc.).
matthewdgreen 2y ago
On the one hand this is true. Particularly the quantum stuff is mostly pointless. On the other hand, failure to incorporate fresh entropy into systems — turning them deterministic - is one of the rising crypto bug classes. The best solutions will mix the two. Recent example: https://paulmillr.com/posts/deterministic-signatures/ https://paulmillr.com/posts/deterministic-signatures/

thebeardisred 2y ago

(2014).02.05

Retr0id 2y ago

> There are also people asserting that it's important for RNGs to provide "prediction resistance" against attackers who, once upon a time, saw the entire RNG state. At this point we regularly have microarchitectural side-channels that can (with varying speed and reliability) leak kernel memory. It's easy to say "if someone can read kernel memory it's game over", but imho it's better to harden against state compromise than to not.

NoImmatureAdHom 2y ago

"If your system is compromised then you have a problem." ...well, yeah.

172327525 2y ago

I think this attack is less interesting than it sounds, given the specificity of the situation. IF you have a device which can read all the state/secrets on your machine AND the only write access it has to your machine is providing bits to use as an RNG seed, THEN (using this article) you can manipulate the output of the RNG, and exfil some data if you want. I'm struggling to come up with a situation where this would happen.

sterlind 2y ago
Low-level supply chain attacks. Like if the Supermicro story had panned out, or if the Intel RDRAND conspiracy theory were true, or you implanted some evil in an HSM.

moralestapia 2y ago

Great article, makes sense, one can reduce entropy, of course.

ex3ndr 2y ago

The most interesting link is broken( does anyone knows how to find source for this link: https://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf https://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf?

_1tan 2y ago
https://web.archive.org/web/20220118154838/https://www.isg.rhul.ac.uk/~sdg/igor-slides.pdf https://web.archive.org/web/20220118154838/https://www.isg.r...

eigenform 2y ago

I'm not qualified to say anything about this stuff, but I get the impression this is just a tradeoff: - Collect bits from many "points" in space, but a single "point" in time - Collect bits from a single "point" in space, but many "points" in time In either case, you are not eliminating the possibility that your "random" bits are subject to external influence, you're just moving it into some different domain.