Paper 2019/1459

Side Channel Information Set Decoding using Iterative Chunking

Norman Lahr, Ruben Niederhagen, Richard Petri, and Simona Samardjiska

Abstract

This paper presents an attack based on side-channel information and Information Set Decoding (ISD) on the Niederreiter cryptosystem and an evaluation of the practicality of the attack using an electromagnetic side channel. First, we describe a basic plaintext-recovery attack on the decryption algorithm of the Niederreiter cryptosystem. In case the cryptosystem is used as Key-Encapsulation Mechanism (KEM) in a key exchange, the plaintext corresponds to a session key. Our attack is an adaptation of the timing side-channel plaintext-recovery attack by Shoufan et al. from 2010 on the McEliece cryptosystem using the non-constant time Patterson’s decoding algorithm to the Niederreiter cryptosystem using the constant time Berlekamp-Massey decoding algorithm. We then enhance our attack by utilizing an ISD approach to support the basic attack and we introduce iterative column chunking to further significantly reduce the number of required side-channel measurements. We theoretically show that our attack improvements have a significant impact on reducing the number of required side-channel measurements. Our practical evaluation of the attack targets the FPGA-implementation of the Niederreiter cryptosystem in the NIST submission "Classic McEliece" with a constant time decoding algorithm and is feasible for all proposed parameters sets of this submission. For example, for the 256bit-security parameter set kem/mceliece6960119 we improve the basic attack that requires 5415 measurements to on average of about 560 measurements to mount a successful plaintext recovery attack. Further reductions can be achieved at increasing cost of the ISD computations.