Paper 2010/325

Effect of the Dependent Paths in Linear Hull

Zhenli Dai and Meiqin Wang and Yue Sun

Abstract

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, K. 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 an individual linear path. In 2009, S. Murphy proved that K. 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 produces such positive effect in linear cryptanalysis only for some keys instead of the whole key space. So the linear hull can be used to improve the classic linear cryptanalysis for some weak keys. In the same year, K. Ohkuma gave the linear hull analysis on reduced-round PRESENT block cipher, and showed that there are $32\%$ weak keys of PRESENT which make the bias of a given linear hull with multiple paths more than a lower bound. However, K. Ohkuma has not considered the dependency of the multi-path, and his results are based on the assumption that the linear paths are independent. Actually, most of the linear paths are dependent in the linear hull. In this paper, we will analyze the dependency of the linear paths in a linear hull and 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 formula to compute the rate of weak keys corresponding to the expected bias of the dependent paths. Based on the formula, we show that the dependency of linear paths reduces the number of weak keys corresponding to higher biases of the linear hull compared with that in the independent case. It means that the dependency of linear paths reduces the effect of linear hull. At last, we verify our conclusion by analyzing reduced-round of PRESENT.