Steven Wolfram of Mathematica uses a pseudorandom number generator based on Rule 30 for applications in Mathematica software but I would like to know if a pseudorandom generator based on Rule 30 is cryptographically secure? Can anyone weigh in on this?
… I would like to know if a pseudorandom generator based on Rule 30 is cryptographically secure?
No. Cellular automata rules are not cryptographically secure; not even close.
Rule30 works somewhat like an LFSR… it's a cellular automata rule (think: finite state machine) having alike problems with repeating patterns (even though with different, expanding repetition — in contrast to how LFSR work), typical finite state machine behaviour, and rather short loops of repetition.
Visualizing Rule30 and the likes can show this in an more "in your face" way — where it becomes rather obvious why you wouldn't want to use "cellular automata" for things like cryptography.
Meanwhile (since the 80s) cryptographic engineering has better building blocks than those "old goodies". For similar reasons, more modern crypto algos stopped using LFSR combining constructions.
Sure… you could use Rule30 in cipher algo design - but the drawbacks and problems of working around cellular automata issues will make the whole algo more suspicable to attacks. This again will make the whole algo less optimal from a resource and certainly from a speed point of view.
Differently stated: just because you could, doesn't mean it makes sense. Especially, since things like Rule30 don't help adding security to your algo as they're not cryptographicall secure by nature… and making cellular automata rules cryptographically secure is comparable with making an LFSR cryptographically secure. It can be done, but the problems will always tend to outweight the gains from choosing such a component for cryptographic engineering purposes.
For example: when we look at the several stream cipher designs based on cellular automata since the 80s, it shows that — most of the time — even a rather simple attack with a SAT solver is already more efficient than a brute force attack. That means most of them are theoretically broken the day they are published (while practical breaks are waiting atround the corner). Especially when looking at cellular automata, such SAT solver attacks are merely the tip of an iceberg which tends to be full of problems includng timing attacks, etc.
This paper analyses the randomness of Rule 30, http://www.cs.indiana.edu/~dgerman/2005midwestNKSconference/dgelbm.pdf. Also note that there are some patterns that, when repeated to fill the cells of a Rule 30 automaton, repeat themselves after finitely many time steps. (https://web.archive.org/web/20130808012847/http://www.iwriteiam.nl/Rule30.html)