针对32位设备上Ascon密码算法的侧信道模板攻击

撰文 | 张京宇

编辑 | 刘梦迪

Ascon是一种轻量级认证加密算法，专为资源受限的环境（如物联网设备和嵌入式系统）设计。它由C. Dobraunig、M. Eichlseder、F. Mendel和M. Schläffer在2014年提出，并在NIST的轻量级密码学标准化过程中被选为标准算法。

相比于大量已发表的关于Ascon的密码分析工作，关于侧信道泄漏的实际研究相对较少。Samwel和Daemen^[1]提出了对一个20位版本的Ascon进行相关能量分析（CPA）攻击，Gross等人^[2]通过模拟泄漏显示了Ascon能够抵抗一阶差分能量分析（DPA）。Abdulgadir等人^[3]在Artix7 FPGA上实现了Ascon的阈值实现，并证明其在抵抗DPA攻击方面有效，Diehl等人^[4]比较了Ascon和其他选定认证密码的阈值实现对抗DPA的成本。

最近，Luo等人^[5]基于仿真提出了一种针对Ascon的软分析侧信道攻击（SASCA），使用8位值的汉明权重加上独立同分布的高斯噪声作为泄漏模型。尽管使用模拟的HW进行攻击可以提供有用的见解，但实际的能量波形可以通过特定值的可能性提供更多信息。然而，实际实验中需要额外的处理，例如兴趣点选择和降维，以处理更大数量的泄漏数据、更长的字大小以及可能来自实际处理流水线的相关噪声。

为了帮助评估Ascon实现的侧信道攻击风险，英国剑桥大学You等人在2023年的CHES会议上提出了一种基于能量波形的模板攻击，该攻击的目标是运行Weatherley实现方式的Ascon-128密码算法的32位STM32F303微控制器板^[6]。此外，在使用片段模板攻击的基础上，You等人还将分析其与置信传播和密钥枚举技术相结合的可能性。

2.1 Ascon

Ascon AEAD是一种基于Sponge海绵模式的轻量级带认证的加密算法，认证加密算法之所以能够对传输过程进行认证，就是因为认证加密算法在输出密文时会附带一个标签，在解密过程中，首先对标签进行验证，在同样的初始向量下如果标签一致那么证明密文在传输过程中没有被更改，具有不可否认性、完整性和机密性。Ascon-128算法的输入包括128位的密钥K、128位的随机数N、任意长度关联数据A、任意长度明/密文P/C，算法输出包括同样长度的密/明文C/P、128位的标签T。算法基本模块是320位输入输出的排列函数p，p^a代表p操作循环a=12轮。

Ascon加密过程包含以下四个主要阶段：

初始化（Initialization）：初始数据状态由初始向量IV、密钥K、公共消息N构成320位的状态S，之后算法流程的每一个步骤都是对状态S进行更新。

关联数据处理（Associated Data）：Ascon以64位作为一块的形式处理填充后的关联数据A，每块与状态S的前64位异或再经过b轮的p置换。

明/密文处理（Plaintext）：同样的，以64位作为一块的形式处理明文P，每块与状态S的前64位异或得出密文。

终止化（Finalization）：经过异或密钥、p操作步骤之后，截取状态S最后128位作为标签T输出。

Ascon整体流程

为了最小化能量波形线长度以保持波形对齐，作者选择空的关联数据和7字节的明文，整个加密过程缩短至只有两次p¹²操作。

文章中研究的Ascon流程

一轮p操作针对320位的状态S,轮函数p遵循替换置换网络（SPN）设计原则，由常数加法p_C、替换p_S和线性扩散p_L三个运算组成。在后面的部分中，作者关心的是p¹²操作的几个中间值。

关心的中间状态

2.2 模板攻击

Chari等人提出的模板攻击（TA）是一种强大的侧信道攻击技术。攻击者首先对操作目标设备进行建模，在建模过程中攻击者可以记录包括密钥在内的任何输入输出信息，同时记录能量波形以构建高斯多元噪声模板，该模板对正在处理的中间值泄漏进行建模。然后，在攻击阶段，攻击者记录设备在加密未知密钥时的能量波形，并将该能量波形与每个模板进行比较得到匹配的概率，构建概率表，根据与攻击波形最相似的候选模板来获取未知密钥。

之后涌现出许多对于模板分析的改进方式，以提高分析过程的效率和准确性。Schindler等人介绍了他们的F9“随机模型”，其中目标字节中的每个比特都被视为多元线性回归模型的自变量。Standaert和Archambeau提出在模板攻击中使用线性判别分析（LDA）来降维。Choudary和Kuhn结合了这两种技术，这种基于LDA的降维有几个好处：投影可以提高信噪比，降维可以带来更好的协方差估计，并且基于LDA的模板在不同设备之间表现出更好的可移植性。

当今许多嵌入式目标设备都使用32位总线，本文作者遵循You和Kuhn早期的片段模板攻击将32位值分成几个片段（例如，四个字节或两个16比特片段）并一次针对一个片段构建一个模板，对每个片段使用不同的LDA投影，将来自其他片段的信息视为噪声。

2.3 置信传播

由于模板攻击对噪声的敏感性，正确的候选密钥并不总是名列前茅，所以作者选择置信传播方法来提高正确率。

Veyrat-Charvillon等人介绍了软分析侧通道分析（SASCA），这是一种基于置信传播算法的密码算法模板攻击的推理技术。SASCA背后的想法是：攻击者将所有可用的概率信息都表示为因子图，其中有两种类型的节点：1）变量，表示密码算法的中间状态；2）因子，表示这些中间状态如何相互依赖。信息可以通过连接变量和因素的边双向流动。如果图是树结构，则可以通过递归遍历树、访问每条边一次来计算所有信息流。

最简单的因子图

然而，密码算法的因子图通常具有循环特征，其递归不会终止。MacKay描述了一种称为循环置信传播（loopy BP）的解决方案。主要思想是将表中所有消息的所有值初始化为1，然后交替更新表中所有信息流，并进行重新归一化以防止概率值变得太小。最后达到稳定状态时，该过程终止。

3.1 实验设置

作者使用了Weatherley的Ascon-128实现，并对其在Cortex-M4微控制器上的p操作进行了优化。使用arm-none-eabi-gcc编译器（版本9.2.1）编译，并将其上传到在侧信道分析平台ChipWhisperer-Lite上的32位微控制器STM32F303中。使用NI PXIe-5160 10位示波器以其最高采样率2.5GHz记录了的能量波形，为目标板提供5 MHz方波时钟信号。因此，在原始波形上每个时钟周期有500个采样点（500 PPC）。

采集波形条数

实验中作者采集1.6万条波进行兴趣点检测、6.4万条进行建模，使用额外的1000条波对模板质量进行检测，在攻击过程中，从1万条攻击数据集中取出几条进行多次实验。

3.2 检测兴趣时钟周期

由于原始能量波形非常长，并非所有时钟周期都与目标中间值相关，因此我们需要先找到与目标中间值明显相关的样本点，这些被称为兴趣时钟周期。

作者遵循之前寻找32位关键片段的兴趣时钟周期的方法：将所有320位的中间状态（β₋₁，α₀，...，β₁₁）分为5个64比特L₀、L₁、L₂、L₃、L₄，每个L分为两个32位，并进一步将它们分为四个字节片段（编号为0、1、2和3），然后应用多元线性回归对能量波形和每个字节上的样本之间的相关性进行建模。建立回归模型后，作者计算其决定系数R²之和，将超过阈值的视为兴趣时钟周期。

其中决定系数R²是统计学中用来衡量回归模型拟合效果的指标，越接近1表示拟合效果越好。

尖峰主要位于四个不同的区域

表明四次使用密钥K的相关时钟周期

作者提到通过观察兴趣时钟的结果，可以发现对于那些更接近p¹²输入或输出的字（即β₋₁或β₁₁），检测到了更多兴趣时钟周期，针对这些值进行建模将得到更好的攻击结果。

3.3 建模效果评估

根据2.2节的基于LDA片段模板攻击对初始化和终止化中p¹²我们关心的每个中间值进行建模后，作者使用了1000条已知密钥的波进行攻击作为对建模效果的评估。评估指标主要有两个：

1-SR（1阶成功率）：正确密钥中排名第1占所有实验的比例，即越接近1建模效果越好。

LGE（对数猜测熵）：正确候选密钥排名的期望值（1是最高排名）的对数，即越接近0建模效果越好。

模板评估

上图代表了所有目标片段模板的一阶成功率（左）和对数猜测熵（右），图中每一行代表一个中间状态（40字节共320比特），纵坐标表示我们在一次p操作中关心从β₋₁，α₀到β₁₁共25个中间值，红色块代表已知值不需要模板。

正如兴趣时钟检测章节所预测的，在p操作的开头和结尾的模板最令人满意。

3.4 应用置信传播

一旦我们从片段模板攻击匹配时得到候选值概率表，我们就可以应用置信传播，先将一次p¹²操作中所有中间值转化为因子图：

一次p¹²操作中所有中间值转化为因子图

同样可以将整个加密过程画成一张大的因子图：

整个加密过程的中间值转化为因子图

从模板评估结果可以得出，处于p¹²操作中间的片段模板仅提供很少的信息，只有开头和结尾的建模效果最好，所以使用覆盖所有中间值的大因子图来执行置信传播可能并不值得。因此，作者还尝试了另一种因子图，即从循环因子图中删除那些位于中间的节点，因子图就缩小至只有一次异或的树状图。同时，为了综合多次实验的猜测结果，可以通过一个外部约束因子f_mext连接使用相同密钥加密的多次实验。

单次加密（左）和多次加密（右）的树形因子图

4.1 不加掩码-空间优化（U-Os）

U-Os实验密钥恢复成功率

本图绘制了实验在给定搜索深度为2ⁿ的情况下进行密钥枚举后的成功率。结果表明，通过对单条波进行循环图置信传播，遍历2³²个候选密钥后将实现接近100%的成功率，并且应用树形图的置信传播将密钥枚举的成本降低到远低于2²⁰个。对于两条或多条波，则得到正确密钥几乎不需要遍历。

4.2 不加掩码-时间优化（U-O3）

之前的U-Os实验中，作者将gcc优化设置为-Os（优化空间选项），这是平台软件的默认设置。为了解编译器代码生成是否影响攻击性能，作者决定使用gcc -O3（优化时间选项）重复实验。

U-O3实验密钥恢复成功率

U-O3实验结果与上一节U-Os结果显示了一样的信息，不过与U-Os实验中非常成功的单条攻击相比，这里的效果显然更差：在作者使用16位片段的树形图进行置信传播后，大约需要搜索2²⁷个候选密钥才能实现高于50%的成功率（与之前的2²个相比），大约需要搜索2³⁶个8位片段的候选密钥（与之前的2⁴个相比）。换句话说，如果没有置信传播和密钥枚举，U-O3攻击就很难成功。

查看C源代码以及编译器生成的汇编程序列表揭示了原因。当使用gcc -Os选项进行编译时，生成的ARMv7-M汇编代码看起来与源代码所示的非常相似，它将K中的一个字节和β₁₁中的一个字节加载到32位寄存器中，对它们进行异或，并在每次迭代时存储T的一个字节。相反，如果我们要求编译器优化时间（-O3），它不仅会展开该循环，还会将其转换为仅包含四次重复操作的序列，用于加载、异或和存储32位字。换句话说，优化器将关键XOR运算的8位实现转换为32位实现。

4.3 加掩码-空间优化（M-Os）

作者继续对加一阶掩码的Ascon进行攻击，带掩码的程序将每个中间值分成两部分：一个是掩码，由基于伪随机生成器提供，另一个是中间值与掩码的异或值，根据一定的调整，树状因子图变为以下形式。

带掩码的因子图

在攻击带掩码的版本时，作者选取了与U-Os基本一样的实验条件，区别在于攻击带掩码的实验需要采集更多能量波形，并且针对每个密钥，需要重复采集100次。

M-Os实验密钥恢复成功率

可以看到，屏蔽确实在一定程度上保护了密钥K，因为与未屏蔽的实验相比，检测到的兴趣时钟周期更少，导致模板质量更低。使用单条波形的攻击并未成功，但是从使用同一密钥记录的大约5条波形开始，枚举2³⁶个候选密钥后可能会成功。

实验结果主要有三点：

(1)如果C编译器针对空间优化、不加掩码实现，从单条能量波形就达到了100%的成功率；

(2)如果编译器改为针对时间优化，则在使用3条能量波形后成功率达到95%；

(3)针对掩码版本，在使用相同密钥的20条能量波形，枚举最多2²⁴个密钥候选后，成功率能超过90%。

这些结果表明，精心设计的模板攻击对Ascon实现构成了实际威胁，同样，这个攻击程序只需少量修改也可适用于Ascon-128a。作者对一阶布尔掩码保护实验的成功表明，最初设计用于防御CPA、DPA攻击的保护可以通过精心设计的模板攻击克服。同时本文也发现编程风格的差异和编译器优化设置能显著影响结果。

[1] Samwel N, Daemen J. DPA on hardware implementations of Ascon and Keyak[C]//Proceedings of the Computing Frontiers Conference. 2017: 415-424.

[2] Gross H, Wenger E, Dobraunig C, et al. Ascon hardware implementations and side-channel evaluation[J]. Microprocessors and Microsystems, 2017, 52: 470-479.

[3] Abdulgadir A, Diehl W, Kaps J P. An open-source platform for evaluation of hardware implementations of lightweight authenticated ciphers[C]//2019 International Conference on ReConFigurable Computing and FPGAs (ReConFig). IEEE, 2019: 1-5.

[4] Diehl W, Abdulgadir A, Farahmand F, et al. Comparison of cost of protection against differential power analysis of selected authenticated ciphers[J]. Cryptography, 2018, 2(3): 26.

[5] Luo S, Wu W, Li Y, et al. An efficient soft analytical side-channel attack on ascon[C]//International Conference on Wireless Algorithms, Systems, and Applications. Cham: Springer Nature Switzerland, 2022: 389-400.

[6] You S C, Kuhn M G, Sarkar S, et al. Low trace-count template attacks on 32-bit implementations of ASCON AEAD[J]. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2023, 2023(4): 344-366.

• RILDEFENDER：一种针对智能手机短信攻击的防御方法

• 通过ICMP限速侧信道测量IPv6网络