Re: Computerized OTP (was 5th AMENDMENT & DECRYPTION)

Timothy Newsham wries:
> Murdering Thug writes:
> > The only way to thwart the NSA is to use an encryption scheme which has
> > been _proven_ uncrackable.  The only one I know of is the One Time Pad.
> 
> didnt shannon prove that the only "unbreakable" encryptions (or
> encryptions with "zero knowledge") have to have a key at least
> as long as the message?

The key stream for a OTP system is infinitely long, and if a real
random source is used (e.g. RF noise/static) no bit in the key stream
has any relationship to any other bit in the key stream, unlike
a pseudo-random-gen key stream where there is a relationship and this
relationship can be found and the seed for the PRNG extracted and
thus the key is broken.  Since TV static on unused channels is
basically amplified RF garbage coming in from outer space radio
sources and is in fact "white noise", it makes the perfect encoding
stream for a one time pad system, it's infinitely long, never repeats,
and is never reused.

Yes I do think the idea of making a "more random than random" stream
by filtering out long runs of 0's or 1's weakens the the key stream
in theory, but in practical use it strengthens it, because if the stream
is left alone, runs of 500 bits of 0's or 1's can come through, and any
fool can then extract plain text using XOR in this area of the cyphertext.
LZW compression of the plaintext helps, but I feel that it is far better
to reduce the possibility of a key stream containing long runs of 0's or
1's, than to leave it alone.

The other possibility is to find a truly random RF source that has all
the properties you want, the more important being that the >average<
length of a homogenous bit run (0's or 1's) is around 4 or 5 bits. Of
course you should let run lengths of 12 bits come through to screw
the stat guys, but the >average< run length should be below 8 bits. Such
a highly variable stream of white noise makes the perfect key stream in my
opinion.


Thug

At risk of belaboring the point about random numbers, I have some
more, hopefully different comments.

Let me at least make the following point clear.  Making random numbers
is a hard problem.  It is hard on the scale of designing a good
cryptographic hash function.

>if a real
>random source is used (e.g. RF noise/static) 

It is unwise to conclude that a source is random merely because it
looks like noise.  Electrical noise is often a poor source of
randomness because much noise comes from unshielded oscillators of one
sort or another.  Even a source based on thermal noise must be
carefully designed, since solid state effects such as avalanching can
generate characteristic contributions.

I would suggest that everyone look and volume 2 of Knuth for the
difficulty of designing pseudorandom number generators in software.
Making hardware random numbers is harder than that, since it requires
all that knowledge and then some.  The difficulty is in knowing that
your numbers are random, not in making noise.

>no bit in the key stream
>has any relationship to any other bit in the key stream, 

This is not sufficient for a stream to be random.  I can have this
property and still have a very non-random stream.  For example,
suppose I have a random stream.  If for every two bits I output those
two bits and their xor (sum mod 2), then no two bits have any relation
to each other, but looking at bits three at a time shows awful
statistics.

The actual statement is that the every conditional probability that a
configuration of size n occur given any other independent
configuration is 1/n.  In others words, every combination of bits must
be independent from every other combination.  This is much stronger than
requiring mere bit independence.

And as an aside, long runs of bits can be removed (as Scott Collins
mentioned) by compression, and short configurations of bits can be
removed by hashing.

Eric