Paper 2021/718

Will You Cross the Threshold for Me? - Generic Side-Channel Assisted Chosen-Ciphertext Attacks on NTRU-based KEMs

Prasanna Ravi and Martianus Frederic Ezerman and Shivam Bhasin and Anupam Chattopadhyay and Sujoy Sinha Roy

Abstract

In this work, we propose generic and novel side-channel assisted chosen-ciphertext attacks for NTRU-based Key Encapsulation Mechanisms (KEM) secure in the chosen ciphertext model (IND-CCA security). Our attacks involve construction of malformed ciphertexts which, when decapsulated by the target device, ensure that a targeted intermediate variable has a very close relation with the secret key. Subsequently, an attacker who can obtain information about the secret-dependent variable through side-channels, can recover the full secret key. We propose several novel CCAs which can be carried through instantiating three different types of oracles, namely plaintext-checking oracle, decryption-failure oracle, and full-decryption oracle, using side-channel leakage from the decapsulation procedure. Our proposed attacks are applicable to two NTRU-based schemes: NTRU and NTRU Prime. The two schemes are candidates in the ongoing NIST standardization process for post-quantum cryptography. We perform experimental validation of our proposed attacks on optimized implementations of NTRU-based schemes taken from the open-source pqm4 library, using the EM-based side-channel on the 32-bit ARM Cortex-M4 microcontroller. All our proposed attacks are capable of recovering the full secret key in only a few thousand chosen ciphertext queries to the target device on all parameter sets of NTRU and NTRU Prime. Our attacks therefore stress on the need for concrete protection strategies for NTRU-based KEMs.