Analysis of EM Fault Injection on Bit-sliced Number Theoretic Transform Software in Dilithium
Analysis of EM Fault Injection on Bit-sliced Number Theoretic Transform Software in Dilithium
复制标题
DOI：
10.1145/3583757
复制
发表时间：
2023-03
影响因子：
2
通讯作者：
Richa Singh;Saad Islam;B. Sunar;P. Schaumont
中科院分区：
文献类型：
--
作者：
Richa Singh;Saad Islam;B. Sunar;P. Schaumont
比特切分是一种软件实现技术，它将 N 比特处理器数据通路视为 N 个并行的单比特数据通路。比特分片特别适用于实现数据并行算法，即对矢量的每个元素应用相同操作序列的算法。事实上，比特处理器指令会对每个单比特切片执行相同的逻辑运算。比特切片执行的第二个好处是，比特切片软件的天然空间冗余可支持针对故障攻击的对策。这样，N 位处理器上的 k 个冗余程序就能以 N/k 个并行冗余片的形式运行。在本文中，我们结合了比特切片的这两个优势，实现了数论变换（NTT）的故障对策。NTT 有效地实现了多项式乘法。NTT 算法的内部对称性适合数据并行实施，因此是冗余比特切分实施的理想候选方案。我们在先进的 667MHz ARM Cortex-A9 处理器上实现了冗余比特切分 NTT，并研究了在优化电磁故障注入 (EMFI) 下受保护 NTT 的故障覆盖率。我们的工作有两大贡献。首先，我们首次展示了如何开发冗余比特切片版本的 NTT。我们将受保护的 NTT 集成到完整的 Dilithium 签名序列中。其次，我们在 ARM Cortex-M9 上演示了 Dilithium 签名序列原型实施的 EMFI 分析。我们进行了详细的电磁故障注入参数搜索，以优化注入电磁脉冲的位置、强度和时间。我们证明，在优化的故障注入参数下，约 10% 的注入故障具有潜在的可利用性。然而，即使 Dilithium 算法的其余部分和控制流未受保护，冗余比特切片 NTT 设计也能捕捉到这些可能被利用的故障中的大部分。据我们所知，这是首次展示在整个算法执行过程中提供分布式故障检测的比特片冗余 NTT 设计。
Bitslicing is a software implementation technique that treats an N-bit processor datapath as N parallel single-bit datapaths. Bitslicing is particularly useful to implement data-parallel algorithms, algorithms that apply the same operation sequence to every element of a vector. Indeed, a bit-wise processor instruction applies the same logical operation to every single-bit slice. A second benefit of bitsliced execution is that the natural spatial redundancy of bitsliced software can support countermeasures against fault attacks. A k-redundant program on an N-bit processor then runs as N/k parallel redundant slices. In this contribution, we combine these two benefits of bitslicing to implement a fault countermeasure for the number-theoretic transform (NTT). The NTT efficiently implements a polynomial multiplication. The internal symmetry of the NTT algorithm lends itself to a data-parallel implementation, and hence it is a good candidate for the redundantly bitsliced implementation. We implement a redundantly bitsliced NTT on an advanced 667MHz ARM Cortex-A9 processor, and study the fault coverage for the protected NTT under optimized electromagnetic fault injection (EMFI). Our work brings two major contributions. First, we show for the first time how to develop a redundantly bitsliced version of the NTT. We integrate the protected NTT into a full Dilithium signature sequence. Second, we demonstrate an EMFI analysis on a prototype implementation of the Dilithium signature sequence on ARM Cortex-M9. We perform a detailed EM fault-injection parameter search to optimize the location, intensity and timing of injected EM pulses. We demonstrate that, under optimized fault injection parameters, about 10% of the injected faults become potentially exploitable. However, the redundantly bitsliced NTT design is able to catch the majority of these potentially exploitable faults, even when the remainder of the Dilithium algorithm as well as the control flow is left unprotected. To our knowledge, this is the first demonstration of a bitslice-redundant design of the NTT that offers distributed fault detection throughout the execution of the algorithm.