期刊文献+

SIMON算法相关密钥不可能差分特征搜索 被引量:1

Searching for Related-Key Impossible Differentials for SIMON
下载PDF
导出
摘要 本文通过求解SIMON算法密钥扩展算法的混合整数线性规划(mixed-integer linear programming,MILP)模型,首次给出其相关密钥不可能差分分析结果.对分组密码算法的不可能差分特征搜索一般是限制输入输出差分均只有1比特或1个S盒活跃,在此基础上遍历求解,如果其MILP模型无解,则得到一条不可能差分特征.而SIMON算法采用线性密钥扩展算法,主密钥差分确定之后每一轮的子密钥差分都随之确定,无法控制其随轮数增加而逐渐扩散,所以限制其输入输出差分并不能得到最长路径.而遍历所有可能的复杂度高达O(2^((m+2)n)),其中n,m取值与SIMON2n/mn相同.当前计算能力无法达到,这也是在此之前一直没有SIMON相关密钥不可能差分分析结果的原因.本文通过研究SIMON算法中ROTATION-AND操作中概率为1的差分传播性质,结合截断差分路径给出满足miss-in-the-middle条件时,子密钥差分需满足的约束条件.通过对密钥扩展算法的MILP模型及约束条件求解,如果有解则得到一条相关密钥不可能差分特征.本文首次给出SIMON32/64和SIMON48/96的13轮相关密钥不可能差分特征,在此前研究结果中其单密钥下最长路径分别为11和12轮. This paper presents related-key impossible differentials for SIMON block ciphers by solving MILP(mixed-integer linear programming)models of the key schedules.For block ciphers,it is necessary to limit the input/output differences with only one active bit for searching impossible differentials,which needs to traverse all the input/output differences.If the MILP model is infeasible,there is an impossible differential characteristic.Nevertheless,the key schedules of SIMON are linear;once the difference of the master key is given,the difference of subkeys of each round is determined.It is not possible to get long related-key impossible differential trails for SIMON with the 1-bit constraint since the number of active bits is not increasing with the number of rounds.There has not been any related-key results for SIMON before since the complexity of traversing is O(^(2(m+2)n))(the value of n,m is the same as SIMON2n/mn)which is far beyond the computing power.This paper studies the difference diffusion property of the ROTATION-AND operation with probability one,and obtain the constraints for key schedules of SIMON by applying the miss-in-the-middle technique.By solving the MILP models of key schedules and their constraints,if one model is feasible,there is a related-key impossible differential characteristic.This paper found 13-round related-key impossible differentials for SIMON32/64 and SIMON48/96 respectively,while the best results in the single-key setting are 11 and 12 rounds respectively.
作者 王旭姿 吴保峰 侯林 林东岱 WANG Xu-Zi;WU Bao-Feng;HOU Lin;LIN Dong-Dai(State Key Laboratory of Information Security,Institute of Information Engineering,Chinese Academy of Sciences,Beijing 100093,China;School of Cyber Security,University of Chinese Academy of Sciences,Beijing 100049,China)
出处 《密码学报》 CSCD 2021年第5期881-893,共13页 Journal of Cryptologic Research
基金 国家自然科学基金(61972393)。
关键词 SIMON算法 相关密钥不可能差分特征 截断差分 SIMON related-key impossible differentials truncated differentials
  • 相关文献

同被引文献5

引证文献1

二级引证文献4

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部