2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$
    – CodesInChaos
    Jul 9, 2013 at 20:57
  • $\begingroup$ @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. $\endgroup$
    – Polynomial
    Jul 9, 2013 at 21:02
  • 1
    $\begingroup$ @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. $\endgroup$
    – Thomas
    Jul 9, 2013 at 22:17
  • $\begingroup$ I would also suggest taking a look at the permutation inside Keccak, it doesn't use any S-Boxes either... $\endgroup$
    – Alexandre Yamajako
    Jul 10, 2013 at 18:35

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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