Wolfram Science Summer School 2015

From June 29 through July 17 this year, I attended the Wolfram Science Summer School in Waltham, MA. It’s an awesome program, focused on computational research through the methods introduced in Stephen Wolfram’s A New Kind of Science.

My project was officially titled Investigating the Viability of a Cellular Automaton-based Cryptographic Hash Function. Before the school I developed a fairly simple hash function that essentially treats its input as the initial conditions for an elementary cellular automaton. My project involved determining if it’s cryptographically secure.

8-tuples
Count of collisions of hashed 8-tuples at various padded bitlengths
16-tuples
Count of collisions of hashed 16-tuples at various padded bitlengths

I was able to evaluate the function for the entire space of 8 and 16-tuples1, the results of which are shown above. My official conclusion was somewhat underwhelming:

I conclude that testing the viability of this function is not feasible on larger bitlengths, and the unpredictable nature of cellular automata makes extrapolation inaccurate.

In other words: with a conventional hash function, collision frequency can be reasonably estimated by evaluating the function on a random sample of a large binary space, but the very nature of cellular automata makes such an approach inaccurate.

But I did lots of other fun things too! One student needed help collecting high-rate data from an accelerometer on a Roomba, so I built parse-keyval (previously called RoombaStore.) I even managed to connect my laptop to the Roomba via serial and parse the raw motion data into a Mathematica AnglePath, learning more than I’d like to know about two’s complement in the process.

The WSSS is an awesome event, with participants ranging from computer science students to English professors to geologists to political science undergraduates, all doing research using NKS techniques. If you have even the slightest interest in complex systems, I highly suggest you check it out.


Postscript: As I have been working on learning C, I started work on a low-level implementation of the function. I got as far as a near-complete implementation of an elementary cellular automaton, but my attempt at periodic boundary conditions does not behave properly. A fix for this would be greatly appreciated from anyone with knowledge in C.

1n-tuples in this context is assumed to mean ordered length-n permutations of the set {0, 1}.

Leave a Reply

Your email address will not be published. Required fields are marked *