Paper 2021/718

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

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

Abstract

In this work, we propose generic and novel side-channel assisted chosen-ciphertext 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 decryption-failure 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 NTRU-based KEMs.

Note: Accepted at IACR TCHES-2022

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Lattice Based CryptographyStreamlined NTRU PrimeChosen-Ciphertext AttacksSide-Channel AttacksPlaintext Checking OracleDecryption Failure OracleNIST PQC Standardization process
Contact author(s)
PRASANNA RAVI @ ntu edu sg
History
2021-10-14: last of 3 revisions
2021-05-31: received
See all versions
Short URL
https://ia.cr/2021/718
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/718,
      author = {Prasanna Ravi and Martianus Frederic Ezerman and Shivam Bhasin and Anupam Chattopadhyay and Sujoy Sinha Roy},
      title = {Will You Cross the Threshold for Me? - Generic Side-Channel Assisted Chosen-Ciphertext Attacks on NTRU-based KEMs},
      howpublished = {Cryptology ePrint Archive, Paper 2021/718},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/718}},
      url = {https://eprint.iacr.org/2021/718}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.