Generic Side-channel attacks on CCA-secure lattice-based PKE and KEMs

  • Prasanna Ravi Temasek Laboratories, Nanyang Technological University, Singapore; School of Computer Science and Engineering, Nanyang Technological University, Singapore
  • Sujoy Sinha Roy School of Computer Science, University of Birmingham, United Kingdom
  • Anupam Chattopadhyay Temasek Laboratories, Nanyang Technological University, Singapore; School of Computer Science and Engineering, Nanyang Technological University, Singapore
  • Shivam Bhasin Temasek Laboratories, Nanyang Technological University, Singapore
Keywords: Lattice-based cryptography, EM-based side-channel attack, LWE/LWR, Chosen Ciphertext Attack, Public Key Encryption, Key Encapsulation Mechanism

Abstract

In this work, we demonstrate generic and practical EM side-channel assisted chosen ciphertext attacks over multiple LWE/LWR-based Public Key Encryption (PKE) and Key Encapsulation Mechanisms (KEM) secure in the chosen ciphertext model (IND-CCA security). We show that the EM side-channel information can be efficiently utilized to instantiate a plaintext checking oracle, which provides binary information about the output of decryption, typically concealed within IND-CCA secure PKE/KEMs, thereby enabling our attacks. Firstly, we identified EM-based side-channel vulnerabilities in the error correcting codes (ECC) enabling us to distinguish based on the value/validity of decrypted codewords. We also identified similar vulnerabilities in the Fujisaki-Okamoto transform which leaks information about decrypted messages applicable to schemes that do not use ECC. We subsequently exploit these vulnerabilities to demonstrate practical attacks applicable to six CCA-secure lattice-based PKE/KEMs competing in the second round of the NIST standardization process. We perform experimental validation of our attacks on implementations taken from the open-source pqm4 library, running on the ARM Cortex-M4 microcontroller. Our attacks lead to complete key-recovery in a matter of minutes on all the targeted schemes, thus showing the effectiveness of our attack.

Published
2020-06-19
How to Cite
Ravi, P., Sinha Roy, S., Chattopadhyay, A., & Bhasin, S. (2020). Generic Side-channel attacks on CCA-secure lattice-based PKE and KEMs. IACR Transactions on Cryptographic Hardware and Embedded Systems, 2020(3), 307-335. https://doi.org/10.13154/tches.v2020.i3.307-335
Section
Articles