Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm looking into "bitcoin like" mining processes. Say a security process uses a hash of data as proof that the data was known at some point in time.

From what I understand, hash functions are pseudorandomly generated based on the initial seed (the raw data).

If the hash function is chaotic, then the seed data should have strange attractors. If so, then I may be able to map a seed to its attractor and "pre-mine" using attractor buckets.

Are these pseudorandom functions deterministic chaotic systems?

share|improve this question
    
Comments are not for extended discussion; this conversation has been moved to chat. – e-sushi Apr 3 at 19:58
up vote 6 down vote accepted

There are many papers about chaos based hash functions but as far as I know none of them is used in commercial applications. Because there are problems with chaos based cryptography schemes. The most important one is the most challenging. There is no chaos in digital systems. Chaos is defined on continous spaces. Therefore, it is a very rare chance that your pseudorandom numbers are produced by a chaotic system. So most probably you won't encounter strange attractors from your pseudorandom sequence. Proper hash functions depend on more reliable algorithms.

share|improve this answer
    
I feel, the aspect of discrete vs continuous goes even further: Chaotic systems often stem from systems with unstable differential equations, combined with uncountable numbers like reals and (for actual experiments) the uncertainty principle. All this is absent in finite algebraic structures. – tylo Oct 7 '14 at 11:12

No. That's not going to help you. The cycle structure of a random function is well-studied, and it doesn't help you break hash-chaining, "proof-of-work", Bitcoin, etc. Crypto schemes already take into account the structure of (the graph of) a random function. It's not going to help you "pre-mine" and get some speedup on breaking Bitcoin (for instance).

For instance, the graph of a random function $\{0,1\}^n\to \{0,1\}^n$ typically has the following form: there is a single large cycle of length $\Theta(2^{n/2})$, such that most inputs eventually lead to the cycle. Starting from a random input, the length of the path that leads to that large cycle is typically $\Theta(2^{n/2})$. This does not break standard schemes for hash-chaining, proof-of-work, Bitcoin, etc., as the parameters for their hash function is chosen to take this structure into account.

Whether you want to count this as "chaos" depends upon your precise definition of "chaos", which you haven't provided in the question. Anyway, from a technical/scientific/engineering perspective, what label we assign it (chaos or not) is less important than the technical properties it provides and the security goals it can help to protect.

share|improve this answer

In chaos theory the defining attribute of a chaotic system is that small changes in the starting state tend to compound. If you look at the internal round structure of many hash functions, you will see a similar phenomenon: a single bit's change in the input will spread more and more evenly to all the state bits as you go through the rounds, until it is (assumed to have) evenly spread to all the bits.

If you iterate further, taking a hash of a hash etc., you would eventually find attractors. Both fixed points and cycles are possible. However, the mathematical structure of a hash function has been designed to resist analysis trying to find these attractors and the time to find them or end up in them by brute force is huge for secure-sized hash functions. It would on average take approximately $2^{n/2}$ iterations to end up in a cycle.

Now, those attractors do not matter in the least for most applications of hash functions, including the proof of work used in crypto-currencies. Typically only one or two iterations of the hash function are used in the proof of work. The output image of a 256-bit hash only loses around a bit of its size from two iterations, so it is nowhere near to getting to those attractors. You cannot have enough iterations to reach an attractor without making the function too costly to compute.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.