Cryptology ePrint Archive: Report 2019/1459

Side Channel Information Set Decoding using Iterative Chunking

Norman Lahr and Ruben Niederhagen and 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.

Category / Keywords: implementation / ISD, Reaction Attack, SCA, FPGA, PQC, Niederreiter, Classic McEliece

Date: received 17 Dec 2019, last revised 16 Jul 2020

Contact author: norman at lahr email,ruben@polycephaly org,rp@rpls de,simonas@cs ru nl

Available format(s): PDF | BibTeX Citation

Version: 20200716:075119 (All versions of this report)

Short URL: ia.cr/2019/1459


[ Cryptology ePrint archive ]