Re: Brin on privacy

James Rogers (jamesr@best.com)
Sat, 21 Dec 1996 16:16:55 -0800


>> It is quite impossible to tell random from pseudorandom,
>
>Why is it impossible? If that's a theorem, I would like to see the proof.
>Anyway the problem here is not to distinguish random from
>pseudorandom. The problem is to distinguish among the many
>different kinds of pseudorandomness.

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.

>> The only way to tell them apart would try a serious cryptoattack,
>> which is a very costly business.
>
>So it's costly. When the government feels seriously threatened,
>they will spend astonomical amounts of money to defend themselves.
>Cryptography is now classified as munitions, and the NSA may emerge
>as a branch of the military, with the same standing as the Army, Navy,
>and Air Force, and with a comparable budget.

You misunderstand the nature of modern cryptography. The computational
complexity is exponential. *Many* common encryption algorithms today could
not be broken even if the entire GNP of the country was applied towards
computational capability.

For example, no amount of budget would allow the NSA to crack an IDEA
encrypted message. There isn't enough computational capability available.

>>: but the NSA could see the difference.
>>
>> But not _casually_. That's the point.
>
>Why is that the point? There is nothing casual about this. Recognizing
>the various kinds of pseudorandom sequences produced by various
>encryption schemes is not easy; neither is finding submarines in the
>ocean. But neither problem is impossible. Suppose NSA has a budget
>as big as the Navy's budget. Then a lot of things become possible.
>
>It is true that universal encryption would make the NSA's task more
>difficult. Instead of using chips that make a simple distinction between
>low-entropy and high-entropy messages, they would have to
>continually upgrade their chips to make more and more fine-grained
>distinctions, and they would have to use other methods as well.

Today people have a fairly broad choice of crypto algorithms that would
produce output that essentially requires that the NSA know what algorithm
was used. The entropy of many encryption methods used today is so high as
to be indistinguishable from noise.

-James Rogers
jamesr@best.com