ARX结构密码算法差分分析中模加运算的非独立性

Abstract

ARX结构密码算法由模加运算、循环移位和异或运算三部分组成，近年来在轻量级密码算法的设计上受到很多的关注。在对于该类算法的异或差分和循环移位-异或差分分析中，通常假设路径中各模加运算的差分传播相互独立，然而当两个模加运算串联或者并联时，这一假设并不一定成立。本文主要研究模加运算在异或差分传播和循环移位-异或差分传播中的非独立性，通过推导这两种差分在模加运算上的传播公式，我们发现由非独立性带来的影响可以通过比较串联或者并联模加对中间状态的差分约束条件来进行刻画。在此基础上，本文提出了一种快速验证差分路径有效性的SAT方法，并将其应用于三种含串联和并联模加的ARX结构算法。对于含串联模加的SipHash算法，本文通过验证发现Xin等人在CANS 2019上提出的两条差分碰撞路径和一条循环移位-异或差分碰撞路径均为不可能差分路径。对于含并联模加的Ballet算法，本文搜索得到Ballet-128/128的一条有效的7轮最优异或差分路径，并将其扩展得到概率为2^(-52)的9轮次优差分路径。此外，基于Liu等人使用4个并联模加构造的一个非线性函数，本文构建了一个含并联模加的典型ARX结构算法，进而在考虑模加非独立性的情况下对其差分攻击安全性进行了初步分析。