# The exact difference between a permutation and a substitution

I've noticed confusing definitions about permutation and substitution, preventing to make the difference.

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

So how can we distinguish exactly these two notions ?

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

-

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.

-

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.

-

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

Despite the Wikipedia plagiarism, 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 octets. e-sushi shows an encryption of 64 bits which is a common block size for something like DES (I know it's 2 * 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 * 8 octets 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 * 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.

-