Effect of the Dependent Paths in Linear Hull
Linear Hull is a phenomenon that there are a lot of linear paths with the same data mask but different key masks for a block cipher. In 1994, Nyberg presented the effect on the key-recovery attack such as Algorithm 2 with linear hull, in which the required number of the known plaintexts can be decreased compared with that in the attack using individual linear path. In 2009, Murphy proved that Nyberg's results can only be used to give a lower bound on the data complexity and will be no use on the real linear cryptanalysis. In fact, the linear hull have this kind of positive effect in linear cryptanalysis for some keys instead of the whole key space. So the linear hull can be used to improve the traditional linear cryptanalysis for some weak keys. In the same year, Ohkuma gave the linear hull analysis on PRESENT block cipher, and pointed that there are $32\%$ weak keys of PRESENT which make the bias of a given linear hull with multiple paths more than that of any individual linear path. However, Murphy and Ohkuma have not considered the dependency of the muti-path, and their results are based on the assumption that the linear paths are independent. Actually, most of the linear paths are dependent in the linear hull, and the dependency of the linear paths means the dependency of the equivalent key bits. In this paper, we will analyze the dependency of the linear paths in linear hull and present the real effect of linear hull with the dependent linear paths. Firstly, we give the relation between the bias of a linear hull and its linear paths in linear cryptanalysis. Secondly, we present the algorithm to compute the rate of weak keys corresponding to the expect bias of the linear hull. At last, we verify our algorithm by cryptanalyzing reduced-round of PRESENT. Compared with the rate of weak keys under the assumption of the independent linear paths, the dependency of the linear paths will greatly reduce the rate of weak keys for a given linear hull.