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 Tue, 7 Sep 2010 22:22:57 -0400 Jerry Leichter 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 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 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, Quantum Mechanics - and Cryptography
On Tue, 07 Sep 2010 11:56:25 -0700 John Denker 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 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 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 Tue, 07 Sep 2010 10:58:59 -0700 John Denker wrote: > On 09/07/2010 10:21 AM, Marsh Ray wrote: > > 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. Very true. > 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. > 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. Well, imagine that you could very reliably force the random number generator on a smart card. You could then probably attack the smart card in all sorts of ways, even retrieving keying material by sufficiently perverting the "random" choices made in some protocol handshakes. This is not a practical attack for a remote server, but for some situations, it probably is. -- 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 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/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/05/2010 08:27 PM, Jerry Leichter 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.
> 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.
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.
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
Randomness, Quantum Mechanics - and Cryptography
The recent discussion of random number generators reminded me of
something that I've been meaning to write a note about. A couple of
years back, John Conway and Simon Kochen proved what they nicknamed
the Free Will Theorem. Its informal statement is: Given three very
simple axioms (which seem to be fundamentally part of any physical
theory even remotely consistent with relativity and quantum
mechanics), "if you have free will, then electrons do, too." This
statement of the theorem is deliberately set up to highlight one set
of philosophical consequences. A different, more straightforward
statement is: The result of a QM measurement cannot be computed by
any function of the entire pre-measurement state of the universe.
Informally, the full pre-existing state of the universe does not
determine the result of a quantum measurement.
Conway gave a series of lectures on these results that are available
free from iTunes - look at iTunes U listings for Princeton. *Well*
worth listening to. Towards the end, he makes a very interesting and
subtle point: We've viewed the unpredictability of QM measurements as
matters of randomness. People always quote Einstein's complaint that
"God doesn't play dice with the universe". Conway and Kocher's
theorem, however, show that this view is very fundamentally wrong. If
QM results were randomly determined, then we could play the same game
in our description of the universe that we play with randomizing
Turing machines: Rather than add randomness to the machine/universe,
simply provide a deterministic machine/universe with access to a pre-
computed "set of random coin tosses" that they call on whenever they
need to make a "random" choice. But if you try this approach with QM,
then Conway and Kocher will argue that the pre-determined tape can now
be considered part of "the complete pre-existing state of the
universe" - and their theorem shows that that cannot be sufficient to
predict the result of a QM measurement!
So QM's indeterminism is subtly different from randomness: It's an
unpredictable choice that "isn't made until the exact moment of
measurement". It irreducibly cannot be determined in advance. Conway
goes on to say that he doesn't *understand* what the distinction
really means - but then he says he doesn't really understand what
randomness means anyway. If John Conway feels this way, what are we
poor mortals to think?
If you think about the use of randomness in cryptography, what matters
isn't really randomness - it's exactly unpredictability. This is a
very tough to pin down: What's unpredictable to me may be predictable
to you, 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.
-- Jerry
-
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majord...@metzdowd.com
