Stream cipher

2015-01-07

A stream cipher that uses a cellular automaton-based pseudorandom number generator to generate a stream of 6-bit values.

Source

The method of operation is:

Compute base64 version of input data
Use the key to seed the initial state of the cellular automaton using SHA1
Advance the cellular automaton while reading values from it
Add those pseudorandom values to 6-bit blocks of the data, modulo

The cellular automaton uses a 3D lattice of size $10\times 8\times 8$ with 64 states per site. The same rule of a neighbourhood of size 3 is applied sequentially in each dimension. We use 16 different cellular automaton rules and take the sum of their outputs.

I have found that, as the dimensionality and number of states increases, a random cellular automaton rule is more likely to produce output that appears random. But random-appearing behaviour appears even for simple automata like Rule 30. More complex automata such as a one-dimensional 256-state one has been shown to pass the same number of statistical tests as the Mersenne Twister 19937 in a popular randomness test suite.

Since my random number combines 16 different streams, and operates in a manner more complex than the one-dimensional 256-state automaton described above, its output should be even more difficult to predict. There are $64^{64^3}=64^{262144}$ possible rules, so guessing which 16 rules are being applied is nearly impossible. The total lattice state of the cellular automaton is $64^{\text{lattice size}} = 64^{10\times 8\times 8} = 64^{640} \approx 10^{1156}$ , which is also huge.

So, it is difficult to predict my cellular automaton pseudorandom number generator using brute force. However, it may be the case that there are other patterns or vulnerabilities, so this should not be used for mission-critical tasks.

Also, this is really slow and, if not used correctly, is vulnerable to all stream cipher attacks.