[subfigure]position=bottom

# Fuzzing+Hardware Performance Counters-Based Detection of Algorithm
Subversion Attacks on Post-Quantum Signature Schemes

Animesh Basak Chowdhury  Anushree Mahapatra  Deepraj Soni  and Ramesh Karri
A.B. Chowdhury, A. Mahapatra, D. Soni, and R. Karri are with the Dept. of
Electrical and Computer Engineering, New York University, Brooklyn, NY, 11201
USA. E-mail: {am11019, abc586, dss545<EMAIL_ADDRESS>
###### Abstract

NIST is standardizing Post Quantum Cryptography (PQC) algorithms that are
resilient to the computational capability of quantum computers. Past works
show malicious subversion with cryptographic software (algorithm subversion
attacks) that weaken the implementations. We show that PQC digital signature
codes can be subverted in line with previously reported flawed implementations
[1, 2] that generate verifiable, but less-secure signatures, demonstrating the
risk of such attacks. Since, all processors have built-in Hardware Performance
Counters (HPCs), there exists a body of work proposing a low-cost Machine
Learning (ML)-based integrity checking of software using HPC fingerprints.
However, such HPC-based approaches may not detect subversion of PQC codes. A
miniscule percentage of qualitative inputs when applied to the PQC codes
improve this accuracy to 98%. We propose grey-box fuzzing as a pre-processing
step to obtain inputs to aid the HPC-based method.

###### Index Terms:

Post-Quantum Cryptography, Hardware Performance Counters, Integrity
Verification, Tamper Detection

##  I Introduction

Algorithm Subversion Attacks (_ASA_) on cryptographic software deployed for
public use is an important class of attacks on cryptosystems besides the well-
known side-channel and fault attacks [3, 4, 1]. ASA is also known as
Kleptography [3]. ASAs weaken cryptography implementation without user
knowledge. The subverted software leaks all (or part) of the secret key during
message encryption and signature generation. The attacker can recover the
secret key of any party that uses such a subverted system. Flawed
implementations by software developers introduce vulnerabilities, which when
discovered can be exploited [5, 6].

The main challenge in detecting ASAs is that the outputs generated by the
subverted crypto software are computationally indistinguishable from those
generated by trusted implementations. The subversion is due to the low
resilience to crypt-analysis, fragility of implementation due to bad
randomness, reuse of nonces, and leakage of sensitive data via side-channels.
_ASA_ was first studied and systematically explored by Young et al. [3], where
they showed feasibility of such attacks on RSA (they called it the SETUP
attack). Bellare et al. extended this attack to symmetric encryption standards
[4]. Recent works show that Post-Quantum Cryptography implementations are
vulnerable to such attacks [7, 8, 9].

This paper will study detection of _subversions_ in PQC implementations.
State-of-the-art literature suggests two pathways to evade _ASA_ : 1) design
of subversion-resilient algorithms and 2) detection. Subversion-resilient
design of cryptography algorithms were proposed in [10, 11]. Designing
subversion-resilient algorithms requires cryptanalysis of the algorithm.
Complementing this approach, we propose a scheme to check if the subverted
software implementations leave unique micro-architectural traces during
execution different from the traces of a trusted PQC software implementation.
We will investigate Machine Learning (ML)-based detectors using Hardware
Performance Counters (HPC).

HPCs are low-cost performance monitors built into all processors and can be
reused at no extra cost. HPCs have been used as light-weight instrumentation
tools in embedded systems to monitor the run-time behaviour of software [12,
13, 14, 15]. HPC-based integrity check has been shown to be a successful and
effective low-cost detection solution [12, 14]. We started with using ML-based
detection technique to classify a subverted PQC implementation using run-time
HPC traces. Unfortunately, our experimental findings in section IV-A show that
95% of HPC traces for a subverted implementation are similar to those for a
trusted implementation. Clearly, vanilla ML-based detectors cannot classify
the run-time HPC traces of subverted implementation. We overcame this
limitation by using Greybox fuzzing to determine the unique input to the PQC
implementations that create distinguishable HPC traces. Contributions of this
study are three-fold:

  1. 1.

We show that PQC implementations can be subverted [1, 2, 16, 17, 18] in at
least three ways: (i) tampering with PQC security parameters, (ii) tweaking
the Random Number generators, and (iii) subverting the hash functions. We show
that ML-based classifiers that monitor HPC traces on random inputs cannot
detect the subversions.

  2. 2.

We adopt Greybox fuzzing to discover inputs that yield discernible HPC
signatures of the PQC codes to distinguish subverted PQC implementations from
the original.

  3. 3.

We build an ML classifier that performs temporal and spatial integrity checks
using discernible HPC signatures on inputs derived using Greybox fuzzing of
PQC implementations.

The paper is organized as follows: Section II lays out the threat model and
preliminaries on HPCs and PQC signature algorithms. Section III describes
three types of subversions introduced into PQC signature algorithms. Section
IV outline the challenges of using vanilla ML-based HPC detection scheme.
Section V shows greybox fuzzing guided input generation to aid ML detection
methodology using HPC signatures. Section VI discusses the experimental
results. Section VII reviews the related work and finally, Section VIII
presents the conclusions of this study.

##  II Preliminaries

###  II-A Threat Model

Our threat model is in line with the setting proposed in [19]. We have four
players in the setting: Saboteur, Victim, Attacker, and Defender(Table I). The
goal of the Saboteur is to stealthily weaken the PQC software, which may later
be exploited by an Attacker to target specific user(s) and recover their
secret keys or sensitive information. The victim is the user who deploys the
weakened PQC software. The defender is the algorithm-level designer of the PQC
software. The goal of the Defender is to ensure that Victim can easily check
the integrity of the PQC software implementations. We encourage the reader to
go through [19] for more details. We motivate our threat model using the
classic FREAK [17] attack, where the Saboteur was allegedly the National
Security Agency (NSA). They intentionally weakened the OpenSSL protocols by
restricting to use RSA_export key size below 512 bits. This can be easily
decrypted by number field sieve factorization algorithm using modest computing
resources. NIST in its role of a Defender has to ensure that the victim can
check for weaknesses in implementations. We assume PQC implementations in
TLS/SSL libraries can be subverted intentionally or accidentally by software
developers.

TABLE I: Players in Threat model[19] Player | Goal
---|---
Saboteur |  | Adds weakness to crypto
---
implementation (Software developer)
Attacker |  | Extract secret information
---
from weakened signature (NSA)
Victim |  | Uses subverted crypto
---
implementation (User)
Defender |  | Protects integrity of crypto
---
implementation (NIST)

###  II-B Motivation

The core research question we ask in our work is: How can a user trust the
implementation of crypto APIs from third-party developers (possible Saboteur)?
Our threat model shows that the Attacker with the help of third-party crypto
software developers (Saboteur) can perform backdoor injection/subvert
cryptography algorithm leaking secret key information through output. There
are multitude reasons leading to failure of existing techniques to solve the
problem.

  * •

Third-party developers generally provide static checksums for users to trust
libraries are from authentic sources. However, this defense is moot since the
source corrupts the implementation.

  * •

Honest implementations are available from Defender but are not user-friendly
APIs (support for debugging, parallelism). One can use such implementation and
tune it according to the needs. This directly mitigate any threats from third-
party developers. However, such scenario is out of scope from our work.

  * •

We show seeds provided by Defender are random and do not fully explore the
state-space of crypto implementations. Thus, validation based on random test-
inputs is incomplete and backdoor may still be hidden.

We propose the defender to release dynamic/runtime signatures generated by
running fuzz-guided inputs on PQC implementations. For versatility across
different architectures (arm, x86), we assume the defender creates the binary
for all notable architectures with predefined libraries and compiler versions.
The defender/victim can train a ML-based model using runtime HPC signatures
generated by fuzzed input for detecting anomalous behaviour in PQC
implementations. We believe our work will help NIST’s ongoing Automated
Cryptographic Validation Testing(ACVT) program[20].

###  II-C Overview of PQC Digital Signature Algorithms

TABLE II: NIST PQC Digital Signature candidates[21] Type | PQC Digital Signature
---|---
Lattice-based | Dilithium, Falcon
Symmetric-based | SPHINCS+ (alternate candidate)
Multivariate-based | Rainbow

NIST is standardizing quantum-resistant a.k.a post quantum public key
cryptography in two main classes: 1. post quantum digital signature (DS)
schemes and 2. post quantum Key Encapsulation Mechanisms (KEM). In current
work, we study impact of algorithm subversion attacks on PQC DS schemes
although these can be similarly extended to KEM algorithms. The DS schemes
authenticate the identity of the signatory [21] and detect unauthorized
modifications to data. There are three main modules of DS: 1) Keypair
generation: The signatory generates a pair of keys: secret key ($s_{k}$) and
public key ($p_{k}$) with seed as input. 2) Signature generation: The
signatory signs a message($m$) with the secret key (sign($s_{k}$,$m$)). 3)
Signature verification: The authenticator receives the signed message and
verifies the signatory using signVerify($p_{k}$,$S_{m}$). We target the DS
algorithms from NIST PQC round 3 submission as summarized in Table II. The DS
candidates are classified into 3 classes based on the underlying mechanisms.
Our work demonstrates on all three types.

  * •

Lattice-based DS builds on the hardness of shortest vector problem (SVP) and
takes polynomial time in quantum computers.

  * •

Multi-variate DS solves Multi-variate Polynomial(MVP) algorithm in finite
field and has NP-hard complexity. They are light-weight due to their short
signatures.

  * •

Symmetric-based DS resists quantum computer attacks based on the security of
the underlying cryptographic hash functions.

###  II-D Hardware Performance Counters (HPC)

HPCs are special-purpose registers built into the performance monitoring unit
of all processors. HPCs store counts of software and hardware events in the
processor. Every HPC provides information about the micro-architectural state
and events in different parts of the processor. Example HPCs include events
like cache misses and branch mis-predictions. HPC-based monitoring incurs
minimal time overhead with zero hardware cost. Further, HPC-based monitoring
does not require any extra modifications to the monitored code.The HPCs differ
from one processor to the next [22]. For example, HPCs in ARM Cortex A8
processor count Level-2 Data Cache misses, while HPCs in AMD x86 processor
count the cumulative misses in Level-2 caches. Table III tabulates the list of
HPCs from ARM Cortex A8 processor that we use.

TABLE III: HPCs and hardware-level events HPC | Hardware events
---|---
CYCLES | CPU Cycles
L2-TCM | L2 Total Cache Misses
BR-MSP | Branch Mispredictions
L1-ICM | L1 Instruction Cache Misses
L1-DCA | L1 Data Cache Accesses
L2-DCA | L2 Data Cache Accesses
L1-DCM | L1 Data Cache Misses
L2-DCM | L2 Data Cache Misses

###  II-E HPC Signatures

HPC signature of a PQC code denotes the HPC values obtained during execution.
We use HPC signatures to fingerprint run-time behavior of a PQC code in two
ways: The time-series based signature captures the temporal variations of the
HPC values during the PQC code execution for a seed input and message.
Program-checkpoint (PC) based signature: A PC is a location in the code where
HPCs are monitored. Fig. 1 shows HPC collection across multiple PCs. PC-based
HPC signature captures spatial variations of HPC values at different PCs by
executing PQC code with seed inputs and message. Tampering with the PQC code
results in deviation from the trusted HPC signature.

HPC signatures represent dynamic hashes of PQC DS implementations. Ideally,
HPC signatures of a PQC implementation at any given time are cumulative of
counts of the monitored HPCs. In reality, when monitoring HPCs at runtime,
system noise becomes a factor. Thus, we form HPC signatures by deriving
statistical measures from multiple readings of the HPCs monitored for a period
of time. The HPC signatures are then reproducible and deterministic. At any
time, when an attacker maliciously modifies the code, the HPC signatures will
vary from the pre-computed signatures. Section 7 has a detailed discussion of
HPC signatures for PQC DS algorithms.

HPC-based techniques complement the static integrity verification techniques
that compute the hashes of the program executable at program installation time
and periodically during the program execution [23].

Figure 1: Consider crypto_sign() of Dilithium with program-checkpoints.
$PC_{1}$, $PC_{2}$ are hit different number of times for trusted (green) and
tampered codes (red) yielding different $HPC$ signatures.

##  III ASA on PQC Digital Signature Codes

In this section, we describe three types of algorithm subversion attacks (ASA)
on PQC DS codes to reduce their security strength: Subverting the random
number generator (PRNG), Subverting the Hash function (HASH), Subverting the
Security Parameters (SPARAM). Our choices of attack for PRNG and HASH were
motivated by software-based attacks FREAK[17]. PRNG and HASH modifications
impact all the cryptographic modules of signature algorithms (Figure 2) and
generated signature were validated at verification end (Although, an honest
verifier showed the signature is corrupted).

S-PARAM attacks introduce vulnerabilities by tampering security parameters.
These vulnerabilities are documented by the signature algorithm designers they
can be exploited by attacker. We aim to detect subversions in PQC signatures
(and not designing them in first place).

Figure 2: Pseudo-RNG: ASA on Hashes used in PQC DS implementations.

###  III-A ASA on Pseudo Random Number Generators (PRNG)

A good pseudo-random number generator (PRNG) is essential for all PQCs. In
NIST submissions, the PQC DS candidates use block ciphers like AES-256 and
cryptographic hashes like SHA-3 to implement PRNGs. These PRNGs underlie all
three modules in a PQC DS code namely, key-pair generation, signature creation
and verification. As shown in Fig. 2, one can subvert the PRNGs by replacing
secure hashes and block ciphers with less secure variants. The adversary
reduces the entropy of the output of the PRNG and make it less secure in line
with Debian openssl threat[1]. Table IV shows implementations of PRNG in the
PQC digital signatures.

PRNG | PQC DS Algorithms
---|---
Dilithium | Falcon | Rainbow | SPHINCS+
AES-256 based | ✓ | ✓ | ✗ | ✓
SHA-3 based | ✓ | ✓ | ✓ | ✓

TABLE IV: PRNGs used in PQC DS Algorithms.

####  III-A1 Lattice-based DS

Lattice DS implementations use PRNGs to generate secret and error components
during key-pair and nonce generation ($y$) during signature generation
(Sign()) modules [24, 25, 26]. Prior knowledge of $y$ or information about its
repeated usage for different messages compromises the security of the
signature [27, 28, 26]. We subvert the with PRNG in Sign() by replacing
AES-256 block cipher in PRNG with a different block cipher Grasshopper [29].
Grasshoper was chosen as the S-box values were not generated pseudo-randomly
[30].

####  III-A2 Symmetric-based DS

In SPHINCS+, PRNG is implemented by SHA-based hash using a secret-key $s_{k}$
and message $M$. In sign(), the PRNG randomly selects a key-pair from the
SPHINCS+ tree to sign a message. We subvert PRNG by replacing it with a
different block cipher (Grasshopper [29]) based PRNG. The signature generation
can leak $s_{k}$ via less-secure PRNG [31].

####  III-A3 Multivariate-based DS

MQDSS and Rainbow use a PRNG for sampling variable coefficients. These
algorithms use secure hashes to implement PRNG using $s_{k}$ as input. We
replace AES in PRNG with Grasshopper [29] cipher.

###  III-B ASA on Hash functions (HASH)

Cryptographic hashes SHA-2 and SHA-3 have been used for key-pair generation,
signature generation and verification modules across PQC DS. In table V, we
outline the secure hashes in various PQC DS codes. ASA replaces secure
SHA-2/SHA-3 hashes with SHA-0 (Fig. 2), which is broken. For compatibility
with length of SHA-2/3 outputs, we repeated the sequence of SHA-0’s output to
match the length. By using SHA-0 for generating hashes, an adversary can
launch collision attacks [32] for key recovery.

TABLE V: NIST hashes used by PQC DS Algorithms. PQC DS Algorithms | Secure Hash Algorithm
---|---
SHA-2 | SHA-3 (SHAKE-)
256 | 384 | 512 | 128 | 256
Dilithium | ✗ | ✗ | ✗ | ✓ | ✓
Falcon | ✗ | ✗ | ✗ | ✓ | ✓
Rainbow | ✓ | ✓ | ✓ | ✗ | ✗
SPHINCS+ | ✗ | ✗ | ✗ | ✗ | ✓

###  III-C ASA on the Security Parameters (SPARAM)

We propose subverting the security parameters for each PQC DS algorithm. The
goal of the adversary is to reduce the strength of the generated signature by
modifying crucial Security parameters in the algorithm. This leads to weaker
PQC codes violating NIST security levels. The ASAs the for three classes are:

Parameters: $d,\gamma_{1},\gamma_{2},\beta,\omega,k,l$ 1. A = PRNG($\rho$)
$\in$ $R_{q}^{k\times l}$ 2. $T_{1}$ = Truncate($T,d$) $\in$ $R_{q}^{k\times
1}$ 3. $T_{0}$ = $T$ \- $T_{1}$ $\cdot$ $2^{d}$ $\in$ $R_{q}^{k\times 1}$
Rejection sampling loop 4. $\rho^{"}$ $\leftarrow$ $\\{0,1\\}^{256}$ 5. $Y$ =
PRNG($\rho^{"}$) $\in$ $R_{\gamma_{1}-1}^{l\times 1}$ 6. $W$ = $A\cdot Y$
$\in$ $R_{q}^{k\times 1}$ 7. $W_{1}$ = $HighBits_{q}(W,2\gamma_{2})$ $\in$
$R_{q}^{k\times 1}$ 8. $C$ = Hash($\gamma,T_{1},W_{1},\mu$) $\in$
$\\{0,1\\}^{256}$ 9. $Z$ = $Y+CS_{1}$ $\in$ $R_{q}^{l\times 1}$ 10. $R_{0}$ =
$LowBits_{q}(W-CS_{2},2\gamma_{2})$ 11. $H$ =
$MakeHint_{q}(-CT_{0},W-CS_{2}+CT_{0},2\gamma_{2})$ Bound Checking 12.
$if\parallel Z\parallel_{\inf}$ $\geq\gamma_{1}-\beta$ goto 4 $\beta=375$
$\Longrightarrow 0$ subverted 13. $if\parallel R_{0}\parallel_{\inf}$
$\geq\gamma_{2}-\beta$ goto 4 $\beta=375$ $\Longrightarrow 0$ subverted 14.
$if\parallel CT_{0}\parallel_{\inf}$ $\geq\gamma_{2}$ goto 4 15. $ifH>\omega$
goto 4 16. $\sigma$ = $(Z,H,C)$ 17. return $\sigma$

Algorithm 1 DILITHIUM.Sign($S_{key},\mu$) [33]

####  III-C1 Lattice-based DS

In Lattice-based DS, security strength and correctness of a signature is
computed by executing bound checks [28]. Security parameters control the
number of times bound checks are performed. The bounds ensure that the
signature does not leak out information about secret key. We subvert the code
such that it modifies one of the crucial Security parameters with a lower
value. For example, in Dilithium (Algo 1), reducing the parameter $\beta$ with
a lower threshold ($375\rightarrow 0$) helps reveal information about the
secret-key components ($S_{1}$, $S_{2}$) making it vulnerable to forging
signatures [24, 34]. SPARAM subversion similarly extends to Falcon as shown in
table VI.

####  III-C2 Symmetric-based DS

SPHINCS+ [31] uses Merkle hyper-tree of height $h$, $k$ sub-trees each with
$t$ leaves in Forest of Random Subsets ($FORS$). The security strength of
SPHINCS+ is affected by $h$, $k$ and $t$ [31]. The classical security of
SPHINCS+ [31] is defined as:

$\displaystyle
b=-\log\left(\frac{1}{2^{8n}}+\sum_{\gamma}\left(1-\left(1-\frac{1}{t}\right)^{\gamma}\right)^{k}{q\choose\gamma}\left(1-\frac{1}{2^{h}}\right)^{q-\gamma}\frac{1}{2^{h\gamma}}\right)$

The security parameter is $n$ (is 128 bits for security level I/II), the
number of adversarial signature queries to the oracle is $q$ and the bit-level
security of SPHINCS+ is $b$. One can weaken 128-bit simple SPHINCS+ by
altering the parameters as follows: $h$: $64\rightarrow 8$, $k$:
$10\rightarrow 2$ and $t$: $2^{15}\rightarrow 2^{1}$. This decreases $b$
violating the security level of SPHINCS+. Secret key recovery is easy for the
adversary by reducing the number of queries $q$ to the oracle.

####  III-C3 Multivariate-based DS

Security assumptions in multivariate cryptography are based on the difficulty
of solving systems of multivariate polynomials over finite fields (MVP).
Rainbow [35] derives its structure from unbalanced Oil and Vinegar (UOV)
scheme. To achieve NIST security level I, Rainbow selects the finite-field
$\mathcal{F}_{q}$ with $q$ elements, $m$ multivariate equations and $n$
variables as the security parameters. Here, $m=n-v_{1}$ and $n=$
$v_{1}+o_{1}+o_{2}$ where $v_{1}$ is the value of vinegar variable and $o_{1}$
and $o_{2}$ are the cardinalities of oil sets $O_{1}$ and $O_{2}$
respectively. In order to maintain security level I/II ($seclev$),
$m\geq\frac{2.seclev}{\log_{2}q}$ must be satisfied by setting $m$ to be at
least 64. We subvert the code by changing $o_{1}$: $32\rightarrow 16$,
$o_{2}$: $32\rightarrow 16$ resulting in $m=32$. This makes the implementation
prone to collision attacks.

TABLE VI: Subverting security parameters (SPARAM) in PQC digital signatures. PQC DS | SPARAM (NIST Security level-I)
---|---
Original | Subverted
Dilithium | $\beta=375$ | $\beta=0$
Falcon | $\beta=6599$ | $\beta=0$
Rainbow | $o_{1}=32,o_{2}=32$ | $o_{1}=16,o_{2}=16$
SPHINCS+ | $h=64,k=10,t=2^{15}$ | $h=8,k=2,t=2^{1}$

##  IV Limitations of State-of-the-Art Detectors

In section III, we injected ASAs [1, 2] into PQC DS codes to create subverted
implementations. We outline limitations of ML-based HPC detectors in detecting
ASA-compromised codes and motivate our approach. We will study whether ML-
based HPC detectors can distinguish a trusted implementation from a subverted
one.

###  IV-A Preliminary Findings

We collect HPC side-channels and use ML-based classifier to detect traces of
ASA-compromised implementations. Results show that about 95% of HPC traces of
ASA-compromised implementations are similar to that for original
implementations. In Fig. 3a and 3b, the spread of HPC values with random
inputs overlaps for trusted and ASA implementations. This motivates us to find
out the shortcomings of such detection techniques. We analyzed the traces from
the profiled code and make two key observations:

  * •

Most inputs (messages + secret keys) used to generate digital signatures have
poor code coverage. Random inputs do not go deep into the code segments. This
led to the indistinguishable HPC traces for trusted and ASA implementations.

  * •

PQCs rely a lot on randomness. Given an input (message + key), the output
signature differs non-determinstically based on the seed used by the
implementation.

((a)) random inputs ((b)) random inputs ((c)) fuzzed inputs ((d)) fuzzed
inputs

Figure 3: Kernel density estimation plots for HPC pairs at a PC in trusted and
(HASH and PRNG) ASA code executions of Dilithium using (a,b) random (c, d)
fuzzed inputs.

###  IV-B Improving the Coverage

Fuzzing [36] is an automated test generation technique used to check the
robustness of software. Our work leverages coverage-guided Greybox fuzz
testing [37] to generate intelligent seed inputs to maximize edge coverage
[38] on the control-flow graph of a PQC code. A control-flow graph (CFG)
represents the flow of sequential program statements (basic blocks) based on
conditions. The technique annotates every edge of the CFG and uses an
evolutionary algorithm with fitness functions to monitor run-time behavior.
Fig 4 represents a typical flow of Greybox fuzzing.

Figure 4: Coverage-based greybox fuzzing. TABLE VII: Coverage achieved using random and Greybox fuzzed seed inputs on PQC DS Algorithms Coverage metric |  PQC DS | Coverage achieved
---|---|---
| Random
---
Seed
| Fuzz
---
Seed
| Improve
---
(%)
Basic blocks covered | Dilithium | 594 | 687 | 15.65
Falcon | 827 | 870 | 5.19
Rainbow | 791 | 815 | 3.03
| SPHINCS+ | 1623 | 1812 | 11.64
Control flow edge covered | Dilithium | 1549 | 2093 | 35.11
Falcon | 1088 | 1314 | 20.77
Rainbow | 1563 | 1696 | 8.57
| SPHINCS+ | 1215 | 1594 | 31.19

Obtaining high quality seed inputs which can provide best coverage is
important as subverted codes are stealthy and trigger at certain program
states. Prior work [39] has shown malicious subverting maybe inserted in
complex conditional checks. Random seed inputs provide shallow coverage and
cannot trigger stealthy subversion. HPC values obtained for a seed input can
be directly correlated to its execution profile [40]. Execution traces using
random seed inputs on trusted and subverted code will be exact, yielding
indistinguishable HPC signatures in subverted PQC codes. HPC signature should
be collected using inputs that maximize state-space coverage. Seed inputs from
Greybox fuzzing give statistical guarantees about achievable program state
coverage under a specific time constraint [41]. In table VII, we compare
basic-block and edge coverage of PQC DS codes using random seeds and seeds
generated using Greybox fuzzing. There is upto $\sim$35 % improvement in edge
coverage relative to random seeds.

These findings lead us to propose our core contribution: combine testing with
HPC-based detection. We leverage light-weight state-of-art greybox fuzzer AFL,
to generate inputs that improve coverage on PQC implementations. Fuzz
generated test-inputs have superior distinguishablity power on HPC traces (see
Fig. 3c & 3d). We use these inputs to extract meaningful features from HPC
traces, train our ML-classifier and deploy it to detect a subverted
implementation. Our work offers a systematic approach to help NIST generate
good quality inputs for detecting vulnerable implementations. In next section,
we discuss our detection scheme.

##  V HPC-based Detection of Algorithm Subversion

We present ML-based methodology to detect subverting of PQC DS codes using
HPCs combined with greybox fuzzing as a pre-processing step. We use a (i)
time-series approach to capture the temporal variations of HPCs and (ii)
program checkpoint (PC) to capture spatial variations of HPCs in program-flow,
as HPC signatures of the PQC codes. The PC-based approach monitors the HPC
values at every checkpoint in the code. Any modification in the code is
expected to cause variation of HPC values during run-time in one (or more) PCs
detecting ASA. Fig. 5 explains our two-phase approach: The offline phase
entails running a trusted PQC code with inputs generated by greybox fuzzing to
form HPC signatures. Features from the HPC signatures are trained using ML
methods. While detection at end-user(victim), given a subverted PQC code from
a third party, the trained ML models are deployed to monitor HPC signatures to
predict if PQC code was subverted. We describe the steps in this section.

Figure 5: Two-Phase Approach to HPC-based Detection of Algorithm Subversion
Attacks.

###  V-A HPC Signature Collection

We use Greybox fuzzing as our first step to generate qualitative seed inputs
$S$ for a trusted PQC code $P$. Using $S$, we collect HPC signatures of the
sign() component of $P$. We present a time-series ($P^{TS}_{sign}$), and PC
HPC signature ($P^{PC}_{sign}$) for fingerprinting $P$.

####  V-A1 Time-series based HPC Signature Collection

We run $P$ using a seed input $s\in S$ for a time-period $T_{M}$. HPC
signatures are collected at sampling interval of $T_{S}$ with $N$ samples,
each having $K$ HPC values. This HPC signature obtained across the monitored
time-period fingerprints the PQC code. Algorithm 2 summarises this approach.

Input: DS Program $P$, Monitored set of HPCs : $\\{HPC_{idx}|idx\in[1,K]\\}$,
Sampling interval : $T_{S}$, Monitored time-period : $T_{M}$

Output: Time-series HPC Signature: $P^{TS}_{sign}\in\mathbb{R}^{N\times K}$,

$P^{TS}_{sign}\leftarrow\phi$;

Number of samples collected ($N$) $\leftarrow\lfloor T_{M}/T_{S}\rfloor+1$ ;

for  _$idx\leftarrow 1$ to $K$_ do

for  _$i\leftarrow 1$ to $N$_ do

Collect $HPC^{i}_{idx}$.

$P^{TS}_{sign}\leftarrow HPC^{N}_{K}$;

return $P^{TS}_{sign}$.

Algorithm 2 Time-series HPC Signature Collection

####  V-A2 PC-based Signature Collection

We insert PCs and run $P$ using seed inputs $S$ from fuzzing. HPC signatures
are collected across multiple PCs $H$ as shown in Algorithm 3.

Input: DS Program $P$, Monitored HPCs: $\\{HPC_{idx}|idx\in[1,K]\\}$ , Seed
inputs: $S$, Checkpoints: $H$

Output: PC-based HPC Signature: $P^{PC}_{sign}\in\mathbb{R}^{(S*H)\times K}$

$P^{PC}_{sign}\leftarrow\phi$;

for  _seed input $i\in S$_ do

for  _PC $j\in H$_ do

Collect $HPC^{ij}_{idx}$, $\forall idx\in[1,K]$

$P^{PC}_{sign}\leftarrow HPC^{S*H}_{K}$;

return $P^{PC}_{sign}$

Algorithm 3 Program Checkpoint (PC) HPC Signature

###  V-B HPC Selection

The ARM Cortex A8 processor has 16 HPCs. However, the processor restricts use
of four HPCs simultaneously. All HPCs can be monitored by time-multiplexing.
It is crucial to select the set of HPCs that can uniquely characterize the
program behavior. We use metrics from [22] to identify HPCs that can uniquely
fingerprint the codes:

  * •

Principal Component Analysis (PCA): Select HPCs with maximum variance by
creating uncorrelated variables from orthogonal components that maximise
variance [42].

  * •

Maximum Standard Deviation threshold: Identify HPCs with high deviation from
mean exceeds a threshold.

  * •

Maximum Variance threshold: Identify HPCs with high variance whose variance
exceeds a threshold value.

  * •

Fisher Score (F-score): Measures discriminative power of HPCs that have large
separation between their deviation and mean for data of different classes.

We use PCA to identify HPCs with maximum variance.

###  V-C Feature Engineering

Feature engineering is an key aspect of our methodology. Our goal is to
generate features from the HPC signature to train our ML-classifiers for every
PQC algorithm.

####  V-C1 Time-series based

To extract features, we apply overlapping sliding time-window and generate
windowed sub-sequence of time-series data. We define two parameters : time-
window duration ($T_{len}$) and time-window shift ($T_{shift}$). $T_{len}$
denotes the time-duration considered in the frame of one window and
$T_{shift}$ denotes the shift in time-interval between successive time-
windows. $T_{len}$ and $T_{shift}$ are configurable parameters based on
temporal granularity required. We obtain $D$ windowed sub-sequences. For
feature generation, we use the set of HPCs $Z$ obtained from HPC selection. We
extract mean, maximum, kurtosis, and Kendall-tau correlation coefficient as
features from every windowed sub-sequence. Algorithm 4 summarizes feature
generation $F^{TS}_{sign}$ of dimension [${D\times 4Z}$] for time-series data.

Input: Time-series HPC : $P^{TS}_{sign}\in\mathbb{R}^{N\times K}$, Time-window
duration : $T_{len}$, Time-window shift : $T_{shift}$, Selected HPCs: $Z$

Output: Feature Matrix : $F^{TS}_{hpc}\in\mathbb{R}^{D\times 4Z}$

Function  _ComputeSWFeature(_$HPC^{N}_{K}$ ,$i$_)_:

$t_{start}\leftarrow(i-1)*T_{shift}$ ;

$t_{end}\leftarrow t_{start}+T_{len}$ ;

$W\subset N$ & $W\in[t_{start},t_{end})$;

$\overrightarrow{\mu_{i}}$ = Mean({$HPC^{j}_{l},j\in W,l\in Z$});

$\overrightarrow{\kappa_{i}}$ = Kurtosis({$HPC^{j}_{l},j\in W,l\in Z$});

$\overrightarrow{\tau_{i}}$ = Corr.({$HPC^{j}_{l},j\in W,l\in Z$});

$\overrightarrow{max_{i}}$ = $\max$({$HPC^{j}_{l},j\in W,l\in Z$});

return [$\overrightarrow{\mu_{i}}$ ,$\overrightarrow{\sigma_{i}}$,
$\overrightarrow{\tau_{i}}$,$\overrightarrow{max_{i}}$];

$F^{TS}_{hpc}\leftarrow\phi$;

$HPC^{N}_{K}\equiv P^{TS}_{sign}$ (Algo-2);

Number of time-window segments ($D$) $\leftarrow\lfloor
T_{M}/T_{shift}\rfloor+1$

for  _ $i\leftarrow 1$ to $D$_ do

$F^{TS}_{hpc}\leftarrow F^{TS}_{hpc}\bigcup$
ComputeSWFeature($HPC^{N}_{K}$,$i$) ;

return $F^{TS}_{hpc}$.

Algorithm 4 Feature Engg. : Time-series

####  V-C2 PC based

Once HPCs $Z$ are selected, we create a feature matrix $F^{PC}_{hpc}$ of
dimension [${(S\times H)\times Z}$] from HPC signature $P^{PC}_{sign}$.
Algorithm 5 describes how to generate feature matrix for PCs.

Input: Checkpoint HPC data : $P^{PC}_{sign}\in\mathbb{R}^{(S*H)\times K}$,
Selected HPCs: $Z$

Output: Feature Matrix : $F^{PC}_{hpc}\in\mathbb{R}^{(S*H)\times Z}$

$F^{PC}_{sign}\leftarrow\phi$;

$HPC^{S,H}_{K}\equiv P^{PC}_{sign}$;

$S\rightarrow$ Seed inputs obtained to from fuzzing (Algo-3);

$H\rightarrow$ Checkpoints in Program $P$ (Algo-3);

$K\rightarrow$ # Number of monitored HPCs (Algo-3);

for  _seed input $i\in S$_ do

for  _checkpoint $j\in H$_ do

$F^{PC}_{hpc}\leftarrow F^{PC}_{hpc}\bigcup$ $HPC^{i,j}_{Z}$ ;

return $F^{PC}_{hpc}$.

Algorithm 5 Feature Engineering: Checkpoint

###  V-D ML Model: Training and Validation

Using the extracted features, we train the ML models to predict if a PQC code
is trusted or subverted. We train two models for every PQC algorithm, using
time-series and PC-based features. Our goal is to train a model that learns
trusted data distribution in an unsupervised manner as a one-class problem.
Once the model is trained, it predicts if a given test point belongs to the
trusted distribution or not. We use the one-class SVM [43] to map the
unlabelled data onto the features space using kernel functions and find the
maximum distance of the data bounded by a hyper-plane from the origin. We use
the Radial Basis Function (RBF) to model non-linear representations. Training
the model with RBF requires parameter tuning to generalize the model. The
model uses parameters $\gamma$ and $\nu$. Increasing $\gamma$ decreases
regularization value and finds the optimal hyper-plane and $\nu\in(0,1]$
controls the trade-off between penalty of mis-classification and
generalization of parameters. We tune $\gamma$ and $\nu$ separately for time-
series and PC-based features.

####  V-D1 Time-series

We use time-series features to train a one-class SVM model for every PQC
algorithm ($Model_{TS}$). We use 90% of trusted feature set for training and
rest for testing. During training, we use feature set $F^{TS}_{sign}$ to train
each model with its own hyper-parameters. We use three steps to evaluate model
performance on test dataset.

  1. 1.

Given a feature set of $X_{ts}$ observation vectors (i.e., feature vectors of
$X_{ts}$ time-windows), on prediction, they yield trusted (1) or subverted
(-1) labels.

  2. 2.

We temporally aggregate prediction label set ($P_{L}$). We define a majority
threshold as $t_{ts}\in X_{ts}$, divide into subsets, where each subset has
$t_{ts}$ prediction labels. The number of subsets, $N_{P}$=$\lfloor
X_{ts}/t_{ts}\rfloor$. In every subset, we aggregate labels as:
$\sum_{i=1}^{t_{ts}}P_{i}$, $P_{i}\in P_{L}$. If this sum is positive, the
prediction label for that subset is assigned as trusted else subverted.

  3. 3.

We compute accuracy: (# correctly predicted subsets) / (# subsets).

We use temporal aggregation with majority threshold to reduce mis-
classification rates. Temporal aggregation enables mitigating errors caused by
mis-predictions of certain time-windows. The best threshold is selected via
experimentation.

((a))  Figure 6: Time-series HPC variations of Trusted (Green) and subverted
codes (SPARAM (Red), PRNG (Blue), and HASH (Black)). HPCs are selected and
monitored for four PQCs.

####  V-D2 Program Checkpoints (PC)

We use PC as a feature of the trusted PQC codes, $F^{PC}_{hpc}$ and develop
ensembles of one-class SVM models ($Model_{PC}$). Our ensemble models are
formed by dividing HPC features into smaller subsets, and train one-class SVM
models on each feature subset. $Model_{PC}$ =
$Ensemble\\{SVM(F^{PC}_{hpc_{1-4}})$, $SVM(F^{PC}_{hpc_{5-8}})\\}$. We train
models on smaller subset of HPCs so that they learn different behavioral
characteristics. We use 66.6% of the baseline dataset for training. We follow
four steps to evaluate performance on any test dataset.

  1. 1.

Given a feature matrix containing $X_{pc}$ observations, on prediction yields
prediction labels ($P_{h}$) of length $X_{pc}$, as 1 or -1, i.e., trusted or
subverted respectively.

  2. 2.

We perform spatial aggregation on the prediction labels. We define a majority
threshold, $t_{pc}\leq X_{pc}$, where the set is divided into smaller subsets,
such that each subset has $t_{pc}$ labels. Thus, the number of subsets becomes
$N_{h}$ = $\lfloor X_{pc}/t_{pc}\rfloor$. For every subset, we aggregate the
labels as: $\sum_{i=1}^{t_{pc}}P_{i}$, $P_{i}\in P_{h}$. If the sum is
positive, the prediction label for that subset is assigned trusted else
subverted obtaining a set of prediction labels of size $N_{h}$.

  3. 3.

We compute accuracy as: (number of truly predicted subsets) / (number of
subsets).

  4. 4.

We perform three-fold cross validation on the trusted dataset. We select the
seed inputs ($Y_{s}$) from the set which performs best during cross
validation.

###  V-E Detection

The victim perform spatial and temporal checking by deploying models,
$Model_{TS}$ and $Model_{PC}$ in his environment. The victim collect PC-based
and time-series based HPC signatures from the untrusted PQC codes using $S$
seed inputs and the given message. While $Model_{TS}$ performs dynamic run-
time detection continuously, $Model_{PC}$ performs a one-time check by
predicting observations using $Y_{s}$ seed inputs.

##  VI Experimental Results

###  VI-A Experimental Setup

We performed our experiments on NIST Round 3 digital signature algorithms -
Dilithium, Falcon, Rainbow and SPHINCS+ from the alternative candidate. The
experiments were run on 32-bit ARM Cortex A8 processor running Linux kernel
4.14 with clock-frequency of 1.5 GHz. We report detailed breakdown of time
consumed at each phase of our proposed HPC-based detection in Table VIII.

###  VI-B HPC Variations

We collect time-series $P^{TS}_{sign}$ and program checkpoint $P^{PC}_{sign}$
HPC signatures for six PQC DS codes. We visualize the variations observed in
time-series and program checkpoint HPC signatures in figures 6 and 7.

((a))  Figure 7: Kernel density estimation plots show correlation between
pairs of HPCs for program checkpoints (PCs) in trusted and subverted (HASH,
PRNG, SPARAM) PQC code executions. Dilithium: (a) PC9 (b) PC9 (c) PC10.
Rainbow: (d) PC5 (e) PC2 (f) PC9. Falcon: (g) PC35 (h) PC31 (i) PC18.
SPHINCS+: (j) PC1 (k) PC4 (i) PC7.

####  VI-B1 Time-series

We run the Sign() module of a PQC DS code in an infinite loop at a sampling
frequency of 100KHz for 1s, to collect $P^{TS}_{sign}$. We run a lightweight
time-series HPC measurement tool parallel to collection of HPCs. We obtain
time-series features ($F^{TS}_{hpc}$) using a time-window of 1000 samples with
an overlap of 100 samples between successive windows. We set $T_{shift}$ =
0.001s and $T_{len}$ = 0.01s. We execute trusted and subverted code (PRNG,
HASH, SPARAM) variants for considered PQC algorithms and collect the HPC
signatures. Fig. 6 show variations of HPC signatures between trusted and
subverted PQC executions. HPCs are selected separately for each trusted PQC
code using principal component analysis (PCA) creating trusted HPC signature.
For Dilithium, L1-ICM and L1-DCA are selected, and Fig. 6 show that they
discriminate the signature of the trusted implementation from subverted
implementation. In Falcon, while trusted code executions incur large L1-ICM,
the subverted implementations yield lower L1-ICM. So L1-ICM has high
distinguishability power for Falcon. The plots also show that L2-TCM for
Falcon and L1-DCA for SPHINCS+ cannot distinguish trusted from subverted
implementations.

####  VI-B2 Program Checkpoints (PCs)

We execute trusted and subverted PQC implementations with seed inputs obtained
by fuzzing. We generate program checkpoint (PC) based HPC signatures. We show
the Gaussian Kernel Density Estimation (KDE) of pairs of HPCs across a set of
checkpoints (Fig. 7). To reiterate, choice of HPCs is guided by PCA. We
visualize checkpoints where maximum HPC variations are seen. The plots
estimate the probability density of HPC pairs. This aids kernel selection. For
SPHINCS+, KDE plots for program checkpoints $pc_{1}$, $pc_{4}$ and $pc_{7}$
(Fig. 7j, 7k, 7l) indicate that data distribution of L1-ICM, L2-DCM, L2-DCA at
those checkpoints are separable by a polynomial kernel. For Dilithium (Fig.
7a, 7b, 7c), HPC data-distribution of subverted code executions lies within
that of the trusted code execution. Therefore, an RBF kernel can learn the
separability of the data for training the SVM. These KDE plots aid us select
kernel function of one-class SVM for training our model. Empirical evaluations
deduce that for an RBF kernel $\gamma$=0.01-0.0001 and $\mu$ = 0.1-0.4 are
parameters for favourable model performance.

TABLE VIII: Timing complexity of proposed detection

|  PQC Signatures $\rightarrow$
---
Time Taken(in s) $\downarrow$
Dilithium | Falcon | SPHINCS+ | Rainbow
Offline |  | Fuzz seed
---
generation
18000 | 18000 | 18000 | 18000
HPC extraction | 2.958 | 20.468 | 209.210 | 2.112
Training | 4.58 | 4.64 | 4.54 | 4.38
Online (TS) | HPC extraction | 10 | 20 | 10 | 20
Detection | 3.7 | 3.6 | 3.6 | 3.7
Online (PC) | HPC extraction | 0.687 | 4.68 | 48.4 | 0.499
Detection | 1.2 | 1.35 | 0.8 | 1.34

TABLE IX: HPC time-series for different thresholds ($t$) over time windows:
Positive ($Pos$), Negative ($Neg$) predictions for trusted and SPARAM, PRNG,
HASH subverted codes.

|  |  | Predicted Type
---
Algorithm | Variant | $\mathbf{t_{ts}=21}$ | $\mathbf{t_{ts}=31}$ | $\mathbf{t_{ts}=41}$
| Type | $\mathbf{Pos}$ | $\mathbf{Neg}$ | $\mathbf{Pos}$ | $\mathbf{Neg}$ | $\mathbf{Pos}$ | $\mathbf{Neg}$
Dilithium | Trusted | 1.0 | 0.0 | 1.0 | 0.0 | 1.0 | 0.0
| SPARAM | 0.02 | 0.98 | 0.02 | 0.98 | 0.02 | 0.98
| PRNG | 0.0 | 1.0 | 0 | 1.0 | 0 | 1.0
| HASH | 0 | 1.0 | 0 | 1.0 | 0 | 1.0
Falcon | Trusted | 1.0 | 0.0 | 1.0 | 0.0 | 1.0 | 0.0
| SPARAM | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| PRNG | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| HASH | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
SPHINCS+ | Trusted | 0.79 | 0.29 | 0.71 | 0.29 | 0.63 | 0.37
| SPARAM | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| PRNG | 0.28 | 0.72 | 0.26 | 0.74 | 0.27 | 0.73
| HASH | 0.21 | 0.79 | 0.22 | 0.78 | 0.21 | 0.79
Rainbow | Trusted | 1.0 | 0.0 | 1.0 | 0.0 | 1.0 | 0.0
| SPARAM | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| PRNG | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| HASH | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0

###  VI-C Code Subversion Detection Results

Subversion detection using $Model_{TS}$ and $Model_{PC}$ are shown in Tables
IX and X. We evaluate using trusted/subverted PRNG, HASH, SPARAM HPC datasets.
In Tables IX and X, predicted type column indicates fractions of test data
points predicted as positive ($Pos$) or negative ($Neg$). Variant type column
lists the type of code subversion.

####  VI-C1 Time-series

In Table IX, $t_{ts}$ is the majority threshold varied over 21 to 41 time
windows. Our models for Falcon and Rainbow can detect the trusted code and
three subverted codes with 100% accuracy. There is good temporal granularity
amongst the successive time-windows in our data and the methodology mitigates
mis-classification rates caused due to a few time-window segments. In
SPHINCS+, the accuracy of our model is less than in other algorithms. Since
the time-series HPC variations of the trusted code is closer to that of
subverted codes, the hyper-plane of the model was not able to distinguish the
trusted code from the subverted ones. The subverted PQC codes are so stealthy
that their behavior closely matches with the trusted code. From the Table, we
select $t_{ts}$=41 to use in the detection phase for authenticating the
integrity of PQC implementation.

####  VI-C2 Program Checkpoints

In Table X, $t_{pc}$ is the majority threshold varied from 11 to 31 seed
inputs. The Table shows that the PC-based models can identify trusted PQC
codes and three subverted code data sets with 100% accuracy across all
$t_{pc}$ values for Dilithium and Falcon. In Rainbow, the performance of the
model in identifying trusted and HASH subverted codes reduces for $t_{pc}$=11
and 21 seeds. The HASH subverted code is hidden in a way that these seeds
capture baseline-like behavior. Hence, HPCs do no show a distinguishable
variation. SPHINCS+ plots in Fig 7 show that the mean BR-MSP and L1-ICA
variations of the HASH subversion is similar to that of the trusted one.
$t_{pc}$=31 is the best choice for use in the online phase for one-time
verification. Our models can detect a subverted or trusted PQC code with
$\sim$100% accuracy and $\sim$2% mis-classification.

TABLE X: Program checkpoints (PCs) with Majority thresholds (t): Positive
($Pos$), negative ($Neg$) predictions for trusted and SPARAM, PRNG, HASH
subverted codes.

|  |  | Predicted Type
---
Algorithm | Variant | $\mathbf{t_{pc}=11}$ | $\mathbf{t_{pc}=21}$ | $\mathbf{t_{pc}=31}$
| Type | $\mathbf{Pos}$ | $\mathbf{Neg}$ | $\mathbf{Pos}$ | $\mathbf{Neg}$ | $\mathbf{Pos}$ | $\mathbf{Neg}$
Dilithium | Trusted | 1.0 | 0.0 | 1.0 | 0.0 | 1.0 | 0.0
| SPARAM | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| PRNG | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| HASH | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
Falcon | Trusted | 1.0 | 0.0 | 1.0 | 0.0 | 1.0 | 0.0
| SPARAM | 0.27 | 0.72 | 0.0 | 1.0 | 0.0 | 1.0
| PRNG | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| HASH | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
SPHINCS+ | Trusted | 0.82 | 0.18 | 0.84 | 0.16 | 1.0 | 0.0
| SPARAM | 0.09 | 0.91 | 0.0 | 1.0 | 0.0 | 1.0
| PRNG | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| HASH | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
Rainbow | Trusted | 0.81 | 0.19 | 0.81 | 0.19 | 1.0 | 0.0
| SPARAM | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| PRNG | 0.0 | 1.0 | 0.0 | 1.0 | 0.0 | 1.0
| HASH | 0.2 | 0.8 | 0.2 | 0.8 | 0.33 | 0.67

##  VII Related Work

Side-channel attacks: PQC implementations for resource constrained embedded
processors are subject to implementation-based attacks. By tracing branch
instructions on AVR micro-controllers one can recover the secret key in the
BLISS PQC signature [44]. Power side-channel attack was performed on Dilithium
using an intermediate value as the side-channel [24]. A single trace is used
as a side-channel on PQC lattice-based encryption schemes to perform key
recovery [25]. Power side-channels on FPGA implementations of McEliece PQC was
shown in [45]. Differential power side-channels were revealed in PQC XMSS and
SPHINCS [46]. Resource-efficient fault attacks on pqm4 implementations are
shown by [26]. These attacks show that PQC implementations on embedded
platforms are vulnerable to side-channel attacks.

Algorithm subversion attacks: Cryptography implementations are subject to code
subversion attacks creating weaker signatures. Weaker RSA signature
implementations are prone to fault attacks [6]. Jafarholi et. al., [5] present
non-malleable codes as counter-measures for cryptographic algorithm subversion
attacks. Cappos et. al. [47] show that software package managers are
vulnerable to code subversion attacks when downloaded via untrusted channels.
Subverting programs by accessing the disk memory of a user device is shown in
[48]. The FREAK exploit [17] shows that vulnerable SSL applications producing
weaker signatures can be retrieved via man-in-the-middle attacks over
untrusted networks. The POODLE exploit [18] downgrades the version of TLS
similarly.

##  VIII Conclusion

PQC based digital signatures will be adopted in several domains replacing
classic digital signatures. This work investigates various types of subverted
PQC signature implementations. Algorithm subversion attacks weaken the PQC
signatures and make it vulnerable to attacks revealing secret information.
Thus, securing PQC implementation on resource-constrained devices is a key
requirement to maintain their integrity. We use Greybox fuzz testing to
generate quality seed inputs to maximize state space coverage of a PQC
implementation. These seed inputs aid in capturing unique HPC signatures and
make our ML-based detection model robust against algorithm subversion attacks.
The scheme makes it difficult for an adversary to hide malicious subversions
from HPC signatures generated using Greybox fuzzed inputs.

## References

  * [1] “Debian security advisory: Openssl predictable random number generator,” May 2008\. [Online]. Available: https://www.debian.org/security/2008/dsa-1571
  * [2] D. J. Bernstein, T. Lange, and R. Niederhagen, _Dual EC: A Standardized Back Door_. Springer Berlin Heidelberg, 2016, pp. 256–281.
  * [3] A. Young and M. Yung, “The dark side of “black-box” cryptography or: Should we trust capstone?” in _IACR Cryptology Conference_ , 1996, pp. 89–103.
  * [4] M. Bellare, K. G. Paterson, and P. Rogaway, “Security of symmetric encryption against mass surveillance,” in _IACR Cryptology Conference_ , J. A. Garay and R. Gennaro, Eds., 2014, pp. 1–19.
  * [5] Z. Jafargholi and D. Wichs, “Tamper Detection and Continuous Non-Malleable Codes,” in _IACR Conference on Theory of Cryptography_ , 2015, pp. 451–480.
  * [6] D. Boneh, R. A. DeMillo, and R. J. Lipton, “On the Importance of Eliminating Errors in Cryptographic Computations,” _Journal of Cryptology_ , vol. 14, pp. 101–119, 2001.
  * [7] Z. Yang, R. Chen, C. Li, L. Qu, and G. Yang, “On the Security of LWE Cryptosystem against Subversion Attacks,” _The Computer Journal_ , vol. 63, no. 4, pp. 495–507, 2019.
  * [8] Z. Yang, T. Xie, and Y. Pan, “Lattice klepto revisited,” in _Proceedings of the 15th ACM Asia Conference on Computer and Communications Security_. Association for Computing Machinery, 2020, p. 867–873.
  * [9] S. Berndt and M. Liundefinedkiewicz, “Algorithm substitution attacks from a steganographic perspective,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_. New York, NY, USA: Association for Computing Machinery, 2017, p. 1649–1660.
  * [10] A. Russell, Q. Tang, M. Yung, and H.-S. Zhou, “Cliptography: Clipping the power of kleptographic attacks,” in _Advances in Cryptology – ASIACRYPT 2016_ , J. H. Cheon and T. Takagi, Eds., 2016, pp. 34–64.
  * [11] G. Ateniese, B. Magri, and D. Venturi, “Subversion-resilient signatures: Definitions, constructions and applications,” _Theoretical Computer Science_ , vol. 820, pp. 91–122, 2020.
  * [12] C. Malone, M. Zahran, and R. Karri, “Are Hardware Performance Counters a Cost Effective way for Integrity Checking of Programs,” in _ACM Workshop on Scalable Trusted Computing_ , 2011, pp. 71–76.
  * [13] M. Alam, S. Bhattacharya, D. Mukhopadhyay, and S. Bhattacharya, “Performance Counters to Rescue: A Machine Learning based safeguard against Micro-architectural Side-Channel-Attacks,” _IACR Cryptology ePrint Archive_ , pp. 564–590, 2017.
  * [14] X. Wang and J. Backer, “SIGDROP: Signature-based ROP Detection using Hardware Performance Counters,” _arXiv preprint arXiv:1609.02667_ , 2016.
  * [15] P. Krishnamurthy, R. Karri, and F. Khorrami, “Anomaly Detection in Real-time Multi-Threaded Processes Using Hardware Performance Counters,” _IEEE Transactions on Information Forensics and Security_ , vol. 15, pp. 666–680, 2020.
  * [16] “Heartbleed CVE,” Common Vulnerabilities and Exposures (CVE), 2014, https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-0160.
  * [17] “Freak CVE,” Common Vulnerabilities and Exposures (CVE), 2014, https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2015-0204.
  * [18] “Poodle CVE,” Common Vulnerabilities and Exposures (CVE), 2014, https://cve.mitre.org/cgi-bin/cvename.cgi?name=CVE-2014-3566.
  * [19] B. Schneier, M. Fredrikson, T. Kohno, and T. Ristenpart, “Surreptitiously weakening cryptographic systems.” _IACR Cryptol. ePrint Arch._ , p. 97, 2015\.
  * [20] Skeller, “Cryptographic algorithm validation program,” Mar 2018. [Online]. Available: https://www.nist.gov/programs-projects/cryptographic-algorithm-validation-program
  * [21] NIST, “PQC round 3 submissions,” 2020, https://csrc.nist.gov/projects/post-quantum-cryptography/round-3-submissions.
  * [22] A. Tang, S. Sethumadhavan, and S. J. Stolfo, “Unsupervised Anomaly-based Malware Detection using Hardware Features,” in _USENIX Workshop on Recent Advances in Intrusion Detection_ , 2014, pp. 109–129.
  * [23] A. M. Fiskiran and R. B. Lee, “Runtime execution monitoring (REM) to detect and prevent malicious code execution,” in _International Conference on Computer Design: VLSI in Computers and Processors_. IEEE, 2004, pp. 452–457.
  * [24] P. Ravi, M. P. Jhanwar, J. Howe, A. Chattopadhyay, and S. Bhasin, “Side-channel Assisted Existential Forgery Attack on Dilithium - a NIST PQC candidate,” _IACR Cryptology ePrint Archive_ , pp. 821–842, 2018.
  * [25] R. Primas, P. Pessl, and S. Mangard, “Single-Trace Side-Channel Attacks on Masked Lattice-Based Encryption,” in _IACR Conference on Cryptographic Hardware and Embedded Systems_ , 2017, pp. 513–533.
  * [26] P. Ravi, M. P. Jhanwar, J. Howe, A. Chattopadhyay, and S. Bhasin, “Exploiting Determinism in Lattice-based Signatures: Practical Fault Attacks on pqm4 Implementations of NIST candidates,” in _ACM Conference on Asia Computer and Communications Security_ , 2019, pp. 427–440.
  * [27] L. Ducas, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehlé, “CRYSTALS-Dilithium: Digital Signatures from Module Lattices,” _IACR Transactions on Symmetric Cryptology_ , vol. 2018, pp. 238–268, 2018.
  * [28] E. Alkim, P. S. Barreto, N. Bindel, P. Longa, and J. E. Ricardini, “The Lattice-Based Digital Signature Scheme qTESLA,” _IACR Cryptology ePrint Archive_ , pp. 85–125, 2019.
  * [29] A. Biryukov, L. Perrin, and A. Udovenko, “The Secret Structure of the S-Box of Streebog, Kuznechik and Stribob,” _IACR Cryptology ePrint Archive_ , pp. 812–818, 2015.
  * [30] L. Perrin, “Partitions in the s-box of streebog and kuznyechik,” Cryptology ePrint Archive, Report 2019/092, 2019, https://eprint.iacr.org/2019/092.
  * [31] D. J. Bernstein, A. Hülsing, S. Kölbl, R. Niederhagen, J. Rijneveld, and P. Schwabe, “The SPHINCS+ Signature Framework,” in _ACM Conference on Computer and Communications Security_ , 2019, pp. 2129–2146.
  * [32] M. Stevens, E. Bursztein, P. Karpman, A. Albertini, and Y. Markov, “The first collision for full SHA-1,” in _IACR Cryptology Conference_ , 2017, pp. 570–596.
  * [33] V. Migliore, B. Gérard, M. Tibouchi, and P.-A. Fouque, “Masking Dilithium,” in _International Conference on Applied Cryptography and Network Security_ , 2019, pp. 344–362.
  * [34] Y. Liu, Y. Zhou, S. Sun, T. Wang, and R. Zhang, “On Security of Fiat-Shamir Signatures over Lattice in the Presence of Randomness Leakage,” _IACR Cryptology ePrint Archive_ , pp. 715–752, 2019.
  * [35] T. Yasuda and K. Sakurai, “A Multivariate Encryption Scheme with Rainbow,” in _International Conference on Information and Communications Security_ , 2015, pp. 236–251.
  * [36] M. Sutton, A. Greene, and P. Amini, _Fuzzing: Brute Force Vulnerability Discovery_. Pearson Education, 2007.
  * [37] M. Zalewski, “American Fuzzy Lop,” 2014, http://lcamtuf.coredump.cx/afl.
  * [38] J. J. Chilenski and S. P. Miller, “Applicability of modified condition/decision coverage to software testing,” _Software Engineering Journal_ , vol. 9, pp. 193–200, 1994.
  * [39] P. Godefroid, M. Y. Levin, and D. Molnar, “SAGE: Whitebox Fuzzing for Security Testing,” _Queue_ , vol. 10, pp. 20–27, 2012.
  * [40] G. Ammons, T. Ball, and J. R. Larus, “Exploiting Hardware Performance Counters with Flow and Context Sensitive Profiling,” _ACM Sigplan Notices_ , vol. 32, pp. 85–96, 1997.
  * [41] M. Böhme, “STADS: Software Testing as Species Discovery,” _ACM Transactions on Software Engineering and Methodology_ , vol. 27, pp. 1–52, 2018.
  * [42] G. T. Chetsa, L. Lefèvre, J.-M. Pierson, P. Stolf, and G. Da Costa, “Exploiting performance counters to predict and improve energy performance of HPC systems,” _Future Generation Computer Systems_ , vol. 36, pp. 287–298, 2014.
  * [43] B. Scholkopf and A. J. Smola, _Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond_. MIT press, 2001.
  * [44] T. Espitau, P.-A. Fouque, B. Gérard, and M. Tibouchi, “Side-Channel Attacks on BLISS Lattice-Based Signatures: Exploiting Branch Tracing against Strongswan and Electromagnetic Emanations in Microcontrollers,” in _ACM Conference on Computer and Communications Security_ , 2017, pp. 1857–1874.
  * [45] C. Chen, T. Eisenbarth, I. von Maurich, and R. Steinwandt, “Horizontal and Vertical Side Channel Analysis of a McEliece Cryptosystem,” _IEEE Transactions on Information Forensics and Security_ , vol. 11, pp. 1093–1105, 2015.
  * [46] M. J. Kannwischer, A. Genêt, D. Butin, J. Krämer, and J. Buchmann, “Differential Power Analysis of XMSS and SPHINCS,” in _International Workshop on Constructive Side-Channel Analysis and Secure Design_ , 2018, pp. 168–188.
  * [47] J. Cappos, J. Samuel, S. Baker, and J. H. Hartman, “A Look In the Mirror: Attacks on Package Managers,” in _ACM Conference on Computer and Communications Security_ , 2008, pp. 565–574.
  * [48] A. Tereshkin, “Evil Maid Goes after PGP Whole Disk Encryption,” in _ACM Conference on Security of Information and Networks_ , 2010, pp. 2–2.

|  Animesh Basak Chowdhury is a Ph.D. candidate at the NYU Centre for
Cybersecurity, where he works in the area of machine learning for Electronics
Design Automation and security testing. He received his MS in Computer Science
from Indian Statistical Institute in 2016. Prior to joining the Ph.D. program,
he spent three years as a researcher at Tata Research Development and Design
Centre (TRDDC), India, where he was primarily working in the area of formal
verification and security testing. He has won several awards and recognition
in International Software Verification and Testing Competitions (SV-COMP, TEST
COMP, and RERS-Challenge).
---|---
|  Anushree Mahapatra is a research engineer at Innatera Systems, Netherlands
where she primarily works on electronics design automation problems of mapping
Neural networks directly on hardware. She worked as post-doctoral researcher
for a year at NYU Tandon School of Engineering in the areas like High-level
synthesis security and Hardware Performance Counters based security. She
received her Ph.D. from Hong Kong Poly-technique University in 2018 and MS
from Nanyang Technological University in 2013. Her research interests include
High level synthesis, design space exploration, machine learning and SoC
security. Post completion of Ph.D., she spent a year in industry and worked on
recommender systems.
---|---
|  Deepraj Soni is a Ph.D. candidate at the NYU Tandon School of Engineering,
where he works on hardware implementation, and evaluation and security of
post-quantum cryptographic algorithms. He received his M.Tech from the
Department of Electrical Engineering at the Indian Institute of Technology in
Bombay (IIT-B). His thesis focused on developing a framework for a hardware-
software co-simulator and neural network implementation on an FPGA. After
graduation, Deepraj worked as a design engineer in the semiconductor division
of Samsung and SanDisk. At Samsung, he was responsible for the design and
architecture of image processing IPs, such as region segmentation and Embedded
CODEC. He also had charge of communication IPs, such as FFT/IFFT, Time &
Frequency Deinterleaving and Demapper for canceling noise. At SanDisk, Deepraj
helped in the development of System-On-Chip (SoC) level design for the memory
controller.
---|---
|  Ramesh Karri is a Professor of ECE at New York University. He co-directs
the NYU Center for Cyber Security (http://cyber.nyu.edu). He founded the
Embedded Systems Challenge (https://csaw.engineering.nyu.edu/esc), the annual
red team blue team event. He co-founded Trust-Hub (http://trust-hub.org).
Ramesh Karri has a Ph.D. in Computer Science and Engineering, from the UC San
Diego and a B.E in ECE from Andhra University. His research and education
activities in hardware cybersecurity include trustworthy ICs; processors and
cyber-physical systems; security-aware computer-aided design, test,
verification, validation, and reliability; nano meets security; hardware
security competitions, benchmarks, and metrics; biochip security; additive
manufacturing security. He published over 250 articles in leading journals and
conference proceedings. Karri’s work on hardware cybersecurity received best
paper nominations (ICCD 2015 and DFTS 2015) and awards (ACM TODAES 2018, ITC
2014, CCS 2013, DFTS 2013 and VLSI Design 2012). He received the Humboldt
Fellowship and the NSF CAREER Award. He is the editor-in-chief of ACM JETC and
serve(d)s on the editorial boards of IEEE and ACM Transactions (TIFS, TCAD,
TODAES, ESL, D&T, JETC). He was an IEEE Computer Society Distinguished Visitor
(2013-2015). He served on the Executive Committee of the IEEE/ACM DAC leading
the SecurityDAC initiative (2014-2017). He served as program/general chair of
conferences and serves on program committees. He is a Fellow of the IEEE for
leadership and contributions to Trustworthy Hardware.
---|---