Multiple Fault Attack on PRESENT with a Hardware Trojan Implementation in FPGA
Jakub Breier Wei He





Multiple Fault Attack on PRESENT


Physical Analysis and Cryptographic Engineering, 

Temasek Laboratories at Nanyang Technological University

Singapore

{jbreier, he.wei}@ntu.edu.sg
Multiple Fault Attack on PRESENT with a Hardware Trojan Implementation in
FPGA
    Jakub Breier and Wei He
    December 30, 2023
==============================================================================




Internet of Things connects lots of small constrained devices to the Internet.
As in any other environment, communication security is important and
cryptographic algorithms are one of many elements that we use in order to keep
messages secure.
Because of the constrained nature of these environments, it is necessary to use algorithms that do not require high computational power.
Lightweight ciphers are therefore ideal candidates for this purpose. 

In this paper, we explore a possibility of attacking an ultra-lightweight cipher PRESENT
by using a multiple fault attack. Utilizing the Differential Fault Analysis technique, we were able to
recover the secret key with two faulty encryptions and an exhaustive search of 2^16 remaining key bits.
Our attack aims at four nibbles in the penultimate round of the cipher, causing faulty output in all nibbles of
the output. We also provide a practical attack scenario by exploiting Hardware Trojan (HT) technique for 
the proposed fault injection in a Xilinx Spartan-6 FPGA.  






§ INTRODUCTION

Internet of Things brings new challenges into the security field. With
interconnection of a huge number of small devices with constrained computational
capabilities, there is a need to design algorithms and protocols simple enough
to be run on such devices within a reasonable time frame yet still preserving
high level of security. Lightweight cryptography provides algorithms that use
operations fulfilling such requirements. It delivers adequate security and does
not always lower the security-efficiency ratio <cit.>. Currently
there are many lightweight cryptography algorithms
available, providing various security levels and
encryption speed <cit.>. For the further work we have chosen
the PRESENT algorithm.

PRESENT is an ultra-lightweight block cipher, introduced by Bogdanov et al. in
2007 <cit.>. The algorithm was standardized in 2011, by the ISO/IEC
29192-2:2011 standard. It is based on SP-network, therefore uses three
operations in each round – 4-bit non-linear substitution, bit permutation and
 with the key. The best cryptanalysis presented so far is a
truncated differential attack on 26 out of 31 rounds
presented in 2014 <cit.>.

Fault attacks exploit a possibility to change the intermediate values in the
algorithm execution so that it can radically reduce the key search space or even
reveal the key. The first attack was proposed by Boneh, DeMillo and Lipton in
1996 <cit.>, following by the practical attack by Biham and Shamir
one year later <cit.>.

Currently, fault analysis is a popular method to attack cryptographic implementations, utilizing clock/voltage glitch techniques, 
diode laser and ION beam irradiation, EM pulse, or hardware trojans. For attacking symmetric block ciphers, the most popular 
technique is Differential Fault Analysis (DFA), in which the fault is usually inserted in the last rounds of a cipher for observing differences 
between correct and faulty ciphertexts. Other techniques include Collision Fault Analysis (CFA), Ineffective Fault Analysis (IFA), Safe-Error Analysis (SEA) <cit.>. We have chosen DFA as our attack technique, with inserting multiple faults in the penultimate round of PRESENT cipher.

In our work we present a novel multiple fault attack on PRESENT. By injecting four nibble-switch faults in the penultimate round we were able to
recover the secret key with only two faulty ciphertexts and an exhaustive search of 2^16 remaining bits of the key. In both faulty ciphertexts, it 
is necessary to flip different nibbles in order to produce a different fault mask in the last round. We provide a practical attack scenario by exploiting Hardware Trojan (HT) technique for fault injection in a Xilinx Spartan-6 FPGA.

The rest of the paper is organized as follows. Section <ref> provides an overview of known fault attacks on PRESENT cipher and Section <ref>
describes this cipher in details. Our attack model is proposed in Section <ref> and HT implementation of our attack is described in Section
<ref>. Finally, Section <ref> concludes our work and provides motivation for further research.



§ RELATED WORK


The first DFA attack on PRESENT was published in 2010 by G. Wang and S. Wang
<cit.>. Their attack aimed at a single nibble and they were able to
recover the secret key with the computational complexity of 2^29 by using 64
pairs of correct and faulty cipher texts on average.

Zhao et al. <cit.> proposed a fault-propagation pattern based DFA
and demonstrated this technique on PRESENT and PRINT ciphers. The attack on
PRESENT-80 and PRESENT-128 uses 8 and 16 faulty cipher texts on average, respectively, and reduces the
master key search space to 2^14.7 and 2^21.1.

Gu et al. <cit.> used a combination of differential fault analysis
and statistical cryptanalysis techniques to attack lightweight block ciphers.
They tested their methodology on PRESENT-80 and PRINT-48. The attack on PRESENT
is aimed at middle rounds of algorithm, using single random S-box and multiple
S-boxes fault attack. The main outcome of the paper is an extension of the fault
model from the usual fault model, which aims at ultimate or penultimate rounds,
to the other rounds as well. 

Bagheri et al. <cit.> presented two DFA attacks on PRESENT, the
first one attacks a single bit and the second one attacks a single nibble of the
intermediate state. They were able to recover the secret key with 18 faulty
cipher texts on average, using the second attack.

The most efficient attack so far was proposed by Jeong et al. <cit.>. They 
used a 2-byte random fault model, attacking the
algorithm state after round 28. For PRESENT-80, they needed two 2-byte faults
and for PRESENT-128 they needed three 2-byte faults and an exhaustive search of
2^22.3 on average.

Hardware Trojans have drawn much attention during the past decade due to their
severity in security-sensitive embedded systems <cit.>. As an
enormous network of diverse embedded devices, Internet of Things (IoT) is populated 
with a great number of ICs, to collect, encrypt, transmit, and store data. For each 
node inside an IoT system, a complete functional chip normally consists of sorts of IPs, 
and they are typically designed and manufactured by off-shore design houses or foundries. 
In theory, any parties involving into the design or manufacturing stages can make 
alterations in the circuits for malicious purposes <cit.> <cit.>. 
These tiny changes or extra logic can hide inside the system during the majority of its lifetime 
until a specific activation mechanism is awaken for pilfering secrets or impairing the main functionality.
  
As a typical stealthy modification to ICs, a Hardware Trojan (either named Trojan Horse) was intentionally
integrated into embedded devices for disabling or destroying a system, leaking 
confidential information from side channels, or triggering critical faults <cit.> <cit.> <cit.>. 
HT can be implanted into the circuit at multiple stages with a stealthy nature. The post-manufacturing 
testing often fail to detect it since Trojan only influences the circuit under specific conditions <cit.>. At a proper future 
time, the Trojan can be activated. Unlikely to the counterpart Software Trojan (ST), HT cannot be removed by upgrading the software in each device. So HT is truly furtive and ineradicable which hence poses more serious threat to the system security, particularly to the cryptographic blocks inside the IoT system. HT basically consists 
of two components: (a) the trigger signal that performs to activate the 
inserted trojan, and (b) the payload that is affected by the trojan <cit.>. Actually, many solutions have been proposed for detecting the implanted trojans, such as the fine-grained optical inspections <cit.> and the side-channel based comparison with the fully trustworthy “golden chip”. To increase the difficulties of HT detection, the trojan size is preferably to be as small as possible, w.r.t its host design. In this 
paper, a compact Trojan module is presented which serves to inject multiple faults into specific algorithmic points in PRESENT cipher, which makes the proposed multiple fault attack approach realistic in practices.



§ OVERVIEW OF PRESENT CIPHER


PRESENT is a symmetric block cipher, based on SP-network. It consists of 31
rounds, block length is 64 bits and it supports keys with lengths of 80 and 128
bits. Considering the usage purposes, authors recommend the 80 bit key length
version. Each round consists of three operations: XOR with the round key,
substitution by the 4-bit S-box (Table <ref>), and bit permutation
(Table <ref>).
At the end of the cipher, a post-whitening XOR with the key is performed, so there are 32 generated keys
in total. A high-level overview of the encryption process is stated in Figure <ref>.





	
	
	









Key schedule of 80-bit version of the algorithm is following. First, a secret
key is stored in register K and represented as k_79k_78… k_0. Since
the block length is 64 bits, only 64 leftmost bits are used for each
round. Therefore, at round i we have:

    K_i := κ_63κ_62…κ_0 = k_79k_78… k_16.

After every round, key register K is updated in a following way:

  
  * [k_79k_78… k_1k_0] = [k_18k_17… k_20k_19]
  
  * [k_79k_78k_77k_76] = S[k_79k_78k_77k_76]
  
  * [k_19k_18k_17k_16k_15] =
  [k_19k_18k_17k_16k_15]⊕ RC 

where RC is a round counter.


§ ATTACK MODEL


PRESENT algorithm uses sixteen 4-bit S-boxes. The output of S-boxes is an input
for the permutation layer. The attack exploits following properties of the
algorithm:

  
  * Output of one S-box is an input for four different S-boxes.
  
  * Input of one S-box consists of outputs from four different S-boxes.
  
  * There are four different groups of S-boxes: 
  
  	
  * The outputs of S-boxes 0-3 are inputs for S-boxes 0,4,8,12,
  	
  * The outputs of S-boxes 4-7 are inputs for S-boxes 1,5,9,13,
  	
  * The outputs of S-boxes 8-11 are inputs for S-boxes 2,6,10,14,
  	
  * The outputs of S-boxes 12-15 are inputs for S-boxes 3,7,11,15.
  

If it is possible to corrupt the whole output of some S-box (flip four bits),
the fault will spread into four S-boxes in the following round, affecting the
same bit position in every S-box. Therefore if we aim at four S-boxes from
distinct groups in round 30, the fault will be distributed to every
S-box in round 31. This fact is depicted in Figure. <ref>.




 §.§ Attack Steps

The attack steps are following:

  
  * The attacker inserts four 4-bit faults at the output of four S-boxes
  from distinct groups.
  
  * She computes difference tables according to the fault model. More
  specifically, the bit faults in S_i,j^31, where i∈0,..,15 are
  S-boxes of round 31 and j∈0,1,2,3 are bits of particular S-box are
  following:
  
    
  * Fault at S_0^30, S_4^30, S_8^30, S_12^30 will result to
    faults at S_i,0^31.
    
  * Fault at S_1^30, S_5^30, S_9^30, S_13^30 will result to
    faults at S_i,1^31.
    
  * Fault at S_2^30, S_6^30, S_10^30, S_14^30 will result to
    faults at S_i,2^31.
    
  * Fault at S_3^30, S_7^30, S_11^30, S_15^30 will result to
    faults at S_i,3^31.
  
  Those difference tables contain the fault mask (bit position of a fault) and
  the output mask, which is the difference of the S-box output of a correct and
  faulty input. As an example, for masks 1000 and 0100, Table
  <ref> shows these values.
  
  * Using a formula <ref>, the attacker observes the output differences and she
  searches for possible S^31 input candidates.
  
  * She repeats steps 1-3, inserting fault in different nibbles, which will
  result to attacking different S-box bits at S^31.
  
  * Shee compares the possible candidate sets from both attacks, the
  intersection of these sets gives exactly one candidate, which is the correct
  state before S^31.
  
  * After obtaining all the key nibbles of K^31, the attacker uses an
  exhaustive search on the rest of the key, so the search space is 2^16. 


    Δ = P^-1(C') ⊕ P^-1(C)




 §.§ Attack Example

After obtaining the faulty ciphertext and inverting the last round permutation
layer, it is possible to obtain information about the input of the substitution
layer. Let us assume that we attacked the first nibble after the S-box operation
in round 30. Therefore the faulty mask of inputs of S-boxes 0,4,8,12 in round 31
will be 1000. We can now observe the changes in the output of the algorithm.
Table <ref> shows every possible input and output of the S-box
operation, together with the faulty one, after attacking the most significant
bit. It is easy to see that in the worst case, we have narrowed the input
candidates to four numbers. For example, for the output difference 1111, we have
input candidates 0, 7, 8, 9. The notation is following:

  
  * I is a correct input of the S-box.
  
  * I' is a faulty input of the S-box.
  
  * O is a correct output of the S-box.
  
  * O' is a faulty output of the S-box.
  
  * Δ is the output difference between the correct and the faulty
  output.




The second step of the attack is to change the attacked nibble, so that it will
affect another output nibble of the S-box belonging to the same group as the
first one. Let us assume, we attacked the second nibble of the S-box output in
round 30. Therefore the input of the same S-boxes in round 31 will be changed,
but the faulty mask will be 0100 in this case. The outputs for this case are
stated in table <ref>. It is easy to see that the groups of the
input values producing the same differences after the fault are not overlapping
with the first attack, therefore we can determine the input value with
certainty. For example if the output difference in this case would be 0101, the
possible input candidates are 0, 1, 4, 5. The only common number for both
attacks is 0, therefore it is the input value for the given S-box.

Using the simplified attack model with only one faulty nibble, it is possible to
reveal the last round key with 8 faulty encryptions, since it is necessary to
attack two distinct nibbles of each of four groups of S-boxes. If there is a
possibility to inject multiple faults per encryption, the last round key could
be revealed with 2 encryptions. In each run, the attacker would inject the fault
into one nibble of the S-box output of four different groups, changing the
nibbles after the first run. In both cases, an exhaustive search of 2^16 is
required to obtain the whole PRESENT-80 key.



§ HARDWARE TROJAN FOR PRACTICAL FAULT INJECTION


In this section, an FPGA implemented PRESENT cipher for the described multiple 
fault analysis approach will be detailed. The hardware realization relies on 
a Spartan-6 FPGA (XC6SLX4), soldered on Diligent Cmod-S6 commercial board <cit.>. We mounted the injections using the hardmacro-based 
Hardware Trojan (HT) <cit.> by inserting specially created 
trojan modules into the algorithmic networks in FPGA scenario.



 §.§ FPGA Scenario

Field Programmed Gate Array (FPGA) has been widely utilized in almost 
all digital/hybrid logic applications due to its rapid implementation, 
low cost and high performance. The major advantage of hardware implementation 
for cipher lies within its parallel computation networks that allow multiple 
logic chains computed in parallel, which results in high computational speed 
compared to the microcontroller scenarios. In our work, PRESENT cipher 
was implemented inside a compact Spartan-6 FPGA. 
The cipher is structured in loops with 16 4-bit S-boxes in parallel. The 
complete encryption is clocked with a global clock signal and the intermediate 
values from each round are stored in 128 1-bit registers. So a complete encryption in out implementation consists of 32 clock cycles, as seen in Figure <ref>.





 §.§ Hardware Trojan for Fault Injection

HT typically requires some trigger signals to activate the inserted trojan 
modules. By the principle of the proposed multiple fault injection, a 1 bit 
signal of trojan_trigger is activated at the 30th encryption 
round when the fault perturbation is required. Since the injection point 
is at the output of the S-box, the specially devised trojan hardmacro for 
S-boxes 0, 4, 8, 12, and for S-boxes 1, 5, 9, 13 can be inserted during the 
chip fabrication or at the off-the-shelf stage. The payload is highlighted 
in the grey box of Figure <ref>. Signal of the flip_trigger 
is used to control the injection into different S-box groups. Since only 2 
injection rounds are needed for the proposed fault attack, another 1 bit 
signal is enough. So there are totally 2 bit signals acting as the trigger 
in this solution. In Spartan-6 FPGA, every slice consists of 4 look-up tables 
(LUT), 8 multiplexers and 8 flip-flops. Even each LUT can either be used as one 
6-input 1-output Boolean function or two 5-input 1-output functions, only 4 multiplexers in each slice has an external input that we have to use as the 1 input bit of the XOR gate and the input of multiplexer after the XOR gate. Therefore
one slice can actually implement 4 HT modules, and 8 extra slices, i.e., 4 
Configurable Logic Blocks (CLBs), are sufficient for inserting all the 8 trojans. 
The states of the 2-bit trigger signals are given in Table <ref>. 
It is emphasized that the insertion of trojan can as well apply to different 
S-box groups, just obeying the principles explained in Section <ref>.






§ CONCLUSIONS


In our paper we have proposed a multiple fault injection attack on PRESENT cipher, using DFA technique. By flipping four nibbles in the penultimate round
we were able to obtain the secret key using two faulty ciphertext and an exhaustive search of a 2^16 bits. We have implemented a hardware trojan,
causing this type of fault on an FPGA implementation of PRESENT.

There are two other possible attack scenarios. The first one is flipping more
than 4 bits, therefore the attack would affect the following nibble as well. In
this case, more than one bit of particular S-box in round 31 will be affected.
The attack can be still executed in the same way, only the differential table
for the concrete fault mask has to be computed. It can be shown, that
intersection of arbitrary two masks from two distinct differential tables gives
exactly one candidate in every case, so it is possible to use multiple-bit fault
masks.

The other scenario is flipping less than 4 bits in one nibble. In this case, the
fault doesn't spread into every S^31 S-box. The solution for this scenario
is to use more faults, therefore the number of encryptions will increase.

The hardware trojan approach supporting the proposed multiple fault attack relies on the hardmacro based HT modules to be inserted into the outputs of 
specific S-boxes. In our tested Spartan-6 FPGA, only 4 CLBs are 
sufficient to implement the 8 trojan modules combined with 2 bit global trigger signal. 
Since the trojan blocks are inserted into the signal path of specific S-box outputs, without altering the main functionality of the ciphers, the trojan can be mounted at almost all design stages, such as front-end HDL coding or netlist alteration, as well as back-end layout or sub-gate manipulation.



In the subsequent work, we would like to focus on the realistic trojan insertion using the proposed multiple fault analysis into the security modules of an IoT scenario, and the related HT detection technique will also be emphasized. 

splncs03
 

