Topic: Rule 30 automaton as hash function - page 7. (Read 10577 times)

I changed the collision test to use different lengths of the messages tested (1 - 160 characters). Then the average value was around 400, even higher than with fixed length test messages:

Attempt 1: 41
Attempt 2: 487
Attempt 3: 122
Attempt 4: 584
Attempt 5: 771
Attempt 6: 474
Attempt 7: 458
Attempt 8: 378
Attempt 9: 109
Attempt 10: 312
Attempt 11: 585
Attempt 12: 558
Attempt 13: 227
Attempt 14: 515
Attempt 15: 266
Attempt 16: 423
Attempt 17: 462
Attempt 18: 305
Attempt 19: 808
Attempt 20: 296
----------------
Average: 409

Source: http://jsfiddle.net/4nFz8/

If I have a hash with 16 bits, then in theory it should take 2^N/2 = 2⁸ = 256 attempts on average to find a collision.

"As an example, if a 64-bit hash is used, there are approximately 1.8 × 10¹⁹ different outputs. If these are all equally probable (the best case), then it would take 'only' approximately 5 billion attempts (5.1 × 10⁹) to generate a collision using brute force. This value is called birthday bound[2] and for n-bit codes it could be computed as 2^n/2.[3]" -- http://en.wikipedia.org/wiki/Birthday_attack#Mathematics

When I tested my hash function I get an average of around 350, not 256:

Attempt 1: 552
Attempt 2: 100
Attempt 3: 452
Attempt 4: 360
Attempt 5: 273
Attempt 6: 336
Attempt 7: 337
Attempt 8: 117
Attempt 9: 419
Attempt 10: 742
Attempt 11: 313
Attempt 12: 408
Attempt 13: 200
Attempt 14: 383
Attempt 15: 385
Attempt 16: 185
Attempt 17: 286
Attempt 18: 265
Attempt 19: 398
Attempt 20: 566
----------------
Average: 354

Source: http://jsfiddle.net/wsEU7/

Is there an error in my code, or is Math.random() in JavaScript a poor random generator, or is the theoretical value 256 only an approximation?

I wonder if a rule 30 hash function would be quantum-safe. Here is an article about SHA-256 not being quantum-safe:

"Bitcoin Is Not Quantum-Safe, And How We Can Fix It When Needed

... Quantum computers have two major tools that make them superior to classical computers in breaking cryptography: Shor’s algorithm and Grover’s algorithm. ...  A modified version of Shor’s algorithm can crack elliptic curve cryptography as well, and Grover’s algorithm attacks basically anything, including SHA256 and RIPEMD-160." -- http://bitcoinmagazine.com/6021/bitcoin-is-not-quantum-safe-and-how-we-can-fix/

Then Bitcoin would fail.   There is no evidence anything like that is possible.   What if Earth collided with a blackhole tomorrow?

But what if a Bitcoin miner has figured out how to select the bits in the block to get the required number of leading zeros? A direct method that bypasses the entire trillion tries brute force approach.

Or successful attacks have happen that people keep silent about! Who in the professional world would admit that their company/service got the cryptographic hash broken?

I read that SHA-1 was considered broken just because someone figured out how to find matches some three magnitudes faster than brute force. In practice this may mean that SHA-1 is still secure enough and that it's not recommended for the fear of exposure of even more efficient ways for finding matches.

I myself wouldn't fully trust either SHA-2 or a rule 30 hash function. Who knows what clever techniques the NSA and other agencies like that have. And big companies like IBM may also have methods they keep hidden from the public community.

Computational irreducibility, in the case of a hash function, only protects against shortcuts when calculating the hash. It doesn't protect from going backwards from the hash to a matching message. Fortunately, in the case of rule 30, to determine previous values quickly becomes increasingly difficult, as Stephen Wolfram pointed out.

In otherwords trust is through time. And the test of time of a particular algorithm or cryptocoin for that matter also needs to stand that test...

Much of these new alt coins have not stood that test of time.

That is very rarely true.   It depends on what you mean by broken.  Faster than brute force no matter how much time or energy that would take (or even if the human race could generate energy on that scale)?  Sure.   Going from no know flaws to exploitable in a real world scenario. That hasn't happened to any major cryptographic hashing function in the last 30 years.  Take SHA-1 for example.  Collision attacks were found as early as 2005 however almost a decade later there isn't a single known preimage attack.  Even MD5 which wouldn't be recommended for any new application is still resistance to first and second preimage attacks.


If you could break SHA-2 there are a lot more valuable things you could do with it.  Hell even if you didn't know what to do with it you could sell it to a three letter agency for seven figures easy.  Still a flaw in SHA-2 it is unlikely to be useful to a miner.   A miner isn't looking for a single hash but rather one of trillions of quadrillions of possible valid hashes.  Mining is block is only on complexity 2^60.  If you found a flaw in SHA-2 which would allow a preimage attack on the order of 2^80 it would be huge but would still be a thousand times slower than just mining by brute force.

Yes, the cryptographic algorithms need to be heavily battle tested in real applications over a long period of time. The scary thing however is that many cryptographic algorithms can become broken overnight, even after several years of widespread use.

To use a rule 30 hash for Bitcoin today would probably be too shaky. Instead a rule 30 hash can be used in a new altcoin as a pilot project to test the concept in a real application with real attacks and attempts to break the algorithm.

Another scary thing I came to think of: what if some Bitcoin miner already has discovered a way to break SHA-256? And they keep that knowledge secret for their own benefit.

Exact same hash function with fewer calculations: http://jsfiddle.net/7TuBy/

The previous version calculated a lot of unnecessary cells. The cellular automaton expands like this:



Only the cells represented by the triangle need to be calculated.

Maybe I should explain how my hash function works. Here is an illustration with a smaller version:

Starting with a sample message: 0123456789

For each byte in the message the initial condition is set to the byte value xor previous wrapped initial condition result, plus the sum of all previous bytes in the message, plus a random value, summed together modulo 256, resulting in something like 5396. In this simple illustration modulo 10 is used for the values and modulo 4 for the length of the initial condition.

The initial condition 5396 is then used in the rule 30 cellular automaton by setting the cell values equal to the bit values of the initial condition. Then a fixed number of rows (cellular automaton generations) are skipped to allow all cells to influence each other left to right and back again. And then after that a hash is generated as the value of every other cell in the expansion of the center column of the cellular automaton. Other values than 640 bits initial condition and 256-bit hash as in my JavaScript example can be used.

Now that I have published it here, no one else can turn this into a patent.

Yes, if computational irreducibility can be proved or at least assumed to be true according to experts, then it per definition means no shortcuts, no matter what fancy mathematics is used.

SHA-1 is considered broken if I understood it correctly. In that case the same may happen to SHA-2.

If SHA-2 becomes broken then Bitcoin will maybe need to replace the SHA-256 hash function, or add another hash on top of SHA-256.

Wolfram's computational irreducibility, if exists, defines the perfect proof of work, therefore the discussion is on spot here or better in an alt-coin forum.

I think that a simple POW algorithm eliminates the risk of possible shortcuts that might exist in complex algorithms like the SHA group.

Here is a harder problem: Try to find a message that produces the following hash:

http://jsfiddle.net/ALV5X/

It's easy to generate a collision for my hash function by the fact that the initial condition is generated with such a simple algorithm. Here is one collision: the byte (0=0x00, 1=0x01) sequence 1000000000000000000000000000000000000000000000000000000000000000000000000000000 00 will generate the same hash as 0100000000000000000000000000000000000000000000000000000000000000000000000000000 01.

Yet I believe that's just because the pigeon hole principle shows that collisions will always occur when a longer message is converted into a shorter hash value.

"In mathematics, the pigeonhole principle states that if n items are put into m containers, with n > m, then at least one container must contain more than one item.[1] ...  For example, collisions are inevitable in a hash table because the number of possible keys exceeds the number of indices in the array. A hashing algorithm, no matter how clever, cannot avoid these collisions." -- http://en.wikipedia.org/wiki/Pigeonhole_principle

For fun, try to crack this hash: http://jsfiddle.net/ALV5X/

Hint: the message is 7 characters long and starts with 'bitcoi'.

When you have cracked the message you can try to find another different message that generates the same hash.

In Bitcoin SHA-256 is used twice iirc; first a hash is generated then that hash is hashed again. From a speculative conspiratorial view, the NSA may have given the public community the SHA family of hash functions because the NSA can break them, for national security reasons. So from that perspective a rule 30 hash function may be useful for privacy reasons.

For example, instead of starting with my simple initial condition, the initial condition could for example be a SHA-256 or SHA-512 hash. My simple initial condition may be enough though since the rule 30 scrambling generates a highly random hash even from plain text as the initial condition.

I have to agree with Peter.  

Schneier's law

A cryptographic primitive becomes more valuable the more it is used (which creates a self reinforcing cycle).  Better known and deployed algorithms are more likely to be researched that esoteric ones.  The longer the algorithm is around without any published breaks the higher the confidence that the algorithm can't be broken at the current time.

I don't think this thread is generating much interest because your proposal doesn't seem to be very useful.  Even if it worked, why would anyone choose this over a widely-analyzed standard like SHA2?  And the fact that you are hashing the message (you called it "crunching to 640 bits") before you hash the message (with Rule 30) suggests that perhaps you are choosing the wrong tool for the job.   

That being said, I do find Wolfram's Theory of Computation Irreducibility very interesting.  I expect that he is right, and I think it would imply that there exists a certain group of hash functions that are fundamentally impenetrable by cryptanalysis.  In essence, they are already fully dense in their complexity.  As far as I know, no one has shown the Rule 30 has any predictability at all--and I know a lot of people would love to prove Stephen Wolfram wrong.  But even if Rule 30 was computationally irreducible, it's still not necessarily useful as a hash function because it is at least O(n^2) with message length to use it in "raw form" (without your pre-hashing).  And then any further changes you make to improve its memory and speed performance may affect its security--which means a lot more analysis.  So I think this is really just of theoretical interest at this point. 

"The notion of Computational Irreducibility (CIR) seems to have been first put forward by Wolfram. Given a physical system whose behavior can be calculated by simulating explicitly each step of its evolution, is it always possible to predict the outcome without tracing each step? Is there always a shortcut to go directly to the nth step? Wolfram conjectured [16, 17, 18] that in most cases the answer is no. While many computations admit shortcuts that allow them to be performed more rapidly, others cannot be sped up. Computations that cannot be sped up by means of any shortcut are called computationally irreducible. ...

In this context, Israeli and Goldenfeld in [9] have shown that some automata that are apparently computationally irreducible have nevertheless properties that are predictable. But these properties are obtained by coarse graining and don’t account for small scales details. Moreover some automata (rule 30 for example) seem to be impossible to coarse grain." -- http://arxiv.org/ftp/arxiv/papers/1304/1304.5247.pdf

The comment about that rule 30 "seems to be" computationally irreducible is actually stronger than it sounds. It's often difficult to give definite answers since some future method may break the assumption. However, the same is the case with provably secure hash functions:

"A cryptographic hash function has provable security against collision attacks if finding collisions is provably polynomial-time reducible from problem P which is supposed to be unsolvable in polynomial time. The function is then called provably secure, or just provable.

It means that if finding collisions would be feasible in polynomial time by algorithm A, we could find and use polynomial time algorithm R (reduction algorithm) that would use algorithm A to solve problem P, which is widely supposed to be unsolvable in polynomial time." -- http://en.wikipedia.org/wiki/Provably_secure_cryptographic_hash_function#Provably_secure_hash_functions

Notice the description "widely supposed". Again, no definite answer even when the hash function is provably secure.