# Selecting bijective functions for permutations

How would one go about selecting an appropriate bijective function for introducing permutations into a cipher or hash?

For example, $f(x) = x+1 \space mod \space n$ is a bijective function, but isn't particularly good as a permutation, in that the outputs do not vary sufficiently when an input bit is changed.

The same applies to $f(X_i) = X_{\sigma(i)}$, where $\sigma(i) \equiv i+1\space mod\space |X|$, i.e. a circular shift.

If I understand it correctly, modular exponentiation can be bijective if you select appropriate parameters, but it's rather slow.

• In most cases we use pretty simple but very fast functions. If you have enough rounds of these it becomes exponentially complicated. For example xor, modular addition and rotation in an ARX cipher, or an sbox in AES. – CodesInChaos Jul 9 '13 at 20:57
• @CodesInChaos Surely those first operations aren't sufficient? I understand the s-box somewhat, though from my understanding it's a transposition of smaller chunks rather than the entire block. – Polynomial Jul 9 '13 at 21:02
• @Polynomial They are - look at Threefish for instance, an ARX cipher with simple permutations and no s-boxes. Even if those operations are simple, repeating them a sufficient number of times leads to high confusion and diffusion. And after all, modular exponentiation is a series of multiplications, which themselves are series of additions... of course this is an oversimplification, it takes a lot of work to make sure the way you're combining the operations leads to such behaviour. – Thomas Jul 9 '13 at 22:17
• I would also suggest taking a look at the permutation inside Keccak, it doesn't use any S-Boxes either... – Alexandre Yamajako Jul 10 '13 at 18:35

It depends. There is no single answer, and no single recipe that works for all block ciphers. The permutation is chosen to work well with the rest of the block cipher design. Therefore, this question can't be answered in general. A question like "Why did cipher X use Y as its permutation?" would be more meaningful and more answerable.

For instance, some ciphers use a permutation to diffuse the bits, or to resist some kinds of attacks (e.g., algebraic attacks). As CodesInChaos says, often one chooses a permutation that is as fast as possible and just barely good enough to meet the other requirements.