A Power Side-Channel Attack on the Reed-Muller Reed-Solomon Version of the HQC Cryptosystem

Thomas Schamberger; Lukas Holzbaur; Julian Renner; Antonia Wachter-Zeh; Georg Sigl

Paper 2022/724

A Power Side-Channel Attack on the Reed-Muller Reed-Solomon Version of the HQC Cryptosystem

Thomas Schamberger, Technical University of Munich, Munich, Germany

Lukas Holzbaur, Technical University of Munich, Munich, Germany

Julian Renner

, Technical University of Munich, Munich, Germany

Antonia Wachter-Zeh, Technical University of Munich, Munich, Germany

Georg Sigl, Technical University of Munich, Munich, Germany

Abstract

The code-based post-quantum algorithm Hamming Quasi-Cyclic (HQC) is a fourth round candidate in the NIST standardization project. Since their third round version the authors utilize a new combination of error correcting codes, namely a combination of a Reed-Muller and a Reed-Solomon code, which requires an adaption of published attacks. We identify that the power side-channel attack by Uneo et al. from CHES 2021 does not work in practice as they miss the fact that the implemented Reed-Muller decoder does not have a fixed decoding boundary. In this work we provide a novel attack strategy that again allows for a successful attack. Our attack does not rely on simulation to verify its success but is proven with high probability for the HQC parameter sets. In contrast to the timing side-channel attack by Guo et al. we are able to reduce the required attack queries by a factor of 12 and are able to eliminate the inherent uncertainty of their used timing oracle. We show practical attack results utilizing a power side-channel of the used Reed-Solomon decoder on an ARM Cortex-M4 microcontroller. In addition, we provide a discussion on how or whether our attack strategy is usable with the side-channel targets of mentioned related work. Finally, we use information set decoding to evaluate the remaining attack complexity for partially retrieved secret keys. This work again emphasizes the need for a side-channel secure implementation of all relevant building blocks of HQC.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Published elsewhere. PQCrypto 2022
DOI: 10.1007/978-3-031-17234-2_16
Keywords: Error Correction HQC Post-Quantum Cryptography Power Analysis Side-Channel Analysis
Contact author(s): t schamberger @ tum de
lukas holzbaur @ tum de
julian renner @ tum de
antonia wachter-zeh @ tum de
sigl @ tum de
History: 2022-10-04: revised; 2022-06-07: received; See all versions
Short URL: https://ia.cr/2022/724
License: CC BY-NC-ND

BibTeX

@misc{cryptoeprint:2022/724,
      author = {Thomas Schamberger and Lukas Holzbaur and Julian Renner and Antonia Wachter-Zeh and Georg Sigl},
      title = {A Power Side-Channel Attack on the Reed-Muller Reed-Solomon Version of the HQC Cryptosystem},
      howpublished = {Cryptology ePrint Archive, Paper 2022/724},
      year = {2022},
      doi = {10.1007/978-3-031-17234-2_16},
      note = {\url{https://eprint.iacr.org/2022/724}},
      url = {https://eprint.iacr.org/2022/724}
}