Bitcoin Forum
September 16, 2024, 01:06:14 PM
 News: Latest Bitcoin Core release: 27.1 [Torrent]
 Home Help Search Login Register More
 Pages: 1 2 [3] 4 5 6 7 8  All
 Author Topic: Rule 30 automaton as hash function  (Read 10607 times)
Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 22, 2014, 03:45:11 PM

"The Davies–Meyer single-block-length compression function feeds each block of the message (mi) as the key to a block cipher. It feeds the previous hash value (Hi-1) as the plaintext to be encrypted. The output ciphertext is then also XORed (\oplus) with the previous hash value (Hi-1) to produce the next hash value (Hi)." -- 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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 22, 2014, 07:27:03 PM

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 H2 from a random oracle (essentially an ideal hash) is much cheaper that it should, namely 264 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 H2 in practice." -- http://crypto.stackexchange.com/questions/7895/weaknesses-in-sha-256d
Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 22, 2014, 10:14:27 PMLast edit: July 22, 2014, 11:20:17 PM by 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
Legendary

Offline

Activity: 1162
Merit: 1007

 Re: Rule 30 automaton as hash function July 23, 2014, 05:59:24 AM

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

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

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 23, 2014, 10:00:07 AM

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

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.

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

Quote
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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 23, 2014, 10:32:08 AM

"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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 23, 2014, 11:18:38 AMLast edit: July 23, 2014, 12:07:15 PM by 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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 23, 2014, 11:57:07 AM

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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 23, 2014, 01:17:31 PMLast edit: July 23, 2014, 01:36:20 PM by 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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 23, 2014, 02:40:20 PM

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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 24, 2014, 11:21:16 AM

Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 25, 2014, 12:47:23 AM

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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 25, 2014, 03:33:00 PM

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
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 26, 2014, 07:28:52 PMLast edit: July 26, 2014, 07:50:27 PM by 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
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 26, 2014, 08:19:23 PM

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
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 July 26, 2014, 08:42:13 PM

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
Hero Member

Offline

Activity: 836
Merit: 1030

bits of proof

 Re: Rule 30 automaton as hash function July 26, 2014, 09:04:30 PM

Does not "seem" to hurt.

Peter R
Legendary

Offline

Activity: 1162
Merit: 1007

 Re: Rule 30 automaton as hash function July 27, 2014, 12:46:22 AMLast edit: July 27, 2014, 12:57:22 AM by 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.

Run Bitcoin Unlimited (www.bitcoinunlimited.info)
Anders (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 03:48:45 AM

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 (OP)
Full Member

Offline

Activity: 126
Merit: 100

 Re: Rule 30 automaton as hash function July 27, 2014, 03:59:03 AM

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.
 Pages: 1 2 [3] 4 5 6 7 8  All