Research Of Linear Hull For Block Cipher

The block cipher is a basic symmetric cryptosystem, which is widely used in other cryptosystems. Linear cryptanalysis and differential cryptanalysis are usually used to attack the block cipher. Furthermore, resisting against linear cryptanalysis and differential cryptanalysis is important security requirements of modern block ciphers.Linear cryptanalysis is a powerful method of cryptanalysis introduced by Matsui in 1993. It is a known plaintext attack in which the attacker studies the linear approximations of parity bits of the plaintext, ciphertext and the subkey. The probability of linear approximation needs to be away from 1/2. Based on this idea, many kinds of variant linear cryptanalysis appeared one after the other, such as single linear cryptanalysis. linear cryptanalysis using multiple approximations with the same key mask, multiple linear approxima-tions crypt analysis and linear cryptanalysis based on linear hull. etc.Linear cryptanalysis using multiple approximations was introduced by Kaliski and Robshaw in 1994. For a given success rate, this method reduced the data complexity by using multiple approximations. But their technique is limited to cases where all approximations have the same mask key bits. Unfortunately, this approach imposes a very strong restriction on the approx-imations. The concept of linear hull was first announced by Xyberg in 1994. and a linear hull stands for the collection of all linear relations that have the same fixed input mask and output mask, but involves different sets of round subkeys according to different linear paths. The linear hull effect accounts for a clustering of linear paths, with the consequence that the final bias may become significantly higher than that of any individual paths. In 2009, how-ever. Murphy proved that there is no linear hull effect in linear cryptanalysis. In the same year, K. Ohkuma pointed that 32%of PRESENT keys are weak for linear cryptanalysis, and the linear bias can be much larger than the linear path value by the multi-path effect. That is to say, attacks based on weak keys exist. However, this conclusion is given under the assumption of independent linear paths. And actually, all the linear paths are dependent. So the current model is inaccurate.Well, how to build a linear cryptanalysis model based on linear hull with weak keys?The main purpose of this paper is to build a linear cryptanalysis model based on linear hull when the linear paths are dependent. And we do the following:1. Introduce the method to compute the final bias of linear hull under the dependent linear paths.2. Give a new method to compute the rate of weak keys for the given linear hull as the linear paths are dependent.3. For PRESENT, compute the rate of weak keys for 7-13 rounds linear hull by our method. Then we compare them with the result computed by Ohkuma's model, and compare the result of practical test for 7-round PRESENT.For a linear hull, the dependency of linear paths means their equivalent key bits are dependent. Here we classify all the independent equivalent key bits, and deduce the method to compute the bias of linear hull and the rate of weak keys. The main idea is described as follows,1. We find all the independent equivalent keys. which are named as in-dependent key bits. The rest equivalent keys are called dependent key bits.2. We study the distribution of the independent subkey bits on the ex-pressions of the dependent subkey bits. For a given master key, every independent subkey bit has two possible values:0 or 1, and|Γ1|= 2R.a. For a possible value ofΓ1, suppose that the number of the independent subkey bits whose values are 0 is s (s≤R), and the number of the independent subkey bits whose values are 1 is R - s. We classify the independent subkey bits into two groups according to their values. b. Consider the values of the dependent subkey bits. If there are odd number of subkey bits among the s subkey bits in the expressions of the dependent key bit kj (R