Even a highly secured algorithm that proves to be mathematically secured has a possibility to leak secret information, like key, thus stored while implementing them in hardware platform. This study focuses on the necessity to prevent such leakage by making some changes in the algorithm in such a way that the functionality of the algorithm is unaltered thereby assuring the possibility of attacks are greatly reduced. This study discusses the Field Programmable Gate Array (FPGA) implementation of the Advanced Encryption Standard (AES) with countermeasures against Differential Power Analysis (DPA) attacks. The study proposes two different countermeasure methods: register swapping and random recharging. As a result, it shows that these countermeasures increase the complexity of attack.
PDF Abstract XML References Citation
How to cite this article
In the year 2001, in response to the need of new cryptographic algorithm National institute of standards and security (NIST) called for a competition and announced the Advanced Encryption Standard (AES) as RIJNDAEL algorithm which was developed by the two Belgian cryptographers Joan Daemen and Vincent Rijmen. AES is an iterative block cipher algorithm which iterates the steps depending on the key size since the message block size is always kept constant. So AES will be represented as AES-128, AES-192 and AES-256 where the numbers represent the size of the key in bits. Here in this paper the AES-128 is taken and modification is done on it to prove itself to be more critical for the attackers.
The algorithmic flow of AES-128 which takes 10 rounds has four intermediate steps Sub Bytes, Shift Rows, Mix Columns, Add Round Key will be executed for first 9 rounds and for the last round Mix Columns is omitted (Daemen and Rijmen, 2002). The Sub bytes is the only non-linear step which replaces a byte with using composite field arithmetic. The Shift Rows is a transposition step where first row has no shift whereas second; third and fourth has one, two and three cyclic left shifts respectively. The Mix Columns takes every column of the state and multiplies with a predefined 4x4 matrix. The Add Round Key performs an XOR operation between the state and the round key from the key schedule. Key scheduling is parallel process with the algorithm which produces a round key for each and every round. It initiates with the input cipher key and some assistance from S-BOX table and R-con table to produce the round key. For further calculation it takes the previous round key and operates.
|AES encryption process flow graph, Red circle: Weak part of our implementation where counterm easures are added
Figure 1 shows the algorithmic flow of AES and the weakest part of implementation is encircled where Differential Power Analysis Attack (DPA) is performed. DPA is a form of Side Channel Attack (SCA) which retrieves the secret information (key), which is used by the cryptographic module. The power consumption of the target FPGA depends on the data it processes and the operation it performs. In straight forward implementation of the algorithm, the state register gets updated every round which can be exploited to retrieve the key. The DPA attack reduces the possibility of attacks to 2ˆ8 from 2ˆ128. In our hardware implementation (Satoh et al., 2001) of AES, the attack is targeted in the last round (tenth round) because:
|The outcome of the algorithm (cipher) is known
|No Mix Columns operation which helps attacker to backtrack from the final round by a single key guess and inverse Sub Bytes and Shift Rows operation
MATERIALS AND METHODS
Figure 2 shows the DPA measurement setup. The setup has a workstation installed with Modelsim tool to simulate, Xilinx ISE/EDK tool to synthesis and to generate the bit file, MATLAB tool to generate random input for testing and to design the power model. Side-channel Attack Standard Evaluation BOard (SASEBO) (Satoh, 2007) is used as a FPGA platform for analysis. SASEBO has target FPGA where AES algorithm is configured and the control FPGA where the control protocol for communication between the target FPGA and the work station is configured.
|Differential power measurement setup
Oscilloscope is used to measure the power consumed (Kocher et al., 1998) and record its points in the work station. The external trigger will activate the oscilloscope every time when the encryption process starts.
Counter measures: The solution to reduce the possibility of attack on the algorithm is termed as countermeasures. The countermeasures that target the output register are experimented here. The target is fixed to be as final round (tenth round) because the cipher is known to the attacker and also there is no Mix Columns operation. The attack model is designed such that back tracking is done on cipher by a key guess and performing inverse Shift Rows and inverse Sub Bytes (Mui, 2007) to get the ninth round output. Then hamming distance is calculated between the output of ninth round and tenth round. We do byte by byte key hypothesis and a trace is obtained by correlating the exact trace obtained from the device and the guessed trace points, we will get a highest peak gives us the exact key that was guessed.
Register swapping: Register swapping (May et al., 2001) is a technique of breaking the link of the data flow by which the dependencies over the data is considerable reduced. If the flow of the data is not known, it will be a tough task for the attacker to retrieve the key.
In this implementation (Fig. 3) rather having a single register for the AES state which gets updated for every round, two registers are placed. These registers are selected alternatively based on the round so that the flow link is broken. So that an attacker who targets any one of the register may not retrieve the exact key by doing single key guess. Because if he does a single key guess he may arrive at ninth rounds output but the value stored previously was the output of the eighth round so the attacker has to do two key guesses, which increases the complexity from 28 to 216. One key guess as 10th round key and one for 9th round totally there will be 65536 combinations for a byte. The 9th round also has Mix Columns which need a column (4 bytes) to operate hence we require 4 times the combination is required. Then comes the shift rows which varies the position and the complexity varies on the position which we are targeting. Likewise the simple 256 combination of key guess in exponentially increased to a huge value which makes the attack more difficult. By having two register the drastic increase in complexity is observed. This can be made even more complex by placing as many register as the round and selecting them randomly by placing a pseudo random number generator.
|Register swapping method
|Random pre-charging method
Thus the register once used will not be used again. By doing this there will a tremendous increase in the complexity of the algorithm and we can prove it be more secure from the DPA attack.
Random pre-charging: Random Pre-charging is a technique by which the value of the state register is randomized by inserting a random number in the last but oneth stage so that the attacker may not know what happens to the state register in the round before the last round of the algorithm hence it will be critical for the attacker to retrieve the key (Rajagopalan et al., 2012).
In this implementation (Fig. 4) the result of the tenth round is stored in a temporary register and also in the state register. While performing the tenth round the value in the state register is XORed with a random number generated by a pseudo random number generator. For the next round the value stored in the temporary register is taken and all other steps are computed and cipher text is expelled out. By this way when an attacker targets the output register may confuse.
AES implementation with different counter measures are coded with VHDL programming language and simulated using Model-sim synthesised using Xilinx ISE and tested in SASEBO board. The device usage and the timing constrains are tabled in Table 1 and 2.
The straight forward implementation of AES will complete the encryption process at 10 clock cycles and it can be attacked even with 4000 random inputs. Figure 5 shows the power trace of one encryption cycle and 4000 encryption cycles with random inputs.
The AES with Register swapping countermeasure occupies more area than all other implementations and completes the process in 10 clock cycles. Figure 6 shows the power consumption trace of one encryption cycle and 10000 encryption cycles with random inputs of AES with register swapping countermeasure. The possibility of attack is checked with 10000 random inputs but the attack fails and the implementation proves it to be rigid for DPA attacks.
|Device utilization of various implementations of AES targeting VIRTEX 2P-VP7
|Timing summary of various implementations of AES targeting VIRTEX 2P-VP7
|Successful attack on straight forward implementation of AES
|Power trace for 1 encryption process and correlation of 10 k power traces of AES-register swapping
|Power trace for 1 encryption process and correlation of 10k power traces of AES-Register pre-charging
The AES with Random Pre-charging countermeasure occupies less area when compared to the other countermeasure but completes the whole encryption process in 11 clock cycles which is one more than the straight forward implementation and register swapping technique. Figure 7 shows the power consumption trace of one encryption cycle and 10000 encryption cycles with random inputs of AES with random precharging countermeasure. The possibility of attack is checked with 10000 random inputs and found to be secure against DPA attacks.
Any algorithm which is proved to be secure mathematically may fail when gets implemented in hardware hence the algorithm should be implemented with some countermeasures which increase the complexity of attacks. Two such countermeasures register swapping and random precharging are taken and analysed. We succeeded in increasing the complexity of attacks exponentially and made the attack a tough task to perform.