Anders (OP)


July 22, 2014, 03:45:11 PM 

"The Davies–Meyer singleblocklength compression function feeds each block of the message (m _{i}) as the key to a block cipher. It feeds the previous hash value (H _{i1}) as the plaintext to be encrypted. The output ciphertext is then also XORed (\oplus) with the previous hash value (H _{i1}) to produce the next hash value (H _{i})."  http://en.wikipedia.org/wiki/Oneway_compression_function#Davies.E2.80.93MeyerThe 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)


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 SHA256. In Bitcoin SHA256 is used twice in a row. I learned that this technique is actually called SHA256d: "You should also consider using a generic lengthextension defense such as the "SHA256d" design by Ferguson and Schneier. SHA256d(x) = SHA256(SHA256(x))."  http://crypto.stackexchange.com/questions/893/atthecurrenttimeissha256thedefactostandardforstrongcryptographichaWith rule 30, length extension defense can be done like in one of my previous posts. As an initial condition, start with the SHA256 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 ^{2} from a random oracle (essentially an ideal hash) is much cheaper that it should, namely 2 ^{64} for SHA256d. 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 ^{2} in practice."  http://crypto.stackexchange.com/questions/7895/weaknessesinsha256d




Anders (OP)


July 22, 2014, 10:14:27 PM Last 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


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
R30(nonce + H(blockheader)) < target
also means you don't have to worry about arbitrarylength messages.
Have you considered what the minimum requirement is for the number of cells in width need to apply Rule 30 to these fixedlength initial conditions? Can the cell width simply be equal to the bitlength 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 (OP)


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
R30(nonce + H(blockheader)) < target
also means you don't have to worry about arbitrarylength messages.
Have you considered what the minimum requirement is for the number of cells in width need to apply Rule 30 to these fixedlength 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 bitlength 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 (OP)


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_oracleThe 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_attackThe 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)


July 23, 2014, 11:18:38 AM Last 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)


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)


July 23, 2014, 01:17:31 PM Last 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)


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 secondpreimage attacks.
 Resistant against collision attacks.
 Resistant against chosenprefix collision attacks.
 Resistant against length extension attacks.
 Resistant against bruteforce attacks.
 Resistant against distinguishing attacks.
 Resistant against cryptanalysis.
 Close approximation to a random oracle.
"preimage resistance: for essentially all prespecified 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] secondpreimage 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' ≠ x such that h(x) = h(x′).[1]"  http://en.wikipedia.org/wiki/Preimage_attack"Collision attack Find two different messages m1 and m2 such that hash(m1) = hash(m2). Chosenprefix collision attack Given two different prefixes p1, p2 find two appendages m1 and m2 such that hash(p1 ∥ m1) = hash(p2 ∥ m2) (where ∥ 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 bruteforce 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 informationtheoretically 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)


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 SHA256 would become seriously breached.




Anders (OP)


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


July 26, 2014, 07:28:52 PM Last 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


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


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


July 26, 2014, 09:04:30 PM 

Does not "seem" to hurt.




Peter R
Legendary
Offline
Activity: 1162
Merit: 1007


July 27, 2014, 12:46:22 AM Last 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.




Anders (OP)


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)


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.




