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 impractical is a combination of the sheer size of the system of equations used and non-linearity in the relations involved. In any algebra system, solving M linear simultaneous equations in N variables is more-or-less straightforward when M is at least as great as N, but non-linear systems are much 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.

Attacks on linear ciphers

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

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.

What makes these attacks impractical is a combination of the sheer size of the system of equations used 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, so the cipher designer strives to introduce non-linearity to the system. Combined with good avalanche properties and enough rounds, this makes both direct algebraic analysis and linear cryptanalysis prohibitively difficult.