Cryptology ePrint Archive: Report 2019/948

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

Prasanna Ravi and Sujoy Sinha Roy and 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.

Category / Keywords: public-key cryptography / Lattice-based cryptography, Error Correcting Codes, FO transform, EM- based side-channel attack, Chosen Ciphertext Attack, PKE/KEM

Date: received 20 Aug 2019, last revised 17 Oct 2019

Contact author: PRASANNA RAVI at ntu edu sg,s sinharoy@cs bham ac uk

Available format(s): PDF | BibTeX Citation

Version: 20191018:013603 (All versions of this report)

Short URL: ia.cr/2019/948


[ Cryptology ePrint archive ]