Algebraic attack

An algebraic attack on a cipher involves:

• expressing the cipher operations as a system of equations (in whatever algebraic system works best for the attacker)
• substituting in known data for some of the variables
• solving for the key

What makes this attacks impractical is a combination of the sheer size of the system of equations and non-linearity in the relations involved. In any algebra, solving a system of linear equations is more-or-less straightforward provided there are more equations than variables. However, solving non-linear systems of equations is far harder. Cipher designers therefore strive to make their ciphers highly non-linear.

One technique for introducing non-linearity is to mix operations from different algebraic systems, for example using both arithmetic and logical operations within the cipher so it cannot readily be described with linear equations in either normal or boolean algebra. Another is to use S-boxes, which are lookup tables containing non-linear data; see Feistel cipher for one example.

An algebraic attack is similar to brute force or a code book attack in that it can, in theory, break any symmetric cipher but in practice it is wildly impractical against any reasonable cipher.

Attacking a linear block cipher

To break a block cipher that uses only linear operations, an attacker can just plug in known plaintext/ciphertext pairs until there are at least as many equations as variables, then solve for the key.

For example, for a cipher with 64-bit blocks and a 128-bit key, the attacker might write 64 Boolean equations each expressing one output bit in terms of 64 inputs and 128 key bits. Plug in a known plaintext/ciphertext pair and only the key bits remain as variables. He has 64 equations in 128 variables, not a soluble system. However, if he has a second known pair, that gives him a different set of 64 equations with the same 128 key bits as variables. The total system is now 128 equations in 128 variables. If the equations are all linear, this is soluble by standard techniques. Of course, he also has the option of plugging in a third known pair to get a system with 192 equations in 128 variables if that is easier to solve, or going even further if that helps.

If the key schedule causes difficulties for him, he has the option of bypassing it. Instead of solving for the 128-bit master key, he can try to solve for all the round keys, 512 to 1024 bits in typical block ciphers. This requires more known plaintext/ciphertext pairs and the number of equations becomes distinctly unwieldy, but if all the equations are linear then the system is still, at least in theory, straightforwardly soluble. Finding the round keys breaks the cipher just as finding the master key would; an attacker can try either or both.

Linearisation of over-determined systems

Suppose the attacker has m equations in n variables, with m significantly greater than n (the system is over-determined), with some linear terms in the equations and some non-linear terms.

He can try replacing all the non-linear terms with new variables. This will give him a linear system with more variables than the original one. If the original system is sufficiently over-determined and does not have too many non-linear terms, this new system may be soluble.

If he can solve that system, he substitutes results back into the original equations hoping that will simplify them enough that the rest is soluble.

AES has a simple algebraic description . Courtois and Pieprzyk claim to have found a vulnerability based on linearisation, but the claim is controversial [1].

Linear cryptananlysis

The attacker can also try linear cryptanalysis. If he can find a good enough linear approximation for the round function and has enough known plaintext/ciphertext pairs, then this will break the cipher. Defining "enough" in the two places where it occurs in the previous sentence is rather complex; see linear cryptanalysis. Simplifying outrageously, a good rule for the cipher designer is the more non-linearity the better; have at least some components that are not even close to linear.