CHAM算法的安全性分析

Security Analysis of CHAM Cipher

本文主要研究基于ARX结构的轻量级分组密码CHAM算法,利用不可能差分分析、零相关线性分析对其进行安全性分析.首先,利用线性不等式组对算法的每个组件进行等价刻画,描述了差分特征和线性掩码的传播规律,建立了基于MILP(混合整数规划问题)的不可能差分和零相关线性自动化搜索模型.其次,根据CHAM算法四分支广义Feistel结构的特点,得到CHAM算法特定形式(输入或者输出差分(掩码)仅含有一个非零块)下的最长不可能差分路径和零相关线性路径具有的性质,优化了搜索策略,缩小了搜索空间.最后,利用搜索算法,遍历特定的输入输出集合,共得到CHAM-64的5条19轮不可能差分区分器,CHAM-128的1条18轮不可能差分区分器和15条19轮零相关线性区分器,均为目前公开发表的最长同类型区分器.

This paper analyzes the security of ARX structure cipher CHAM by impossible difference analysis and zero-correlation linear analysis. Firstly, each component of the cipher is characterized equivalently by using a set of linear inequalities. The propagation characteristics of the differential features and linear masks are described, then an MILP(Mixed Integer Linear Programming) impossible differential and zero-correlation linear automated search model are established. Secondly, according to the characteristics of the four-branch generalized Feistel structure of CHAM, the properties of the longest impossible differential path and zero-correlated linear path in the specific form(the input or output differential contains only one non-zero block) of CHAM are obtained, the search strategy is optimized, and the search space is reduced. Finally, by using the search algorithm, traversing a specific set of inputs and outputs, five 19-round impossible differential distinguishers of CHAM-64,one 18-round impossible differential distinguisher of CHAM-128 and fifteen 19-round zero-correlation linear distinguishers of CHAM-128 are found, they are the longest publicly available distinguishers of the same type known so far.