Cryptology ePrint Archive: Report 2017/033

Analyzing the Shuffling Side-Channel Countermeasure for Lattice-Based Signatures

Peter Pessl

Abstract: Implementation security for lattice-based cryptography is still a vastly unexplored field. At CHES 2016, the very first side-channel attack on a lattice-based signature scheme was presented. Later, shuffling was proposed as an inexpensive means to protect the Gaussian sampling component against such attacks. However, the concrete effectiveness of this countermeasure has never been evaluated. We change that by presenting an in-depth analysis of the shuffling countermeasure. Our analysis consists of two main parts. First, we perform a side-channel attack on a Gaussian sampler implementation. We combine templates with a recovery of data-dependent branches, which are inherent to samplers. We show that an adversary can realistically recover some samples with very high confidence. Second, we present a new attack against the shuffling countermeasure in context of Gaussian sampling and lattice-based signatures. We do not attack the shuffling algorithm as such, but exploit differing distributions of certain variables. We give a broad analysis of our attack by considering multiple modeled SCA adversaries. We show that a simple version of shuffling is not an effective countermeasure. With our attack, a profiled SCA adversary can recover the key by observing only 7000 signatures. A second version of this countermeasure, which uses Gaussian convolution in conjunction with shuffling twice, can increase side-channel security and the number of required signatures significantly. Here, roughly 285000 observations are needed for a successful attack. Yet, this number is still practical.

Category / Keywords: implementation / Lattice-Based Cryptography, BLISS, Side-Channel Analysis, Countermeasures

Original Publication (with minor differences): Indocrypt 2016
DOI:
10.1007/978-3-319-49890-4

Date: received 12 Jan 2017

Contact author: peter pessl at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Version: 20170113:183157 (All versions of this report)

Short URL: ia.cr/2017/033

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]