|
GCM is a different type of construction, but the polynomial used there is explainable---it's the irreducible polynomial of the type x^128 + f(x) for which f(x) has the lowest degree (i.e., it's the lexicographically smallest irreducible GF(2) polynomial of degree 128). Any irreducible polynomial picked here would work as well, from a security point of view. AES is a good case study, because you _cannot_ remove any operation without ending up with a broken cipher: - If you remove AddRoundKey, there's no key getting mixed and you don't really have a block cipher in the first place;
- If you remove SubBytes, the entire thing becomes linear and elementary to break;
- If you remove ShiftRows, each column of the 4x4 state is independent of each other, and you could trivially distinguish the cipher from random by observing that only 32 bits change for any single byte change;
- If you remove MixColumns, you're removing most of the diffusion of the cipher, and once again it becomes much easier to break because there's no longer any mixing across bytes. The order itself doesn't matter all that much. You can reorder AddRoundKey, ShiftRows, and Mixcolumns any way you like and you end up with the exact same cipher, since those are all linear operations. Ordering them differently with respect to SubBytes would have no meaningful security impact, but it serves no purpose to start with anything other than adding the key and applying SubBytes, since all the other linear stuff can be trivially canceled out by the attacker until the first nonlinear operation. The general principle in AES-like ciphers is to iterate rounds of the shape `block = nonlinear_operation(block, key[i])` followed by `block = linear_operation(block)`. You will find many (many!) designs like this if you go looking, trying various choices of nonlinear and linear operations that guarantee various useful properties. In the case of AES, SubBytes guarantees that the differential probability going through any byte is upper bounded by 1/64; MixColumns guarantees that for any two distinct 4-byte inputs, between the input and output there are at the very least 5 changed bytes. When you mix these two together, with the help of ShiftRows you can show that useful differential trails are pretty much gone after 4 rounds. Constructions like SHA-1 (or more precisely, the block cipher underlying SHA-1) do not generally have such clean rationales. You can view it as a Feistel-like cipher with a linear key schedule, so it's hardly a random mashing of operations, but how the particular sequence of operations of the round function is chosen is a bit of a trial and error process. The same applies to Salsa20, Chacha20, and most other ARX constructions. |