### 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
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
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
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
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
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
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
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

```