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

TLDR

The authors aim to demonstrate generic EM side‑channel attacks that break IND‑CCA secure lattice‑based PKE and KEM schemes, targeting six NIST candidate systems. They use EM leakage to build a plaintext‑checking oracle, exploit weaknesses in error‑correcting codes and the Fujisaki‑Okamoto transform, and validate the attacks on pqm4 implementations running on an ARM Cortex‑M4. The attacks reveal side‑channel vulnerabilities in ECC and the Fujisaki‑Okamoto transform, enabling complete key recovery within minutes on all six targeted schemes.

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.