Skip to main content
CSIRO Logo Data 61 logo

Flush, gauss, and reload — a cache attack on the BLISS lattice-based signature scheme

Authors

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

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}
  }

Download