对16轮PRESENT算法差分分析的改进

Improved Differential Attack on 16-round PRESENT Cipher

PRESENT算法是一个SPN结构的轻量级分组密码算法,适用于计算资源有限的环境与设备.差分分析是攻击分组密码最为基本和有效的方法之一,对于迭代31轮的PRESENT算法,目前最好的差分分析结果是16轮,使用明文全空间2^(64)个选择明文.本文在原有差分分析结果的基础上,根据线性P置换的扩散性质,得出在相邻两轮中活动S盒的数目与S盒差分值的汉明重量之间的关系.搜索差分路径时取不同位置的活动S盒,比较6轮差分路径的结果,在得到最多结果的位置上寻找14轮概率为2^(-62)的差分路径,从解密方向找到119个,从加密方向找到28个.在成功率为99%的情况下,将16轮多差分输入值-单差分输出值分析结果的数据量由原来的2^(64)个选择明文降低到2^(59.16)个,时间复杂度由原来的2^(64)次内存访问降低到2^(59.16)次,存储复杂度由原来的2^(32)个6比特计数器降低到2^(32)个3比特计数器.同时给出单差分输入值-多差分输出值的差分分析结果,数据量为2^(61.16)个选择密文,时间复杂度为2^(61.16)次内存访问,存储复杂度为2^(32)个4比特计数器.

PRESENT is an SPN structured lightweight block cipher and aims to the constrained resources environment. Differential analysis is one of the most effective methods of attacking block ciphers. PRESENT cipher is a block cipher which iterates for 31 rounds, the best differential analysis result on it is 16 rounds, with 2^(64) chosen plaintexts of the whole plaintext space. In this paper, based on the previous analysis results, by analyzing the diffusion property of the linear transformation P-Layer, the relationship between the number of active S-boxes and the hamming weight of active S-boxes' difference in two joint rounds is presented. Based on the observation of the results of 6-round differential characteristics in different position, 119 of 14-round differential characteristics with probability of 2^(-62) in decryption direction and 28 in encryption direction are found, which lead to a differential attack on 16-round PRESENT. With the success probability 99%, our multiple-inputs-and-single-output differential cryptanalysis reduces the data complexity from 2^(64) chosen plaintexts to 2^(59.16), reduces the time complexity from 2^(64) memory accesses to 2^(59.16), and reduces the memory complexity from 2^(32) 6-bit counters to 2^(32) 3-bit counters. Finally, a single-inputs-and-multiple-output differential cryptanalysis is proposed, using 2^(61.16) chosen plaintexts, 2^(32) 4-bit counters, and 2^(61.16) memory accesses.