# How do you calculate the linear approximation of an S-BOX?

I've been following this very good tutorial on linear cryptanalysis, and I'm stuck at the linear approximation part. I have no idea what input and output masks are. I don't understand what he's doing and why. Can somebody please help?

• That tute looks interesting. You might want to google Howard Heys' tutorial as well, its a bit more mathematical. Commented Apr 9, 2018 at 22:21

The goal is to find a set of output bits that can be expressed as a linear combination of input bits with the highest probability. "A linear combination" in this case basically means no bitwise AND/OR gate are present in the expression, only XOR gates. This is relevant because when you have something like $\text{out} = a \oplus b \oplus k$, where $\oplus$ is XOR, then you can trivially solve for $k$ by computing $k = \text{out} \oplus a \oplus b$.
• @HammiCloud Which bits are selected depends on what mask you use. The input and output masks are generated the same way input and output differences are generated: You iterate through a nested loop, where you use the first loop index as the input mask and the second loop index as the output mask. The number of loop iterations is determined by the size of the S-Box. In that tutorial there is a 4-bit S-Box, so the number of iterations in each loop would be $2^4 = 16$. Commented Apr 9, 2018 at 21:51