| 摘要: |
| ARX结构密码算法由模加运算、循环移位和异或运算三部分组成，近年来在轻量级密码算法的设计上受到很多的关注。在对于该类算法的异或差分和循环移位-异或差分分析中，通常假设路径中各模加运算的差分传播相互独立，然而当两个模加运算串联或者并联时，这一假设并不一定成立。本文主要研究模加运算在异或差分传播和循环移位-异或差分传播中的非独立性，通过推导这两种差分在模加运算上的传播公式，我们发现由非独立性带来的影响可以通过比较串联或者并联模加对中间状态的差分约束条件来进行刻画。在此基础上，本文提出了一种快速验证差分路径有效性的SAT方法，并将其应用于三种含串联和并联模加的ARX结构算法。对于含串联模加的SipHash算法，本文通过验证发现Xin等人在CANS 2019上提出的两条差分碰撞路径和一条循环移位-异或差分碰撞路径均为不可能差分路径。对于含并联模加的Ballet算法，本文搜索得到Ballet-128/128的一条有效的7轮最优异或差分路径，并将其扩展得到概率为2^(-52)的9轮次优差分路径。此外，基于Liu等人使用4个并联模加构造的一个非线性函数，本文构建了一个含并联模加的典型ARX结构算法，进而在考虑模加非独立性的情况下对其差分攻击安全性进行了初步分析。 |
| 关键词: ARX结构算法 模加运算 差分分析 循环移位-异或差分分析 SAT SipHash Ballet |
| DOI： |
| 投稿时间：2022-02-11修订日期：2022-04-07 |
| 基金项目:国家自然科学基金项目（面上项目，重点项目，重大项目）; 中国科学院信息工程研究所攀登计划 |
|
| Towards Non-independence of Modular Addition in Dif-ferential Cryptanalysis of ARX-based Ciphers |
|
Qinhaiwen, WuBaoFeng
|
| (State Key Laboratory Of Information Security, Institute of Information Engineering, Chinese Academy of Sciences) |
| Abstract: |
| ARX-based ciphers, constructed by modular addition, rotation and XOR operations, have been receiving more and more attentions in the design of lightweight symmetric ciphers in recent years. In the current framework of differential crypta-nalysis and Rotational-XOR (RX) cryptanalysis of such kinds of ciphers, the independence assumption is often adopted, that is, the propagation of differentials or RX differentials through different modular addition operations in a cipher are often assumed to be independent. However, when there are consecutive or parallel modular additions in the cipher, this assumption does not necessarily hold. In this paper, we study the non-independence of modular additions in the propaga-tion of differentials and RX differentials. By deriving the differential equations of a modular addition under these two kinds of differentials, we find the influence of non-independence can be described by relationships between the differen-tial constraints on the inputs and output of the modular addition. Based on this, we introduce a SAT-based method to ver-ify the validity of differential and RX characteristics and apply it to three typical ARX ciphers with consecutive or parallel modular additions. For SipHash, which consists consecutive modular additions in the round function, we find the differen-tial characteristics and RX differential characteristics found by Xin et al. at CANS 2019 are all invalid due to incompatible differential constraints of consecutive modular additions. For Ballet-128/128, which consists parallel modular additions in the round function, we find the valid optimal differential characteristic of 7 rounds and extend it to a valid 9 round char-acteristic with probability 2-52. In addition, we construct a new ARX cipher, the core component of whose round functions is adopted from the nonlinear diffusion function designed by Liu et al. in DCC 2018, which is composed of four parallel modulo additions. We give elementary analysis of its security under differential attacks with the consideration of non-independence of modular additions. |
| Key words: ARX cipher Modular addition differential cryptanalysis Rotational-XOR cryptanalysis SAT SipHash Ballet |
