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

Multi-Operation Attacks

You might think you're better off mixing different operations, but consider adds and multiplies:
    valuei = Akeyi + Mkeyi * valuei-1

We can't directly re-associate, so this looks better at first glance:
    value3 = Akey3 + Mkey3 * (Akey2 + Mkey2 * (Akey1 + Mkey1 * plaintext))

But of course, multiplication distributes over addition, so this is equivalent to:
    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 * 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(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 / valuei-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:
    value3 = key3 + matrix / (key2 + matrix / (key1 + 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 round functions (other than the XOR stages) are chosen so they're:
SHA-256 uses the same nonlinear functions, but applies both functions at every round.