认证加密算法SUNDAE-GIFT 的故障分析

朱晓铭

（东华大学 计算机科学与技术学院，上海 201620）

0 引言

随着信息产业的快速发展，一些软硬件资源受限的设备，如射频识别标签和智能卡等，正在广泛应用于智能农业、智慧医疗、智慧建筑等生活领域，需要密码保护的范围也因此变得更加广阔［1］。但是早期的认证工作模式由于对资源有较高的要求，不再适用于资源受限的设备中。轻量级的认证加密算法在保证数据机密性、完整性和消息鉴别功能的基础上，又降低了对资源的需求，因此受到国内外学者的高度关注，不同模式的轻量级认证加密算法的设计与分析成为研究的重点［2］。

SUNDAE-GIFT 是由Banik 等学者提出的基于SUNDAE（Small Universal Deterministic Authenticated Encryption）模式，并采用GIFT-128 为底层分组密码的轻量级认证加密算法，入选美国国家标准与技术研究院（NIST）启动的轻量级密码标准化项目的第二轮评选［3］。相较于PRESENT，轻量级密码GIFT更加安全和高效，甚至优于轻量级密码SKINNY 和SIMON［4］。相较于传统的认证加密模式，SUNDAEGIFT 具有低功耗，高效率等特点，适合RFID 和智能卡网络等资源受限设备。

1997 年，Boech 等学者首次利用故障分析破译RSA 算法［5］。后来，通过结合传统密码分析和故障分析，逐渐衍生出差分故障攻击、不可能故障分析、代数故障分析和统计故障分析等分析方法，具备不同的分析优势［6］。目前，故障分析已经成为对密码进行安全性分析的重要方法。

自从SUNDAE-GIFT 被提出以来，已经有学者利用故障分析研究其安全性。2021 年，Sun 等［7］对SUNDAE-GIFT 进行了17 轮的线性故障分析，成功破译了128 比特的主密钥；同年，Liu 等［8］使用碰撞故障分析，仅以128 个错误密文恢复密钥。

2013 年，Fuhr 等［6］首次提出了针对AES 密码算法的统计故障分析；2016 年，Dobraunig 等［9］提出了针对基于随机数的认证加密算法模式的统计故障分析思想；2017 年，Li 等［10］首次针对轻量级分组算法LED 统计故障分析；2018 年，Ramezanpour 等［11］首次通过统计故障分析对认证加密算法进行安全性分析。本文对SUNDAE-GIFT 进行了统计故障分析，证明了分组密码工作模式类的认证加密算法存在设计上的安全问题，为轻量级认证加密算法的安全设计提供了重要思路。故障分析的结果对比见表1，表明SUNDAE-GIFT 在故障数方面更具优势。

表1 统计故障分析破译部分子密钥的结果对比Tab.1 Comparison of statistical fault analysis on a partial subkey

1 SUNDAE-GIFT 算法

1.1 符号说明

记SC、SC-1为S盒和S盒的逆，PB、PB-1为P置换和P置换的逆，ARK为子密钥加；

1.2 SUNDAE-GIFT 密码

SUNDAE-GIFT 是以GIFT-128 为底层密码的SUNDAE 结构的认证加密算法。输入包括初始块B、关联数据A、明文M和密钥K，输出包含标签T和密文C，分组长度为128 比特，算法结构如图1 所示。

图1 认证加密算法SUNDAE-GIFT 结构Fig.1 The structure of authenticated encryption algorithm SUNDAE-GIFT

GIFT 是一种SPN 结构的轻量级分组密码。GIFT-128 是其中的一个版本，其密钥长度为128 位，分组长度为128，轮数为40 轮，每一轮的轮函数包括S盒、P置换和轮密钥加，算法结构如图2 所示。

图2 GIFT-128 算法结构Fig.2 The structure of GIFT-128

1.3 故障模型

本文采取的故障模型是半字节随机“与”故障模型，通过在加密过程中的某一轮注入半字节随机“与”故障，影响中间状态值的分布律产生偏移，而不注入故障的中间状态值的分布律呈现均匀分布。半字节中间状态在注入故障后理论分布律如图3 所示。

图3 半字节的理论分布律Fig.3 The theoretical distribution of a nibble

1.4 攻击步骤

本文使用统计故障分析破译SUNDAE-GIFT 算法的主密钥，主要包括以下步骤：

步骤1故障注入。攻击者在生成密文阶段通过在底层密码GIFT-128 的第39 轮注入随机“与”故障，使半字节中间状态值的分布律产生偏移，最后故障扩散并生成错误标签，故障扩散路径如图4 所示。攻击者在故障扩散后收集错误密文样本，为后续的密钥破译提供数据基础。

图4 SUNDAE-GIFT 的故障扩散路径Fig.4 Fault diffusion path of SUNDAE-GIFT

步骤2计算中间状态值。攻击者依据公式（1）逆推错误标签样本集，穷举最后两轮子密钥中的10 比特作为候选密钥值样本集，解密计算得出半字节错误中间状态样本集合为

步骤3区分器选取。攻击者按照步骤1、2 操作，取得候选密钥和对应的半字节错误中间状态样本集，并通过区分器进行统计分析，筛选出实验分布律最接近理论分布律的半字节错误中间状态所对应的密钥候选值，即正确子密钥。

步骤4主密钥恢复。重复步骤1～步骤3，直至破译RK39和RK40的全部比特。再依据公式（2）和公式（3）中的密钥编排方案恢复主密钥。

1.5 区分器

区分器主要用于计算样本集的分布律，利用统计学的知识对样本集进行分析并筛选出正确密钥。本文采用Fuhr 等［6］统计故障分析AES 时使用的SEI、HW 和MLE 3 个区分器对SUNDAE-GIFT 算法进行分析。3 个区分器对应的公式和选取的极值见表2。

表2 不同区分器的计算公式和所取极值Tab.2 The formulas and extreme values of different distinguishers

2 实验分析

本文实验利用计算机软件模拟随机故障导入，使用Java 语言编程进行分析。本文基于成功率、故障数、耗时和复杂度等指标评测不同区分器和两种故障分析方法的效果。

2.1 成功率

成功率是指不同区分器破译密码的概率。各个区分器恢复10 比特子密钥时，不同故障数对应的成功率如图5 所示，3 个区分器均能够在故障数少于50 时，成功率达到100%。

图5 不同区分器恢复部分子密钥的成功率Fig.5 The probability of recovering a partial sub key with different distinguishers

2.2 故障数

故障数是指不同区分器以最大概率破译密码所需最少故障数。统计故障分析在恢复SUNDAEGIFT 密码主密钥时的故障数见表3，SEI、HW 和MLE 3 个区分器的故障数分别为768、576 和608。

表3 不同区分器破译主密钥的故障数Tab.3 The faults of breaking the master key with different distinguishers

2.3 耗时

耗时是指破译SUNDAE-GIFT 算法所需要的时间，包括故障导入、密钥猜测和统计分析等过程。采用各个区分器恢复子密钥时，不同故障数对应的时间如图6 所示。其中，横轴与纵轴分别表示故障数和时间堆积。当成功率达到最高时，SEI、HW 和MLE 的耗时分别为7.98、5.80 和6.13 s。

图6 不同区分器恢复部分子密钥的耗时Fig.6 The time of recovering a partial subkey with different distinguishers

2.4 复杂度

复杂度是指破译SUNDAE-GIFT 算法主密钥所需的时间复杂度和数据复杂度，用于衡量统计故障分析的效率和占用的资源。不同区分器在破译SUNDAE-GIFT 时的时间复杂度和数据复杂度见表4，均表现优秀，其中F表示故障数，S表示密钥搜索空间且S ＝210。

表4 不同区分器破译主密钥的复杂度Tab.4 The complexity of breaking the master key with different distinguishers

3 结束语

本文实现了针对SUNDAE-GIFT 认证加密算法的统计故障分析，是首次针对分组密码工作模式类的认证加密算法的统计故障分析。实验结果表明，统计故障分析对SUNDAE-GIFT 认证加密密码具有较大威胁性。在物联网中使用SUNDAE-GIFT 时，应考虑对密码加以更多保护，该结果为轻量级认证加密算法抵御故障分析提供了有价值的参考。