Paper 2020/549

Drop by Drop you break the rock - Exploiting generic vulnerabilities in Lattice-based PKE/KEMs using EM-based Physical Attacks

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

Abstract

We report an important implementation vulnerability exploitable through physical attacks for message recovery in five lattice-based public-key encryption schemes (PKE) and Key Encapsulation Mechanisms (KEM) - NewHope, Kyber, Saber, Round5 and LAC that are currently competing in the second round of NIST's standardization process for post-quantum cryptography. The reported vulnerability exists in the message decoding function which is a fundamental kernel present in lattice-based PKE/KEMs and further analysis of the implementations in the public pqm4 library revealed that the message decoding function is implemented in a similar manner in all the identified schemes and thus they all share the common side-channel vulnerability that leaks individual bits of the secret message. We demonstrate that the identified vulnerability can be exploited through a number of practical electromagnetic side-channel attacks, fault attacks and combined attacks on implementations from the pqm4 library running on the ARM Cortex-M4 microcontroller. As a key contribution, we also demonstrate the first practical EM-based combined side-channel and fault attack on lattice-based PKE/KEMs.