# When it comes to linear cryptanalysis, is there always a key that could work for every possible input/output?

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?

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

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