Paper 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 article, we demonstrate practical side-channel assisted chosen-ciphertext attacks (CCA) over multiple CCA-secure lattice-based public-key encryption schemes (PKE) and key-encapsulation mechanisms (KEM). Most lattice-based PKE/KEMs suffer from the problem of decryption failures and some of these schemes use forward error correction codes to reduce the failure probability. These error correcting codes, when used within public-key cryptographic schemes, involve computations with secret components and hence might leak sensitive side-channel information. In this work, we identify a side-channel vulnerability in constant-time error correcting codes, which help the attacker distinguish between faulty and valid codewords through the EM/power side-channel information. We exploit the vulnerability to demonstrate a practical chosen-ciphertext attacks on the CCA-secure Round5 algorithm which uses timing attack resistant error correcting code. We further identify a generic side-channel vulnerability within the CCA transformation steps used in multiple CCA-secure lattice-based PKE/KEM schemes. Exploiting the vulnerability, we demonstrate a practical chosen-ciphertext attack which can be performed on multiple CCA-secure lattice-based PKE/KEM schemes. We perform experimental validation of our attacks using Electromagnetic measurements observed over optimized implementations of multiple NIST candidates taken from the pqm4 library, a benchmarking framework for post quantum cryptographic implementations for the ARM Cortex-M4 microcontroller. We thus establish that (1) lattice-based schemes that use error correcting codes, no matter constant-time or not, are vulnerable to power/EM side-channel attacks and (2) the notion that CCA-secure schemes are as insecure as their CPA-secure versions unless suitably masked against side-channel attacks.