Re: The Onion on Lava Lamps

From: kragen@pobox.com
Date: Thu Mar 01 2001 - 23:22:21 PST


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:15 PDT