3
$\begingroup$

Until now every tutorial I've seen about linear cryptanalysis, is written on the basis that we have all possible inputs/outputs. Is that a condition? And if not, how many should we have as a minimum?

I also noticed that the idea is to find a key that would work for every possible combination. So, when it comes to block ciphers that could be cracked using linear cryptanalysis, is there always a key that could work for every possible input/output?

$\endgroup$
  • $\begingroup$ Unclear. All possible inputs/outputs of what? Sbox? $\endgroup$ – kodlu Apr 9 '18 at 22:04
3
$\begingroup$

Regarding your first question, we assume (for known plaintext attacks such as Linear cryptanalysis) that we can obtain a large number of inputs and the corresponding outputs under the unknown key. The goal of designing a good linear attack is to find a biased linear approximation to the cipher to minimize how many input/output pairs we need. But we shouldn't need all input/output pairs, since that would turn into a brute force codebook(dictionary) attack. Matsui's Linear cryptanalysis attack on DES needs only $\approx 2^{42}$ of the $2^{64}$ possible input output pairs.

Addressing your second question "..when it comes to block ciphers that could be cracked using linear cryptanalysis, is there always a key that could work for every possible input/output?":

Any block cipher defines a unique invertible mapping between the input and output spaces, say both are $\{0,1\}^n,$ given any fixed key, so the answer is yes, absolutely.

$\endgroup$

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.