Paper 2024/2043

Efficient Error-tolerant Side-channel Attacks on GPV Signatures Based on Ordinary Least Squares Regression

Abstract

The Gentry-Peikert-Vaikuntanathan (GPV) framework is utilized for constructing practical digital signatures, which is proven to be secure in both the classical/quantum random-oracle models. Falcon is such a signature scheme, recognized as a compact and efficient signature among NIST-standardized signature schemes. Recently, Guerreau et al. (CHES 2022) and Zhang et al. (Eurocrypt 2023) proposed the secret key recovery attack on Falcon utilizing signatures filtered by simple power analysis (SPA) attacks. However, these attacks, which exploit the conditional signature distributions, require a large number of SPA attacks to obtain the filtered signatures. Furthermore, no existing attack considers general GPV signatures despite the importance of the GPV framework in modern digital signatures. Therefore, we address these problems as follows. First, we introduce, for the first time, a concept of vulnerable partial information of GPV signatures and propose a non-filtering secret key recovery attack, called OLS attack, which effectively utilizes partial information without filtering. The proposed OLS attack is a linear estimator with computational complexity that scales linearly with the number of samples, making OLS attack highly practical. Furthermore, we prove that the secret key recovered by the OLS attack converges to the real secret key in probability as the number of samples increases. Second, we leverage SPA to extract Gaussian leakage, which is used as partial information for the OLS attack on Falcon. As a result, the OLS attack shows a significantly higher success rate with the fewest samples than the state-of-the-art attacks. Furthermore, by incorporating the DDGR attack, the OLS attack can recover the secret key using much fewer samples with a success rate close to 100%. Moreover, we propose an OLS attack specialized for Falcon, which can even more reduce the number of required side-channel attacks. Third, we propose an error-tolerant power analysis attack using MAP decoding, which effectively corrects the errors in samples to properly estimate Gaussian leakage. For concrete experimental validation, an ELMO simulator generates noisy power traces and ChipWhisperer measures power traces from the STM32F415 model. The proposed MAP decoding achieves high effectiveness for estimating Gaussian leakage, particularly when applied to power traces collected using low-resolution ChipWhisperer. In conclusion, it is important for future work to study countermeasures for OLS attacks.

Note: A simple source code applying the OLS attack on Falcon has been publicly released, and experimental evaulation based on ChipWhisperer have been added. Additionally, comparisons with other side channel attack have been revised, and the paper has been comprehensively updated.