Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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?
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.
