# Re: The Onion on Lava Lamps

From: Jeff Bone (jbone@jump.net)
Date: Fri Mar 02 2001 - 08:35:46 PST

What are you assuming as a bitrate, here? My math looks fairly different, but I could well be
wrong. BTW, you're assuming that a whole message is encrypted from a single stream ---
stream-hopping or blending yields a much more acceptable solution. (Imagine, for example, that the
key stream is generated by agreement on observing *two* stars simultaneously, and XORing them
together to yield the key stream. Or, if you prefer, 3, or 4, or whatever.) The total randomness
from those (say) 10,000 sources is combinatoric, not additive.

The combinatorics quickly approximate one time pads. A random bitstream is a random bitstream;
we're assuming that the bit source (star) is *as random as* a single lava lamp, or group of
grannies with bingo cages, or whatever.

So the randomness sources are equivalent. The problem is that they're shared, instead of
unshared; so the key to proving equivalence is to demonstrate that the combinatorics possible
yields an approaching infinite random field rather than a additive, finite number of random
streams, making key discovery infinitely unlikely *even if* all possible bitstreams are
intercepted. (The latter, AFAICT, is the point of the MIT guy's deal as well...)

jb

kragen@pobox.com wrote:

> Jeff Bone <jbone@jump.net> writes:
> > And if I happen across a random bitstring that just happens to
> > decrypt my ciphertext, well, fantastic. :-) Proves what, exactly?
> > In either case, I've just proved that I've decrypted the ciphertext.
>
> And, say, convicted Mary, Queen of Scots, of high treason.
>
> > That doesn't help me compromise future messages.
>
> True.
>
> > The point is, that with a large enough set of randomness sources
> > (and high enough bit rates) and enough time, you've got a problem
> > that's much more an approx. of the one-time pad problem than the
> > n-length key problem.
> >
> > > This is because the one-time pad has a keyspace as large as the number
> > > of possible plaintexts.
> >
> > And the total size of the possible streams generated by a vast number of bit sources across a
> > large quantity of time?
>
> Not even close. If our pad sources are all the visible stars (about
> 10,000) and we have a way of obtaining a gigabit per second from each,
> and we have a one-week window within which to find our key, there are
> 86400 * 7 * 10^9 * 10^4 different possible starting bit positions.
> That's about 6.0 * 10^19 different possible keys, or about 2^82.3.
> It's an approximation of the one-time pad problem for up to a ten-byte
> message. For an eleven-byte message, the probability of a key
> existing that decrypts it to a particular plaintext is 63 to 1. For a
> twelve-byte message, it's 16,383 to 1; for a thirteen-byte message,
> it's about four million to one; for a fourteen-byte message, it's a
> billion to one.
>
> If we have a decade instead of a week, we have another nine bits of
> "key"; if we have a billion stars instead of 10,000, we have another
> 16.6 bits of "key"; if we measure at a terabit instead of a gigabit,
> we have another 10 bits. The allows us to claim an imitation of a
> one-time pad for messages up to 117.9 bits, or almost 15 bytes.
>
> The possible is much larger than the actual. Human language is
> grossly insufficient to describe the difference.

This archive was generated by hypermail 2b29 : Fri Apr 27 2001 - 23:13:17 PDT