One Bit is All It Takes: A Devastating Timing Attack on BLISS’s Non-Constant Time Sign Flips
| Autor: | Mehdi Tibouchi, Alexandre Wallet |
|---|---|
| Přispěvatelé: | NTT Secure Platform Laboratories [Tokyo], Nippon Telegraph & Telephone Corporation - NTT, Inria Rennes – Bretagne Atlantique, Institut National de Recherche en Informatique et en Automatique (Inria) |
| Rok vydání: | 2020 |
| Předmět: |
0301 basic medicine
Computer science BLISS law.invention Cryptanalysis [INFO.INFO-CR]Computer Science [cs]/Cryptography and Security [cs.CR] 03 medical and health sciences 0302 clinical medicine law QA1-939 Information geometry 94a60 computer.programming_language 62f30 Information Geometry Maximum Likelihood Estimation Applied Mathematics Side-Channel Analysis Lattice-Based Cryptography Computer Science Applications Parametric Inference Computational Mathematics Bit (horse) Timing attack 030104 developmental biology 030220 oncology & carcinogenesis 60d05 Lattice-based cryptography Constant (mathematics) Algorithm computer Mathematics Sign (mathematics) |
| Zdroj: | Journal of Mathematical Cryptology Journal of Mathematical Cryptology, 2021, 15 (1), pp.131-142. ⟨10.1515/jmc-2020-0079⟩ Journal of Mathematical Cryptology, Vol 15, Iss 1, Pp 131-142 (2020) |
| ISSN: | 1862-2984 1862-2976 |
| DOI: | 10.1515/jmc-2020-0079 |
| Popis: | As one of the most efficient lattice-based signature schemes, and one of the only ones to have seen deployment beyond an academic setting (e.g., as part of the VPN software suite strongSwan), BLISS has attracted a significant amount of attention in terms of its implementation security, and side-channel vulnerabilities of several parts of its signing algorithm have been identified in previous works. In this paper, we present an even simpler timing attack against it. The bimodal Gaussian distribution that BLISS is named after is achieved using a random sign flip during signature generation, and neither the original implementation of BLISS nor strongSwan ensure that this sign flip is carried out in constant time. It is therefore possible to recover the corresponding sign through side-channel leakage (using, e.g., cache attacks or branch tracing). We show that obtaining this single bit of leakage (for a moderate number of signatures) is in fact sufficient for a full key recovery attack. The recovery is carried out using a maximum likelihood estimation on the space of parameters, which can be seen as a statistical manifold. The analysis of the attack thus reduces to the computation of the Fisher information metric. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|