Flush, gauss, and reload — a cache attack on the BLISS lattice-based signature scheme
Authors
Eindhoven University of Technology
University of Adelaide
Data61
CSIRO
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 after observing 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.
BibTeX Entry
@inproceedings{GrootBruinderink_HLY_16, month = aug, keywords = {side-channel attack, flush+reload, lattice-based signature scheme, bliss, discrete gaussians}, paperurl = {https://ts.data61.csiro.au/publications/nicta_full_text/9266.pdf}, booktitle = {Workshop on Cryptographic Hardware and Embedded Systems}, author = {Groot Bruinderink, Leon and H\"ulsing, Andreas and Lange, Tanja and Yarom, Yuval}, year = {2016}, pages = {323--345}, title = {Flush, Gauss, and Reload --- A Cache Attack on the {BLISS} Lattice-Based Signature Scheme}, address = {Santa Barbara, CA, US} }