LDPC Strikes Again: New Key-Recovery Chosen-Ciphertext Side-Channel Attacks on NTRU-based KEMs
Xiaofei Tong, Denis Nabokov, Qian Guo · 2025
In this work, we introduce novel techniques for adapting the SCA-LDPC framework to conduct efficient plaintext-checking (PC) oracle-based side-channel attacks on NTRU-style Key Encapsulation Mechanisms (KEMs). We specifically address the unique algebraic structure of the NTRU and NTRU Prime schemes, demonstrating how to extract information related to secret variables from side channels and modeled as Low-Density Parity-Check (LDPC) codes. Then, we can recover the complete secret key using an iterative decoding method. For both NTRU and NTRU Prime schemes, our approach achieves significant reductions in the required number of measurements compared to previous state-of-the-art under similar oracle noise assumptions, validated through extensive simulations, and exhibits robustness against decision errors in the constructed oracle. Furthermore, we present the first documented power analysis attack targeting a first-order masked NTRU implementation. Using standard microcontroller hardware (ARM Cortex-M4), we successfully constructed a PC oracle achieving a low 0.5% decision error rate; importantly, within a practical cross-device setting where training and attack devices differ. Our experimental results demonstrate that approximately 1250 side-channel measurements are sufficient to recover the secret key in this challenging scenario, closely aligning with our simulation findings. These results underscore the vulnerability of first-order masking for NTRU against this attack vector and motivate the thorough evaluation of higher-order countermeasures.