Hey Kyber, Give me a Sign! | Expert Review #4

Introduction

Welcome back to the Expert Review series, where, together with PQShield, we delve into the dynamic world of cybersecurity to bring you unbiased and detailed analyses from seasoned professionals. If you missed any of our previous editions, you can find them here.

Today, we focus on one of the posts from the IACR eprint archive that appeared at the beginning of this year: “Exploiting the Central Reduction in Lattice-Based Cryptography” written by Tolun Tosun, Amir Moradi, and Erkay Savas. The article leverages the characteristic of many implementations of Lattice-Based Cryptography and in particular the coming NIST Standards, to mount a side-channel attack working around masking counter-measures.

About the paper

This research elaborates on a new power model called “the range power model”, and proposes a new method for second-order side-channel attacks on ML-KEM(Module-Lattice-based Key Encapsulation Mechanism) and ML-DSA (Module-Lattice-based Digital Signature Algorithm). Unlike previous attacks on implementations protected by masking, this attack is non-profiled but stays efficient regarding trace collection. Moreover, the targeted characteristic is different from former attacks. It was these features, and the novelty of the approach, that caught our attention.

Our Expert Review

What was studied?

The authors studied second-order correlation power analysis (CPA) on implementations protected by first-order arithmetic masking. They specifically target implementations that use central modular reduction, where the output of a modular operation is a signed integer in an interval centered around 0. In Two's complement, a method of representing signed integers, the average Hamming weight of negative integers is higher than that of positive integers. This means that an integer's sign may leak through side channels, which the authors exploit, to improve existing methods for second-order CPA.

The above figure, extracted from the preprint, illustrates the unbalanced distribution of the Hamming weight between positive and negative values. 𝑞 is the modulo and 𝛃 the bit size of the architecture. Due to these distributions, the sign of a number can be accurately guessed by looking at its Hamming weight. This property of the approach is at the heart of the proposed attack efficiency.

Why is it important?

In ML-KEM and ML-DSA the secret key is multiplied by some known value. Few works have studied side-channel attacks (SCA) protections for this multiplication, because it is a linear operation and those are thought to be trivial to protect with arithmetic masking. Therefore, papers about designing advanced masking gadgets often focus on the non-linear part of the algorithms only. This does not mean, however, that it is hard to succeed with SCA on the protected multiplication. On the contrary, with their new method, the authors show that first-order masking might not be sufficient to protect against Side Channel attacks.

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

In a second-order CPA, the attacker first locates the points in the power trace where the masked secret and its mask are processed, and then uses a combination function to combine those points. The output of this function correlates with the Hamming weight of the unmasked secret, thus enabling a CPA attack. The authors showed that a higher correlation can be obtained by relating the Hamming weight leakage of the masked secret and its mask to their signs. Knowledge of these signs can be used to deduce information about the value of the unmasked secret. How practical are the results?

The proposed method is as easy to implement as any second-order CPA. The paper demonstrates, by both simulations and real experiments, that their second-order CPA requires fewer traces for key recovery than previously used methods. However, the method applies only on implementations that use signed integer representation. For efficiency reasons developers might prefer the two’s complement arithmetic to the positive one. This is just an implementation choice linked to the device supporting the implementation. Still, the two’s complement arithmetic choice introduces the lever used by the attack, while the unsigned integer representation use would prevent this attack.

When is the impact expected?

The two lattice-based NIST PQC standards are currently under development, and the final standards are set to be published by NIST this summer. It can be expected that there will be an increasing demand for side channel resistant ML-KEM and ML-DSA implementations. The article demonstrated that the use of signed arithmetic in masked implementations of these standards degrades the effectiveness of the masking countermeasure. The impact of this work can therefore be felt in the immediate future. Protected implementations of the standards that were designed to be secure against side channel attacks might still succumb to the attack from this paper.

What’s next?

This review is our second one on the side-channel attack topic breaking masked implementation of modular-lattice-based PQC algorithm. This highlights the fact that the road to strong implementation of PQC regarding side-channel is hard, and also shows the importance of implementation knowledge for security validation.

Stay tuned for more reviews of other groundbreaking articles as we delve deeper into the latest advancements and challenges in the field of cryptography. The journey towards securing our digital infrastructure is ongoing, and we are committed to bringing you the best insights and analyses from the forefront of cryptographic research.