# 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. – kodlu Apr 9 '18 at 22:21

## 1 Answer

You might want to check out this stackoverflow question: What is Bit Masking?

Basically, the mask selects certain bits from the words, where a word is a vector (a row) of bits. The input mask selects certain bits from the input word, and the output mask selects certain bits from the output word.

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$.

• what are these "certain bits" that are selected.. and where do you get the input and output masks – Hammi Cloud Apr 9 '18 at 21:42
• @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$. – Ella Rose Apr 9 '18 at 21:51
• If you get stuck again, there is source code for that tutorial on that site – Ella Rose Apr 9 '18 at 21:53
• i noticed that he talks about being 90% correct ... but isn't 87.3% since he using 14/16 or 2/16 ?? – Hammi Cloud Apr 9 '18 at 22:32