Re: A Modern Reappraisal of the One-Time Pad Cipher.

On 2010-05-13, Greg Rose <ggr@xxxxxxxxxxxxx> wrote:
In article <slrnhumecj.ttm.unruh@xxxxxxxxxxxxxxxxxxxxxxx>,
unruh <unruh@xxxxxxxxxxxxxxxxxxxxxxx> wrote:
On 2010-05-12, Simon Johnson <simon.johnson@xxxxxxxxx> wrote:

Realizing a practical-as-possible OTP is an interesting and worthwhile
project. The 'adacrypt' context here is obviously worse than useless.
Somewhat ironic that after all the effort sci.crypt has put into
explaining to the math-deniers the limits of the OTP, we still don't
have an OTP implementation anywhere near as practical as we know how
to build.

I think you nearly got it and went astray on that last paragraph.

The cryptographic community did exactly what you suggested. They built
a workable one-time pad implementation.

It's called a stream-cipher.

Except it is not a one time pad. The key advantage of a OTP is that
every character is completely underivable from an arbitrary number of
previous (or later )characters. this is not true of a stream cypher.
Assuming a 128 bit key, once you have 16 characters you have a very high
probability of predicting all the rest, by exhaustive search of the key
space. Now, whether or not that is practical is irrelevant. It says that
16 characters determine all the rest of the characters.

A minor nit: if the state of the stream cipher is
only 128 bits, time-memory-tradeoff attacks would
be surprisingly efficient, so all modern stream
ciphers have a larger state than keyspace. See the
EStream project for more details on this.

I am not sure that it matters. Given 16 bytes, what is the chance that
more than one key would give those same 16 bytes? If we assume that the
stream produces random bits, then teh probability that the 128 bits
would occur for two different keys would be of order 2^-128.

But I agree that it might require a bit more than 16 bytes to make sure.

But your point remains, that maybe 32 bytes would
allow an efficient brute force attack. 16 might
not be sufficient. The complexity would still be 2^128,
just rainbow tables etc wouldn't help.


PS. Isn't it nice to have substantive discussions?
Please stop feeding trolls, everyone.