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

Prasanna Ravi; Sujoy Sinha Roy; Anupam Chattopadhyay; Shivam Bhasin

Paper 2019/948

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

Prasanna Ravi, Sujoy Sinha Roy, Anupam Chattopadhyay, and Shivam Bhasin

Abstract

In this work, we demonstrate generic and practical side-channel assisted chosen ciphertext attacks on multiple LWE/LWR-based Public Key Encryption (PKE) and Key Encapsulation Mechanism (KEM) secure in the chosen ciphertext model (IND-CCA security). Firstly, we identified EM-based side-channel vulnerabilities in the error correcting codes (ECC) used in LWE/LWR-based schemes that enable to distinguish the value/validity of the codewords output from the decryption operation. We also identified a similar vulnerability in the Fujisaki-Okamoto transformation which leaks side-channel information about decrypted messages, applicable to multiple lattice-based schemes/variants of schemes that do not use ECC. Our attacks are applicable to about six CCA-secure lattice-based PKE/KEMs currently 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 are performed in a non-profiled setting and complete key-recovery could be performed in a matter of minutes on all the targeted schemes, thus showing the ease and effectiveness of our attack. We thus attempt to demonstrate the side-channel weaknesses of error correcting codes in CCA-secure LWE/LWR-based schemes and also establish/strengthen the notion that IND-CCA secure LWE/LWR-based schemes are as in-secure as IND-CPA secure schemes in the presence of side-channels unless suitably masked/protected.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published by the IACR in TCHES 2020
Keywords: Lattice-based cryptography Error Correcting Codes FO transform EM- based side-channel attack Chosen Ciphertext Attack PKE KEM
Contact author(s): PRASANNA RAVI @ ntu edu sg
History: 2021-06-02: last of 3 revisions; 2019-08-20: received; See all versions
Short URL: https://ia.cr/2019/948
License: CC BY

BibTeX

@misc{cryptoeprint:2019/948,
      author = {Prasanna Ravi and Sujoy Sinha Roy and Anupam Chattopadhyay and Shivam Bhasin},
      title = {Generic Side-channel attacks on CCA-secure lattice-based PKE and KEM schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2019/948},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/948}},
      url = {https://eprint.iacr.org/2019/948}
}