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.
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.
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?
> 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.
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.
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).
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.
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.
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.
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.).
Keeping the DRBG’s state (seed material) secure for the duration of its use is the problem. If this state is leaked, depending on the type of leak, then anything generated from that DRBG is now not protected. Even worse, you may not even know that this the case and continue to use the DRBG assuming that it is safe.
If state management is was not an issue, I’d agree with you, but the fact that vulnerabilities tend to appear in very unexpected places (side channels, speculative execution, etc.), makes this problem difficult. A sidestep is to simply have fresh entropy.
Yeah that argument seems more a marketing gimmick than makes technical sense. If the OS RNG needs fresh entropy it can reseed with fresh entropy from various sources as it does today and use fast key erasure for forward resistance. Sure there will be windows of opportunity of state compromise, but if the state can be compromised then you have deeper problems, for example they can copy the output of a TRNG source. It's just wasteful to spend a large amount of money on a problem that has a negligible chance of ever actually happening, and in reality would only potentially patch one small issue in what would be a larger shitstorm.
> If the OS RNG needs fresh entropy it can reseed with fresh entropy from various sources as it does today and use fast key erasure for forward resistance.
This assumes that the OS has access to a source of entropy that replenishes itself quickly enough for whatever the OS is using. One of the biggest complaints I’ve seen from customers selecting entropy sources is the speed of ‘built-in’ entropy sources, to the point where they will actively look for faster ones and pay quite a bit more when they do genuinely need them. The market is there.
While they could implement the fast key erasure, there is still the looming threat of future mathematic attacks on it, and if some analysis comes forward which shows a way to abuse this, then the house of cards falls down. While these attacks are a concern with any DRBG instantiation, the sidestep is, once again, fresh entropy.
If you happen to need a certification for your entropy source, fast key erasure, as described, doesn’t map cleanly to the SP 800-90 series (NIST’s RNG standards) or the AIS 20/31 (BSI’s RNG standards). Most of the time, people wanting high speed entropy are wanting it in a way that not only they trust it, but in a way where governments would too. While I think there could be a way to define the fast key erasure in terms of SP 800-90C, I don’t think there is an implementation that NIST has approved yet.
> Sure there will be windows of opportunity of state compromise, but if the state can be comprised you have bigger problems, for example they could just copy the output of a TRNG source.
This type of compromise (copying the output of TRNG) is an issue outside the scope of the DRBG’s state… Replicating, calculating, or leaking the DRBG state does not require a persistent listener after the initial compromise, would likely be undetectable to the user, and would be effective until the user gets fresh entropy.
I’ve seen from customers selecting entropy sources is the speed of ‘built-in’ entropy sources, to the point where they will actively look for faster ones and pay quite a bit more when they do genuinely need them. The market is there.
Sure and customers buy Monster cables because they've been told they sound better. I'm sure there's a market, but exactly what is this genuine need and do they really understand their own problem? Also for more than a decade now modern systems have a fast entropy source with on chip RNG such as RDRAND and this extends to the embedded context.
> I'm sure there's a market, but exactly what is this genuine need and do they really understand their own problem?
Unfortunately, my information stops at the fact that they claim to need the high-output entropy source.
> Also for more than a decade now modern systems have a fast entropy source with on chip RNG such as RDRAND and this extends to the embedded context.
On-chip RNGs are useful, yes, and are often enough for most use cases. In particular, I like Intel’s RDSEED quite a bit, but the larger (in terms of core count) the chips have gotten, the more convoluted the distribution network for the material has become. Even still, the speed of RDSEED (note, RDRAND is an automatically reseeded DRBG, whereas RDSEED is an RBG3 XOR construction (as defined in SP 800-90C) which has fresh entropy in each output) has fallen to a rate in which some vendors are looking for something faster.
Fast key erasure uses symmetric cipher. If there's a mathematical attack on that, then you just don't have any symmetric cipher, or you need to rekey faster than fast key erasure, i.e. rekey every 16 bytes of plaintext or even faster. You need a custom protocol for this, how is that certified?
> Fast key erasure uses symmetric cipher. If there's a mathematical attack on that, then you just don't have any symmetric cipher
The generation of the RNG’s output stream is the result of a symmetric cipher, yes, but an attack doesn’t need to be on the cipher as a whole. And, once again, if there is a state leakage at any point we end up with the same problem that any future output of the key stream can be undetectably replicated. Sure, you can always replace the key sooner, but that only better protects against the state leakage; the output sequence is still deterministic no matter how fast you replace it.
> You need a custom protocol for this, how is that certified?
This is where cybersecurity testing labs are useful, especially ones who can do entropy source validation. If the protocol itself can be described in terms of the standard, and fulfill its requirements, then it can be easily certified. If there is no way to map the behavior to the standard, but the behavior is secure (according to the lab), the SMEs at the lab can request guidance from the certifying body on how to deal with the situation. These requests have culminated in public guidance (e.g., the FIPS 140-3 IGs) on how to certify industry specific protocols.
My point is that you don't need an extravagant Quantum source for randomness, and you definitely don't need high throughput. It's really a solution looking for a problem.
Also, I've seen numerous people working in the Quantum space claim that metastability is a quantum effect of ring oscillators, but very doubtful and the literature around it never mentions the q-word.
Most people do not need high throughput entropy sources, sure. But the people who do pay quite a bit for that functionality.
I also haven’t seen any oft-referred literature describing metastability do so using a quantum-physics context. The metastability itself is a product of quantum behavior but has been described well enough without needing it. Depending on what you’re exploiting randomness-wise (like the metastability or the oscillation period length), the type of physical description you use to analyze the noise source changes quite a bit. For most ring oscillator work, I prefer to look at the work near the 2000’s by Ali Hajimiri, none of which is in terms of quantum anything.
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 aptly explained why I left my job, because Quantum RNG is a gimmick and doesn't solve any real problems. But to expand on that, it was heavily marketed with the idea that somehow we're living in a "entropy starved" world. We do a pretty good job of gathering entropy today from various sources such as mixing unique identifiers of hardware, CPU jitter, interrupt timing, RDRAND (which is a similar design to metastability of ring oscillators), etc. So the remark if you haven't managed to generate one secure 256-bit key then you have much bigger problems resonated heavily with me, and I realised there just isn't a need for gigabit speed TRNGs and the Quantum marketing is just scare tactics which my employer employed.
Also no crypto library or application is going to modify its entropy source to get its randomness from a TRNG device directly when it already has access to a high quality RNG via OS APIs/crypto libraries (for a good list of these check out https://randombytes.cr.yp.to/).
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
> 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.
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.
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.
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.
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.
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/
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?
> 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.
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.
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).
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.
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.
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.
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.).
> The advantage of a quantum-based entropy sources are that they are often much > faster than other hardware based entropy source.
What kind of problem is solved by a fast, hardware-based entropy source? You only need a couple of bytes of entropy to initialize your RNG.
Keeping the DRBG’s state (seed material) secure for the duration of its use is the problem. If this state is leaked, depending on the type of leak, then anything generated from that DRBG is now not protected. Even worse, you may not even know that this the case and continue to use the DRBG assuming that it is safe.
If state management is was not an issue, I’d agree with you, but the fact that vulnerabilities tend to appear in very unexpected places (side channels, speculative execution, etc.), makes this problem difficult. A sidestep is to simply have fresh entropy.
Yeah that argument seems more a marketing gimmick than makes technical sense. If the OS RNG needs fresh entropy it can reseed with fresh entropy from various sources as it does today and use fast key erasure for forward resistance. Sure there will be windows of opportunity of state compromise, but if the state can be compromised then you have deeper problems, for example they can copy the output of a TRNG source. It's just wasteful to spend a large amount of money on a problem that has a negligible chance of ever actually happening, and in reality would only potentially patch one small issue in what would be a larger shitstorm.
> If the OS RNG needs fresh entropy it can reseed with fresh entropy from various sources as it does today and use fast key erasure for forward resistance.
This assumes that the OS has access to a source of entropy that replenishes itself quickly enough for whatever the OS is using. One of the biggest complaints I’ve seen from customers selecting entropy sources is the speed of ‘built-in’ entropy sources, to the point where they will actively look for faster ones and pay quite a bit more when they do genuinely need them. The market is there.
While they could implement the fast key erasure, there is still the looming threat of future mathematic attacks on it, and if some analysis comes forward which shows a way to abuse this, then the house of cards falls down. While these attacks are a concern with any DRBG instantiation, the sidestep is, once again, fresh entropy.
If you happen to need a certification for your entropy source, fast key erasure, as described, doesn’t map cleanly to the SP 800-90 series (NIST’s RNG standards) or the AIS 20/31 (BSI’s RNG standards). Most of the time, people wanting high speed entropy are wanting it in a way that not only they trust it, but in a way where governments would too. While I think there could be a way to define the fast key erasure in terms of SP 800-90C, I don’t think there is an implementation that NIST has approved yet.
> Sure there will be windows of opportunity of state compromise, but if the state can be comprised you have bigger problems, for example they could just copy the output of a TRNG source.
This type of compromise (copying the output of TRNG) is an issue outside the scope of the DRBG’s state… Replicating, calculating, or leaking the DRBG state does not require a persistent listener after the initial compromise, would likely be undetectable to the user, and would be effective until the user gets fresh entropy.
I’ve seen from customers selecting entropy sources is the speed of ‘built-in’ entropy sources, to the point where they will actively look for faster ones and pay quite a bit more when they do genuinely need them. The market is there.
Sure and customers buy Monster cables because they've been told they sound better. I'm sure there's a market, but exactly what is this genuine need and do they really understand their own problem? Also for more than a decade now modern systems have a fast entropy source with on chip RNG such as RDRAND and this extends to the embedded context.
> I'm sure there's a market, but exactly what is this genuine need and do they really understand their own problem?
Unfortunately, my information stops at the fact that they claim to need the high-output entropy source.
> Also for more than a decade now modern systems have a fast entropy source with on chip RNG such as RDRAND and this extends to the embedded context.
On-chip RNGs are useful, yes, and are often enough for most use cases. In particular, I like Intel’s RDSEED quite a bit, but the larger (in terms of core count) the chips have gotten, the more convoluted the distribution network for the material has become. Even still, the speed of RDSEED (note, RDRAND is an automatically reseeded DRBG, whereas RDSEED is an RBG3 XOR construction (as defined in SP 800-90C) which has fresh entropy in each output) has fallen to a rate in which some vendors are looking for something faster.
Fast key erasure uses symmetric cipher. If there's a mathematical attack on that, then you just don't have any symmetric cipher, or you need to rekey faster than fast key erasure, i.e. rekey every 16 bytes of plaintext or even faster. You need a custom protocol for this, how is that certified?
> Fast key erasure uses symmetric cipher. If there's a mathematical attack on that, then you just don't have any symmetric cipher
The generation of the RNG’s output stream is the result of a symmetric cipher, yes, but an attack doesn’t need to be on the cipher as a whole. And, once again, if there is a state leakage at any point we end up with the same problem that any future output of the key stream can be undetectably replicated. Sure, you can always replace the key sooner, but that only better protects against the state leakage; the output sequence is still deterministic no matter how fast you replace it.
> You need a custom protocol for this, how is that certified?
This is where cybersecurity testing labs are useful, especially ones who can do entropy source validation. If the protocol itself can be described in terms of the standard, and fulfill its requirements, then it can be easily certified. If there is no way to map the behavior to the standard, but the behavior is secure (according to the lab), the SMEs at the lab can request guidance from the certifying body on how to deal with the situation. These requests have culminated in public guidance (e.g., the FIPS 140-3 IGs) on how to certify industry specific protocols.
My point is that you don't need an extravagant Quantum source for randomness, and you definitely don't need high throughput. It's really a solution looking for a problem.
Also, I've seen numerous people working in the Quantum space claim that metastability is a quantum effect of ring oscillators, but very doubtful and the literature around it never mentions the q-word.
Most people do not need high throughput entropy sources, sure. But the people who do pay quite a bit for that functionality.
I also haven’t seen any oft-referred literature describing metastability do so using a quantum-physics context. The metastability itself is a product of quantum behavior but has been described well enough without needing it. Depending on what you’re exploiting randomness-wise (like the metastability or the oscillation period length), the type of physical description you use to analyze the noise source changes quite a bit. For most ring oscillator work, I prefer to look at the work near the 2000’s by Ali Hajimiri, none of which is in terms of quantum anything.
> 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.
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.
hannob aptly explained why I left my job, because Quantum RNG is a gimmick and doesn't solve any real problems. But to expand on that, it was heavily marketed with the idea that somehow we're living in a "entropy starved" world. We do a pretty good job of gathering entropy today from various sources such as mixing unique identifiers of hardware, CPU jitter, interrupt timing, RDRAND (which is a similar design to metastability of ring oscillators), etc. So the remark if you haven't managed to generate one secure 256-bit key then you have much bigger problems resonated heavily with me, and I realised there just isn't a need for gigabit speed TRNGs and the Quantum marketing is just scare tactics which my employer employed.
Also no crypto library or application is going to modify its entropy source to get its randomness from a TRNG device directly when it already has access to a high quality RNG via OS APIs/crypto libraries (for a good list of these check out https://randombytes.cr.yp.to/).
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
A modern RNG would implement fast key erasure which is what Jason Donenfeld did with random device in Linux. See https://blog.cr.yp.to/20170723-random.html and https://www.zx2c4.com/projects/linux-rng-5.17-5.18/inside-li... .
> 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.
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.
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.
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.
(2014).02.05
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://web.archive.org/web/20220118154838/https://www.isg.r...
Great article, makes sense, one can reduce entropy, of course.
"If your system is compromised then you have a problem."
...well, yeah.