# Is SHA-256 a one way permutation when restricting the domain to {0,1}^256? [duplicate]

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?

• 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...". Oct 11, 2013 at 15:46
• See: crypto.stackexchange.com/questions/301/… I think it answers your question Oct 11, 2013 at 15:47
• 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." Oct 11, 2013 at 18:21
• Oct 11, 2013 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.

• "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. Oct 13, 2013 at 22:22
• I love that description of the random oracle model. All of cryptography should be described in terms of dwarves. Jan 30, 2016 at 1:28