Rule 30 automaton as hash function

[Anders]

"The Davies–Meyer single-block-length compression function feeds each block of the message (m_i) as the key to a block cipher. It feeds the previous hash value (H_i-1) as the plaintext to be encrypted. The output ciphertext is then also XORed (\oplus) with the previous hash value (H_i-1) to produce the next hash value (H_i)." -- http://en.wikipedia.org/wiki/One-way_compression_function#Davies.E2.80.93Meyer



The trick with the Davies–Meyer compression function seems to be the xor of the previous hash value with the ciphertext.

I made a very simple version based on this: http://jsfiddle.net/2mK9R/

[Anders]

The initial conditions I have developed are way too amateurish for any serious application. Anyway, it's fun to learn about hash functions, and hopefully others new to this stuff can learn some basics too.

Length extension attacks are a serious threat even to SHA-256. In Bitcoin SHA-256 is used twice in a row. I learned that this technique is actually called SHA-256d:

"You should also consider using a generic length-extension defense such as the "SHA-256d" design by Ferguson and Schneier. SHA256d(x) = SHA256(SHA256(x))." -- http://crypto.stackexchange.com/questions/893/at-the-current-time-is-sha256-the-de-facto-standard-for-strong-cryptographic-ha

With rule 30, length extension defense can be done like in one of my previous posts. As an initial condition, start with the SHA-256 hash and concatenate it with the bits for the length of the message. And then run the rule 30 automaton as I have described earlier. That could be a serious use of the rule 30 hash function.

"Distinguishing H² from a random oracle (essentially an ideal hash) is much cheaper that it should, namely 2⁶⁴ for SHA-256d. This doesn't lead to any practical attacks, but it hurts security proofs relying on indistinguishably. It is easy to avoid this problem by using distinct prefixes for the inner and outer hash, so I see little reason to use H² in practice." -- http://crypto.stackexchange.com/questions/7895/weaknesses-in-sha-256d

[Anders]

There is a risk that any form of reducing the length of the original message will affect the security of the rule 30 hash function (as Peter R already pointed out earlier).

Therefore I made a version that uses the entire message as initial condition: http://jsfiddle.net/8aR3W/

It's very computationally demanding for long messages. On the other hand, computing performance is progressing exponentially year by year, and many practical cryptographic applications deal with short messages.

[Peter R]

I agree with DeathAndTaxes and Grau that Rule 30 is probably most interesting as a proof of work.  Using it as such, and applying D&T's suggestion

   R30(nonce + H(blockheader)) < target

also means you don't have to worry about arbitrary-length messages. 

Have you considered what the minimum requirement is for the number of cells in width need to apply Rule 30 to these fixed-length initial conditions?  Can the cell width simply be equal to the bit-length of the initial conditions, or do you need additional width to ensure irreversibility (I wouldn't think so)?  Have you given any thought to what a Rule 30 PoW ASIC would look like?  I suspect it might be simpler and cheaper than a SHA256 ASIC (although I understand the SHA256 ASICs are fairly simple too).   

[Anders]

I agree with DeathAndTaxes and Grau that Rule 30 is probably most interesting as a proof of work.  Using it as such, and applying D&T's suggestion

   R30(nonce + H(blockheader)) < target

also means you don't have to worry about arbitrary-length messages.  

Have you considered what the minimum requirement is for the number of cells in width need to apply Rule 30 to these fixed-length initial conditions

I did a quick test now, and skipping a number of rows equal to 1.5 times the number of bits in the initial condition seems enough: http://jsfiddle.net/r3qAd/

And that makes theoretical sense since that's the point where all the bits have influenced each other and reached back to the center column.

Can the cell width simply be equal to the bit-length of the initial conditions, or do you need additional width to ensure irreversibility (I wouldn't think so)?

I think skipping rows 1.5 times the number of bits in the initial condition is enough. The initial condition is the number of bits in the message plus 32 bits for the concatenation of the length bits. The length bits need to be added or else there would be no difference for different length messages containing only zeros. The cellular automaton in addition must be large enough to contain the additional rows for calculating the hash value, i.e. taking the bit value of every other cell in the center column.

Have you given any thought to what a Rule 30 PoW ASIC would look like?  I suspect it might be simpler and cheaper than a SHA256 ASIC (although I understand the SHA256 ASICs are fairly simple too).

I guess a hardware implementation of the automaton would be very fast. I have also seen a term "quantum dot cellular automaton".

[Anders]

"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

The Rule 30 hash function is almost like a random oracle perhaps.

"In cryptography and computer security, length extension attacks are a type of attack on certain types of hashes which allow inclusion of extra information." -- http://en.wikipedia.org/wiki/Length_extension_attack

The Rule 30 hash function is automatically protected against length extension attacks since the bits for the length of the message are concatenated with the bits of the full message, making the cellular automaton expand with different values for every different message length.

[Anders]

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:

[Anders]

The image below shows how the bits for the hash value are taken from the further expansion of the cellular automaton after 2.5 N rows have been calculated. If the bit values would be taken from the top of the automaton the result would be far from random for similar messages.

[Anders]

Here is the Rule 30 hash function with the same algorithm and with fewer calculations: http://jsfiddle.net/GwLp4/

Since it's only the center column from where values are taken, fewer cells need to be calculated at the bottom half of the pyramid.

[Anders]

I think the full message version of my Rule 30 hash function has at least the following cryptographic benefits:

• Resistant against preimage attacks.
• Resistant against second-preimage attacks.
• Resistant against collision attacks.
• Resistant against chosen-prefix collision attacks.
• Resistant against length extension attacks.
• Resistant against brute-force attacks.
• Resistant against distinguishing attacks.
• Resistant against cryptanalysis.
• Close approximation to a random oracle.

"preimage resistance: for essentially all pre-specified outputs, it is computationally infeasible to find any input which hashes to that output, i.e., to find any preimage x such that h(x) = y when given any y for which a corresponding input is not known.[1]

second-preimage resistance: it is computationally infeasible to find any second input which has the same output as any specified input, i.e., given x, to find a second preimage x' &#8800; x such that h(x) = h(x&#8242;).[1]" -- http://en.wikipedia.org/wiki/Preimage_attack

"Collision attack
    Find two different messages m1 and m2 such that hash(m1) = hash(m2).

Chosen-prefix collision attack
    Given two different prefixes p1, p2 find two appendages m1 and m2 such that hash(p1 &#8741; m1) = hash(p2 &#8741; m2) (where &#8741; is the concatenation operation)." -- http://en.wikipedia.org/wiki/Collision_attack

"In cryptography and computer security, length extension attacks are a type of attack on certain types of hashes which allow inclusion of extra information." -- http://en.wikipedia.org/wiki/Length_extension_attack

"In cryptography, a brute-force attack, or exhaustive key search, is a cryptanalytic attack that can, in theory, be used against any encrypted data[1] (except for data encrypted in an information-theoretically secure manner)." -- http://en.wikipedia.org/wiki/Brute_force_attack

"In cryptography, a distinguishing attack is any form of cryptanalysis on data encrypted by a cipher that allows an attacker to distinguish the encrypted data from random data. [1]" -- http://en.wikipedia.org/wiki/Distinguishing_attack

"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

[Anders]

I created a Google Code project called R30 hash function: https://code.google.com/p/r30-hash-function/

[Anders]

It would probably be too risky to use R30 in Bitcoin today. The algorithm is way too untested. And even if experts would find it likely to be strong, the algorithm has to be used in real applications and be exposed to real and heavy attacks. Anyway, R30 could be a good backup in case SHA-256 would become seriously breached.

[Anders]

Another potential problem with R30 other than it being untested is that it may turn out to bee too good! Imagine criminal organizations including terrorists being able to communicate in a way that is hidden even to intelligence agencies like the NSA. I don't like Orwellian stuff, but I trust the NSA more than I would trust secret communication between criminal elements.

[grau]

I think Satoshi's solution to the Byzantine General's problem is the first real world application of Wolfram's computational irreducibility, since doing an irreducible computation is the ideal proof of work.

My intuition says that known attacks to hash functions are only special cases of reducibility checks and a computationally irreducible function must be resistant of them by definition.

Maybe SHA256 is also computationally irreducible, it is however more likely that irreducibility of an R30 hash will be rigorously proven, than that of SHA256.

It is desirable to use the least complex irreducible computation for proof of work, as that leaves least room for implementation differences. If R30 is irreducible then it is also the least complex of such.

Note that computation of the below area is sufficient.

[grau]

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.

This sounds weak. This is the path to perceived security through perceived complexity, the thinking how SHA probably was constructed.

If there is really something with R30, then below should be sufficient.

[grau]

Note that R30 has an apparent asymmetry in its "chaos".

The below pictures hint that left and right side of an input do not receive the same "kind" of hashing. Likely irrelevant, but puzzling.

[grau]

Does not "seem" to hurt.

[Peter R]

I mined my name  



I noticed that the nonce needs to be on the left side of the message, as the hashing seems much more effective moving to the right than moving to the left (as Grau observed too).  So, I think this phenomenon needs to be better understood before you can decide what column to take your hash from and how many rows to calculate.  

[Anders]

Note that computation of the below area is sufficient.

Yes, that area is what is calculated in my Java (and latest JavaScript) version of R30.

[Anders]

I mined my name  



I noticed that the nonce needs to be on the left side of the message, as the hashing seems much more effective moving to the right than moving to the left (as Grau observed too).  So, I think this phenomenon needs to be better understood before you can decide what column to take your hash from and how many rows to calculate.  

Nice. So for that smaller hash at least is shows that leading zeros can be achieved with R30. Yes, the right side of the Rule 30 automaton is more chaotic it seems. But did you skip at least 1.5 times the number of bits in the initial condition? That's the smallest number of generations needed for both left and right side to become "blended" back into the center column.