An End-to-End Analysis of EMFI on Bit-sliced Post-Quantum Implementations

Abstract

Bit-slicing is a software implementation technique that treats an N-bit processor datapath as N parallel single-bit datapaths. The natural spatial redundancy of bit-sliced software can be used to build countermeasures against implementation attacks. While the merits of bit-slicing for side-channel countermeasures have been studied before, their application for protection of post-quantum algorithms against fault injection is still unexplored. We present an end-to-end analysis of the efficacy of bit-slicing to detect and thwart electromagnetic fault injection (EMFI) attacks on post-quantum cryptography (PQC). We study Dilithium, a digital signature finalist of the NIST PQC competition. We present a bit-slice-redundant design for the Number-Theoretic Transform (NTT), the most complex and compute-intensive component in Dilithium. We show a data-redundant countermeasure for NTT which offers two concurrent bits for every single bit in the original implementation. We then implement a full Dilithium signature sequence on a 667 MHz ARM Cortex-A9 processor integrated in a Xilinx Zynq SoC. 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 bit-sliced 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 Dilithium that offers distributed fault detection throughout the execution of the algorithm. Countermeasure, ARM Cortex-A9, Electromagnetic Fault Injection ACM Reference Format: Sunar, and Patrick Schaumont. 2022. An End-to-End Analysis of EMFI on Bit-sliced Post-Quantum Implementations. ACM Trans. Embedd. Comput. Syst. 1, 1 (April 2022), 28 pages. using a general purpose IO pin of the target. The test program running on the target sets this trigger signal high just before the beginning of attack window and then sets the trigger signal low after the window ends. The test program used for all the experiments is open-source reference C implementation of Dilithium Round 3 version integrated with our countermeasure. This implementation was compiled with the arm-none-eabi-gcc-9.2.0 using compiler flags -mcpu=cortex-a9 -mfpu=neon-vfpv3 -mfloat-abi=hard -O0 . For every fault injection, the test program sends a fault response and complete signature at the end of execution to the PC over UART for faults classification.