RAFA：破解密码芯片侧信道防护的新武器

撰文 | 乔　晗

编辑 | 刘梦迪

代数故障分析（AFA）是一种结合代数分析与故障注入的密码攻击技术。其基本原理是通过故障注入制造加密过程中的异常数据，并利用代数方法分析这些数据，从而推导出密码的密钥。然而，由于重量级分组密码算法（如AES-128）代数系统的复杂性，AFA在这些密码上的应用效率受限。

近年来，随着硬件性能的提升和SAT求解器技术的发展，AFA逐渐显现出其对轻量级密码强大的破解能力。然而，对于AES-128等重量级密码，传统AFA方法往往因求解时间过长而失去实用性。在2023年的TCHES会议上，来自浙江大学的研究团队提出了一种名为冗余辅助代数故障分析（RAFA）的新方法^[1]。RAFA通过引入冗余约束和线性化策略，显著提升了代数系统的求解效率，使其能够在单次故障注入的情况下破解AES-128等重量级密码算法。

传统AFA可以分为三步，第一步为密码算法方程组的构建。即将AES的加密过程表示为一组代数方程，这些方程描述了密钥、明文、中间状态和密文之间的关系。第二步为故障注入及利用。即注入故障后，根据差分故障攻击可以得到∆𝐶和∆𝑋之间的约束方程。第三步为代数方程组求解。结合约束方程和密码算法方程组，减少解空间，进而求解正确密钥。

RAFA的核心思想是通过修改代数系统，提升SAT求解器的效率。具体而言，RAFA包含以下三个关键技术：

1、冗余约束的引入：除了传统的正向约束（从明文到密文的加密过程），还引入了逆向约束（从密文到明文的解密过程）。这使得求解时能够在两个方向上进行推理，从而更快地找到解。同时，利用故障传播路径中的中间状态来建立更多的冗余约束方程，帮助减少代数系统的解空间。换句话说，通过对AES-128等密码的故障传播路径和SPN结构进行分析，RAFA为代数系统添加了额外的冗余约束。这些约束不仅加速了SAT求解器的冲突检测，还提高了单位传播效率。

AFA流程图

2、非线性代数标准形式（ANF）的高级线性化：RAFA采用了包括n-Partner策略在内的多种线性化技术，将复杂的非线性代数方程转化为更易处理的线性方程，从而显著减少了辅助变量和生成约束的长度。这种方法不仅在理论上降低了代数系统的复杂性，还在实验中表现出卓越的性能提升。

3、前向-后向约束的结合：RAFA通过结合加密和解密的代数表示，强化了代数系统中变量间的推理能力。这种前后结合的策略，使得SAT求解器能够更高效地定位密钥候选解。

从第8 轮行移位开始的故障传播图

以在第八轮行移位的输出注入故障为例，RAFA利用传播路径构建冗余约束方程。

下图展示了AES算法提供前k个字节，使用RAFA恢复密钥所需要的对数运行时间。

不同k下RAFA耗时

下面表格展示了RAFA相对于AFA算法的加速比。 加速比表示相同k的情况下RAFA相较于AFA的速度提升比。例如，表1中的“加速比”36999.61是通过商81399.14/2.20计算的。结果表明，针对AES分组密码，RAFA相对于AFA算法有显著的改进。

RAFA v.s. AFA 在13≤ k ≤ 15

此外在其他分组密码Serpent以及SPEEDY上，RAFA依然展示出更高的效率。如下图所示，RAFA在Serpent-256上的性能明显优于AFA。此外，RAFA仅使用三次故障，就能在合理的时间内恢复出Serpent-256的主密钥。

RAFA v.s. AFA 在 Serpent-256

RAFA 在 SPEEDY-r-192 上表现出比 AFA 显着的提升效果。 此外，使用三个故障，RAFA 就能够有效地恢复 SPEEDY-r-192 的主密钥。实验结果如下图所示。

RAFA v.s. AFA 在 SPEEDY-r-192

RAFA是一种通用且高效的代数故障分析框架，在本文中，通过引入冗余约束和高级线性化策略，显著提升了重量级分组密码的破解效率。相比传统AFA方法，RAFA在处理复杂密码时展现了更高的灵活性和效率。实验结果表明，RAFA在AES-128、Serpent-256等密码算法上的性能远优于传统方法，为未来的密码分析研究提供了新思路。此外，RAFA的设计理念还为SAT求解器的优化提供了新的启发。

[1] Zhang F, Feng T, Gong X. RAFA: Redundancies-assisted Algebraic Fault Analysis and its implementation on SPN block ciphers[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023, 2023(3): 570-596.

• 通过在感知通信信道上注入电磁干扰信号使无人机瘫痪

• SEV-Step：一种针对AMD-SEV分析的单步执行框架

• 基于深度学习的侧信道分析模型EstraNet