Preventing Algebraic Attacks on Ciphers
Lecture, Dr. Lawlor
There's an annoying problem with round-based ciphers, that the
rounds can sometimes be folded together using algebraic
For example, if each round consists of:
valuei = keyi ^ valuei-1
Then a four-round cipher produces this final output:
value4 = key4 ^ (key3
^ (key2 ^ (key1 ^ plaintext)))
This looks fine, but re-associating we can algebraically combine all
the round keys:
value4 = (key4 ^ key3
^ key2 ^ key1) ^ plaintext = key ^ plaintext
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.
You might think you're better off mixing different operations, but
consider adds and multiplies:
valuei = Akeyi + Mkeyi
We can't directly re-associate, so this looks better at first
value3 = Akey3 + Mkey3
* (Akey2 + Mkey2 * (Akey1 + Mkey1
But of course, multiplication distributes over addition, so this is
value3 = (Akey3 + Mkey3
* (Akey2 + Mkey2 * (Akey1))) +
(Mkey3 * Mkey2 * Mkey1) * plaintext
And an attacker just needs to brute-force the two equivalent key
values in the outermost parenthesis:
value3 = Akey + Mkey *
This rearranging trick works whenever your round operations
distribute over one another.
Algebraic Resistance in AES
I was a little worried to notice that AES keeps every operation
inside the GF(28) 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:
valuei = keyi + matrix /
("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:
value3 = key3 + matrix /
(key2 + matrix / (key1 + matrix /
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
Algebraic Resistance in SHA-1
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
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 +
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 round functions (other than the XOR stages) are chosen so
- 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.
the same nonlinear functions, but applies both functions at every
- 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.