3
$\begingroup$

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?

$\endgroup$

marked as duplicate by Gilles 'SO- stop being evil', 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.

4
$\begingroup$

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.

$\endgroup$
  • 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.