4
$\begingroup$

Reading through Wikipedia, I saw this:

It has been shown that the Merkle–Damgård construction, as used by SHA-2, is collapsing and, by consequence, quantum collision-resistant, but for the sponge construction used by SHA-3, the authors provide proofs only for the case that the block function f is not efficiently invertible; Keccak-f[1600], however, is efficiently invertible, and so their proof does not apply.

So:

  1. What does "efficiently invertible" mean in this case? It isn't reversible (as in decryption), so what else could that mean?

  2. Why is Keccak invertible? Is it by design or did they not bother as it's not important?

$\endgroup$
  • 1
    $\begingroup$ Please edit your question to remove the spurious questions, especially now you have accepted an answer that only answered the main one. Again, feel free to ask the other questions separately. $\endgroup$ – Maarten Bodewes Oct 6 '18 at 1:21
  • $\begingroup$ Need a link to this $\endgroup$ – kelalaka Jan 29 at 20:46
6
$\begingroup$
  1. What does "efficiently invertible" mean in this case? It isn't reversible (as in decryption), so what else could that mean?

  2. Why is Keccak invertible? Is it by design or did they not bother as it's not important?

If you look closely, you will see it does not claim that Keccak is efficiently invertible, it says that Keccak-f is efficiently invertible.

Keccak-f is the function used to mix the internal state in the sponge construction.

Since it is a permutation, it is invertible. If you have the entire state, you can apply the inverse permutation to go backwards to the previous state.

Since the hash function does not output the entire state as the hash output, an adversary may not perform this operation when given the hash output to find the preimage, so it's not a problem for Keccak-f to be invertible (though there may be more subtle differences when using a permutation versus a function to mix the state).

So efficiently invertible means the same thing that it usually does.

As for why the designers chose it, you would probably need to ask them to get a definitive answer. It is not difficult to ensure that a function is an invertible permutation, as long as each step is invertible the entire function will be.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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