Paper 2016/300

Flush, Gauss, and Reload -- A Cache Attack on the BLISS Lattice-Based Signature Scheme

Leon Groot Bruinderink, Andreas Hülsing, Tanja Lange, and Yuval Yarom

Abstract

We present the first side-channel attack on a lattice-based signature scheme, using the FLUSH+RELOAD cache-attack. The attack is targeted at the discrete Gaussian sampler, an important step in the Bimodal Lattice Signature Schemes (BLISS). After observing only 450 signatures with a perfect side-channel, an attacker is able to extract the secret BLISS-key in less than 2 minutes, with a success probability of 0.96. Similar results are achieved in a proof-of-concept implementation using the FLUSH+RELOAD technique with less than 3500 signatures. We show how to attack sampling from a discrete Gaussian using CDT or rejection sampling by showing potential information leakage via cache memory. For both sampling methods, a strategy is given to use this additional information, finalize the attack and extract the secret key. We provide experimental evidence for the idealized perfect side-channel attacks and the FLUSH+RELOAD attack on two recent CPUs.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
A minor revision of an IACR publication in CHES 2016
Keywords
SCAFLUSH+RELOADlatticesBLISSdiscrete Gaussians
Contact author(s)
l groot bruinderink @ tue nl
History
2016-08-17: revised
2016-03-17: received
See all versions
Short URL
https://ia.cr/2016/300
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/300,
      author = {Leon Groot Bruinderink and Andreas Hülsing and Tanja Lange and Yuval Yarom},
      title = {Flush, Gauss, and Reload -- A Cache Attack on the BLISS Lattice-Based Signature Scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2016/300},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/300}},
      url = {https://eprint.iacr.org/2016/300}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.