Paper 2019/898

One Bit is All It Takes: A Devastating Timing Attack on BLISS’s Non-Constant Time Sign Flips

Mehdi Tibouchi and Alexandre Wallet

Abstract

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.

Note: Updated the description of the distribution for w and (-1)^b*z : made it more accurate and improved the analysis in appendix. Fixed minor editorial stuff.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. MINOR revision.Mathcrypt 2019
Keywords
Lattice-Based CryptographyCryptanalysisBLISSSide-Channel AnalysisMaximum Likelihood EstimationParametric InferenceInformation Geometry
Contact author(s)
mehdi tibouchi @ normalesup org
wallet alexandre @ gmail com
History
2019-08-29: revised
2019-08-06: received
See all versions
Short URL
https://ia.cr/2019/898
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/898,
      author = {Mehdi Tibouchi and Alexandre Wallet},
      title = {One Bit is All It Takes: A Devastating Timing Attack on BLISS’s Non-Constant Time Sign Flips},
      howpublished = {Cryptology ePrint Archive, Paper 2019/898},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/898}},
      url = {https://eprint.iacr.org/2019/898}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.