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?

  • $\begingroup$ That tute looks interesting. You might want to google Howard Heys' tutorial as well, its a bit more mathematical. $\endgroup$
    – kodlu
    Apr 9 '18 at 22:21

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.