Entropy Attacks
blog.cr.yp.to
blog.cr.yp.to
This excerpt was the impetus to leave my job working for a company that makes a stupidly expensive high throughput hardware Quantum TRNG.
Recent example: https://paulmillr.com/posts/deterministic-signatures/
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.
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.
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.
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.
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.).
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.
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.
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.
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.
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.
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.
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.
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.
Every OS already has a secure RNG API. That's a solved problem.
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... .
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'm struggling to come up with a situation where this would happen.
- 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.
...well, yeah.