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.