5
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This paper seems to say "no, it's not secure", but I haven't read it fully yet. $\endgroup$ – Ilmari Karonen Jan 7 '16 at 21:44
  • $\begingroup$ @IlmariKaronen: The "attack" seems highly theoretical, but I guess it was enough to scare Mr. Wolfram into not recommending it be used in stream ciphers. Wolfram showed the Rule 30 PRG to Richard Feynman and Shafi Goldwasser when he was consulting for Thinking Machines ( Hillis) back in the 80's and he says they couldn't "crack" it. But I guess breaking generators is a highly specialized craft and Meier and Staffelbach are the heavyweights in that game :-) $\endgroup$ – William Hird Jan 8 '16 at 19:16
5
$\begingroup$

… 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.

visualizing Rule30

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.

cells/time comparison

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.

| improve this answer | |
$\endgroup$
2
$\begingroup$

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)

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.