Alzette的安全性分析

Security Analysis of Alzette

本文研究了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.