Randomness, Quantum Mechanics - and Cryptography

[Marsh Ray]

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 majordomo at metzdowd.com