论文标题
在搜索ARX密码的差异轨迹时，模块化添加的非独立性：新的自动方法应用于Speck和Chaskey
Towards non-independence of modular additions in searching differential trails of ARX ciphers: new automatic methods with application to SPECK and Chaskey
论文作者
论文摘要
通过模块化添加，旋转和XOR操作构建的基于ARX的密码在轻巧对称密码的设计中引起了很多关注。对于它们的差分密码分析，大多数自动搜索方法的差异轨迹都采用了模量添加的独立性的假设。但是，当跟踪包含连续的模块化添加（CMA）时，这种假设不一定会成立。已经发现，在这种情况下，以前通过自动方法搜索的一些差异跟踪实际上是不可能的，但是该研究尚未深入，例如，很少有人付出任何努力来利用CMAS之间非独立的根本原因，并且在CMAS之间进行了非独立的概率计算。在本文中，我们致力于解决这两个问题。通过检查单个和连续模块化添加的微分方程，我们发现非独立的影响可以通过约束对两个添加的中间状态之间的关系来描述。具体而言，第一个添加的约束可能使其某些输出位不均匀，并且当它们达到第二添加的约束时，整个CMA的差异概率可能与独立假设计算的值不同。结果，我们可以构建SAT模型，以验证给定的ARX密码和#SAT模型的差分径向的有效性，以计算通过TRAIL中CMA的差分传播的确切概率，并保证对步道概率进行更准确的评估。我们的自动方法和搜索工具用于搜索Speck和Chaskey的相关键差跟踪，包括关键时间表和圆形功能中的CMA。
ARX-based ciphers, constructed by the modular addition, rotation and XOR operations, have been receiving a lot of attention in the design of lightweight symmetric ciphers. For their differential cryptanalysis, most automatic search methods of differential trails adopt the assumption of independence of modulo additions. However, this assumption does not necessarily hold when the trail includes consecutive modular additions (CMAs). It has already been found that in this case some differential trails searched by automatic methods before are actually impossible, but the study is not in depth yet, for example, few effort has been paid to exploiting the root causes of non-independence between CMAs and accurate calculation of probabilities of the valid trails. In this paper, we devote to solving these two problems. By examing the differential equations of single and consecutive modular additions, we find that the influence of non-independence can be described by relationships between constraints on the intermediate state of two additions. Specifically, constraints of the first addition can make some of its output bits non-uniform, and when they meet the constraints of the second addition, the differential probability of the whole CMA may be different from the value calculated under the independence assumption. As a result, we can build SAT models to verify the validity of a given differential trail of ARX ciphers and #SAT models to calculate the exact probabilities of the differential propagation through CMAs in the trail, promising a more accurate evaluation of probability of the trail. Our automic methods and searching tools are applied to search related-key differential trails of SPECK and Chaskey including CMAs in the key schedule and the round function respectively.
