What is a permutation in Keccak?

Question

I am trying to understand Ethereum's hash algorithm Keccak. Keccak uses permutations in the hashing process. Could anyone explain me what this permutation looks like or how it works ? I only know permutation from mathematics, is it the same here? A permutation of "abc" is: abc, acb, cab, bac, bca, cba Is the same logic applied in Keccak?

Answer 1

I only know permutation from mathematics, is it the same here? A permutation of "abc" is: abc, acb, cab, bac, bca, cba Is the same logic applied in Keccak?

It's a slightly different sense of the word permutation that's in play here. The initial sentence of the Wikipedia entry touches on this:

In mathematics, the notion of permutation relates to the act of arranging all the members of a set into some sequence or order, or if the set is already ordered, rearranging (reordering) its elements, a process called permuting.

In your example, the set is $\{a, b, c\}$, and it's already ordered as $abc$, so those other strings are permutations of the set and the string.

In cryptography when we talk about permutations, normally we're talking about sets of binary strings of some fixed length (notation: $\{0,1\}^n$) and a permutation is a bijective function with that set as both domain and codomain. This is the same sense in which the term is used in abstract algebra:

In algebra and particularly in group theory, a permutation of a set $S$ is defined as a bijection from $S$ to itself. That is, it is a function from $S$ to $S$ for which every element occurs exactly once as an image value. This is related to the rearrangement of the elements of $S$ in which each element $s$ is replaced by the corresponding $f(s)$.

Or, since the elements of a set $\{0,1\}^n$ can be read as numerals, you can read that as a providing an implicit, canonical ordering of the set, where the first element is the numeral for zero, the second element is the numeral for one, and so on. And in that setting a permutation can be written as a nonrepeating sequence of all the numerals in the set, such that the $i$th element in the set's canonical ordering is substituted with the $i$th element of the sequence that denotes the permutation.

So the specification for Keccak defines certain permutations that are just some standardized functions over binary strings of a fixed length (which the specification defines for several lengths, but the most common is for 1600-bit strings). These functions are designed to behave as much as possible like a permutation chosen at random from the set of all possible permutations of the same set, but to be efficiently computable. But one way to reason about how Keccak works is to pretend like the permutation really is a randomly chosen one. Again, if we think of the bit strings in the set that the Keccak permutation operates on as binary numerals, what the function does is, given any one of these as input, compute the position it would occupy in the randomly shuffled set.

Answer 2

Yes, the permutation in Keccak is just one of the possible bit permutations of the state cube. The FIPS PUB 202 paper has nice visualisation of the changes in the state (p. 13-14).