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 nonlinearity 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 nonlinear systems of equations is far harder. Cipher designers therefore strive to make their ciphers highly nonlinear.

One technique for introducing nonlinearity 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 nonlinear 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 can — at least in principle, though it might be quite difficult in practice — 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, For example, against AES-128 he can try to solve for the eleven 128-bit round keys instead of the single 128-bit primary key. This lets him ignore the complexity and nonlinearity of the key schedule which derives the round keys from the primary key. It 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 primary key would; an attacker can try either or both.

Linearisation of over-determined systems

Suppose the attacker has a nonlinear system with $m$ equations in $n$ variables, and the system is over-determined; $m$ is significantly greater than $n$. He can try replacing all the nonlinear terms in the equations 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 nonlinear 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 nonlinearity the better; have at least some components that are not even close to linear.