Cryptology ePrint Archive: Report 2019/1459

Side Channel Information Set Decoding

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 on the Niederreiter cryptosystem and an evaluation of the practicality of the attack using a physical side channel. First, we describe a basic plaintext-recovery attack on the decryption algorithm of the Niederreiter cryptosystem. 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 algorithm for decoding. We then enhance our attack by utilizing an Information Set Decoding approach to support the basic attack and we introduce column chunking to further significantly reduce 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. The attack idea is to distinguish between successful and failed error correction based on the Hamming weight of the decrypted plaintext using the electromagnetic field as side channel. We theoretically estimate that our attack improvements have a significant impact on reducing the number of required side-channel traces. We confirm our findings experimentally and run successful attacks against the ``Classic McEliece'' NIST submission parameter sets. E.g., for the 256bit-security parameter set kem/mceliece6960119 we require starting from a basic attack with 6962 traces over a plain ISD approach with 5415 traces down to on average about 606 traces to mount a successful plaintext recovery attack.

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

Date: received 17 Dec 2019

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

Available format(s): PDF | BibTeX Citation

Version: 20191218:195248 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]