Protecting software implementations of block ciphers from side channel attacks is a significant concern to realize secure embedded computation platforms. The relevance of the issue calls for the automation of the side channel vulnerability assessment of a block cipher implementation, and the automated application of provably secure defenses. The most recent methodology in the field is an application of a specialized data-flow analysis, performed by means of the LLVM compiler framework, detecting in the AES cipher the portions of the code amenable to key extraction via side channel analysis. The contribution of this work is an enhancement to the existing data-flow analysis which extending it to tackle any block cipher implemented in software. In particular, the extended strategy takes fully into account the data dependencies present in the key schedule of a block cipher, regardless of its complexity, to obtain consistently sound results. This paper details the analysis strategy and presents new results on the tailored application of power and electro-magnetic emission analysis countermeasures, evaluating the performances on both the ARM Cortex-M and the MIPS ISA. The experimental evaluation reports a case study on two block ciphers: the first designed to achieve a high security margin at a non-negligible computational cost, and a lightweight one. The results show that, when side-channel-protected implementations are considered, the high-security block cipher is indeed more efficient than the lightweight one.
Embedded systems have a high platform diversification in terms of both the available computational
resources on board, the actual instruction set architecture of the underlying computing core, and the
availability of both volatile and non volatile memory. Such significant differences result in
corresponding high engineering costs to realize functional, energy efficient and secure embedded systems. In
particular, providing sound security guarantees in the embedded system world is a crucial issue, as they
are increasingly in charge of critical tasks, and their expected long field life results in failures causing
concrete problems over potentially a decade’s worth of devices, especially in the Internet of Things and
automotive environments [
Contributions. We propose an improvement over the current state of the art of compiler-based
automated SCA countermeasure application. We provide accurate identification technique determining
the most effective choice of the key material (i.e., the user key and the expanded key computed during
the cipher keyschedule) to be retrieved when attacking via SCA a block cipher. Our contribution pushes
forward the abilities of the automated analysis proposed in [
Given a block cipher implementation, the side channel attack (SCA) workflow is a known plaintext
attack, where the adversary knows both the plaintext and the ciphertext, and aims at retrieving the secret
key through examining multiple runs of the algorithm on different inputs [
Countermeasures aimed at protecting block cipher implementations can be classified ashiding [
In a masked implementation, each sensitive intermediate value is represented as split in a number of shares, s, which are all needed for its reconstruction For example, s shares are obtained as s−1 random values and the xor combination of them with the original input. The target algorithm is modified to perform the entire computation on the set of share-split values recombining them only at the end.
The instantaneous power consumption is independent from the original (non-masked) value, as unpredictable random values are newly generated at each run of the cipher. Typically, masking techniques are categorized by the number of masks, d=s−1, employed for each sensitive value, which is known as the order of the masking. A d-th-order masking can be broken by a (d+1)-th-order attack through combining d+1 measurements of the computations of different shares during the same cipher execution.
Currently, state of the art masking schemes are the Ishai-Sahai-Wagner (ISW masking) [
The only provably secure scheme providing a constructive framework to perform secure table
lookups on share split values for any number of shares is described in [
In this section we provide the preliminary notions on data-flow analysis, and subsequently report the
enhanced key material identification allowing the analysis in [
From now on, we will also indicate the elements of V as nodes and consider both GC(V, AC) and GD(V, AD) as augmented graphs containing two additional nodes, vbegin, vend, such that vbegin acts as the immediate predecessor of all the nodes which do not have one, and vend acts as the immediate successor of all the nodes without successors. Moreover we will also consider the nodes of the graphs to be composed of single operation statements. A static analysis of a program P , represented either as its CFG or DFG, is called Data-Flow Analysis (DFA) if it aims to describe a well-defined property on how P manipulates its data at runtime. Being a static technique a DFA will only be able to compute a conservative approximation of the said property as no knowledge on the actual runtime execution flow is available to it. More formally, the definition of a DFA is as follows.
Definition 3.3 (Data-flow Analysis) . Let P be a program, represented as either GC(V, AC) or GD(V, AD). Let BVn be an n-dimensional Boolean lattice, n ≥ 1, endowed with a partial ordering relation closed with respect to two operations, named as meet (t) and join (u), which yield the minimum and maximum of any pair of elements in BVn. A Data-Flow Analysis decorates each node of GC(V, AC) (resp. GD(V, AD)) with an element of BVn and describes a well-defined property of P through computing the solution of a set of simultaneous equations over the elements of BVn. A practical example of DFA is the computation of a program property known as reaching definitions , i.e.: the identification of all the possible points on the CFG of the program,GC(V, AC), where a variable visible from a program statement may have been defined. In this context, the semantics of an element of BVn map each one of its Boolean components to a the definition point of a program variable on the CFG. The solution of the set of simultaneous equations checked by the DFA consists in the values in BVn (one for each node of CFG), which are expected to have a bit set if the corresponding definition point is visible from the statement to which the element of BVn at hand is bound.
Depending on the nature of the program property which is being computed, it is commonplace to categorize data-flow analyses into forward DFAs or backward DFAs. Furthermore, the aforementioned set of simultaneous equations is expressed using use of the concepts of In-Set and Out-set, which are formally defined as follows.
Definition 3.4 (In-Set, Out-Set). Given a CFG GC(V, AC), In(v) is defined for each statement v∈V the input set as the collection of elements in BVn associated to all immediate predecessors of v: In(v)={ dv0 ∈BVn | dv0 is bound to v0, v0∈pred(v) }. The output set of a statement v, denoted as Out(v) is defined as In(v)∪{dv}, where dv is the element of BVn bound to v.
For each node v of the CFG (resp. the DFG) of a program, the data-flow equations describing the property at hand can be specified as follows:
(Out(v)
In(v) = fv(In(v)) = Fp∈pred(v) Out(p)
(In(v)
Out(v) = fv0 (Out(v)) = Fs∈succ(v) In(s) where pred(v) and succ(v) denote the sets of immediate predecessors and the immediate successors of v, while fv(·) and fv0 (·) are functions depending on the nature of the considered property which specify the local computations to be performed on the values in BVn associated with In(v) and Out(v).
The program property is computed by the DFA through applying iteratively the data-flow equations to an initial assignment of the values dv∈BVn for each node v in GC(V, AC) (resp. GD(V, AD)) until a fixed point is reached. Usually, a DFA solver implements an iterative visiting strategy of the CFG (resp. DFG) which keeps a worklist of nodes. Such a list is initialized with all v∈V and, until it is empty, a node is evicted to apply the data-flow equations to its In-set and Out-set. Once done so, all the nodes having their In-set or Out-set modified as a result are added to the worklist. Sound data-flow analyses have a proof of termination which is provided in terms of the existence of a fixed point for each possible initial assignment to the program nodes. 3.1
Security oriented DFA To define a resistance metric against SCA for each instruction of a block cipher, we consider the data dependencies holding between the user key loading instructions and the outputs of every other instruction of the program. We model these data dependencies binding to each output bit of an instruction as an element b∈BV|k|, where |k| is the size in bits of the user key of the block cipher. The result of our DFA sets the i-th component of b to one if the associated output bit of the instruction depends on the i-th user key bit. It is useful to group all the elements of BV|k| bound to the output bits of a given node v of the CFG as a |v| × |k| Boolean matrix, where |v| is the size (in bits) of the output of the node. The SCA resistance of an instruction is formalized as follows.
Definition 3.5 (SCA resistance). Let v be a CFG node to which is associated a |v|×|k| Boolean matrix and let COUNT(j) be the count of the components of the j-th row of the matrix set to one, i.e., the number of user key bits on which the j-th output bit of v depends on. The SCA resistance of v, r(v), is defined as minj (COUNT(j)) if COUNT(j)>0 for at least one value of j, or ⊥ if the entire output of the instruction does not depend on the user key. Source Code Front-end
Extended Intermediate Representation
(IR) Optimization
Passes Targeted Key
Material Identification SCA Resistance
Computation Forward DFA
with Targeted Key
Backward DFA
with Targeted Key
Decorated IR Countermeasure
Application Protected IR Back-end Protected Binary Code
We note that, given the SCA resistance of an instruction v, r(v), an adversary will require a computational effort Ω(2r(v)) to perform a key retrieval guessing r(v) bits. The computation of the SCA resistance is performed through a sequence of static code analyses and transformations performed by the front-end and middle-end of the LLVM compiler infrastructure as depicted in Figure 1. Compiler Front-End and Optimization Passes. First of all, we modified theclang LLVM front-end to recognize three attributes with the standard GNU syntax, which are employed by the programmer to mark i) the variables containing the block cipher input and ii) user key, and iii) the tabulated nonlinear functions named substitution boxes (SBoxes). To tag instructions in a way that survives the optimization passes of LLVM, we employ the input and key values as arguments of opaque intrinsics, defined to have memory affecting side effects. We run the entire set of optimizations of the middle end (-O3), bar the ones able to identify patterns in the code which can be substituted with a call to the C standard library (e.g., replacing a memory copy with a call to memcpy). The LLVM Intermediate Representation (IR) emitted by the front-end is in Single Static Assignment form: a 1:1 binding between an instruction v∈V and its defined variable is present. We will employ the two concepts interchangeably from now on, and consider the IR as the program P out of which GC(V, AC) and GD(V, AD) are built.
User Key Dependency Propagation. The user key dependency propagation pass is the first one of our analysis. Its purpose is to compute the data dependency of the entire cipher and key schedule from the user (i.e., non expanded) key. To this end, we compute a partition of the nodes of GC(V, AC) in three subsets, Vks, Vc, Va according to whether they belong to the key schedule, the cipher body, or to eventual ancillary code, respectively. Such a partition is computed as a simple forward DFA, of which the property is constituted by a two bit vector, the first one indicating if the node lies in Vks, and the second one if it is in Vc. The function of the DFA equations sets the first bit only if all the nodes having their result used by the current instruction are in Vks, while the second bit is set if at least one of the operands is in Vc. The initial state of the data-flow marks as belonging to Vc all the instructions tagged with our intrinsics, while the key schedule bit is set only on the key-load ones. The results of this analysis will be employed by the Forward/Backward DFA with Targeted Key passes (see Figure 1).
Subsequently, a second DFA computes the data dependency of each operation from the user key. To this end, the computed property is described as a |v|×|k| Boolean matrix Uv. The DFA solver initializes, for all v∈V , the Uv matrices to zero, save for the ones bound to user key-load instructions, which have the appropriate |v|×|v| submatrix set to the identity matrix, to represent the 1:1 dependency of a user key bit from itself. The fv(·) function of the forward DFA considers the user key dependencies Algorithm 3.1: Target Key Material Identification
Input: GC(V, AC): CFG of a block cipher with a |k| bits user key; δs(v) : V →{0, . . . , dmax}: map of a node v∈V to its distance from vbegin of GD(V, AD); dmax is the height of the DFG; Uv: matrix of user key dependencies for v ∈ V Output: T : set of elements of Vks containing target key material, ⊥ if no viable assignment Data: f , o, b: bit vectors of size |k|; 0, 1: constant |k| bit vectors, zero- and one-filled.
F : Set of triples (v, c, l) where v ∈ V , where c, l are Boolean vectors of length |k| containing the subkey bits bound to v and
left over as a result of an unconstrained choice
1 b ← 0; T ← ∅; F ← ∅
2 for d ← 1 to dmax do
3 foreach v ∈ V s.t. δ(v) = d do
4 f ← ORROWWISE(Uv) ∧ ¬b
5 o, F ← GREEDYOPTIMIZE(v, Uv, f , F )
6 if o 6= 0 then
7 b ← b ∨ CHECKCONSTRAINTS(v, f , o, F )
8 T ← T ∪ {v}
9 if b = 1 then return T
10 return ⊥
of the operands of v, and sets its Uv combining the ones of its operands. The user key dependencies of
a single bit of the output of v, i.e., a row of Uv, are obtained computing the elementwise Boolean-or
combination of the rows corresponding to the bits of the operands required to compute it. If v is a bitwise
operation, its fv(·) function derives Uv matrix as the row-wise or of the matrices of its operands. By
contrast, the fv(·) for arithmetic operations take into account also the effects of borrows and carries. For
an in-depth description of the individual fv(·) functions we refer the reader to [
Target Key Material Identification. Once the first pass of the analysis has computed the contents of
the U matrices for all the instructions, we proceed to the identification of the subkey bits which yield
the best adversary choice during an attack. While such an identification is easy in the case of AES,
as reported in [
Consequentially, the set of key material bits which will be the target of the actual SCA needs to fulfill the following properties: i) its size is greater or equal than the user key size, ii) for each user key bit, at least one of its members depends on it, iii) the entirety of its members are not dominated by the remaining key material on the GD(V, AD), iv) its size is minimized. Conditions i) and ii) ensure the computation of the user key employing the retrieved key material, while condition iii) ensures the minimization of the adversary effort. Condition iv) is imposed so that no key material which cannot be derived from SCA extracted one, is selected.
To derive the set of instructions T ⊂Vks containing the target key material as output, the first step is to compute a map δs(·) :V →N which expresses the distance of a given instruction from vbegin in the GD(V, AD). Subsequently a map δe(·) :V →N which expresses the distance from vend is also computed. Such maps can be computed performing a breadth first visit ofGD(V, AD), following the definition-use chains in it. Two maps are required, as the optimal choice of an adversary for the target key material is different, depending on whether the data available to her is the input or the output of the cipher. For the sake of clarity, we consider from now on the former case, noting that the latter is analogous, provided that care is taken to reverse the direction of the analyses. Once the δs(·) map is available, the target key identification pass proceeds to employ Algorithm 3.1 to compute the setT , initializing it as empty (line 1). To determine 1:1 binding between the user key bits and the target key material bits satisfying conditions i) and ii), a |k|-bit sized vector b is employed to keep track of which user key bits have already been bound. Such a vector is initially set to 0 (line 1). The examination of the user key dependency matrix Uv of an instruction v may have a significant degree of freedom in choosing which user key bits should be bound to the target key material ones. Indeed, its |v|-bit output may depend on all the |k|>|v| user key bits. Since a bijection is desired, Algorithm 3.1 will perform an arbitrary choice locally, and memorize it in the form of a triple (v, c, l) containing the instruction v, which user key bits were chosen to be bound c, and which ones to be left l, respectively. Such an information is stored in the set F , initially empty (line 1), which is exploited to optimize the target key material selection process.
After initializing b, T and F , Algorithm 3.1 examines the elements of Vks starting from the ones closer to vbegin in GD(V, AD) (lines 2-10) and tries to bind all the user key bits as soon as possible. To this end, the computation starts with determining which of the user key bits, on which the output of v depends, are still free from binding (line 4). Such bits, which are deduced removing the bound ones from the row-wise Boolean-or reduction of Uv, are stored in the |k|-bit long vector: f .
Subsequently, to the GREEDYOPTIMIZE procedure attempts to ameliorate the current user key dependency choice Uv for the current node v exploiting the information on which bindings have already been made, and which ones had freedom of choice in being done as memorized in f and F In particular, for each element (v0, c, l) of F , GREEDYOPTIMIZE checks if a) some of the bits bound to v0 can also be bound to the output of v, and b) some of the unbound bits in v0 cannot be bound to v. If this is the case, it is possible to optimize the decision of the bits to be bound to the output of v having it relieve v0 of some of its arbitrarily assigned bits, in exchange for v0 taking care of bits which cannot be bound in v. Since the nodes of v are visited in increasing depth order, GREEDYOPTIMIZE effectively realizes swaps which guarantee condition iii), i.e., no set of target key material bits dominates strictly the chosen one on the DFG. GREEDYOPTIMIZE returns both an optimized choice bit vector o, and the updated set F . If the optimized binding selection contained in o suggests that at least a user key bit should be bound to the output of v, i.e., o6=0, (line 6) Algorithm 3.1 proceeds to add the contents of o to the bound bits contained in b after verifying the feasibility of the binding invoking the CHECKCONSTRAINTS function. The CHECKCONSTRAINTS verifies that the amount of user key bits which should be bound in the outputs of v does not exceed |v|, and, if that is the case, limits the amount of the bound bits to |v|, adding an element to the F set to memorize the choice made. Upon completing the visit of all the nodes with a given depth, Algorithm 3.1 checks whether all the user key bits are bound (line 9) and, if that is the case, returns the set T . The reason for checking this condition at the end of the visit of the set of nodes having the same depth is to allow the possible optimization of all last level assignment to take place. Forward/Backward DFA with Targeted Key and SCA Resistance Computation. After computing the set of target key material, the analysis passes proceed with the computation of the data dependencies of all the nodes in Vc from the selected target subkey bits. Such a computation is performed employing the same DFA used to determine the dependencies from the user key, taking care of considering the target key material data dependencies as the ones to be propagated. The analysis is performed both in the form of a forward DFA, and a backward one considering the data dependencies of the inverse operations, starting from the cipher output. The final result of the computation are two Boolean matrices, Fv and Bv, containing the data dependencies of each instruction from the target subkey bits. To the end of computing the SCA resistance of an instruction v, the analysis computes the minimum, non null, number of key bits which depend on a single output bit of v across both matrices. We note that having an instruction output bit which depends on no key bits results in the value being irrelevant for SCAs, as it does not contain any key.
Countermeasure Application. Finally, after the computation of the per-instruction SCA security
margin, we realized a code transformation pass applying systematically the ISW masking scheme [
In our case study, we chose a general purpose block cipher, Serpent, and two lightweight ones, MISTY1 and Simon, implemented in C language without any architecture-specific optimization.
We chose Serpent due to its significant security margin, which resulted in the design being selected
as a finalist in the AES contest [
MISTY1 is a lightweight cipher designed in 1995, and described in the IETF RFC 2994 [
Simon is a lightweight block cipher released in 2013 by Beaulieu et al. from the U.S.A. National
Security Agency [
Figure 2 reports the graphical representation of the results of our security oriented data-flow analysis
on Serpent, MISTY1 and Simon. The ciphers are represented as a sequences of colored tiles, one per
instruction, organized in program order from left to right, and from top to bottom. The figure shows the
SCA resistance of each instruction executed during a cipher run, with colors ranging over a chromatic
scale from 1 (red) to 128 (blue). The higher the resistance value, the higher the computational effort
required to perform a secret key retrieval. The maximum resistance value (128 in our case) corresponds
to the computational effort required for an exhaustive user key search [
Performance Evaluation. We conducted our performance evaluation measuring both implementations
of the aforementioned three ciphers plus the one of AES-128 cipher. To provide a fair comparison with
the results of [
The first evaluation platform is the STM32F4Discovery board equipped with a STM32F407 μC based on a 120MHz ARMv7 Cortex-M4, and endowed with 128kiB of SRAM, 1MiB of Flash and a hardware Random Number Generator (RNG). The binaries are run on the bare metal, and the timings are gathered measuring the time between the assertion and deassertion of a GPIO on 30 runs of the cipher. The second platform is an Imagination Creator CI20 board equipped with an Ingenic JZ4780 SoC. The SoC is based on a dual core MIPS32 clocked at 1.2GHz, with a 32k L1 I- and D-cache, a 512k L2 I&D cache, and 1GiB of DDR3 RAM, running Debian wheezy. Timing measurements where collected using the Linux kernel timer CLOCK_PROCESS_CPUTIME_ID, which only accounts for cycles attributed to the current process. To compensate for the higher variability of the environment, timings have been averaged over 104 measurements. To supply random values for the masking countermeasures, we employed the hardware RNG on the Cortex-M4, and the system-wide RNG on the MIPS based one.
Table 1 reports the results of our experimental campaign. Applying tailored SCA countermeasures,
i.e., applying them to all instructions with a SCA resistance lower than the key size, allows to obtain
significant performance improvements over a fully protected implementation. Block ciphers which
employ lookup tables, i.e., AES and MISTY1 have the largest absolute gain in execution time, although the
smallest relative one. Moreover, block ciphers which do not use lookup tables for non-linear functions
are significantly faster when endowed with SCA countermeasures. It is worth noting that both Serpent
and Simon, which are slower than MISTY1 in their unprotected implementation, are at least one order
of magnitude faster when protected. Indeed, it is interesting how Serpent outperforms Simon on both
platforms if tailored SCA countermeasures are applied, despite the latter being explicitly designed as a
lightweight cipher, and the former not being so. Finally, it is interesting to note how the 10× difference
in clock speed between the two platforms yields only moderate speedups for the fully protected variants
of AES and MISTY1. This behavior is caused by the increase in the size of the lookup tables required
by the share splitting of [
In this work we presented an enhancement to the existing security oriented data-flow technique, which
allows the automatic identification of the target key material in a block cipher. Such an enhanced
analysis allowed us to analyze block ciphers with nontrivial target key material choices, and to
evaluate a tailored protection to their implementation as a secure alternative to a code morphing approach
such as [