International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
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
Download:
DOI: 10.13154/tches.v2020.i3.307-335
URL: https://tches.iacr.org/index.php/TCHES/article/view/8592
Search ePrint
Search Google
Presentation: Slides
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.
Video from TCHES 2020
BibTeX
@article{tches-2020-30393,
  title={Generic Side-channel attacks on CCA-secure lattice-based PKE and KEMs},
  journal={IACR Transactions on Cryptographic Hardware and Embedded Systems},
  publisher={Ruhr-Universität Bochum},
  volume={2020, Issue 3},
  pages={307-335},
  url={https://tches.iacr.org/index.php/TCHES/article/view/8592},
  doi={10.13154/tches.v2020.i3.307-335},
  author={Prasanna Ravi and Sujoy Sinha Roy and Anupam Chattopadhyay and Shivam Bhasin},
  year=2020
}