Cryptology ePrint Archive: Report 2016/300

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

Leon Groot Bruinderink and Andreas Hülsing and 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.

Category / Keywords: implementation / SCA, FLUSH+RELOAD, lattices, BLISS, discrete Gaussians

Original Publication (with minor differences): IACR-CHES-2016

Date: received 16 Mar 2016, last revised 17 Aug 2016

Contact author: l groot bruinderink at tue nl

Available format(s): PDF | BibTeX Citation

Version: 20160817:222705 (All versions of this report)

Short URL: ia.cr/2016/300

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]