Preventing Algebraic Attacks on Ciphers

CS 463 Lecture, Dr. Lawlor

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_i = key_i ^ value_i-1

Then a four-round cipher produces this final output:
    value₄ = key₄ ^ (key₃ ^ (key₂ ^ (key₁ ^ plaintext)))

This looks fine, but re-associating we can algebraically combine all the round keys:
    value₄ = (key₄ ^ key₃ ^ key₂ ^ key₁) ^ 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.

Multi-Operation Attacks

You might think you're better off mixing different operations, but consider adds and multiplies:
    value_i = Akey_i + Mkey_i * value_i-1

We can't directly re-associate, so this looks better at first glance:
    value₃ = Akey₃ + Mkey₃ * (Akey₂ + Mkey₂ * (Akey₁ + Mkey₁ * plaintext))

But of course, multiplication distributes over addition, so this is equivalent to:
    value₃ = (Akey₃ + Mkey₃ * (Akey₂ + Mkey₂ * (Akey₁))) + (Mkey₃ * Mkey₂ * Mkey₁) * plaintext

And an attacker just needs to brute-force the two equivalent key values in the outermost parenthesis:
    value₃ = Akey+ Mkey * plaintext

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(2⁸) 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₃ = key₃ + matrix / (key₂ + matrix / (key₁ + 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.

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 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.

The round functions (other than the XOR stages) are chosen so they're:

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.

SHA-256 uses the same nonlinear functions, but applies both functions at every round.