8 ms·

Quantum mechanics used for better random numbers

39 points by quazar 9y ago

nabla9 9y ago
Another example of physicists selling their basic research by linking it to cryptography in a way that makes no sense. Generating quantum random numbers is not solving any real cryptographic problems. It's just marketing ploy or ignorance. DJB: Is the security of quantum cryptography guaranteed by the laws of physics? https://sidechannels.cr.yp.to/qkd/holographic-20180312.pdf https://sidechannels.cr.yp.to/qkd/holographic-20180312.pdf DJB: Security fraud in Europe's "Quantum Manifesto" https://blog.cr.yp.to/20160516-quantum.html https://blog.cr.yp.to/20160516-quantum.html Schneier: Quantum Cryptography: As Awesome As It Is Pointless https://www.schneier.com/essays/archives/2008/10/quantum%5Fcryptography.html https://www.schneier.com/essays/archives/2008/10/quantum%5Fc...
- dsacco 9y ago
  We collectively set aside one time pads for the same reason. I’m sure the NSA or GCHQ will implement this for some practical purpose eventually since they use one time pads, but this concept is madness. It’s telling that proposals for information theoretic guarantees come from individuals and institutions utterly disconnected from mainstream theoretical cryptography research. That’s what it would take to propose something like this, because the modern foundation of cryptography is explicitly computational for reasons established decades ago. Basically every reputable cryptography textbook rehashes this discussion alongside a nod to elementary complexity theory. It’s hard not to be cynical about the sincerity of research like this when there is an abundance of literature indicating that it’s conceptually untenable.
- asafira 9y ago
  Regarding the last article: it is a little vague in its argument, and I definitely have a few questions: Is it true that the encrytion algorithms still aren't the weakest link for highly sensitive classified information (e.g. in the government)? (Or in similar high-secrecy situations, not the ones that an everyday person takes part in) Also, if current methods aren't backed by rigorous mathematics, isn't that a risk in it of itself? So, while the benefit of having a more mathematically rigorous security protocol may not have practical implications, it would still be more secure, right? (Even if it isn't the top issue in most cryptography) It might not solve security's biggest issues, but I don't think it is claiming to do so, anyway. The author is also fairly harsh in general on quantum computers. Note that they have made notable strides since 2008, and much larger computers have already been built --- they haven't performed a computation that classical computers would struggle with, but they can certainly factor numbers larger than 15 (although you wouldn't use a near-term quantum computer for this, anyway, as they will not be powerful enough anytime soon to factor interestingly large numbers, anyway). At the very least, it is outdated in that respect, and at worst, it's rude and being dramatic to catch people's attention. At least, nothing that has been carefully analyzed in this respect and published.
  - dsacco 9y ago
    > Is it true that the encrytion algorithms still aren't the weakest link for highly sensitive classified information (e.g. in the government)? (Or in similar high-secrecy situations, not the ones that an everyday person takes part in) Yes. The weak link for cryptography is implementation. Implementation is insidious because it's easy to implement an existing cryptographic specification in a way that looks safe but which is completely broken. It's also an attractive exercise for people who know how to write software. In contrast, designing novel cryptography (especially public key cryptography) requires a very advanced understanding of mathematics and complexity theory before you can even get to the "seems convincing, but is actually horribly broken" stage. If you want to compromise a cryptosystem you attack the individual implementation, not the design specification that has withstood a generation of careful scrutiny by well-funded mathematicians and computer scientists. > Also, if current methods aren't backed by rigorous mathematics, isn't that a risk in it of itself? I think Schneier probably shouldn't have written his point this way; in context he's referring to provable security. Provable security is a separate, complexity theoretic study. The mathematics underlying our cryptosystems is very well understood in the sense that we generally have a mature understanding of how difficult various intractable problems are. The difficult part is mapping that intractability to specific cryptographic properties in an adversarial model, such as existential unforgeability. For example, NTRU is a well studied, currently safe cryptosystem which didn't have any provable security metrics for at least a decade after it was invented. Provable security does represent a risk, which is why it's always an active research topic. But importantly, provable security exists within a computational framework - it is not solved by proposals for quantum cryptography.
- Florin_Andrei 9y ago
  Isn't this criticism a bit too harsh? All else being equal, better randomness means better crypto.
  - dsacco 9y ago
    All else isn't equal. The better randomness that might be provided by quantum computers comes at a significant complexity cost. This is the same reason we don't use one time pads, and why modern cryptography is computational instead of information theoretic. "Quantum cryptography" is philosophically antithetical to a generation of well studied problems and research results in the field.
cornholio 9y ago
Good hardware generators are based on Johnson–Nyquist resistor noise, that is just as unpredictable, and generated by thermal circulation of charge carriers in conductors. In real life, RNG attacks are against the implementation not the noise source, even something as "predictable" as "atmospheric noise" is random enough for all practical applications.
- asafira 9y ago
  Why is it just as unpredictable? There are measurements you can make that could help you predict Johnson noise. For many quantum schemes, it's much tougher. (Not that it is easy for an attacker to make those measurements in the first place, but it doesn't seem fair to say it is rigorously just as unpredictable)
  - darkmighty 9y ago
    Nope. Johnson noise is quantum mechanical (at least in significant part). If you use a good algorithm, you can sample a partial TRNG into an epsilon-perfect TRNG (as close as you'd like). Not to mention all of this is pointless since even if the noise were classical a few applications of strong hash functions (which is the normal procedure -- they're entirely practical) require would require computers using more energy than the entire universe has available you want.
    - asafira 9y ago
      I definitely appreciate now that there are good algorithms to make your random bits more random, and hash functions can help, but regarding calling johnson noise quantum mechanical: can you give one reference of a description of finite-temperature johnson noise in which at least 1 observable necessitates a quantum mechanical treatment? (I don't think it exists, given that it is a thermal phenomenon, but maybe I'm wrong...)
  - cornholio 9y ago
    You can characterize the noise using things like temperature and material properties. But you cannot simulate the system, you cannot reproduce it, the noise itself is the result of subatomic particles interacting. Two resistors made of the exactly same material, the same cristaline structure down to every atom and heated in the same way up from 0K will generate different noise.
mbaye 9y ago
People paranoid about randomness have been duct-taping ionizing radiation sources from smoke detectors to webcams for decades now. This is non-news.
blauditore 9y ago
Is it really that relevant whether randomness is true* thanks to quantum effects rather than obfuscated-enough pseudo-random based on really hard to predict entropy sources; or is this more a PR stunt? I mean, is it realistic that someone would ever manage to predict e.g. electronic signal noise in a useful enough manner? * To nit-pick, the question whether quantum mechanics are truly random boils down to Bell's theorem, which has been experimentally supported, but still leaves some loopholes open: https://en.wikipedia.org/wiki/Loopholes_in_Bell_test_experiments https://en.wikipedia.org/wiki/Loopholes_in_Bell_test_experim...
- dsacco 9y ago
  It’s relevant in an information theoretic sense. However modern security is explicitly computational rather than information theoretic, which means it’s not relevant for modern security in any practical sense. For example one time pads are only really used (correctly and safely) by agencies like the NSA and GCHQ, and even then only for the strictest, “spare no expense” security requirements. I’d personally be appalled to see a quantum random number generator utilized in a cryotosystem. Well understood cryptographic failures like nonce reuse and side channel attacks are still routine; I can’t imagine the number of novel side channels and footgun opportunities that would be introduced with a cryptosystem utilizing this thing. The hardware, design and implementation requirements would add an enormous amount of complexity for an extremely small improvement overall.
  - asafira 9y ago
    Genuine question: why would switching out the source of random bits make for that much more complexity? The hardware is more complicated right now for sure --- do you mean to say that the work in checking the hardware doesn't have less obvious exploits (compared to simple Johnson noise measurements) is the tricky bit?
    - tptacek 9y ago
      Because hardware and hardware connectivity can fail, and the one thing cryptography needs from the system CSPRNG is not having failure cases. Since past a threshold the quality of the entropy source does not in fact matter, no amount of added complexity, however marginal, has a positive return on investment.
seanwilson 9y ago
When you're generating random numbers from a physical source, how do you detect when there's some failure in the hardware or sensors that's reducing the randomness? Can you use redundancy so the probability of this is vanishingly low?
- asafira 9y ago
  I always thought you did this by performing statistics on sample values to see if very unlikely correlations exist.
  - seanwilson 9y ago
    What I meant was happens if hardware passes such a test on release but then after months of use develops a fault?
MikkoFinell 9y ago
Anyone know a cheap DIY way to generate quantum-random numbers at home? For example, get a Geiger counter and wire it up to code that counts the milliseconds between clicks... something like that?
- BenjiWiebe 9y ago
  Wouldn't a simple noise generator using a reverse-biased diode wired to an ADC be pretty good?
- smaddox 9y ago
  Yes: use your chip's generator through your OS's random number generator (urandom on Linux). The chip's thermal-noise entropy source is fundamentally based on quantum mechanics.
- msisk6 9y ago
  https://www.fourmilab.ch/hotbits/ https://www.fourmilab.ch/hotbits/
mrcactu5 9y ago
how do we decide or quantify that certain random numbers are good or bad? if I flip a coin? maybe that's inadequate, but can we measure how much it is failing to be random?
akvadrako 9y ago
To all the people saying high quality random numbers are not important for crypto, there have been a number of important failures over the years due to semi-predictable keys. And there is no way to generate randomness in software, while quantum sources can be provably random. It just makes the crypto system easier to reason about.
- pvg 9y ago
  None of these failures have been due to a computer's inability to generate sufficiently random numbers so this particular thing is not solving any kind of practical cryptographic problem.
- dsacco 9y ago
  No one is saying high quality random numbers are not important for cryptography. We are saying true randomness is unimportant and undesirable, given the comparatively enormous complexity required to achieve it. The modern conception of cryptography is explicitly that you do not need "true" anything - randomness, security, indistinguishability, unforgeability, etc. Everything is modeled in game semantics with a computational cost:benefit analysis for attackers. Cryptographic failures with respect to entropy sources occur not because they aren't random enough, but because they're implemented incorrectly. When they're implemented correctly, they're fine, because this is a well studied problem for which we have a variety of useful solutions. This is why proposing a replacement source of entropy using quantum computers is ridiculous, because you would commensurately increase the complexity of the system into completely unknown territory. This isn't exactly a controversial perspective. I don't know of a single reputable cryptographer who takes quantum cryptography seriously. I would be happy to learn of a few, but if you look at the research landscape you'll quickly see that proposals for quantum cryptography are disconnected from the academic cryptography community.

39 points by quazar 9y ago

Another example of physicists selling their basic research by linking it to cryptography in a way that makes no sense. Generating quantum random numbers is not solving any real cryptographic problems. It's just marketing ploy or ignorance. DJB: Is the security of quantum cryptography guaranteed by the laws of physics? https://sidechannels.cr.yp.to/qkd/holographic-20180312.pdf https://sidechannels.cr.yp.to/qkd/holographic-20180312.pdf DJB: Security fraud in Europe's "Quantum Manifesto" https://blog.cr.yp.to/20160516-quantum.html https://blog.cr.yp.to/20160516-quantum.html Schneier: Quantum Cryptography: As Awesome As It Is Pointless https://www.schneier.com/essays/archives/2008/10/quantum%5Fcryptography.html https://www.schneier.com/essays/archives/2008/10/quantum%5Fc...

dsacco 9y ago
We collectively set aside one time pads for the same reason. I’m sure the NSA or GCHQ will implement this for some practical purpose eventually since they use one time pads, but this concept is madness. It’s telling that proposals for information theoretic guarantees come from individuals and institutions utterly disconnected from mainstream theoretical cryptography research. That’s what it would take to propose something like this, because the modern foundation of cryptography is explicitly computational for reasons established decades ago. Basically every reputable cryptography textbook rehashes this discussion alongside a nod to elementary complexity theory. It’s hard not to be cynical about the sincerity of research like this when there is an abundance of literature indicating that it’s conceptually untenable.
asafira 9y ago
Regarding the last article: it is a little vague in its argument, and I definitely have a few questions: Is it true that the encrytion algorithms still aren't the weakest link for highly sensitive classified information (e.g. in the government)? (Or in similar high-secrecy situations, not the ones that an everyday person takes part in) Also, if current methods aren't backed by rigorous mathematics, isn't that a risk in it of itself? So, while the benefit of having a more mathematically rigorous security protocol may not have practical implications, it would still be more secure, right? (Even if it isn't the top issue in most cryptography) It might not solve security's biggest issues, but I don't think it is claiming to do so, anyway. The author is also fairly harsh in general on quantum computers. Note that they have made notable strides since 2008, and much larger computers have already been built --- they haven't performed a computation that classical computers would struggle with, but they can certainly factor numbers larger than 15 (although you wouldn't use a near-term quantum computer for this, anyway, as they will not be powerful enough anytime soon to factor interestingly large numbers, anyway). At the very least, it is outdated in that respect, and at worst, it's rude and being dramatic to catch people's attention. At least, nothing that has been carefully analyzed in this respect and published.
- dsacco 9y ago
  > Is it true that the encrytion algorithms still aren't the weakest link for highly sensitive classified information (e.g. in the government)? (Or in similar high-secrecy situations, not the ones that an everyday person takes part in) Yes. The weak link for cryptography is implementation. Implementation is insidious because it's easy to implement an existing cryptographic specification in a way that looks safe but which is completely broken. It's also an attractive exercise for people who know how to write software. In contrast, designing novel cryptography (especially public key cryptography) requires a very advanced understanding of mathematics and complexity theory before you can even get to the "seems convincing, but is actually horribly broken" stage. If you want to compromise a cryptosystem you attack the individual implementation, not the design specification that has withstood a generation of careful scrutiny by well-funded mathematicians and computer scientists. > Also, if current methods aren't backed by rigorous mathematics, isn't that a risk in it of itself? I think Schneier probably shouldn't have written his point this way; in context he's referring to provable security. Provable security is a separate, complexity theoretic study. The mathematics underlying our cryptosystems is very well understood in the sense that we generally have a mature understanding of how difficult various intractable problems are. The difficult part is mapping that intractability to specific cryptographic properties in an adversarial model, such as existential unforgeability. For example, NTRU is a well studied, currently safe cryptosystem which didn't have any provable security metrics for at least a decade after it was invented. Provable security does represent a risk, which is why it's always an active research topic. But importantly, provable security exists within a computational framework - it is not solved by proposals for quantum cryptography.
Florin_Andrei 9y ago
Isn't this criticism a bit too harsh? All else being equal, better randomness means better crypto.
- dsacco 9y ago
  All else isn't equal. The better randomness that might be provided by quantum computers comes at a significant complexity cost. This is the same reason we don't use one time pads, and why modern cryptography is computational instead of information theoretic. "Quantum cryptography" is philosophically antithetical to a generation of well studied problems and research results in the field.

cornholio 9y ago

Good hardware generators are based on Johnson–Nyquist resistor noise, that is just as unpredictable, and generated by thermal circulation of charge carriers in conductors. In real life, RNG attacks are against the implementation not the noise source, even something as "predictable" as "atmospheric noise" is random enough for all practical applications.

asafira 9y ago
Why is it just as unpredictable? There are measurements you can make that could help you predict Johnson noise. For many quantum schemes, it's much tougher. (Not that it is easy for an attacker to make those measurements in the first place, but it doesn't seem fair to say it is rigorously just as unpredictable)
- darkmighty 9y ago
  Nope. Johnson noise is quantum mechanical (at least in significant part). If you use a good algorithm, you can sample a partial TRNG into an epsilon-perfect TRNG (as close as you'd like). Not to mention all of this is pointless since even if the noise were classical a few applications of strong hash functions (which is the normal procedure -- they're entirely practical) require would require computers using more energy than the entire universe has available you want.
  - asafira 9y ago
    I definitely appreciate now that there are good algorithms to make your random bits more random, and hash functions can help, but regarding calling johnson noise quantum mechanical: can you give one reference of a description of finite-temperature johnson noise in which at least 1 observable necessitates a quantum mechanical treatment? (I don't think it exists, given that it is a thermal phenomenon, but maybe I'm wrong...)
- cornholio 9y ago
  You can characterize the noise using things like temperature and material properties. But you cannot simulate the system, you cannot reproduce it, the noise itself is the result of subatomic particles interacting. Two resistors made of the exactly same material, the same cristaline structure down to every atom and heated in the same way up from 0K will generate different noise.

mbaye 9y ago

People paranoid about randomness have been duct-taping ionizing radiation sources from smoke detectors to webcams for decades now. This is non-news.

blauditore 9y ago

Is it really that relevant whether randomness is true* thanks to quantum effects rather than obfuscated-enough pseudo-random based on really hard to predict entropy sources; or is this more a PR stunt? I mean, is it realistic that someone would ever manage to predict e.g. electronic signal noise in a useful enough manner? * To nit-pick, the question whether quantum mechanics are truly random boils down to Bell's theorem, which has been experimentally supported, but still leaves some loopholes open: https://en.wikipedia.org/wiki/Loopholes_in_Bell_test_experiments https://en.wikipedia.org/wiki/Loopholes_in_Bell_test_experim...

dsacco 9y ago
It’s relevant in an information theoretic sense. However modern security is explicitly computational rather than information theoretic, which means it’s not relevant for modern security in any practical sense. For example one time pads are only really used (correctly and safely) by agencies like the NSA and GCHQ, and even then only for the strictest, “spare no expense” security requirements. I’d personally be appalled to see a quantum random number generator utilized in a cryotosystem. Well understood cryptographic failures like nonce reuse and side channel attacks are still routine; I can’t imagine the number of novel side channels and footgun opportunities that would be introduced with a cryptosystem utilizing this thing. The hardware, design and implementation requirements would add an enormous amount of complexity for an extremely small improvement overall.
- asafira 9y ago
  Genuine question: why would switching out the source of random bits make for that much more complexity? The hardware is more complicated right now for sure --- do you mean to say that the work in checking the hardware doesn't have less obvious exploits (compared to simple Johnson noise measurements) is the tricky bit?
  - tptacek 9y ago
    Because hardware and hardware connectivity can fail, and the one thing cryptography needs from the system CSPRNG is not having failure cases. Since past a threshold the quality of the entropy source does not in fact matter, no amount of added complexity, however marginal, has a positive return on investment.

seanwilson 9y ago

When you're generating random numbers from a physical source, how do you detect when there's some failure in the hardware or sensors that's reducing the randomness? Can you use redundancy so the probability of this is vanishingly low?

asafira 9y ago
I always thought you did this by performing statistics on sample values to see if very unlikely correlations exist.
- seanwilson 9y ago
  What I meant was happens if hardware passes such a test on release but then after months of use develops a fault?

MikkoFinell 9y ago

Anyone know a cheap DIY way to generate quantum-random numbers at home? For example, get a Geiger counter and wire it up to code that counts the milliseconds between clicks... something like that?

BenjiWiebe 9y ago
Wouldn't a simple noise generator using a reverse-biased diode wired to an ADC be pretty good?
smaddox 9y ago
Yes: use your chip's generator through your OS's random number generator (urandom on Linux). The chip's thermal-noise entropy source is fundamentally based on quantum mechanics.
msisk6 9y ago
https://www.fourmilab.ch/hotbits/ https://www.fourmilab.ch/hotbits/

mrcactu5 9y ago

how do we decide or quantify that certain random numbers are good or bad? if I flip a coin? maybe that's inadequate, but can we measure how much it is failing to be random?

akvadrako 9y ago

To all the people saying high quality random numbers are not important for crypto, there have been a number of important failures over the years due to semi-predictable keys. And there is no way to generate randomness in software, while quantum sources can be provably random. It just makes the crypto system easier to reason about.

pvg 9y ago
None of these failures have been due to a computer's inability to generate sufficiently random numbers so this particular thing is not solving any kind of practical cryptographic problem.
dsacco 9y ago
No one is saying high quality random numbers are not important for cryptography. We are saying true randomness is unimportant and undesirable, given the comparatively enormous complexity required to achieve it. The modern conception of cryptography is explicitly that you do not need "true" anything - randomness, security, indistinguishability, unforgeability, etc. Everything is modeled in game semantics with a computational cost:benefit analysis for attackers. Cryptographic failures with respect to entropy sources occur not because they aren't random enough, but because they're implemented incorrectly. When they're implemented correctly, they're fine, because this is a well studied problem for which we have a variety of useful solutions. This is why proposing a replacement source of entropy using quantum computers is ridiculous, because you would commensurately increase the complexity of the system into completely unknown territory. This isn't exactly a controversial perspective. I don't know of a single reputable cryptographer who takes quantum cryptography seriously. I would be happy to learn of a few, but if you look at the research landscape you'll quickly see that proposals for quantum cryptography are disconnected from the academic cryptography community.