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
participants (2)
-
Eric Hughes -
thug＠phantom.com