Secret and Shared Keys Recovery on Hamming Quasi-Cyclic with SASCA

Chloé Baïsse; Antoine Moran; Guillaume Goy; Julien Maillard; Nicolas Aragon; Philippe Gaborit; Maxime Lecomte; Antoine Loiseau

Paper 2024/440

Secret and Shared Keys Recovery on Hamming Quasi-Cyclic with SASCA

Chloé Baïsse, XLIM, University of Limoges, CEA LETI

Antoine Moran, CEA LETI, Inria Saclay - Île-de-France Research Centre, Institut Polytechnique de Paris

Guillaume Goy

, XLIM, University of Limoges, CEA LETI

Julien Maillard

, XLIM, University of Limoges, CEA LETI

Nicolas Aragon

, XLIM, University of Limoges

Philippe Gaborit, XLIM, University of Limoges

Maxime Lecomte

, CEA LETI

Antoine Loiseau

, CEA LETI

Abstract

Soft Analytical Side Channel Attacks (SASCA) are a powerful family of Side Channel Attacks (SCA) that allow to recover secret values with only a small number of traces. Their effectiveness lies in the Belief Propagation (BP) algorithm, which enables efficient computation of the marginal distributions of intermediate values. Post-quantum schemes such as Kyber, and more recently, Hamming Quasi-Cyclic (HQC), have been targets of SASCA. Previous SASCA on HQC focused on Reed-Solomon (RS) codes and successfully retrieved the shared key with a high success rate for high noise levels using a single trace. In this work, we present new SASCA on HQC where both the shared key and the secret key are targeted. Unlike the previous SASCA, we take a closer look at the Reed-Muller (RM) code. The advantage of this choice, is that the RM decoder is applied before the RS decoder. This is what makes it possible to attack the two keys. We build a factor graph of the Fast Hadamard Transform (FHT) function from the HQC reference implementation of April 2023. The information recovered from BP allows us to retrieve the shared key with a single trace. In addition to the previous SASCA targeting HQC, we also manage to recover the secret key with two chosen ciphertext attacks. One of them require a single trace and is successful until high noise levels.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: SASCA Belief Propagation HQC Reed-Muller Codes Single Trace Chosen Ciphertext Attacks
Contact author(s): chloe baisse @ unilim fr
antoine moran @ cea fr
guillaume goy @ unilim fr
julien maillard @ cea fr
nicolas aragon @ unilim fr
gaborit @ unilim fr
maxime lecomte @ cea fr
antoine loiseau @ cea fr
History: 2024-03-15: approved; 2024-03-14: received; See all versions
Short URL: https://ia.cr/2024/440
License: CC BY

BibTeX

@misc{cryptoeprint:2024/440,
      author = {Chloé Baïsse and Antoine Moran and Guillaume Goy and Julien Maillard and Nicolas Aragon and Philippe Gaborit and Maxime Lecomte and Antoine Loiseau},
      title = {Secret and Shared Keys Recovery on Hamming Quasi-Cyclic with SASCA},
      howpublished = {Cryptology ePrint Archive, Paper 2024/440},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/440}},
      url = {https://eprint.iacr.org/2024/440}
}