4
$\begingroup$

I am pondering, how each of the four functions that a full AES round does consist of (Add Round Key, Substitute Bytes, Shift Rows and Mix Columns) add to the confusion and diffusion of the full AES.

My understanding would be

  • Add Round Key: Confusion
  • Substitute Bytes: Confusion
  • Shift Rows: Diffusion
  • Mix Columns: Confusion and Diffusion

Is my understanding correct? There are actually two parts, where I am quite unsure:

  • Can confusion be introduced without a secret (subBytes)?
  • Can confusion be introduced from the state alone (Mix Columns)?

I am aware of that and that answer, but they don't go all the way.

$\endgroup$
  • $\begingroup$ Without a secret(Add Round Key), cipher will totally invertable. One can easily go back from ciphertext to plaintext, because there is nothing unknown(mixing of key), all the steps (sub byte, shift rows, mix column) are invertable. MixColumn is Linear Step, it can diffuse the small changes to global changes, change in one byte will effect all other bytes too. But its still linear, it will be prone to differential and linear crypt analysis. this mean M( x + k ) = M (x) + M(k). where as in case of sub byte such relation is not true. $\endgroup$ – khan Aug 31 '17 at 10:21
5
+50
$\begingroup$

I should start by saying that the notions "confusion" and "diffusion" can not provide an in-depth understanding of the design of the AES, simply because they are not specific enough. Instead, the key to understanding the choice of the steps in the round transformation is the wide trail strategy.

That said, we can of course try to understand the effect of each transformation with respect to the "confusion" / "diffusion" concepts. Needless to say, the outcome of such a thought experiment is at least somewhat subjective. In any case, a proper definition of "confusion" / "diffusion" is essential. Shannon wrote:

Two methods (other than recourse to ideal systems) suggest themselves for frustrating a statistical analysis. These we may call the methods of diffusion and confusion. In the method of diffusion the statistical structure of $M$ which leads to its redundancy is “dissipated” into long range statistics—i.e.,into statistical structure involving long combinations of letters in the cryptogram. The effect here is that the enemy must intercept a tremendous amount of material to tie down this structure, since the structure is evident only in blocks of very small individual probability. Furthermore, even when he has sufficient material, the analytical work required is much greater since the redundancy has been diffused over a large number of individual statistics.

The method of confusion is to make the relation between the simple statistics of $E$ and the simple description of $K$ a very complex and involved one. In the case of simple substitution, it is easy to describe the limitation of $K$ imposed by the letter frequencies of $E$. If the connection is very involved and confused the enemy may still be able to evaluate a statistic $S_1$, say, which limits the key to a region of the key space. This limitation, however, is to some complex region $R$ in the space, perhaps "folded ever" many times, and he has a difficult time making use of it. A second statistic $S_2$ limits $K$ still further to $R_2$ , hence it lies in the intersection region; but this does not help much because it is so difficult to determine just what the intersection is.

The first comment I would like to make is that diffusion and confusion, if described using the intuitions above, typically only arise by repeated application of the round transformations. Shannon uses the following metaphor (for the construction of "mixing tranformations"):

Good mixing transformations are often formed by repeated products of two simple non-commuting operations. Hopf has shown, for example, that pastry dough can be mixed by such a sequence of operations. The dough is first rolled out into a thin slab, then folded over, then rolled, and the folded again, etc.

For this reason, my answer will mostly be about how each transformation contributes to confusion/diffusion (rather than if these transformations contribute at all).

Diffusion

Paraphrasing to the context of the AES, one might say that diffusion means that the "statistic structure" (this is quite vague) of a plaintext block is spread out over the resulting ciphertext block. For instance, if the first input bit is zero which large probabilty, this should not be apparent in any small subset of the output bits. (Remark that if this was not the case, one would obtain a strong linear approximation.) This is unfortunately very vague and in fact not really helpful if you are designing a block cipher.

Note that the above interpretation of diffusion is somewhat different from Shannon's "long range statistics", because the latter might be interpreted as "non-neighboring/close bits" rather than "small subsets of bits". I would argue that "small subsets" is what is really meant, because Shannon also talks about "long combinations of letters [~bits] in the cryptogram" (emphasis mine).

With this interpretation:

  • AddRoundKey does not contribute to diffusion. (Well... there are reasons why you could argue that they do, but let's not go into that.)
  • ShiftRows and MixColumns: these operations mix bits among rows or columns. Hence, you could say that this ensures "non-localized statistics" (again, somewhat vague). Again, the fact that the linear layer has to "mix" bits is not concrete enough to be very useful to a designer - maximizing the number of active S-boxes (cf. wide trail) is the real underlying idea.
  • SubBytes leads to diffusion at the byte level. If you think of the "symbols" as bytes then you can argue that SubBytes doesn't provide diffusion. I think it is more accurate to say that SubBytes does contribute to overall diffusion.

The last point may need some clarification. It is commonly said that the S-boxes provide confusion (this is correct by the way, see below) rather than diffusion. Nevertheless, consider a cipher such as PRESENT which uses a bitwise permutation for its linear layer. Clearly, if you remove the S-box layer of PRESENT then the result does not satisfy the intuition behind diffusion that was mentioned above. In this context another answer of mine about statistical saturation attacks seems relevant.

Of course, if you remove SubBytes in AES, the whole cipher becomes affine over $\mathbb F_{2^8}$. More about that below.

Confusion

Confusion, according to Shannon, is all about the secret key. The idea is that the key is mixed into the output in such a "complicated" (this is again vague, for sure) way that a simple/reasonable test statistic $s$ only allows you to conclude that the key must satisfy some complicated equation $f(K) = s$. Shannon notes that if $f$ is sufficiently complicated, it should also be hard to combine the information provided by different statistics.

Now what is a complicated $f$? This is difficult to formalize, but at least one can think of a few things that $f$ should not be. For example:

  • If we take $s$ to be the ciphertexts corresponding to one or more known plaintexts, then obviously $f$ should be nonlinear (otherwise one can just solve a linear system of equations). In fact, "nonlinear" is not enough by itself: there is a broad class of so-called algebraic attacks.
  • If we take $s$ to be the (estimated) bias of a sum of a few plaintext and ciphertext bits, then the sign of $f(K)$ should not be (roughly) $(-1)^{\kappa}$ where $\kappa$ is some linear combination of key bits. Indeed, this is Matsui's first algorithm for linear cryptanalysis.
  • ... (One can think about most other attacks from this point of view.)

That said, I would conclude the following about the steps in the AES:

  • AddRoundKey is essential for confusion because you need to have some way of mixing the secret key (which is what confusion is about) with the state.
  • ShiftRows and MixColumns: these operations are typically associated with diffusion, but they are also necessary to obtain overall confusion. Indeed, if you wouldn't mix columns (or rows), then the equations describing the AES would be easy to solve.
  • SubBytes is essential for confusion. In particular, it is nonlinear. Note that SubBytes alone is clearly not sufficient.
  • The key schedule shouldn't be forgotten. It also contributes (or rather, can contribute) to confusion.

In modern cryptography, "confusion" is often used in a broader sense. For example, one can reasonably talk about confusion even in the absence of a key (e.g. in permutation-based cryptography). That's a different question though.

Conclusion

I should reiterate that "confusion" and "diffusion" are rather vague. At best, these concepts can give you some intuition about why it might be possible at all to construct a secure block cipher. They are not sufficient to really understand the design of modern block ciphers such as the AES.

Just to make sure you get a clear answer to your specific questions:

Can confusion be introduced without a secret (subBytes)?

Can confusion be introduced from the state alone (Mix Columns)?

The answer to the first question is no, but I must remark that SubBytes is not secret in the AES. (But if "AddRoundKey" was intended, the answer would still be no.) The second question must also be answered in the negative, see the comments about nonlinearity above.

$\endgroup$
  • 3
    $\begingroup$ That's one great extensive answer, Aleph, I'm very glad that I decided on the bounty. Please allow some time for it to be assigned - it would be a pretty darn great answer to trump this one :) $\endgroup$ – Maarten Bodewes Jan 27 at 21:02
  • 2
    $\begingroup$ @MaartenBodewes Never mind the points, I just assumed the bounty meant there was renewed interested in this question. Confusion/diffusion is one of those things that gets thrown around a lot when people talk about cryptography (well, on the internet at least), so I thought a somewhat longer answer was appropriate. Feel free to suggest improvements by the way. $\endgroup$ – Aleph Jan 27 at 22:01
  • $\begingroup$ Wouldn't know where to start. Maybe I can proof read it some time :) $\endgroup$ – Maarten Bodewes Jan 30 at 1:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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