I figured I should try to learn about linear cryptanalysis with a super simple cipher with only one Sbox. The problem is that with that approach the last subkey bits seem to be involved in the linear approximation.
It looks like I need at least 2 Sboxes, keeping the last one to bring randomness in case of a bad guess on the bits of the last subkey. So obviously, the last one should also not appear in the linear approximation.
Is that understanding of Linear Cryptanalysis correct?
If you include a key addition layer ($K_1$) at the output as well the key addition layer ($K_0$) at the input of the Sbox then you can perform linear cryptanalysis on this simple cipher. You shall have access to $P,C$ pairs but no keys, of course, and the $P/C$ relationship is $$C=K_1\oplus(S(P\oplus K_0))$$ and so your linear bias equations become something like $$ \textrm{bias}(A,B)=\sum_{P} (-1)^{B \cdot (C\oplus \hat{K_1}) + A \cdot P} $$ where $A$ is the input mask, $B$ is the output mask, $P$ plaintext, $C$ resulting ciphertext and you choose the most likely key guess $\hat{K_1}$ which maximizes the observed bias. Before this, you choose the best mask pairs $(A,B)$ with $A\neq 0$ which give the best bias for the Sbox linear characteristics defined below $$ \sum_{X} (-1)^{B \cdot S(X) + A \cdot X} $$ where the sum ranges over the input set of the Sbox, and perform the attack for that $(A,B).$
