# Understanding Linear Cryptanalysis

I'm reading about the linear cryptanalysis of an SPN and I have some questions about the practicality of this. The example I'm looking at is from 3.3.3 of Stinson's Book and I believe the same example is given in these notes (pg.13 for the diagram)

First, a question of practicality. The SPN is comprised of many independent S-boxes. In both Stinson's book and the notes we seem to have the linear approximation for each S-box (in consideration). How would one get this information in practice? It seems like an attacker would need to know both the input and output of each S-box in order to get the linear approximation. But in the attacks, the only information known is the plaintext-ciphertext pairs. So, for instance how does one get that $$S_{2}^1$$ can be approximated by $$U_5^1\oplus U_7^1 \oplus U_8^1 \oplus V_6^1$$?

Here, the $$U^1$$'s are in the inputs into the 1st round S-boxes and the $$V^1$$'s are the outputs.

Second, you would need to know for instance that $$S_2^2$$ feeds into $$S_2^3$$ and $$S_2^3$$. Wouldn't this require knowledge of the permutation used by the SPN? If so, how does an attacker get this knowledge.

Lastly, how does these linear approximations allows us to get any of the subkey bits. I do not find the explanations clear enough. Does anybody have a reference that explains this clearly?

• SBOX's are analyzed beforehand in order to mount the attack. The rest is the statistics. The more data one has the better to distinguish. Of course, the bound can be computed. The Hayes' article is the clearest one. Aug 1 '20 at 17:33
• One characterizes each S-BOX by linear approximation then try to combine this with the network in a way to maximize. Aug 1 '20 at 17:57
• Yes, that was done by hand. Now one can automize it. Some paths die earlier since it goes worst than the brute-force. The practically depend on the requirement and there is no need to be practical. Matsui's attack on DES was required $2^{43}$ known-plaintext and it was implemented in 1994 by Matsui. In the end, if you break it faster than the brute-force it is called broken. Aug 1 '20 at 18:21
• Just to clarify: the first "offline" step is to find a so-called trail - pattern of approximations along the cipher (for each S-Box the approximation can be different). Enumerating all patterns would typically be infeasible, and in fact optimal trails are not known for most ciphers. However, we can use heuristic methods to find relatively good trails and use them for attack. The second "online" step is to collect plaintext-ciphertext data of a cipher instance* and check if the chosen approximation (defined by the pattern) holds. This allows to distinguish random data from cipher-generated. Aug 2 '20 at 12:06
• Hi! Small administrative note: could you try and make the title of your question title as specific as possible? That will both attract more / better views and it makes it much easier to judge the question for future readers as well. Aug 3 '20 at 15:21