Could a simple template attack break DPA-protected Kyber? | Expert Review #1

Introduction

Welcome to the Expert Review series, where we delve into the dynamic world of cybersecurity to bring you unbiased and detailed analyses from seasoned professionals. This is a field where the flow of information is both complex and unremitting, and we believe expert analysis is indispensable. It's this expertise that transforms data into understanding, and intricate research findings into actionable insights.

In this edition, we are honored to feature a distinguished panel of experts, each bringing unique and invaluable insights to our discussion. Together, we will be dissecting the paper "Breaking DPA-protected Kyber via the pair-pointwise multiplication", offering our unique perspectives and expert analysis.

About the paper

The research paper, “Breaking DPA-protected Kyber via the pair-pointwise multiplication” authored by Estuardo Alpirez Bock of Xiphera LTD, Finland; Gustavo Banegas from Qualcomm France SARL, France; Chris Brzuska and Kirthivaasan Puniamurthy of Aalto University, Finland; alongside Łukasz Chmielewski, and Milan Šorf from Masaryk University, Czech Republic, was published on April 18, 2023, in the International Association for Cryptologic Research (IACR) Cryptology ePrint Archive.

This particular research paper was chosen for review due to its focus on a cutting-edge topic in cybersecurity: the vulnerability of DPA (Differential Power Analysis)-protected Kyber, a new standard coming from the NIST Post-Quantum Cryptography standardization project. The study’s exploration into the pair-pointwise multiplication aspect of Kyber provides valuable insights into potential security weaknesses in the implementation of what is considered a leading algorithm for future cryptographic standards.

Our Expert Review

What was studied?

The authors observed that pair-pointwise polynomial multiplication, as a result of an incomplete NTT transformation in Kyber, results in significant side-channel leakage. Consequently, they decided to try to exploit this leakage in an attack in order to deduce the secret key coefficients.

Why is it important?

The paper claims that the attack also applies to protected Kyber implementations. This attack was enabled by a technical choice made by Kyber designers for Round 2 of the NIST PQC competition in 2019. Kyber changed its modulus parameter from to , as a result of new results studying fast NTT transformations. This choice of modulus makes a complete NTT transformation impossible, which leads to new implementation methods for the NTT transform, subsequently leading to new potential side-channel leakage to be exploited.

Which new insights have been contributed, and how significant are they?

The paper proposes a kind of template attack targeting the pair-pointwise multiplication of the secret key and ciphertext in the NTT domain. The attack can be adapted for different types of implementations, and could potentially be applied to other Kyber-like algorithms, of which there are many. Other types of attack targeting masked implementations of Kyber have been previously studied and published. However, this attack is uniquely straightforward to understand and implement. Since it is a relatively simple attack, it can be considered more of a potential threat, and therefore work should be done to develop countermeasures to protect against such an attack.

How practical are the results?

The authors of the paper ran a partial experiment to try to prove that the attack works. The attack is incomplete in the sense that no recovery of secret key coefficients is demonstrated. The practicality of the attack might suffer from the particular profiling method used, during which templates are only made for single-coefficient secret keys. This strategy assumes that there is no dependency between the power consumption of operations computing on any two secret key coefficients. This is a strong assumption that may not hold in practice, depending on the implementation and platform.

However, the main purpose of the article is more to prove theoretically that there are simple attacks that can exploit leakage from multiple operations in a single trace. The simplicity of the profiling phase contributes to the practicability of the attack in the real world.

It should also be noted that the paper assumes Hamming Weight leakage, which may not be valid on all implementations. The question of possible portability in another leakage model is an open question.

When might the impact happen (now, within 1 year, 5 years, more than 10 years)?

As the coming NIST Key Encapsulation Mechanism (KEM) standard FIPS 203 is based on Kyber, any and all cryptanalysis and side-channel analysis is very relevant. The impact is significant, and it can be felt in the immediate future. For instance in the article, an attack is proposed that can be applied to implementations of Kyber that use masking and shuffling protections - meaning new and/or different protection methods should be implemented to ensure this particular side-channel leakage can not be exploited by an attacker.

What’s next?

It's clear that the journey into the realm of Post-Quantum Cryptography (PQC) is just beginning. Every day brings new information and fresh research papers that further deepen our understanding of this quickly-evolving field. We are committed to analyzing these developments and offering insights to ensure you remain well-informed and prepared for the challenges ahead. Consider this review the first of many more insightful explorations to come. Stay tuned.