Xiao Huang
Southeast University, Nanjing, China

Zhuo Huang
Shanghai Jiao Tong University, Shanghai, China

Yituo He
Shanghai Jiao Tong University, Shanghai, China

Quan Yuan
Shandong University, Qingdao, China

Chao Sun
Southeast University, Nanjing, China

Mehdi Tibouchi
NTT Social Informatics Laboratories, Tokyo, Japan

Yu Yu
Shanghai Jiao Tong University, Shanghai, China

Keywords: Fault Analysis, Post-Quantum Cryptography, LESS Signature Scheme, ChipWhisperer

Abstract

To enhance the diversity of basic hard problems underlying post-quantum cryptography (PQC) schemes, NIST launched an additional call for PQC signatures in 2023. Among numerous candidate schemes, several code-based ones, which have successfully advanced to the second round, are constructed by applying the Fiat– Shamir transform to the parallel repetition of a (relatively low soundness) commitand- prove sigma protocol similar to the Stern identification scheme.In Fiat–Shamir-based signatures, it is well-known that key material will be leaked if an attacker can somehow obtain what amounts, in the sigma protocol, to the responses to different challenges with respect to the same commitment. This idea is for example at the basis of a famous differential fault attack against deterministic Fiat–Shamir-based signatures like EdDSA. It is usually difficult to mount a fault injection attack based on that principle against a properly randomized Fiat–Shamir-based scheme however (at least with single faults): since commitment collisions are ruled out, it typically involves obtaining the responses to multiple challenges with respect to the same commitment within a single execution of the signature, which is often impossible by construction (e.g., because the extra information will not fit in a single signature, or because it is hard to force the computation of both responses).Due to the comparative inefficiency of signatures based on Stern-like protocols with parallel repetition, candidate constructions are led to use clever compression techniques to reduce signature size, in a way that increases the attack surface for physical attacks. In this paper, we demonstrate this against the LESS signature scheme, which uses so-called GGM trees for signature compression. We propose a simple fault attack on the construction of a binary array used to build the GGM tree, and show that a small number of faulty signatures suffice for full key recovery.We provide a thorough mathematical model of the attack as well as extensive experimental validation with glitch attacks on a ChipWhisperer board, showing that, depending on the target parameter set and the precise fault model we consider, full key recovery can very often be achieved with just one or two faulty signatures, and never more than a couple hundred even in the least favorable scenario for the attacker.