Cyber security's randomization problem

Modern encryption systems rely on pseudorandom number generators, which are computer algorithms for generating data streams that pass all statistical tests for randomness. For example, computer software tycoon Stephen Wolfram has related that he has used segments of a bit stream from one of his cellular automata in his encryption systems.

But it turns out that any fully deterministic system leaves fingerprints that largely random systems don't have.

Consider the most complicated output definable: that which is generated by a deterministic chaos system. It leaves an output graph that is indistinguishable from a randomly generated pattern. Such artificial randomization leads computer experts to have confidence in their encryption systems.

However, a difference plot of those output values will show a curve or curves completely uncharacteristic of a difference plot for random numbers (in which the deterministic process is negligible). One takes successive output values and subtracts them from one another, and then plots these new values on a graph. The deterministic process, no matter how random looking on first analysis, will stand out like a sore thumb.

One can also deploy a pseudo phase space graph on the output, with the same result. For both truly random and deterministically complicated (chaotic) ouputs, the basic output value graphs are highly scattered. But in pseudo phase space, only the truly random output is highly scattered; the deterministic output is very obvious. That is, the randomization feature vanishes.

Now what does this mean for computer security? Potentially, that these forms of analysis yield sufficient information to speed up certain decryption techniques. Weaker encryption systems -- and there are many relatively weak systems -- may be quite vulnerable.

At the very least, we learn that attempts to conceal data as mere noise are probably naive, even if the scrambled bit stream defeats a Fourier bandwidth analysis.

Perhaps it is true that NSA and private cyber security experts are aware of these methods and have been quietly exploiting them, where appropriate. On the other hand, one may wonder whether even military grade encryption is as safe as has been assumed.