Re: Randomness, Quantum Mechanics - and Cryptography
On Sep 6, 2010, at 10:49 PM, John Denker wrote: If you think about the use of randomness in cryptography, what matters isn't really randomness - it's exactly unpredictability. Agreed. This is a very tough to pin down: What's unpredictable to me may be predictable to you, It's easy to pin down. If it's unpredictable to the attacker, it's unpredictable enough for all practical purposes. I was talking about mathematical, even philosophical, underpinnings - not practical purposes. In any case, even if you are concerned with practice, the statement that something is unpredictable to the attacker sounds suspect. After all, most junk cryptographic arguments claim that some algorithm is not reversible by the attacker. One should really expect more. and unpredictability collapses as soon as the random value is known (measured?). QM unpredictability as described by Conway seems much closer to the kind of thing you really need to get crypto results. You're working too hard. QM is interesting, but it is overkill for cryptography. Plain old classical thermodynamical randomness is plenty random enough. But there isn't actually such a thing as classical thermodynamical randomness! Classical physics is fully deterministic. Thermodynamics uses a probabilistic model as a way to deal with situations where the necessary information is just too difficult to gather. Classically, you could in principle measure the positions and momenta of all the atoms in a cubic liter of air, and then produce completely detailed analyses of the future behavior of the system. There would be no random component at all. In practice, even classically, you can't hope to get even a fraction of the necessary information - so you instead look at aggregate properties and, voila, thermodynamics. There's no randomness assumption - much less an unpredictability assumption - for the micro-level quantities. What you need is some uniformity assumptions. If I had access to the full micro details of that liter of air, your calculations of the macro quantities would be completely undisturbed. FWIW, quantum noise is just the limiting case of thermal noise in the limit of high frequency and/or low temperature. There is no dividing line between the two, by which I mean that the full range of intermediate cases exists, and the same equation describes both asymptotes and everything in between. A graph of noise versus temperature for a simple circuit can be found at http://www.av8n.com/physics/thermo/partition-function.html#fig-qho If anybody can think of a practical attack against the randomness of a thermal noise source, please let us know. By practical I mean to exclude attacks that use such stupendous resources that it would be far easier to attack other elements of the system. As a matter of practical engineering, I agree with you. But read what you said over again, and distinguish it from typical snake-oil arguments for novel crypto algorithms. The differences that make your claims believable while those of the snake-oil salesmen are not are subtle and illuminating. But, as the long argument on this subject today has shown, that's still not the end of the story. Just as the snake-oil systems typically fail because their security claims require constraints on the attacker (which real attackers will get around), your claims assume constraints as well. Lowering the temperature and injecting RF. Hmm, hadn't thought of that as an attack technique -- Jerry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On Tue, 7 Sep 2010 22:22:57 -0400 Jerry Leichter leich...@lrw.com wrote: On Sep 6, 2010, at 10:49 PM, John Denker wrote: It's easy to pin down. If it's unpredictable to the attacker, it's unpredictable enough for all practical purposes. I was talking about mathematical, even philosophical, underpinnings - not practical purposes. In any case, even if you are concerned with practice, the statement that something is unpredictable to the attacker sounds suspect. After all, most junk cryptographic arguments claim that some algorithm is not reversible by the attacker. One should really expect more. Actually, I've seen a significant number of proofs in the crypto world that amount to show that the attacker cannot distinguish these bits from a set of random bits with probability better than uninformed guessing. It appears to be reasonable to think that if the attacker cannot distinguish a stream from a true random stream, or cannot predict the next bit with better probability than chance, the attacker has no handle on which to base an attack. I would invite people who are more versed on this topic to chime in. Perry - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On Tue, Sep 07, 2010 at 10:22:57PM -0400, Jerry Leichter wrote: But there isn't actually such a thing as classical thermodynamical randomness! Classical physics is fully deterministic. Thermodynamics uses a probabilistic model as a way to deal with situations where the necessary information is just too difficult to gather. Classically, you could in principle measure the positions and momenta of all the atoms in a cubic liter of air, and then produce completely detailed analyses of the future behavior of the system. There would be no random component at all. In practice, even classically, you can't hope to get even a fraction of the necessary information - so you instead look at aggregate properties and, voila, thermodynamics. There's no randomness assumption - much less an unpredictability assumption - for the micro-level quantities. What you need is some uniformity assumptions. If I had access to the full micro details of that liter of air, your calculations of the macro quantities would be completely undisturbed. This glosses over the *fundamental* complexity of non-linear classical dynamics. It is a leap to claim that the underlying determinism of a classical dynamical system leads one to conclude that it is even in principle predictable, in the presence of chaos. We should not short-change classical chaos which is an emergent property of complex deterministic systems. http://www-chaos.umd.edu/research.html ... Riddled Basins The notion of determinism in classical dynamics has eroded since Poincar??'s work led to recognition that dynamical systems can exhibit chaos: small perturbations grow exponentially fast. Hence, physically ubiquitous measurement errors, noise, and computer roundoff strongly limit the time over which, given an initial condition, one can predict the detailed state of a chaotic system. Practically speaking, such systems are nondeterministic. Notwithstanding the quantitative uncertainty caused by perturbations, the system state is confined in phase space (on an attractor) so at least its qualitative behavior is predictable. Another challenge to determinism arises when systems have competing attractors. With a boundary (possibly geometrically convoluted ) between sets of initial conditions tending to distinct attractors (basins of attraction), perturbations make it difficult to determine the fate of initial conditions near the boundary. Recently, mathematical mappings were found that are still worse: an attractor's entire basin is riddled with holes on arbitrarily fine scales. Here, perturbations globally render even qualitative outcomes uncertain; experiments lose reproducibility. J.C. Sommerer and E. Ott, A Qualitatively Nondeterministic Physical System, Nature, 365, 135 (1993). -- Viktor. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On 09/06/2010 09:49 PM, John Denker wrote: If anybody can think of a practical attack against the randomness of a thermal noise source, please let us know. By practical I mean to exclude attacks that use such stupendous resources that it would be far easier to attack other elements of the system. Blast it with RF for one. Typically the natural thermal noise amounts to just a few millivolts, and so requires a relatively sensitive A/D converter. This makes it susceptible to injected unnatural noise overloading the conversion and changing most of the output bits to predictable values. Using digital outputs from an enclosed module with enough shielding could probably prevent it. But there are plenty of environments which are too small (e.g., smart cards) or are potentially in the hands of the attacker for an extended period of time (smart cards, DRM devices, power meters, etc.). - Marsh - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On 09/07/2010 10:21 AM, Marsh Ray wrote: If anybody can think of a practical attack against the randomness of a thermal noise source, please let us know. By practical I mean to exclude attacks that use such stupendous resources that it would be far easier to attack other elements of the system. Blast it with RF for one. 1) This is not an argument in favor of quantum noise over thermal noise, because the same attack would be at least as effective against quantum noise. 2) You can shield things so as to make this attack very, very difficult. 3) The attack is detectable long before it is effective, whereupon you can shut down the RNG, so it is at best a DoS attack. And then you have to compare it against other brute-force DoS attacks, such as shooting the computer with an AK-47. Typically the natural thermal noise amounts to just a few millivolts, and so requires a relatively sensitive A/D converter. This makes it susceptible to injected unnatural noise overloading the conversion and changing most of the output bits to predictable values. Even the cheapest of consumer-grade converters has 16 bits of resolution, which is enough to resolve the thermal noise and still have _two or three orders of magnitude_ of headroom. If you are really worried about this, studio-grade stuff is still quite affordable, and has even more headroom and better shielding. How much RF are we talking about here? At some point you can undoubtedly DoS the RNG ... but I suspect the same amount of RF would fry most of the computers, phones, and ipods in the room. Is the RF attack in any way preferable to the AK-47 attack? - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On 09/07/2010 11:19 AM, Perry E. Metzger wrote: 2) You can shield things so as to make this attack very, very difficult. I suspect that for some apps like smart cards that might be hard. OTOH, it might be straightforward to detect the attempt. We should take the belt-and-suspenders approach: a) Do some reasonable amount of shielding, and b) detect the attack. Detecting the attack is utterly straightforward. The primary defense is to close the loop around the noise-generating element. That is, we inject a known calibration signal on top of the noise ... and use that to constantly check that the input channel gain and bandwidth are correct. The true noise level depends only on gain, bandwidth, temperature, and resistance. Blasting the system with RF will not lower the temperature, so that's not a threat. So unless you have a scenario where the RF lowers the resistance, lowers the gain, and/or lowers the bandwidth _in a way that the calibrator cannot detect_ then this attack does not rise above the level of a brute-force DoS attack, in the same category as the AK-47 attack or the stomp-the-smart-card-to-dust attack. The calibrator idea relies on the fact that the computer's i/o system has an o as well as an i. Note that this defense is equally effective against both *) Continuing attacks, where a continuing RF blast drives the first stage amplifier into saturation, without necessarily doing irreversible damage, and *) One-shot attacks, where a super-large blast does irreversible damage to the amplifier. Secondary defenses, if you want to go to the trouble, include putting a canary in the coal mine, i.e. implementing a second sensor with a different gain, bandwidth, and resistance. I reckon that attacking one sensor and getting away with it is only possible on a set of measure zero, but the chance of attacking two non-identical sensors without either one of them noticing is a set of measure zero squared. - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On 09/07/2010 12:58 PM, John Denker wrote: On 09/07/2010 10:21 AM, Marsh Ray wrote: If anybody can think of a practical attack against the randomness of a thermal noise source, please let us know. By practical I mean to exclude attacks that use such stupendous resources that it would be far easier to attack other elements of the system. Blast it with RF for one. 1) This is not an argument in favor of quantum noise over thermal noise, because the same attack would be at least as effective against quantum noise. Agreed. 2) You can shield things so as to make this attack very, very difficult. The point is that this it's a generic, relatively low-tech attack that is likely to be effective against a straightforward implementation of the general idea. 3) The attack is detectable long before it is effective, whereupon you can shut down the RNG, so it is at best a DoS attack. Only if the engineers know about it and spend the resources to build in such resistances to it. So the system which consumes the entropy also as to look for the I'm not producing any more entropy signal as well. The proper operation of this signaling has to part of the test process. So now there needs to be a way to simulate the attack scenario for testing. Presumably this becomes another input to the system which itself must be test. All this adds time, cost, and complexity and it's not surprising that they don't always get it perfect. There is some evidence that engineers designing chips that go into actual products (little stuff like girls' toys and smart grid power meters) aren't familiar with this: http://www.flickr.com/photos/travisgoodspeed/4142689541/ This graph shows the counts of individual seed bytes in a poor random number generator. The sample width is a single integer, and the RNG byte is expected to be one of the very few spikes presented on this graph. Note that the above description is a little confusing because there are multiple problems going on here. The seed bytes are coming from a poorly engineered radio source and are also going into a poor random number generator. Here's a better description: http://rdist.root.org/2010/01/11/smart-meter-crypto-flaw-worse-than-thought/ And then you have to compare it against other brute-force DoS attacks, such as shooting the computer with an AK-47. Well, the idea of physical stress attacks is that you get the system to do something it isn't supposed to do (e.g., sign with a weak nonce). Typically the natural thermal noise amounts to just a few millivolts, and so requires a relatively sensitive A/D converter. This makes it susceptible to injected unnatural noise overloading the conversion and changing most of the output bits to predictable values. Even the cheapest of consumer-grade converters has 16 bits of resolution, which is enough to resolve the thermal noise and still have _two or three orders of magnitude_ of headroom. Were they engineered for use with crypto to resist attack? Were they tested in an actively hostile RF environment? It's really unwise to try to reason about the behavior of complex systems like digitial circuitry when operated outside of its absolute maximum specifications. You'd have to re-qualify them for such use. If you are really worried about this, studio-grade stuff is still quite affordable, and has even more headroom and better shielding. And it will not get built into any product if it costs $0.01 more unless the hardware engineer is unable to justify the additional expense. How much RF are we talking about here? Probably very little if the engineer didn't take special precautions. Also the attacker gets to choose the frequency and direction from which the device is most susceptible and combine this will all other techniques simultaneously. For example, perhaps would run current through the external shielding or expose it to a static magnetic field (thus heating it or saturating its magnetic permeability). At some point you can undoubtedly DoS the RNG ... but I suspect the same amount of RF would fry most of the computers, phones, and ipods in the room. So the attacker leaves his ipod out of the faraday cage in which he's abusing the smart card or DRM device. Is the RF attack in any way preferable to the AK-47 attack? The attacker doesn't necessarily have to completely eliminate all entropy from the output, just enough that he can make up the difference with brute force or analytic techniques. http://focus.ti.com/docs/prod/folders/print/cc2531.html Changes from Revision Original (September 2009) to Revision A Removed sentence that pseudorandom data can be used for security. - Marsh - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On Tue, 07 Sep 2010 11:56:25 -0700 John Denker j...@av8n.com wrote: The true noise level depends only on gain, bandwidth, temperature, and resistance. Blasting the system with RF will not lower the temperature, so that's not a threat. One could, however, run the card one is trying to attack under reduced temperature and hit it with RF at the same time. The question is, can you make it more expensive to do that than to, say, buy a new parking card or whatever else the smart card is being used for. If the attack is fairly cheap and repeatable and yields something reasonably valuable, you have a problem. If you can make the attack expensive and only yield something cheap, you're doing well. So unless you have a scenario where the RF lowers the resistance, lowers the gain, and/or lowers the bandwidth _in a way that the calibrator cannot detect_ Don't assume, though, that the attacker can't lower the temperature in most of the circuit, keep the tiny thermometer you included at room temperature, and inject RF at the same time. Don't even assume they will need to rip the device apart to do it. The only question is, can you make it expensive enough to succeed to protect what you're trying to protect. Perry -- Perry E. Metzgerpe...@piermont.com - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness, Quantum Mechanics - and Cryptography
On 09/07/2010 02:18 PM, Perry E. Metzger wrote: The question is, can you make it more expensive to do that than to, say, buy a new parking card or whatever else the smart card is being used for. If the attack is fairly cheap and repeatable and yields something reasonably valuable, you have a problem. If you can make the attack expensive and only yield something cheap, you're doing well. The designer often has wrong information about what the system will be used for. Most systems don't see much adoption and are discontinued because they don't make any money. Systems that succeed with low-value transactions tend to get repurposed for more and more important roles until the breaking point. SSL and Zigbee are two examples. Imagine how much an additional shielded region would cost to a cell phone that's expected to sell 50 million units. An engineer is probably going to be trading that cost off against some other feature with a tangible benefit. When the junior engineer speaks up and says let's just use the microphone for entropy gathering instead he's going to be considered a hero for saving millions. An additional consideration is that the device must also operate reliably when someone puts popcorn in the microwave or uses an arc welder in the next room. The detector must absolutely never create a false positive. Most actual consumer products sold will prefer to continue insecure operation rather than shut off. For example, the GSM standard includes a mechanism to notify the user on the display if they're connected to a cell tower with an unencrypted signal. Cell carriers typically disable this notification, presumably because it tangibly increases support costs for a benefit that appears highly theoretical. It's usually only when it's the interests of the manufacturer that are being protected that a device will actually go out of its way to find a reason to cease operation (e.g., DRM). - Marsh - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to majord...@metzdowd.com
Re: Randomness testing Was: On the randomness of DNS
On Aug 3, 2008, at 13:54, Alexander Klimov wrote: If your p-value is smaller than the significance level (say, 1%) you should repeat the test with different data and see if the test persistently fails or it was just a fluke. Or better still, make many tests and see if your p-values are uniformly distributed in (0,1). [Hint: decide on a p-value for that last equidistribution test *before* you compute that p-value.] Best, Stephan - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
Re: Randomness testing Was: On the randomness of DNS
On Mon, 4 Aug 2008, Stephan Neuhaus wrote: Or better still, make many tests and see if your p-values are uniformly distributed in (0,1). [Hint: decide on a p-value for that last equidistribution test *before* you compute that p-value.] Of course, there are many tests for goodness of fit (Kolmogorov- Smirnov, chi-square, etc.) and also you can calculate for a given number of tests how many tests should have p-value below the significance level. And after making hundred tests you ask yourself what you gonna do once your test gives good uniformity, say p-value is 0.23, but the proportion is 0.95, while the minimum pass rate for 1% is 0.96. Only a bad statistician cannot justify any predefined answer :-) -- Regards, ASK - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
RE: Randomness
On 27 April 2007 20:34, Eastlake III Donald-LDE008 wrote: See http://xkcd.com/c221.html. Donald http://web.archive.org/web/20011027002011/http://dilbert.com/comics/dilbert/ar chive/images/dilbert2001182781025.gif cheers, DaveK -- Can't think of a witty .sigline today - The Cryptography Mailing List Unsubscribe by sending unsubscribe cryptography to [EMAIL PROTECTED]
