The exact difference between a permutation and a substitution

Question

I've noticed confusing definitions about permutation and substitution, preventing me from understanding the difference.

A permutation changes the order of distinct elements of a set, but this can be written as a function changing one element by another, exactly as a substitution.

So, how exactly can we distinguish between these two notions?

This question is interesting since we have these two notions in block ciphers, in which S-boxes perform substitution. The problem is that this table is used to replace one element by another, exactly like a permutation.

Answer 1

As noted in this answer and this answer to another question, permutation is just a mathematical term for a function $\sigma:X{\rightarrow}X$ that maps a finite set $X$ onto itself, in such way that for each $y \in X$ there exists exactly one $x \in X$ such that $\sigma(x) = y$. This is also equivalent to how the term substitution is used in cryptography, so your question is indeed justified.

For instance, the term Pseudo Random Permutation denotes a function that might also have been described as a Pseudo Random Substitution (but never is).

As D.W. pointed out in a comment below, the terms P-boxes (permutation boxes) and S-boxes (substitution boxes) have a specific meaning in block cipher design. Suppose you have a P-box and a S-box that both map a bit-string of length $n$ to another bit-string of length $n$. In such case the P-box can be expressed as a function $\sigma:[0..n-1]\rightarrow[0..n-1]$ that maps one index in the bit string to another, while the S-box, simply put, does more. This means that there are only $n! = \Pi_{i=1}^ni$ different P-boxes that map one bit string of length $n$ to another, while there are $2^n!-n!$ different S-boxes that map any bit string of length $n$ to another, without being a P-box and without mapping two different inputs to the same output.

Using the term Permutation in the specific meaning described in the above paragraph is unambiguous within the field of block cipher design. However, I would recommend using the term P-box, which, to the best of my knowledge, is never used in a meaning that differs from above.

Why? Well, for instance, a block cipher designer who hypothetically decides to incorporate e.g. the RC4 key schedule for setting up the S-boxes used in a block cipher, would be technically correct to refer to the operation that sets up those S-Box as a "permutation" (because one property of such a S-box might be best understood by looking at the setup in terms of permutation decomposition). The result would clearly not be a P-box, though.

Consequently, the best answer is probably that the distinction must be clear from definitions made in the context where the terms appear. When in doubt, avoid terms that might cause confusion.

Answer 2

Permutation

A “P-box” is a permutation of all the bits, meaning: it takes the outputs of all the S-boxes of one round, permutes the bits, and then feeds them into the S-boxes of the next round. A good P-box has the property that the output bits of any S-box are distributed to as many S-box inputs as possible.

Substitution

An “S-box” is usually not simply a permutation of the bits. Rather, a good S-box will have the property that changing one input bit will change about half of the output bits… the so-called “avalanche effect”. An S-box will also have the property that each output bit will depend on every input bit.

Answer 3

The answer is that P and S boxes are effectively two halves of the same thing. This is the reason people confuse the two.

e-sushi's S-P network diagram is an excellent example of the reason for needing both. The object of a cryptographic function is to alter the input in an unpredictable way, be it for an encryption cypher or a hash. That means what comes out bears very little resemblance to what went in. This is Shannon's confusion and diffusion principle.

The best theoretical way to mangle the input bits (it's all a question of bit mangling) is to use a look up table to replace the incoming byte with it's stored value, as in $x=S[x]$ with $S$ populated with random numbers. For a byte that's great. $S$ would be $2^8$ values that could be stored as 256 bytes. e-sushi shows an encryption of 64 bits which is a common block size for something like DES (I know it's $2 \times 32$ bits but who's counting?) That would require $2^{64}$ 64 bit words in $S$, in a perfect world. That's actually $2^{64} \times 8$ bytes or about $10^{20}$ bytes. More than enough to fill a few floppy discs. This is one of the reasons that cryptography deals with large numbers.

These things have to run on anything from mainframes to smart cards and iButtons for wide stream acceptance. e-sushi shows us 16 smaller S boxes with $2^4$ bit inputs. That requires $2^4 \times 16$ nibbles or 128 bytes. Amazing! Where did all that storage requirement go?

Problem is that a 4 bit S box isn't that dissimilar to a 1 bit input box, i.e. a direct 1 - 1 mapping. You've sacrificed storage for less bit mangling and so less security and invert-ability. Hence the P box to distribute the S box output as broadly as possible before doing it all again. e-sushi's P box has a 1 - 1 mapping at the bit level, but it doesn't have to. Any bit can map to any other so the input and output widths do not have to match. You can lose bits, and you can duplicate bits.

Putting the S and P boxes together creates another type of function so that now we have $x=f(x)$. You might call this a Feistel function. If you're really good at it you might call it a Bent function as well. Somewhere inside there you might also stuff in some modular arithmetic and /or bitwise operations like SHA-1. And so you go round and round (in what are called rounds surprisingly) till you think that the original input is sufficiently encrypted. You've traded storage space for cpu cycles /time.

So in summary, in order to mangle the bits better and for the algorithm's implementation onto commonly used hardware, you must compromise and perform a balancing act between S and P boxes. You therefore balance security as well.

Answer 4

Though there's a lot confusion between substitution and permutation(or transportation) cipher but, we can make the difference from the basics. It is known that substitution cipher refers to mono alphabetic(if we take example of alphabets) and permutation refers to poly alphabetic. That is for every single alphabet in substitution cipher will have a unique alphabet and every alphabet in permutation cipher may have different values(alphabets).