对KATAN算法的相关密钥条件差分分析

Related-key Conditional Differential Cryptanalysis of KATAN

在2010年亚密会上,Simon Knellwolf和Willi Meier等人针对基于非线性移位寄存器设计的密码算法,提出了条件差分分析方法,随后Simon Knellwolf等人又结合相关密钥分析方法,分别攻击KATAN32/48/64算法到120轮、103轮、90轮.本文给出了一种更优的密钥差分选取算法,对原有的相关密钥条件差分分析方法进行了改进,使用该算法选取的初始密钥差分在利用明文差分和约束条件抵消后,能保证在最大的轮数内不会有新的密钥差分被引入移位寄存器,这样我们就能够在更多的轮数内对移位寄存器中差分的传递进行控制,使差分以较大偏差传递更远,进而攻击算法到更多的轮数.本文使用改进后的相关密钥条件差分分析方法,分别攻击KATAN32/48/64算法到122轮、104轮、92轮,并相应恢复出13、10、8比特密钥,攻击的计算复杂度均为233,所有的结果都能在一个可行的时间内通过实验得到.

The concept of conditional differential cryptanalysis was applied to NLFSR-based cryptosystems by Simon Knellwolf etc. at ASIACRYPT 2010. Then, they presented attacks on 120, 103 and 90 rounds of 254-round KATAN32, KATAN48 and KATAN64, respectively. This paper presents a better key-difference selecting algorithm, which improves the original related-key conditional differential cryptanalysis. This algorithm can ensure that in the maximum number of rounds, no new key difference will be injected into the shift registers after the initial key difference being eliminated by the plaintext difference and conditions. In this way we can control the difference propagation in more rounds, enabling the difference propagate farther with larger bias. Using the new related-key conditional differential cryptanalysis method, we tried to attack 122, 104 and 92 rounds of KATAN32, KATAN48 and KATAN 64 respectively, recovering 13, 10 and 8 bits of key respectively. The computational complexity of the attacks is always 233 and all the results can be verified within practical time.