Rule 30 automaton as hash function

[dentldir]

I noticed that the rightmost bit in initial condition needs to be 1. If all the bits are zero on the right side of the initial condition then the hash values become nonrandom and with collisions for similar messages. The whole left side of the Rule 30 cellular automaton is nonrandom it seems.

This observation is a key part of the paper I linked on the first page.  You can use that non-randomness to reverse the "right adjacent" states effectively (i.e. taking 2^17 possibilities down to 32 or so).  After messing with it for some time, you can see the importance of the structure left in the CA diagrams as they iterate.  You ideally don't want any recognizable continuities.

One of the papers you linked (with the omega-flip network), overcomes this by alternating with a different rule and performing a permutation between subsequent runs.  That paper also links to the correct testing framework you'd want to use if you intend to go further.  (NIST's sts, apply the strict avalance criterion, etc.)

I'm a huge fan of CAs and Wolfram's work from the 80's but I was disappointed at the non-peer reviewed approach he took with NKS.  This is one area where his intuition is superseded by decades of rigorous work by cryptography experts.

[1715512698]

1715512698

[1715512698]

1715512698

[1715512698]

1715512698

[1715512698]

1715512698

[Anders]

I noticed that the rightmost bit in initial condition needs to be 1. If all the bits are zero on the right side of the initial condition then the hash values become nonrandom and with collisions for similar messages. The whole left side of the Rule 30 cellular automaton is nonrandom it seems.

This observation is a key part of the paper I linked on the first page.  You can use that non-randomness to reverse the "right adjacent" states effectively (i.e. taking 2^17 possibilities down to 32 or so).  After messing with it for some time, you can see the importance of the structure left in the CA diagrams as they iterate.  You ideally don't want any recognizable continuities.

One of the papers you linked (with the omega-flip network), overcomes this by alternating with a different rule and performing a permutation between subsequent runs.  That paper also links to the correct testing framework you'd want to use if you intend to go further.  (NIST's sts, apply the strict avalance criterion, etc.)

I'm a huge fan of CAs and Wolfram's work from the 80's but I was disappointed at the non-peer reviewed approach he took with NKS.  This is one area where his intuition is superseded by decades of rigorous work by cryptography experts.

This image shows how the left side is easy to determine when the bits are sampled too tight:



Notice that when every other row of the center column is sampled, the left side becomes difficult to determine. That's the sample method I use in my hash function.

[Anders]

I created a GitHub project for R30: https://github.com/AndersLindman/R30-hash-function

[jtimon]

Interesting thread, I love cellular automata (well, most bio-inspired algorithms).
Sorry if I missed something because I haven't fully read it yet.

First, SHA256 + R30 (on the resulting 256 bits) should remove some of Peter R's performance concerns, but not all.

Here is a version of the Rule 30 hash function that skips rows 2.5 times the number of bits in the initial condition: http://jsfiddle.net/d3NS6/

The reason is to ensure that the bits become influenced enough as a protection against cryptanalysis. The image shows that 2.5 times the message length in bits is enough to make the bits to the far left and right influence the cells back into the center column after N rows.



The next image shows again how protection against cryptanalysis is achieved:

Why don't you just calculate the 256 bits column in the middle?
cell 255 can be the cell at the right of cell 0 (and therefore cell 255 is the one at the left of 0).
I don't think this would remove randomness and if it does it can probably be compensated with more loops.
But having a constant-size cell array would make it much simpler to optimize.
For example, using SSE2 you can probably implement this with shift and bitwise logic operations alone, using all the 256 bits of the XMM registries with each instruction!

So yeah, maybe SHA256 + R30 could become a hardfork alternative to SHA256d in case it gets somehow broken.
Even for an anti-centralization hardfork in the event that a single entity is so stupid to consistently control 30%+ of the mining hardware or something like that.

[Anders]

Interesting thread, I love cellular automata (well, most bio-inspired algorithms).
Sorry if I missed something because I haven't fully read it yet.

First, SHA256 + R30 (on the resulting 256 bits) should remove some of Peter R's performance concerns, but not all.

Why don't you just calculate the 256 bits column in the middle?
cell 255 can be the cell at the right of cell 0 (and therefore cell 255 is the one at the left of 0).
I don't think this would remove randomness and if it does it can probably be compensated with more loops.
But having a constant-size cell array would make it much simpler to optimize.
For example, using SSE2 you can probably implement this with shift and bitwise logic operations alone, using all the 256 bits of the XMM registries with each instruction!

So yeah, maybe SHA256 + R30 could become a hardfork alternative to SHA256d in case it gets somehow broken.
Even for an anti-centralization hardfork in the event that a single entity is so stupid to consistently control 30%+ of the mining hardware or something like that.

I was wrong about the 2.5N value and grau measured that at least 7N is needed. See for example: https://bitcointalk.org/index.php?topic=698460.msg8047993#msg8047993

The values in the center column depend on all the values in the initial condition after 7N generations where N is the length of the initial condition in number of bits. It turns out that the rightmost value (bit) of a worst case initial condition takes a nonlinear walk first to the right and then to the left in the cellular automaton. And after 7N steps (generations) of the cellular automaton the rightmost value has reached the center column.

Without the 7N initial steps the hash values would be far from random for similar messages.

[jtimon]

Reading your answer and more of the thread, I'm not sure what you're doing anymore. I thought the initial state was the data...

My recipe is the following:

Apply SHA256 once, you get 256 bits.
Those 256 bits obtained are the initial state (the first row).
You apply R30 N times (N generations) using a constant row size of 256 cells per generation, treating cell 0 and cell 255 as neighbors (so no pyramid here, just a 256 cells-wide column all the time).
With 128 generations all cells should have influenced all other cells.
So this is constant space and can be optimized to constant time per generation, thus constant time per N generations.
If we assume that N must be at least S/2 are required, being S the size of the cell array, then is O(S^2) time and O(S) space, but here S=256 is constant.

Can any of you prove that my approach doesn't produce enough randomness?

You see, Wolfrang always starts with 1 block cell alone as initial condition and allows infinite space for simplicity but that's not a requirement for cellular automata.
They don't even need to be a 2D universe (1D space + time), you could perfectly have initiate a 16x16 binary toroid (2D space where the edges opposite edges are neighbors) with your 256 bits and use a 3D rule with much less generations. But first you have to find out which one is equivalent in randomness to rule 30, and here instead of 2^(2^3)=256 possible automata, there are 2^(2^9) to analyze!!!).

[Anders]

Reading your answer and more of the thread, I'm not sure what you're doing anymore. I thought the initial state was the data...

My recipe is the following:

Apply SHA256 once, you get 256 bits.
Those 256 bits obtained are the initial state (the first row).
You apply R30 N times (N generations) using a constant row size of 256 cells per generation, treating cell 0 and cell 255 as neighbors (so no pyramid here, just a 256 cells-wide column all the time).
With 128 generations all cells should have influenced all other cells.
So this is constant space and can be optimized to constant time per generation, thus constant time per N generations.
If we assume that N must be at least S/2 are required, being S the size of the cell array, then is O(S^2) time and O(S) space, but here S=256 is constant.

Can any of you prove that my approach doesn't produce enough randomness?

You see, Wolfrang always starts with 1 block cell alone as initial condition and allows infinite space for simplicity but that's not a requirement for cellular automata.
They don't even need to be a 2D universe (1D space + time), you could perfectly have initiate a 16x16 binary toroid (2D space where the edges opposite edges are neighbors) with your 256 bits and use a 3D rule with much less generations. But first you have to find out which one is equivalent in randomness to rule 30, and here instead of 2^(2^3)=256 possible automata, there are 2^(2^9) to analyze!!!).

Sure, you could start with a SHA-256 value as initial condition instead of the full plain text message. I even proposed that somewhere earlier in this thread. Then N would be 256 bits. With 128 generations (0.5N) you would get something like this: https://bitcointalk.org/index.php?topic=698460.msg8045418#msg8045418

Notice how similar the hash values are.

Compare 0.5 N: http://jsfiddle.net/UQ6B7/

With 7N: http://jsfiddle.net/596XN/

I have experimented with 2D cellular automata and they seem to be good at producing random results. The reason for why I chose Rule 30 is that Stephen Wolfram has done extensive research on that and showed that it produces good random numbers and that it's likely that cryptanalysis will be difficult when every other row in the center column is sampled. 2D automata may be at least as good, but that would require a lot of work to find out. It's easier to build on Wolfram's research.

[jtimon]

Sure, you could start with a SHA-256 value as initial condition instead of the full plain text message. I even proposed that somewhere earlier in this thread.

Yes, you answered to Peter R when he was pointing out that your message-to-256-bits mechanism was too expensive.
 

Then N would be 256 bits. With 128 generations (0.5N) you would get something like this: https://bitcointalk.org/index.php?topic=698460.msg8045418#msg8045418

Notice how similar the hash values are.

Compare 0.5 N: http://jsfiddle.net/UQ6B7/

With 7N: http://jsfiddle.net/596XN/

I have experimented with 2D cellular automata and they seem to be good at producing random results. The reason for why I chose Rule 30 is that Stephen Wolfram has done extensive research on that and showed that it produces good random numbers and that it's likely that cryptanalysis will be difficult when every other row in the center column is sampled. 2D automata may be at least as good, but that would require a lot of work to find out. It's easier to build on Wolfram's research.

But that's with your infinite space approach, I think you're missing my main point:

Those 256 bits obtained are the initial state (the first row).
You apply R30 N times (N generations) using a constant row size of 256 cells per generation, treating cell 0 and cell 255 as neighbors (so no pyramid here, just a 256 cells-wide column all the time).
With 128 generations all cells should have influenced all other cells.

Maybe 0.5N is still not enough, but my main point is that you don't need to calculate the state of more than 256 cells per generation.
My prediction is that (for the same number of generations) with fixed size it will not only be faster to calculate, but you'll even get more randomness than with your infinite space approach.

[Anders]

Maybe 0.5N is still not enough, but my main point is that you don't need to calculate the state of more than 256 cells per generation.
My prediction is that (for the same number of generations) with fixed size it will not only be faster to calculate, but you'll even get more randomness than with your infinite space approach.

You mean that the cellular automaton should be truncated to a width of 256 cells? I think the randomness will be much lost then. It would produce a lot of hash collisions is my guess.

[jtimon]

You mean that the cellular automaton should be truncated to a width of 256 cells?

Yes, but it is important than 0 and 255 are neighbors instead of 0 having always white on the left and 255 on its right.

I think the randomness will be much lost then. It would produce a lot of hash collisions is my guess.

What it's clear is that it would be much more efficient and easier to optimize.
There's only one way to find out who's right about randomness though...
As said I think it will be as good as the infinite space one or even better. But, please, prove me wrong.

[Anders]

You mean that the cellular automaton should be truncated to a width of 256 cells?

Yes, but it is important than 0 and 255 are neighbors instead of 0 having always white on the left and 255 on its right.

I think the randomness will be much lost then. It would produce a lot of hash collisions is my guess.

What it's clear is that it would be much more efficient and easier to optimize.
There's only one way to find out who's right about randomness though...
As said I think it will be as good as the infinite space one or even better. But, please, prove me wrong.

Ok, the automaton is wrapped around for width N cells. It might work. I read somewhere that the random generator in Mathematica uses Rule 30 with a kind of fixed width size like that. I'm worried however that cryptanalysis would become easier with a truncated cellular automaton. The image I posted from the book A New Kind of Science is about the full cellular automaton, not a truncated one I assume.

[jtimon]

Ok, the automaton is wrapped around for width N cells. It might work. I read somewhere that the random generator in Mathematica uses Rule 30 with a kind of fixed width size like that.

Yes, I think I remember that the book said that some of the rules appeared to be random, but they weren't with certain initial conditions or with different setups from the "cannonical" one, but some (or one?) were resistant and I assume that's R30.
It's been more almost four years since I read the book, so I could be wrong

I'm worried however that cryptanalysis would become easier with a truncated cellular automaton. The image I posted from the book A New Kind of Science is about the full cellular automaton, not a truncated one I assume.

Yeah, he always uses the "cannonical" except for showing exceptions or just other ways in which you can organize the different algorithms.
But I don't understand your concern. There's many other models in the book besides cellular automata, and his point is that all of them have some equivalent of R30.
I thought you, like Wolfram, had chosen cellular automata precisely because they are simple to understand and analyze.

My hope was that maybe this could serve to have a "provably secure hashing function", instead of just "nobody has broken it".
Maybe to prove that "provably secure hashing functions" (PSHF ?) are an impossibility, who knows.

IMO the most interesting lesson about the book is that unpredictable behavior (in the sense that it can only be predicted by simulating the whole process) can emerge from apparently simple deterministic rules.
Have you played go? Very simple rules but no machine can beat professional players who relying on a strong intuition grown through experience.
I believe this two facts are profoundly related.

That's why I've been planning for some time to evolve a neural network to play go and become 9 dan by playing against versions of itself while(success || eternity).
But I got an 8-to-6 job and learned about Bitcoin, so it ended up playing against the machine I wrote in my first year of computer science to play reversi/othello, showing graphs of how much it kicked its ass with generation on the Y coordinate (the "dumb" machine kicked my own ass without any problem or second thought).

Sorry for the long story, that's also why I love your cellular automata hasing function (CAHF ?) idea.
I hope my little contribution is useful and I wish I had time to help with the code, but it doesn't look like you'll have problems to make 0 and 255 neighbors and try another version.

To finish, I also like the fact that you're interested in security for your custom hash function and not "anti-ASIC" nonsense.
 

[Anders]

Ok, the automaton is wrapped around for width N cells. It might work. I read somewhere that the random generator in Mathematica uses Rule 30 with a kind of fixed width size like that.

Yes, I think I remember that the book said that some of the rules appeared to be random, but they weren't with certain initial conditions or with different setups from the "cannonical" one, but some (or one?) were resistant and I assume that's R30.
It's been more almost four years since I read the book, so I could be wrong

I'm worried however that cryptanalysis would become easier with a truncated cellular automaton. The image I posted from the book A New Kind of Science is about the full cellular automaton, not a truncated one I assume.

Yeah, he always uses the "cannonical" except for showing exceptions or just other ways in which you can organize the different algorithms.
But I don't understand your concern. There's many other models in the book besides cellular automata, and his point is that all of them have some equivalent of R30.
I thought you, like Wolfram, had chosen cellular automata precisely because they are simple to understand and analyze.

My hope was that maybe this could serve to have a "provably secure hashing function", instead of just "nobody has broken it".
Maybe to prove that "provably secure hashing functions" (PSHF ?) are an impossibility, who knows.

IMO the most interesting lesson about the book is that unpredictable behavior (in the sense that it can only be predicted by simulating the whole process) can emerge from apparently simple deterministic rules.
Have you played go? Very simple rules but no machine can beat professional players who relying on a strong intuition grown through experience.
I believe this two facts are profoundly related.

That's why I've been planning for some time to evolve a neural network to play go and become 9 dan by playing against versions of itself while(success || eternity).
But I got an 8-to-6 job and learned about Bitcoin, so it ended up playing against the machine I wrote in my first year of computer science to play reversi/othello, showing graphs of how much it kicked its ass with generation on the Y coordinate (the "dumb" machine kicked my own ass without any problem or second thought).

Sorry for the long story, that's also why I love your cellular automata hasing function (CAHF ?) idea.
I hope my little contribution is useful and I wish I had time to help with the code, but it doesn't look like you'll have problems to make 0 and 255 neighbors and try another version.

To finish, I also like the fact that you're interested in security for your custom hash function and not "anti-ASIC" nonsense.
 

Cellular automata may actually be difficult to analyze mathematically. Maybe like the game go you mentioned. And proving randomness is really tricky. My guess is that the R30 hash function acts well as a random oracle.

"In cryptography, a random oracle is an oracle (a theoretical black box) that responds to every unique query with a (truly) random response chosen uniformly from its output domain. If a query is repeated it responds the same way every time that query is submitted." -- http://en.wikipedia.org/wiki/Random_oracle

[gmaxwell]

Cellular automata may actually be difficult to analyze mathematically. Maybe like the game go you mentioned. And proving randomness is really tricky. My guess is that the R30 hash function acts well as a random oracle.

Except you already proved it bad by conventional cryptographic standards in https://bitcointalk.org/index.php?topic=698460.msg7927510#msg7927510 where you find a collision. A good hash-function is not efficiently distinguishable from a random oracle (other than in the trivial sense where it has a compact implementation).

I've struggled a bit watching along worrying that this thread is a train-wreak of everything wrong with amateur cryptography: There are many reasonably well studied and designed functions in this space already (hash functions, and hashcash as proof of work), that benefit from decades of knoweldge and experience in building constructs which are actually irreducible for the purposes they're designed for... This is precisely the kind of effort people are counseled against, and for good reason.

Being difficult to analyze mathematically is pretty much the polar opposite what we want in a cryptographic building block— there is just an extreme danger of a complete break lurking right behind an intellectual speed-bump.  It's often said that anyone can come up with a scheme that they can't crack themselves, but it's perhaps more interesting to note that almost anyone can come up with a scheme with a trivial weakness but which is hard enough to analyze that no one will find it until someone's money (or life!) is on the line.

OTOH, I'm happy people have been having fun; and most of the other POW navel gazing I've seen is even more worthless... I've drafted and canned a couple messages for this thread, struggling with the difficulty in conveying a kind of underlying understanding of what responsible work looks like for cryptographic primitives— telling you to time travel back to 1994 and read sci.crypt with me is not likely to be helpful....

—  but when you get to the point of making claims that the function might actually be useful in cryptographic applications, I feel the need to speak up before another one of these incidents (which was caused by this thread, which went without adequate criticism) happens (read all the messages, not just my first response).

Have fun, by all means— but cryptography is a subtle and difficult science and art. Building a good system is an engineering discipline and having any confidence of security requires formalizing your work and putting in effort which is orders of magnitude more difficult than the basic implementation tinkering. If you don't find that kind of hard core analysis interesting yourself, then sadly it's likely never going to be done for your function. I'd say you were on the right path when you attacked and found a severe cryptographic flaw in your approach, but then something went wrong when you discarded it and continued like it never happened...  If BCT were a forum that I expected competent cryptographic review in, I might also say that something has gone wrong that it's taken this long to get a less than supportive message in this thread.

You were on to something with your attack— why not dig into it more and instead of adding complexity (which might just be obfuscating weaknesses instead of removing them), just assume this is a fun learning experience and see how many other ways you can break the original construct or what other kinds of seemingly-okay-but-really-broken functions you can build in this space?  I think more than anything else doing cryptanalysis and finding holes in functions has increased my appreciation for the enormous challenge that doing good work in this space involves. (I suppose I could say that In one sense there is no science of cryptography except cryptanalysis).

But this is just my curmudgeonly view, offered for your consideration.

[Anders]

Cellular automata may actually be difficult to analyze mathematically. Maybe like the game go you mentioned. And proving randomness is really tricky. My guess is that the R30 hash function acts well as a random oracle.

Except you already proved it bad by conventional cryptographic standards in https://bitcointalk.org/index.php?topic=698460.msg7927510#msg7927510 where you find a collision. A good hash-function is not efficiently distinguishable from a random oracle (other than in the trivial sense where it has a compact implementation).

No! That's an old pre-hash version that absolutely sucks. It was before I had learned proper ways to do it. Here is the current version that uses a Merkle–Damgård construction and the Davies–Meyer compression function that, if I have done the implementation correctly, should be the real deal: http://jsfiddle.net/596XN/

Being difficult to analyze mathematically is pretty much the polar opposite what we want in a cryptographic building block— there is just an extreme danger of a complete break lurking right behind an intellectual speed-bump.  It's often said that anyone can come up with a scheme that they can't crack themselves, but it's perhaps more interesting to note that almost anyone can come up with a scheme with a trivial weakness but which is hard enough to analyze that no one will find it until someone's money (or life!) is on the line.

Easy to analyze mathematically is no guarantee for that it will be secure. Take SHA-2 for example which is based on pretty straightforward plain math it seems, yet someone may discover a technique to break it. And Stephen Wolfram has pointed out that the math used in science today is only a tiny subset of the universe of possible constructs, a result more out of tradition and legacy rather than a deliberate design behind it.

[Anders]

The reason for using a Merkle–Damgård construction is that the version without it becomes very slow for long messages. As a Davies–Meyer compression function I simply take B xor H_i-1 and then feed that into the Rule 30 hash function and then xor that result with H_i-1, where B is a 256-bit block of the message and H is the 256-bit hash value.

Notice the trick with xor of H_i-1 after the same H_i-1 has been encrypted with a message block (m_i) as key:



Source: http://en.wikipedia.org/wiki/One-way_compression_function#Davies.E2.80.93Meyer

This may make the hash function a bit weaker but hopefully only insignificantly weaker.

For Bitcoin proof of work, the Merkle–Damgård construction can be removed. It's only useful for long messages, except perhaps that the 256-bit limit makes it easier to prove that all cells are influencing each other to produce a random value. That could be difficult to prove for infinitely long (or arbitrarily long) messages.

[21M Bitcoin]

sorry for OT but i want ask to be crypromaster like you all . what should i learn before ?
i type of strong mental to learn.

[rarkenin]

sorry for OT but i want ask to be crypromaster like you all . what should i learn before ?
i type of strong mental to learn.

You know it's off-topic, so why mention it here?

[grau]

@gmaxwell: Thanks for you view, that I was looking forward in this thread.

Yes its amateur cryptography here, but knowingly.

I respectfully question if your below assumption is the path to the ideal POW.

Being difficult to analyze mathematically is pretty much the polar opposite what we want in a cryptographic building block— there is just an extreme danger of a complete break lurking right behind an intellectual speed-bump.

What I like most in Wolfram's book is his systematic exploration of functions of utmost simplicity. Some of them are irreducible by our standard means of computation. They might be poor primitives for other cryptographic uses, but ideal for POW.

[Anders]

I learned that Bitcoin has a big problem with what is called variance. Transaction times are on average 10 minutes, yet they can vary from a few minutes to an hour. That indicates that the search space for the Bitcoin miners is non-randomly distributed. Perhaps Rule 30 could give much less variance so that the transaction times become more even.