Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
1  
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
1  
@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
add comment

1 Answer

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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