Why does invertibility matter? AND and OR are not invertible, but they are used?
Here's an answer: https://crypto.stackexchange.com/questions/47872/why-is-kecc...
1) it forces you to allocate more memory (to do the Davies-Mayer construction)
2) it complicates the security analysis because you get collisions (if you do not use a permutation, it means you have an injective construction)
And more from http://sponge.noekeon.org/CSF-0.1.pdf section 8.1.3
screenshot here: http://i.imgur.com/4xncceB.png
Indeed, the whole permutation is invertible and I'm not sure why either.
Permutations are always invertible. Otherwise several different inputs will be mapped to the same output, which needlessly reduces your state space.
The inverse is also required for decryption: If you encrypt as ciphertext = permutation(plaintext + key), decryption is plaintext = inverse(ciphertext) - key.
My question is why does Keccak not use a one-way function instead of a permutation.
> The inverse is also required for decryption: If you encrypt as ciphertext = permutation(plaintext + key), decryption is plaintext = inverse(ciphertext) - key.
This is not how encryption/decryption works with Keccak. Keccak is used to create a stream (it is then XORed with the plaintext or ciphertext).
Another fun one is x ^= x >> n with n some strictly positive constant, this is also invertible. It's used a lot in the murmurhash family of non-cryptograhic hash functions.