There's an annoying problem with round-based ciphers, that the rounds can sometimes be folded together using algebraic manipulation.

For example, if each round consists of:

value

Then a four-round cipher produces this final output:

value

This looks fine, but re-associating we can algebraically combine all the round keys:

value

This is bad, because an attacker now only needs to brute-force the single end-to-end key, instead of each of the four round keys (which would be harder to the fourth power!).

This simple reassociation trick works identically for *any* associative round operation, including +, *, or any of the finite field versions of these operations.

value

We can't directly re-associate, so this looks better at first glance:

value

But of course, multiplication distributes over addition, so this is equivalent to:

value

And an attacker just needs to brute-force the two equivalent key values in the outermost parenthesis:

value

This rearranging trick works whenever your round operations distribute over one another.

I was a little worried to notice that AES keeps every operation
inside the GF(2^{8}) finite field. Because the field
operations are associative, distributive, commutative, and
invertible, there are many opportunities for algebraic
attacks. AES is resistant against algebraic attacks
primarily because of the finite field division in the S-box, for
an equivalent round function of:

value_{i} = key_{i} + matrix /
value_{i-1}

("matrix" here is the product of the affine part of the S-box,
the row shifts, and MixColumns.)

The advantage here is after a few rounds, we get:

value_{3} = key_{3} + matrix /
(key_{2} + matrix / (key_{1} + matrix /
plaintext))

The big advantage is it's hard to separate the key terms from the
plaintext terms in the denominator of each divide--divide doesn't
distribute over addition (in the denominator).

I think if I were designing AES, I would have made one of the
steps use ordinary addition (with carries) instead of finite field
addition (XOR), purely to break the associative and distributive
properties of the finite field. But that's clearly a
belt-and-suspenders approach.

SHA-1 is a hash function, so it uses a fixed key, and doesn't
need a decryption operation. This means it can be built from
non-invertible operations.

Each SHA-1 round
consists of mixing 32-bit values a,b,c,d, and e:

e += rol(a,5) + F(b,c,d) + stage_key +
round_key;

b = rol(b,30);

The round keys (W array) are derived from the original data.
After this, the five values a,b,c,d,e are circularly shifted.

The round function F provides the only nonlinearity and
noninvertibility, and varies depending on the round:

- The first 20 rounds use the function (z ^ (x & (y ^ z))).
This is actually equivalent to the bit selection function
(x&y) ^ ((~x) & z), which more clearly shows the
symmetry (and non-invertibility) involved.

- The middle 20 rounds use XOR (x ^ y ^ z). The purpose
here is to mix the bits well.

- The next 20 rounds use the function ((x & y) | (z & (x
| y))). The output of AND is biased toward zero; OR is
biased toward one. Alternating them removes the bias.

- Ends with 20 rounds of XOR.

- Nonlinear, so you can't build a linear series of equations.
- Non-commutative, so you can't rearrange the operations.
- Non-associative, so you can't reorder the operations.
- Non-distributive, so you can't shuffle the operations.
- Non-invertible, so you can't undo the operations.