Alzette的安全性分析  

Security Analysis of Alzette

作　　者：许峥 李永强[1,2] 王明生 XU Zheng;LI Yong-Qiang;WANG Ming-Sheng(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)

机构地区：[1]中国科学院信息工程研究所信息安全国家重点实验室,北京100093 [2]中国科学院大学网络空间安全学院,北京100049

出　　处：《密码学报》2022年第4期698-708,共11页Journal of Cryptologic Research

基　　金：国家自然科学基金(61772516,61772517)。

摘　　要：本文研究了Alzette(2020年美密会议上提出的ARX结构S盒)抗差分类分析的安全性.首先,对于模加操作上的有效异或差分,通过利用符号差分的概念,本文给出了符号差分比特之间关系的比特向量表示.其次,通过将Lipmaa-Moriai限制条件以及符号差分比特约束条件转化为SMT问题,本文提出了一种基于SAT/SMT求解器的ARX结构不可能差分区分器自动化搜索工具.该自动化工具是首个利用Lipmaa-Moriai限制条件以及符号差分搜索ARX结构不可能差分区分器的自动化工具.利用该工具可以发现被传统搜索方法忽略的有效的不可能差分区分器.最后,通过利用新的自动化工具以及传统方法搜索Alzette的不可能差分区分器,在输入差分汉明重量为2、输出差分汉明重量为1的条件下,我们分别发现了128993个和128767个不可能差分区分器,证明新的自动化工具能够更好地过滤无效差分路径;此外,将新的自动化搜索工具用于搜索4轮无密钥注入SPECK64不可能差分区分器,在输入差分汉明重量为2、输出差分汉明重量为1的条件下,我们发现了128976个不可能差分区分器,说明Alzette设计团队的安全性评估是不够全面的.据我们所知,这是首次利用不可能差分性质评估Alzette的安全性.This paper studies the security of Alzette(a 64-bit ARX-based S-box proposed at CRYPTO 2020)against differential-like cryptanalysis.Firstly,for a valid XOR differential over a modulo addition,the bit-vector representation of the relations between signed differential bits is given by using the concept of signed differences.Secondly,by converting Lipmaa-Moriai constraints and the constraints between signed differential bits into SMT problems,a SAT/SMT-based automatic search tool is proposed for impossible differential distinguishers in ARX structures.The automatic tool is the first tool to use Lipmaa-Moriai constraints and signed differences to automatically search for impossible differential distinguishers in ARX structures.This tool can find valid impossible differential distinguishers that are ignored by traditional search methods.Finally,impossible differential distinguishers for Alzette are searched by using the proposed automatic tool and traditional methods,and 128993and 128767 impossible differential distinguishers with wt(InD)=2 and wt(OutD)=1 are found,which means that the new automatic tool can better filter invalid differential characteristics.Moreover,by searching impossible differential distinguishers for 4-round no-key SPECK64 using the proposed automatic tool,128976 impossible differential distinguishers with wt(InD)=2 and wt(OutD)=1 are found,which means that the security assessment of Alzette’s design team is not comprehensive enough.To the best of our knowledge,this is the first time that the impossible differential property is used to evaluate the security of Alzette.

关 键 词：Lipmaa-Moriai限制条件 符号差分 不可能差分 Alzette SAT/SMT求解器 

分 类 号：TP309.7[自动化与计算机技术—计算机系统结构]