Why is the DES s-box non-linear? Why does it make the cracking of the cipher more difficult?

Question

I know that if we have a cipher that makes only linear transformations (let's say a bunch of $XOR$s), we break it simply by writing a system of equations with $\oplus$ operation starting from the cipher's scheme.

In the end, we'll have a system of $n$ equation involving the $n$ plaintext bits, the $n$ ciphertext bits, and the $n$ key bits holding with probability: $\Pr(1)$ and we can solve for the $n$ key bits.

Why with the presence of S-boxes is this not possible in the same way?

Thinking about $DES$, couldn't we just reverse the S-Boxes (which at the end are only lookup tables) to write the same system of equations? In that case, the relations won't be again deterministic? (holding with $\Pr(1)$)

What is the precise meaning of non-deterministic transformation and how is it applied here?

Could you please make me a counter-example of what I'm saying, just to see why this approach couldn't be used as it is, with the presence of S-Boxes?

Answer 1

It is of course possible to write DES or any block cipher as a system of non-linear equations involving the plaintext bits, the ciphertext bits, and the key bits, which hold with probability 1. In principle, cracking the cipher would then merely involve collecting enough linearly independent equations (e.g. from a couple different known plaintexts) and then solving the system.

However, for any typical block cipher the equations are going to be extremely high degree, involving preposterous numbers of terms. Solving very high degree systems of equations with large numbers of terms is actually a very hard problem. Which is to say, while systems of linear equations can be solved in polynomial time (e.g. with Gauss-Jordan elimination), solving systems of non-linear equations is NP-Complete and can take longer than the expected life of the universe to solve.

It is possible to reduce the degree of the system by clever use of intermediate or temporary variables (which also increases the number of equations). In fact, you can make the system as low degree as quadratic. But as it turns out, that doesn't help much - solving multivariate quadratic systems is still NP-Complete (this is called the "MQ" problem).

There have been a few papers in recent decades concerning "algebraic cryptanalysis" which purport to solve the specific systems of equations involved in certain ciphers in polynomial time. The idea with these papers is that while MQ in general is very hard, the specific systems of equations associated with some block ciphers might be sufficiently structured and sparse as to be efficiently solvable by some clever technique or another. However, none of the techniques thus far been convincing to the cryptographic community.

Answer 2

The S-Boxes are lossy. They map 6-bit inputs to 4-bit outputs, so for a given 4-bit output there are several possible inputs. Considering that there are 8 S-boxes, that's 16 bits of information lost per round, or 256 bits for all 16 rounds. It's much easier to exhaustively search the 56-bit keyspace than try to work backwards against that kind of information loss.

(There are optimizations to the naive working-backwards method, but hopefully you get the idea.)