The key size warning

[Dmitri]

On Sat, 2002-03-30 at 00:17, Enzo Michelangeli wrote:

> [...]
> > A popular idea, since "Johnny Mnemonic" the movie, is to use broadcast
> > TV as source of randomness.
> 
> A random stream that can be eavesdropped by an attacker (as it's surely the
> case with digital broadcasts) is useless for cryptographic purposes.

Though you certainly have a point, the TV bitstream is quite random in a
sense that the opponent does not know at what point in time you grab a
bit of it, and from what channel.

Let's assume that there is only one HDTV channel, with 1 Mbps stream.
Let's also assume that the attacker records this stream and timestamps
it. Also we have to assume some window of stream capture - for example,
1 hour (which is too small, something like weeks would be more
practical).

Within 1 hour (3600 seconds) you can choose any moment (any bit) in time
to start capturing the HDTV signal. This is the random event (not the
data itself), and you have 1e6*3600 = 3.6e9 possible choices. The event
that actually happens (one of those billions) can produce from 1 bit to
as many as you want, but if you take more than one bit then the second
and later bits are related to each other (as recorded by attacker).

If you take only one bit then the case is simple - the data is random
simply because you take the bits at random moments, defined only by your
own physical actions. It is similar to throwing a coin. The attacker
knows that you may stumble upon 0 or 1, but he has no way of knowing
which one you in fact took (aside from Tempest attack).

More interesting case is when you take more than one bit. Then the bits
are related to each other, and the relationship is known to the
attacker. Whether you take one bit or one gigabit (within the known
hour), the moment you start the capture is absolutely random. The
probability that your key starts with k[i] where i E [0..3.6e9-1] is the
same, namely 1/3.6e9 = 2.8e-10.

But the trick is that if you take _as many bits as you want_ from the
HDTV datastream, this does not increase the strength of the key - the
attacker still has to go through the same 3.6e9 possible cases to
recover the exact same bitstream that you had. This is the problem.

What this all means is simple. The randomness of the captured data
decreases as you capture more and more data, and as your "capturing time
frame" becomes more known. In worst case, if you captured the entire
HDTV stream of your local PBS station from the moment it was built to
the monent the meteor hit and destroyed it, the probability of the
recovery of the stream is exactly 1 (a certainty).

Therefore, each user-initiated capture event (in the scenario above)
gives you one outcome out of 3.6e9 possibilities. This is more than a
standard dice can offer (one possible outcome out of 6). In binary
terms, one throw of a coin gives you 1 random bit; one throw of a
6-sided dice will result in 2.5 bits; one reading from the TV receiver
gives you about 32 bits. The fact that the attacker knows your alphabet
(list of choices) is not a danger because the attacker also knows how
coins fall, and how a dice can possibly roll. What the attacker does not
know is *how exactly* the dice fell, and *what channel and when* you
switched to.

The amount of entropy you get translates into the dictionary entries
that you use as your random output. The coin's heads can be translated
into 0, and tails - into 1. But you must not translate it into "000" and
"111". If you capture from the HDTV, you can grab up to 32 bits of the
stream, and even if the attacker knows the entire stream, he will need
to try all 3.6e9 combinations to get to the same 32-bit segment; there
is no other way to reconstruct it; he can as well just try all 32-bit
numbers, without even accessing the recorded TV stream. However if you
*exceed* the entropy of your random event and take more than 32 bits (in
this scenario!) then the attacker will be better off trying the recorded
TV stream. For example, if you take 100 bits instead of 32, then the
attack on the key itself will take 1.3e30 tries, but the attack on the
HDTV stream will cost only the same 3.6e9 attempts - a big difference!

All this means that one *can* use the HDTV streams as source of
randomness, but one have to understand exactly how much entropy one
event produces, and then to manually generate the necessary number of
events to make enough of random bits. If there are many channels, and if
there is a longer window of capture, then the amount of entropy per
capture increases. The exact calculation is not easy because there are
other factors involved (such as correlation between user-initiated
events).

In any case, one can always point a digital camcorder to a HDTV screen,
tune to a football game, and the output of the camcorder is likely to be
very random (reencoded), and unavailable to any attacker since it is not
stored anywhere.

Thanks,
Dmitri

-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 240 bytes
Desc: This is a digitally signed message part
Url : /pipermail/attachments/20020331/61669a20/attachment.bin