Machine-Learning Side-Channel Attacks on the GALACTICS Constant-Time Implementation of BLISS [original]

Soundes Marzougui, Nils Wisiol, Patrick Gersch, Juliane Krämer,

Jean-Pierre Seifert

Machine-Learning Side-Channel Attacks on the

GALACTICS Constant-Time Implementation of

BLISS

Open Access via institutional repository of Technische Universität Berlin

Document type

Conference paper | Accepted version

(i. e. final author-created version that incorporates referee comments and is the version accepted for

publication; also known as: Author’s Accepted Manuscript (AAM), Final Draft, Postprint)

This version is available at

https://doi.org/10.14279/depositonce-21361

Citation details

Marzougui, S., Wisiol, N., Gersch, P., Krämer, J., & Seifert, J.-P. (2022). Machine-Learning Side-Channel

Attacks on the GALACTICS Constant-Time Implementation of BLISS. In Proceedings of the 17th International

Conference on Availability, Reliability and Security (Vol. 2016, pp. 1–11). ARES 2022: The 17th International

Conference on Availability, Reliability and Security. ACM. https://doi.org/10.1145/3538969.3538980.

This work is protected by copyright and/or related rights. You are free to use this work in any way permitted by

the copyright and related rights legislation that applies to your usage. For other uses, you must obtain

permission from the rights-holder(s).

Machine-Learning Side-Channel Attacks on the

GALACTICS Constant-Time Implementation of

BLISS

Soundes Marzougui1, Nils Wisiol1, Patrick Gersch1, Juliane Kr¨amer2, and

Jean-Pierre Seifert1

1Technical University Berlin, Str. des 17. Juni 135, 10623 Berlin, Germany

{soundes.marzougui,nils.wisiol,patrick.gersch}@tu-berlin.de

2University of Regensburg, Bajuwarenstr. 4, 93053 Regensburg, Germany

[email protected]

Abstract. Due to the advancing development of quantum computers,

practical attacks on conventional public-key cryptography may become

feasible in the next few decades. To address this risk, post-quantum

schemes that are secure against quantum attacks are being developed.

Lattice-based algorithms are promising replacements for conventional

schemes, with BLISS being one of the earliest post-quantum signature

schemes in this family. However, required subroutines such as Gaussian

sampling have been demonstrated to be a risk for the security of BLISS,

since implementing Gaussian sampling both efficient and secure with re-

spect to physical attacks is highly challenging. This paper presents three

related power side-channel attacks on GALACTICS, the latest constant-

time implementation of BLISS. All attacks are based on leakages we

identified in the Gaussian sampling and signing algorithm of GALAC-

TICS. To run the attack, a profiling phase on a device identical to the

device under attack is required to train machine learning classifiers. In

the attack phase, the leakages of GALACTICS enable the trained classi-

fiers to predict sensitive internal information with high accuracy, paving

the road for three different key recovery attacks. We demonstrate the

leakages by running GALACTICS on a Cortex-M4 and provide proof-of-

concept data and implementation for all our attacks.

Keywords: BLISS, GALACTICS, Gaussian sampler, Machine-Learning, post-

quantum cryptography, side-channel analysis

1 Introduction

BLISS [DDLL13], one of the earliest lattice-based signature schemes, attracted

significant attention from the scientific community. However, despite the emerg-

ing real-world adoption [S+17] and the efforts targeting efficient and secure im-

plementation [BBE+19], BLISS had been the target of a number of different

side-channel attacks [GBHLY16, TW20, EFGT17a, PBY17a].

2 Marzougui et al.

Security against side-channel attacks is a major concern for schemes that

are meant for real-world deployment; the NIST lists the side channel resistance

of implementations as one of the criteria for its selection. According to Kocher

et al. [KJJ99], side-channel attacks are considered the main threat to crypto-

graphic algorithms meant for deployment in embedded systems. In such attacks,

an attacker does not exploit mathematical weaknesses or invalid behavior of an

implementation, but uses the behavior of their implementation to reveal secret

data.

In the past, BLISS has been attacked by side channel attacks based on cache

timing of the CPU, where the attacker exploits the time variation caused by the

memory management execution to leak sensitive information [S+17, BBE+19,

TW20, PBY17a, EFGT17a].

Side channel attacks based on power consumption of embedded devices have

also gained much research attention. In this class of attacks, the attacker gains

information about sensitive internal data of the device by measuring the power

a device consumes during a cryptographic operation, typically with high sam-

ple rate. The power side channel attack in this paper can be counted towards

the profiling attack category which gained popularity in recent years [APSQ06,

CPM+18, BFD20, KPH+18, MPP16, SKL+20].

Our Contributions We present three machine-learning-based profiling side-channel

attacks against the GALACTICS implementation of BLISS, each allowing a full

secret key recovery.

–We identify four leakages in the power analysis of GALACTICS which al-

low the prediction of internal values with high accuracy. For one case, we

demonstrate the superiority of a prediction based on machine learning over

linear regression.

–Based on the leakages, we demonstrate three attacks.

•In the first attack, we target the constant-time Gaussian sampler [ZSS20],

and the constant-time sign flip implementation of the signing algorithm.

After observing the power consumption of approx. 320 signatures, we

are able to fully recover the secret key in only a few seconds.

•In the second attack, we restrict the attacker to only one of the four

leakages. Following the strategy of Groot Bruinderink et al. [GBHLY16],

we demonstrate that – at the expense of more observed signatures – a

secret key recovery is still feasible.

•Our third attack demonstrates that GALACTICS can also be attacked if

the sampling process does not leak any information, i.e., that a secret key

recovery by the method of Tibouchi et al. [TW20] is still possible even

if the attacker only learns information about the sign flipping procedure

of the signing algorithm.

–Our three attacks are demonstrated via proof-of-concept experiments which

were performed on Cortex-M4 microcontrollers.

Machine-Learning Side-Channel Attacks on GALACTICS 3

Related Work The security of lattice-based cryptography often relies on the

Learning with Errors problem (LWE). An LWE instance contains the secret

vectors blinded with a noise vector (error). Usually, the noise vectors are taken

from a Gaussian distribution, typically acquiring many samples for a single run

of the scheme. The Gaussian sampling process is essential to the security of

the scheme, as an attacker with knowledge of the samples can compute the

solution to the LWE problem and obtain the secret key of the scheme by solving

a system of linear equations. Hence, the Gaussian sampling has been considered

a potential weakness of lattice-based schemes in general and BLISS in particular.

The sampling from the Gaussian distribution can be based upon a Cumula-

tive Distribution Table (CDT). The CDT sampler includes a table of cumulative

distribution function values covering a finite interval. To output a sample, one

generates a uniform random value and determines the Gaussian sample value by

iterating through the CDT until the entry corresponding to the uniform random

value is found. A constant-time implementation of a CDT sampler forces the

execution of a comparison on all the table’s entries [BCNS15]. This approach is

however broken by Kim et al. by a single trace power analysis attack [KH18].

Ducas et al. [DDLL13] proposed an efficient and secure approach for Gaussian

sampling. In a first step, their approach draws from a Gaussian distribution with

a small standard deviation. Then, in a second step, these samples are blended

with uniformly random values. The deviation of the resulting values from a

Gaussian distribution is compensated by an additional rejection condition based

on a Bernoulli sample. Due to the blending with uniform values, even if the CDT

sample values are obtained by an attack such as the one by Kim et al. [KH18],

the values of the final Gaussian sample cannot be derived. Thus, the secret key

cannot be recovered as the solution to a system of linear equations.

Using cache timing attacks, Groot Bruinderink et al. [GBHLY16] targeted not

only the CDT sampler [PDG14a], but also the Bernoulli rejection [DDLL13].

Groot Bruinderink et al. demonstrated that the obtained leakage along with pub-

lic information leads to a full recovery of the secret key. In a similar side-channel

attack, Espitau et al. [EFGT17b] target the Gaussian sampler and the rejection

sampler during the BLISS signing process. Using a branch tracing technique,

they reveal the Gaussian samples as well as the Bernoulli samples and demon-

strate how to use this information to infer the secret key. The techniques demon-

strated in these attacks are based on leakages of the Gaussian sampling and the

Bernoulli rejection (during Gaussian sampling) and do not apply to BLISS-B, an

improved variant of BLISS and the default option in strongSwan [S+17]. How-

ever, Pessl et al. [PBY17a] present a new side-channel key-recovery algorithm

against both the original BLISS and the BLISS-B variant. Their key recovery

attack, while based on the same leakages, also works against BLISS-B and re-

covers the key using, among other tools, integer programs, maximum likelihood

tests, and a lattice-basis reduction. We conclude that independently of the used

techniques for key recovery, the Gaussian sampler and the Bernoulli rejection

both pose a risk to the security of BLISS as well as BLISS-B signature schemes.

4 Marzougui et al.

Gaussian and rejection samplers were not the only vulnerabilities of the

BLISS scheme. A recent timing attack against BLISS exploits only the bit sign

information to achieve full secret key recovery [TW20]. In this attack, Tibouchi

and Wallet computed part of the secret key using a maximum likelihood estima-

tion on the space of parameters. To mitigate this attack, they propose to use a

constant-time implementation of sign flip, mitigating the leakage based on cache

timing.

To mitigate the previously mentioned side channel attacks, a constant-time

sampling for both Gaussian and Bernoulli distribution via value tables of the

cumulative distribution function is suggested. An example of this approach is

the FACCT Gaussian sampler due to Zhao et al. [ZSS20]. Being an extension of

the approach suggested by Ducas et al. [DDLL13], the FACCT sampler avoids

storing precomputed values for the Bernoulli sampling, using an approach based

on polynomial approximation instead.

Organization In Sec. 2, we introduce the BLISS signature scheme. Subsequently,

in Sec. 3, we present our experimental setup and explain the different phases of

the attacks. In Sec. 4, we analyze four different information leakages of GALAC-

TICS using power analysis. In Sec. 5, we give a detailed mathematical description

of the key recovery strategies. We end the paper with Sec. 6, where we discuss

possible countermeasures against the three proposed attacks.

2 Background

For any integer q, the ring Zqis represented by the set [−q/2, q/2) ∩Z. Polyno-

mials are defined in the rings R=Z[X]/(Xn+ 1) or Rq=Zq[X]/(Xn+ 1) and

denoted as bold lower case letters. Vectors are considered column vectors and

denoted by bold lower case letters as well, while matrices are denoted by bold up-

per case letters. By default, we use the Euclidean L2-norm, i.e. ∥v∥=pPiv2

By ⌊x⌉dwe denotes the dhighest-order significant bits of an integer x, i.e.,

x=⌊x⌉d·2d+x′, with x′∈[−2d−1,2d−1).

Gaussian Sampling. A discrete Gaussian distribution is characterized by two

important values: the standard deviation σand the mean value µ. A value x∈Z

is sampled with probability

X∼Dσ

[X=x] = ρ(x)

P∞

y=−∞ ρσ(y),

where ρσ(y) = exp(−x2

2σ2) is the continuous Gaussian function. With D+

σwe de-

note the non-negative part of Dσ. There are different generic ways to sample

from a discrete Gaussian distribution. An early approach employs the cumula-

tive distribution table (CDT) for sampling [Dev86]. It consists in computing

a table Ψof cumulative distribution function values of D+

σthat cover a finite

interval [−τσ, +τσ ]. The parameter τdenotes the tail-cut and is chosen such

Loading more pages...