Shannon confusion and diffusion concept

Question

I read the document(not the whole document) from Shannon where he speaks about the concepts of confusion and diffusion. I read in many places(not in the document but around the internet) that confusion is enforced using substitution. Diffusion is enforced using permutation/transposition. Ciphers must use both of them because either confusion or diffusion alone are not enough. I read that a substitution cipher can apply by itself confusion(only). Permutation/Transposition applies by itself diffusion(only). It's precisely the last case that bothers me: Can a permutation/transposition cipher by itself apply diffusion?

Shannon explains diffusion as a property that spreads statistic properties of text all over the text preventing statistic analysis. It's frequently translated to: an alteration to a plaintext symbol affects many cipher text symbols. Assuming permutation of bits or characters, how can diffusion be achieved by simple permutation? I mean, if you permute bits, there will be no other bits affected. But if you consider a symbol a character and you permute bits, a change in a character will affect many other characters. It's a question of what is a symbol.

I also read versions of this diffusion concept where the point was just changing bits order just to avoid pattern analysis of the text. But, where is the avalanche effect in simple permutation?

So, what is the correct definition and the implications of diffusion?

I hope you understand what is troubling me.

Thank you once more

Answer 1

I think that you missed a pivotal point in the concept, which is the small blocks that are used to compose a secure PRF (or PRP), i.e. when you permute one bit, you actually change the value of the small block of that bit, i.e. the whole small-block is effected and thus prepared to be confused in the next round, this way you will reach a confusion of the entire big-block very fast.

I attach a good explanation of the concept as described in Lindell-Katz Book

In addition to his work on perfect secrecy, Shannon also introduced a basic paradigm for constructing concise,random-looking permutations. The basic idea is to construct a random looking permutation $F$ with a large block length from many smaller random (or random-looking) permutations $\{f_i\}$ with small block length. Let us see how this works on the most basic level. Say we want $F$ to have a block length of $128$ bits. We can define $F$ as follows: the key $k$ for $F$ will specify $16$ permutations $f_1,\ldots, f_{16}$ that each have an $8$-bit ($1$-byte) block length. Given an input $x\in\{0, 1\}^{128}$, we parse it as $16$ bytes $x_1,\ldots,x_{16}$ and then set (equation 6.2) $F_k(x)=f_1(x)||\ldots||f_{16}(x_{16})$. These round functions $\{f_i\}$ are said to introduce confusion into $F$. It should be immediately clear, however, that F as defined above will not be pseudorandom. Specifically, if $x$ and $x'$ differ only in their first bit then $F_k(x)$ and $F_k(x')$ will differ only in their first byte (regardless of the key k). In contrast, if $F$ were a truly random permutation then changing the first bit of the input would be expected to affect all bytes of the output. For this reason, a diffusion step is introduced whereby the bits of the output are permuted, or “mixed,” using a mixing permutation. This has the effect of spreading a local change (e.g., a change in the first byte) throughout the entire block. The confusion/diffusion steps—together called a round —are repeated multiple times. This helps ensure that changing a single bit of the input will affect all the bits of the output.

As an example, a two-round block cipher following this approach would operate as follows. First, confusion is introduced by computing the intermediate result $f_1(x_1)||\ldots||f_{16}(x_{16})$ as in Equation (6.2). The bits of the result are then “shuffled,” or re-ordered, to give $x'$. Then $f'_1(x'_1)||\ldots||f'_{16}(x'_{16})$ is computed (where $x'= x'_1,\ldots,x'_{16}$), using possibly different functions $f'_i$, and the bits of the result are permuted to give output $x''$. The $\{f_i\},\{f'_i\}$, and the mixing permutation(s) could be random and dependent on the key, as we have described above. In practice, however, they are specially designed and fixed, and the key is incorporated in a different way

Answer 2

I find the terms "confusion" and "diffusion" to be slightly nebulous and can lead to over-simplifications.

Confusion

For example, saying that "substitution" is responsible for "confusion" is not necessarily correct: "Substitution" is actually just a function application to the state; The implementation often utilizes a memoized function, but you can easily 1. calculate the non-linear function explicitly on each application, as well as 2. use a memoized linear function to provide only diffusion and not confusion. So saying Substitution provides Confusion is an over simplification.

Now, the reason why non-linear functions are often implemented with a memoized table is because non-linear functions can be complicated to compute. Generally speaking, the more complicated a function is, the longer it takes to evaluate it. For example, the AES S-Box utilizes calculation of the multiplicative modular inverse of an element in a finite field. This could be computed explicitly instead of using a table lookup; Doing so will result in a cipher that is significantly slower.

So the confusion does not stem from substitution per se, it results from applying complicated non-linear functions that tend to produce maximally unhelpful and complicated equations. The more "linear" a non-linear function is, the easier it becomes to cryptanalyze and break (we can assume that it acts like a linear function in certain inputs/outputs with a certain probability of being true). There is plenty of research into what kind of non-linear functions are maximally un-helpful to the cryptanalyst.

So it may be more accurate to say non-linearity is responsible for "confusion". Non-linearity is always required in a symmetric cipher algorithm, because otherwise the resulting systems of equations that represent the cipher can easily be manipulated and solved.

Diffusion

As for "Diffusion", other answers have touched on it. But going into more detail, when you really get down to it, all we can really do when attempting to encrypt anything is apply XOR and AND gates to bits. Yes, there exist other operations, such as integer addition; However, these are actually implemented by a circuit of XOR/AND, so at the end of the day, that's all we're really capable of doing. (This is not absolutely true; You could, as a counter-example, use NAND as your basis; This is not really helpful to the current discussion.)

This is relevant to diffusion because XOR and AND are both bit sliced operations. They take two bits as input as produce one bit as output. So what happens if you XOR together two 8-bit words? You're actually performing eight, totally separate XOR gates on 8 separate groups of data in parallel. XOR and AND (on any wordsize larger the 1) is actually an SIMD operation. Thus, the bits at index $i$ in the words do not influence the bits at any other index in the words. In reality, we only have 1-bit registers, we just have a lot of them in parallel.

This is why "Transposition" (rotations and shifts) is required to produce diffusion: Rotations and shifts ensure that new pairs of bits are utilized as inputs to future XOR/AND gates. Basically, the linear diffusion layer is responsible for mixing the contents of these 1-bit registers.

More specifically: The job of the linear diffusion layer is to ensure that each successive input to the non-linear function consists of a balanced and maximum number of super-positioned input bits. If your non-linear function operates on X-bit words, then ideally each input bit will have X/2 input bits super positioned in each index (50% of each input bits influence each output bit, aka "the avalanche effect"). (Note: An exclusive-or sum is a linear superposition of the summed bits)

Put simply, the combination of diffusion and confusion means that we want to produce equations with a maximum number of terms and maximum algebraic complexity. Then, of course, we repeat the process, until the resultant system of equations that describes the output is simply impossible to work with by even probabilistic reasoning.