Keep it Simple: Refreshing the NTT of Kyber’s Decapsulation to Prevent Plaintext-Checking Side-Channel Attacks

In this paper, we revisit the protection of Kyber’s NTT implementation against plaintext-checking side-channel attacks, for which the current mainstream solution is to combine masking and shuffling. For this purpose, we first bring consolidating arguments why shuffling alone is (theoretically) of limited help to improve security against such distinguishing attacks, and why masking alone may be (practically) hindered by a lack of physical noise in low-cost embedded devices. We then discuss the challenges to address when implementing and (mostly) evaluating masked and shuffled implementations, and the lack of easy-to-extrapolate scaling trends for such a mix of countermeasures. We use this discussion as a motivation for a simpler approach, namely refreshing the layers of the NTT thanks to simple gadgets with linear overheads. Using both simulated analyses and actual experiments, we show that such an approach can limit the propagation of information through the NTT layers via belief propagation, even in low-noise contexts. We also show that this combination can simplify the side-channel security evaluation of a protected NTT implementation, and lead to the exponential security amplification that is expected when masking. As side contributions, we discuss the significant differences between the (very leaky) reference C implementation of Kyber’s NTT and an efficient assembly one, together with the profiling difficulties raised by lazy reduction techniques.