From: James Rogers (jamesr@best.com)
Date: Mon Dec 23 1996 - 20:55:30 MST
>Eugene Leitl proposes to make routine low-overhead encryption part of
>TCP/IP. I am only claiming that NSA can tell the difference between
>an encrypted message generated by such a routine algorithm, and one
>generated by a more sophisticated algorithm. Not that they can read the
>messages, just that they can tell which is which.
This is not necessarily true. You have several fast encryption algorithms
available today that are sufficiently strong as to be essentially
indistinguishable from other "strong" algorithms. It will would depend on
exactly which algorithm is used.
>> A good pseudo-random number generator is indistinguishable
>> from a true set of random numbers. The RC4 stream cipher (= PRNG)
>> is a case in point. The output has a totally white spectrum.
>> The only thing that makes it "pseudorandom" is that it is generated
>> deterministically. The output is indistinguishable from
>> non-deterministic random noise.
>
>Is that a theorem? Are you saying that trying to distinguish between
>these outputs is like trying to find a rational number whose square is 2?
>
>If it's not a theorem -- and I don't think it is -- then I wouldn't be
>too quick to assert that it is *impossible* to distinguish between
>different kinds of pseudorandomness. I could be wrong, but my
>mathematical common sense tells me that each algorithm leaves
>some kind of fingerprint, and distinguishing between them is
>just a matter of cleverness and patience.
Yes and no. For "weak" PRNGs, it is usually possible to ascertain
distinguishing traits in the output stream that suggest the content of the
input stream or seed. The fact that the output produces a distinguishing
pattern is what makes them weak and therefore unsuitable for cryptographic
purposes. For "strong" PRNGs there are (as yet) no known distinguishing
cycles or patterns in the output that suggest the content of the input
components. To discover patterns and cycles in a PRNG usually means that it
can be fairly easily cracked as cypher. Identifying characteristics of PRNG
output lets the code-breaker gain knowledge regarding the state of the PRNG
at points in time. This substantially limits the total search space for
brute force attacks by eliminating huge chunks of keyspace. In the case of
RC4, the total number of possible states is 10^1700. If no cycles or
patterns are found, then cracking this cypher is much more formidable than
the usual off-the-shelf symmetric cyphers like IDEA and DES.
But like factoring, we cannot currently prove the complexity of the problem.
In the specific case of RC4 however, the algorithm is extremely simple and
therefore fairly easy to analyze for weaknesses.
>What I am doing -- not in this thread particularly, but in general -- is
>the opposite of encryption. I am trying to decrypt my thoughts. I am
>trying to create a vocabulary in which I can make myself understood.
>The most subversive thing I can do is to tell the truth in plain English.
>But first I have to establish a context within which my ideas will be
>intelligible. This has been the purpose of all my posts from day one.
>
>Lyle
>
-James Rogers
jamesr@best.com
This archive was generated by hypermail 2.1.5 : Fri Nov 01 2002 - 14:35:55 MST