Simpira置换的差分路线研究

李 铮，张建标，赵静远，徐万山，袁艺林

（1 北京工业大学信息学部 可信计算北京市重点实验室 北京 100022 2 中国科学院信息工程研究所 信息安全国家重点实验室 北京 100093 3 北京遥测技术研究所 北京 100094）

引 言

我们处在一个信息爆炸的时代，无论是人们日常生活中的社交网络、线上支付，还是航空航天、卫星探测等科工项目，都离不开密码算法的应用。由于加密速度快，对称密码算法在很多效率要求比较高的事务中得到了广泛的应用。

目前，对称密码算法设计进入一个相对成熟、较为稳定的发展阶段，算法结构的类型主要包括有Feistel结构、SPN（substitution permutation network）结构、ARX（modular addition，rotation and bitwisexor）结构等，而算法的置换函数是提供算法随机性的重要部件，它对于密码算法的安全性和效率等性能都十分重要。对称密码算法设计由算法结构设计和内部置换函数设计组成，但又不是一种单纯的累加，算法结构与置换函数之间的配合与相互作用也是至关重要的。对配套密码算法进行安全性分析研究，除了对于该算法本身具有评估价值之外，还可以对于算法结构和置换函数的设计与结合方式给出理论参考，对密码算法的设计也有一定的指导意义。

高级加密标准AES（Advanced Encryption Standard）[1]于2001年由NIST（National Institute of Standards and Technology）颁布，其安全性和效率经过了密码分析者和工程设计人员多年来的分析、应用和研究，实践出真知，AES至今在安全性和效率两个方面的表现仍然十分突出，应用十分广泛，现今已成为许多算法设计的标杆算法，也是相似应用方向的模板算法。其设计过程遵循宽轨道设计原则，AES经由嵌套，改造等多种方式，呈现在不同对称密码算法当中，提供着稳定可靠的性能。更因如此，AES及其相关算法的安全性研究具有十分重要的价值和意义。Simpira置换[2]是由Gueron和Nicky Mouha在2016年亚密会上提出的，是一族密码置换，其内核算法即为AES，充分利用了AES高效成熟的指令集，实现了高吞吐量。SPHINCS[3]由Bernstein等在2015年欧密会上提出，是基于哈希函数算法、具有后量子安全性的数字签名算法。后来，其设计者又将其运用到了SPHINCS当中，提出了SPHINCS-Simpira[4]，为原始的SPHINCS-256算法加快了实现速度。

1 Simpira算法介绍

Simpira置换支持128×b比特的输入，其中b是一个正整数，其设计目标是为了覆盖现有的64位存储器，实现高吞吐量，因为现有处理器已经具有AES的指令集。为了充分利用指令集，实现高吞吐量，Simpira以AES的轮函数作为唯一的构建模块，对于b=1的情形，Simpira相当于轮密钥具有固定取值的12轮AES，对于b≥2，Simpira的F函数为2轮AES，整体结构为广义Feistel结构。对于以上所有的情形，考虑进区分器的情况，设计者给出的安全界均为2128。b∈{1,2,3}时Simpira的框架图如图1所示。

本文主要研究的情形为F函数为1轮AES的情形，因此，接下来再简单介绍一下AES的轮函数，包括密钥加、S盒代换、行移位、列混合这四个步骤。这里考虑单密钥的情形，因此忽略密钥加。S盒代换操作过程如图2所示，行移位操作过程如图3所示，列混合是对状态的每一列进行线性变换，变换公式如下：

2 安全性分析相关研究

图1 Simpira的框架图（b∈{1,2,3}）[2]Fig.1 Structure of Simpira（b∈{1,2,3}）[2]

图2 AES中的S盒代换[1]Fig.2 S-box operation in AES[1]

图3 AES中的行移位[1]Fig.3 ShiftRows operation in AES[1]

密码算法的设计离不开安全性分析评估。Simpira置换支持可变的状态大小128×b比特，其中b为正整数，即为Simpira-b。鉴于差分分析和线性分析在安全性评估中的重要意义，其设计者在安全性评估中给出了最小活跃S盒个数的下界。此外，Simpira置换适用于多种功能模式，设计者提出了许多应用场景，包括Even-Mansour分组密码结构，或用于限制输入长度的哈希函数的无密钥的Davies-Meyer结构。Mendel等[5]对基于Davies-Meyer结构的哈希函数Simpira-4给出了全轮的碰撞攻击，主要基于15轮40个活跃S盒的碰撞路线。鉴于他们的研究工作，Simpira也经历了从v1版本到v2版本的改变。Rønjom等[6]发现了Simpira-4算法中的不变子空间，Zong等[7]给出了9轮Simpira-4算法的不可能差分路线。Simpira置换选取著名的AES算法作为内部函数，密码工作者在过去的二十年间持续、广泛地研究AES类算法的安全性，AES类算法的安全性分析是密码学领域的焦点问题之一，陆续有一些缩减轮数AES的区分攻击出现。区分攻击的目的在于将密码算法与随机置换区分开来，也就是找到非随机特性，使得在相应的测试中，密码算法与随机置换的测试结果具有足够不同的概率。本文发现的差分路线即为密码算法区分器的一种形式，在算法安全性要求范围内，对缩减轮数简化版本密码算法进行了分析研究。

3 差分路线研究

差分分析是密码分析中最重要的分析方法之一，寻找概率大于随机情况的差分路线，以此作为非随机特性，是差分分析的关键，概率越高，区分效果越好。一般来说，差分路线中的活跃S盒越少，则差分路线的概率越高。事实上，Simpira设计文档中也考虑了轮函数为1轮AES的情况，并给出在b=2的情况下，需要25轮来保证至少有25个线性活跃S盒。本文研究的对象就是Simpira-2的这种简化情形，算法的状态大小为256比特，整体结构为Feistel结构，其中F函数采用1轮AES。

对于这种情形，我们研究给出了4轮截断差分路线，共有6个活跃S盒，如图4所示，对应具体的4轮差分路线，概率为2–36；以及5轮截断差分路线，共有15个活跃S盒，如图5所示，对应具体的5轮差分路线，概率为2–91。在图4和图5中，灰色方块代表字节的差分非零，部分取值需满足一些约束条件；而白色方块表示该字节为全零差分。中间状态的符号表示说明，第r轮的输入状态记为Sr，第r轮的输入差分记为ΔSr，Sr中（i,j）位置的字节记为Sr[i][j]，其中r≥1，0≤i≤3，0≤j≤3。第r轮字节代换S盒的输出状态为，类似地，第r轮过程中的状态依次为输入状态，常数加、字节代换、行移位、列混合和总的输出状态，即，第r轮的输出状态，即第r+1轮的输入状态，其中

图4 4轮截断差分路线Fig.4 4-round truncated differential trail

根据Feistel结构的性质，在第1轮中，初始状态的左侧一半，共有128比特进入AES算法的S盒。为使得总体活跃S盒的个数更少，我们优先考虑了第1轮中有1个活跃S盒的情况，也就是第1轮S盒代换的输入状态中，只有1个非零S盒。首先经过第1轮的常数加和S盒代换操作，并不改变活跃S盒的个数。此外，我们选取（0,0）位置的字节作为活跃S盒，因此在第1轮中行移位操作相当于一个恒等变换，并不改变活跃S盒的个数和位置。经过第1轮的列混合操作时，其输入差分具有1个活跃S盒，输出差分具有4个活跃S盒，这里的输出状态与初始状态当中的右侧一半比特异或。因为我们可以自由地选取初始状态，所以选取初始状态右侧一半与第1轮中列混合的输出状态完全相等，这样可以抵消掉第1轮中F函数的输出差分，由此，第2轮中F函数的输入差分为零，即活跃S盒的个数为零。

第2轮中F函数的输出状态与初始状态的左侧一半比特异或，于是第3轮中F函数的输入状态与初始状态的左侧一半完全相等，可以选择第3轮中F函数的差分变换与第1轮中的情况相同，因此，第3轮中F函数的输入差分具有1个活跃S盒，输出差分具有4个活跃S盒。由于第2轮中F函数的输入差分为零，所以第4轮中F函数的输入差分与第3轮中F函数的输出差分一致。然后在第4轮中，常数加和S盒代换并不改变活跃S盒的位置和个数情况，在行移位操作之后，4个活跃S盒分布到了互不相同的列。于是，在列混合之后，第4轮F函数输出的整个差分状态中的每个S盒都活跃，实现了首次差分扩满的现象。在第4轮末尾，第4轮F函数的输出状态与第3轮F函数的输入状态异或，这里限定两状态在（0,0）位置的差分抵消。至此，给出了4轮6个活跃S盒的截断差分路线。

图5 5轮截断差分路线Fig.5 5-round truncated differential trail

具体分析第4轮F函数后异或的情况，为了使得（0,0）位置处的差分抵消，那么第3轮的输入差分与第4轮F函数的输出差分相等，即例如，列出一组可能的相关差分取值：

这里第3轮、第4轮中（0,0）位置S盒的差分概率均为2–6，其他S盒的取值不受列混合操作的限制，因此，4轮差分路线具有1+0+1+4=6个活跃S盒，概率可以达到2–36。如果由此路线出发，那么第5轮中有15个活跃S盒，由此得到的5轮截断差分路线将具有21个活跃S盒。

为寻找活跃S盒个数更少的差分路线模式，我们在截断差分路线中加入列混合中的线性约束，并选取S盒输入、输出的差分状态，进而给出具有15个活跃S盒的5轮截断差分路线，如图5所示。为使得分别为（i,j）位置S盒的输入差分和输出差分，且0≤i≤3，0≤j≤3。根据第3轮的行移位

在第4轮的F函数之后，为抵消（0,0）处的差分，需要满足在上述前提条件下，第3轮和第4轮位置S盒的输入输出情况需要特别研究，其他活跃S盒均可直接取到概率2–6。特别地，当第3轮（0,0）位置S盒的输入输出差分取值为该S盒的概率为2–6，当第4轮（0,0）位置S盒的输入输出差分取值为该S盒的概率为2–7。综上，5轮差分路线具有4+0+4+1+6=15个活跃S盒，概率可以达到2–91。

4 结束语

本文对于Simpira置换的差分路线进行了初步探索，对标准Feistel结构下简化版F函数为1轮AES的情况，给出了4、5轮截断差分路线，对应差分路线的概率分别达到2–36、2–91。高级加密标准AES的安全性和效率等性能出众，经过了多年来的分析评估、应用和研究，现今应用十分广泛，对于分组密码算法的设计具有很强的参考价值和参照意义，它在不同密码结构中的混合应用，对于AES本身和相关密码算法，比如Simpira置换，其安全性、效率等性能的评估可以相互借鉴。此外，对于相关密码算法的分析工作在数学本质上是对有限域多项式系统的研究，也是一个数学困难问题。因此，这些安全性分析工作在理论和应用方面都具有很重要的意义。