Prasanna Ravi
Temasek Labs and School of Computer Science and Engineering, Nanyang Technological University, Singapore

Martianus Frederic Ezerman
School of Physical and Mathematical Sciences, Nanyang Technological University, Singapore

Shivam Bhasin
Temasek Labs, Nanyang Technological University

Anupam Chattopadhyay
Temasek Labs and School of Computer Science and Engineering, Nanyang Technological University, Singapore

Sujoy Sinha Roy
Institute of Applied Information Processing and Communications, TU Graz, Austria

Keywords: Lattice-Based Cryptography, Electromagnetic-based Side-Channel Attack, Learning With Error, Learning With Rounding, Chosen-Ciphertext Attack, Public-Key Encryption, Key Encapsulation Mechanism

Abstract

In this work, we propose generic and novel side-channel assisted chosenciphertext attacks on NTRU-based key encapsulation mechanisms (KEMs). These KEMs are IND-CCA secure, that is, they are secure in the chosen-ciphertext model. Our attacks involve the construction of malformed ciphertexts. When decapsulated by the target device, these ciphertexts ensure that a targeted intermediate variable becomes very closely related to the secret key. An attacker, who can obtain information about the secret-dependent variable through side-channels, can subsequently recover the full secret key. We propose several novel CCAs which can be carried through by using side-channel leakage from the decapsulation procedure. The attacks instantiate three different types of oracles, namely a plaintext-checking oracle, a decryptionfailure oracle, and a full-decryption oracle, and are applicable to two NTRU-based schemes, which are NTRU and NTRU Prime. The two schemes are candidates in the ongoing NIST standardization process for post-quantum cryptography. We perform experimental validation of the attacks on optimized and unprotected 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 of our proposed attacks are capable of recovering the full secret key in only a few thousand chosen ciphertext queries on all parameter sets of NTRU and NTRU Prime. Our attacks, therefore, stress on the need for concrete side-channel protection strategies for NTRUbased KEMs.