Generalization of Matsui's Algorithm 1 to linear hull for key-alternating block ciphers (Q1934241)

The paper extends Matsui's algorithm which defined for the first time linear cryptanalysis of iterated block ciphers. The basic concept is that of a ``linear hull'', defined later on in Matsui's Algorithm 2 as the set of all linear trails -- the paths of sequences obtained by the process of encryption of a given plaintext -- which characterize the correlation of a given linear approximation between plaintext bits and ciphertext bits. The results exploit and extend some earlier idea of the second author to establish some dependency relations between varying correlation values and keys via modular addition (XOR) with a secret-key-dependent constant. The goal is to obtain bits of information of the secret key (their number is logarithmic in the number of trails considered). The paper is organized as follows: The first three sections are for defining ideas and terms (linear hull, transition from trails to key masks). Section 4 is dedicated to a ``direct attack'' which obtains information about the key by exploiting the fact that it is contained in any correlation of a linear approximation with input and output masks. Section 5 shows a method to reduce the number of strong key masks, and therefore the complexity of the algorithm; an improved attack (related-key) is defined and analyzed. Section 6 presents a way to obtain more information about the master key by using several multiple-related keys; an optimal selection of these keys is necessary but can be found by an offline analysis. A comparative table of complexity of these three types of attacks (direct, related key, multiple-related key) is presented in Section 7, while Section 8 is dedicated to a comparison with other methods of linear cryptanalysis. Finally, Section 9 gives results of experiments with these three attacks on a 7-round block-cipher PRESENT with 80-bits key. The text is dense in results and analysis, which are presented in a clear and precise manner. The mathematical proofs use four assumptions, perhaps not so intuitive but justified by practical experiments. In my opinion the paper is an important reference for those interested in block-cipher cryptanalysis.