Suppose we consider the space of $\lbrace 0,1 \rbrace^{256}$ as the domain and SHA-256 as our hash function. Does SHA-256 become a one way permutation?

Has anyone tried to prove this? Or can it be shown that SHA-256 has more than one cycle under the given constraints?


marked as duplicate by Gilles, user6961, Reid, rath, B-Con Oct 14 '13 at 18:26

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I notice someone had asked something similar. It does not seem to be that case that anyone had said "yes" or "no" and "here is why...". $\endgroup$ – torrho Oct 11 '13 at 15:46
  • 2
    $\begingroup$ See: crypto.stackexchange.com/questions/301/… I think it answers your question $\endgroup$ – mikeazo Oct 11 '13 at 15:47
  • $\begingroup$ The second answer is basically what I am looking for i.e."No. Cryptographic hash functions model a random function, not a random permutation. A significant fraction of output hash values are expected to be unreachable and another fraction have multiple preimages." $\endgroup$ – torrho Oct 11 '13 at 18:21
  • $\begingroup$ See also Is it theoretically possible to construct a string that contain its own hash value? $\endgroup$ – Gilles Oct 11 '13 at 19:23

There's been similar questions before but the answer is probably no with very high probability.

You can imagine a hash as being a little box with a dwarf in it. You give him a message and the first thing he does is looks for the message in his book. If he finds it, he gives you the n-bit string he wrote in his book.

If it's not in his book, he rolls some dice to create a random n-bit string. He then writes in his book both your message and the random string he just rolled. He then hands you the random n-bit string. If you pass him the same message again, he gives you back the same n-bit string.

Now we have a mental model of a hash, let's ask what happens when we start querying this construction.

Suppose we start counting from zero to $2^{256}$. We write the output of the hash of the counter in a table next to the counter that generated it. How many entries will it take before the probability is greater than 50% that an evaluation of hash(x) will hit an item already in the list?

Well each time the dwarf encounters a value not in his list, he rolls his dice. The value that comes out of those rolls might well collide with an item already in the list. The birthday paradox tells us that it will happen after approximately $\sqrt{2^{256}}$ queries.

That's about 0% of the hash space. This is why we can say with a good degree of confidence that no hash is a permutation.

  • 1
    $\begingroup$ "This is why we can say with a good degree of confidence that no hash is a permutation." I disagree with that statement. Permutations that may appear to have a random output are quite feasible. Assuming what I stated before, the simplest that comes to mind is a generator of a galois field that was selected at random and kept secret to everyone. Is it cryptographic? no. do the outputs appear random? Well, if the generator was larger than $\sqrt{n}$ where $n$ was the size of the galois field, then you might be on to something that may appear random and is a permutation. $\endgroup$ – torrho Oct 13 '13 at 22:22
  • 1
    $\begingroup$ I love that description of the random oracle model. All of cryptography should be described in terms of dwarves. $\endgroup$ – Daffy Jan 30 '16 at 1:28

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