FEAL-4 Linear Cryptanalysis - Prevention

Question

currently, I prepare for an exam about cryptanalysis. In class, we talked about linear cryptanalysis for FEAL-4. We constructed four linear equations, extended them to equations for three rounds and then applied a Brut Force search in order to find the keys of every round.

My question is as follows: How can I prevent such an attack?

My idea: I think, it is necessary to replace the S-Boxes of FEAL with 'better' S-Boxes? Such that, it is not possible to find relationships between input and output bits of the S-boxes (and therefore, also for the whole F-Function). But how does such an 'good' S-Box look like?

Answer 1

By convention:

• LC = Linear Cryptanalysis
• DC = Differential Cryptanalysis

---

There are multiple ways to increase the security of a block cipher.

The first one (and usually applied) is to increase the number of rounds. In the case of FEAL, they switched from 4 to 8 rounds and then to X rounds. Therefore you would have to extend the equations for 7+ rounds before starting your brute force attack (see table below from Handbook of applied Crypto, note that the time indicated is not correct anymore due to the book being written in 1996...)

+---------------+------------------------+----------------+-----------------+
|               |                        |                |                 |
|  Attack       |    Data complexity     |   storage      |  procesing      |
|  Method       |                        | complexity     |  complexity     |
|               | known   |  chosen      |                |                 |
+---------------------------------------------------------------------------+
|   FEAL-4-LC   |   5     |              |    30K bytes   |   6 minutes     |
|   FEAL-6-LC   |  100    |              |   100K bytes   |  40 minutes     |
|   FEAL-8-LC   |  2^24   |              |                |  10 minutes     |
|   FEAL-8-DC   |         | 2^7  pairs   |  280K bytes    |   2 minutes     |
|   FEAL-16-DC  |         | 2^29 pairs   |                | 2^30 operations |
|   FEAL-24-DC  |         | 2^45 pairs   |                | 2^46 operations |
|   FEAL-32-DC  |         | 2^66 pairs   |                | 2^67 operations |
+---------------+---------+--------------+----------------+-----------------+

In the case of Linear cryptanalysis, the linear equations/approximations used to break the cipher holds with a certain probability. You just have to make sure that this probability stays low.

It has been shown by Joan Daemen and Vincent Rijmen in The Design of Rijndael: AES, chapter 7 that LC and DC share similarities by the Walsh-Hadamard transform. Increasing the DC resistance of an algorithm also increases the LC resistance.

The idea is therefore to find a good S-box, you need to prove that the Differentials don't go over a certain probability (the lower the better). In the case of Rinjdael (AES), they use a $8$ bit S-box. Therefore the table of the differentials has $2^8 = 256$ rows and columns. By analyzing such table, they made sure that no differential probabilities goes over $\frac{4}{256}$.

The bigger the S-box, the harder the differentials will be to exploit. However, it is also required from the designer to prove the security of his algorithm. So increasing the size of the S-box also make the proof harder. This is the reason why the $\chi$ function of keccak is similar to a 5 bit s-box.

Smaller S-box implies higher probabilities right ? Therefore, we add a diffusion layer. The goal is to propagate the differences and make them harder to track. There you have two kind of strategies: weak alignment or strong alignment... But that is getting too far.

I would suggest to have a look at this presentation Two ways of building round functions for block ciphers by J. Daemen.