InteractionbetweenFaultAttackCountermeasures ...

1 Interaction between Fault Attack Countermeasuresand the Resistance against Power Analysis AttacksFrancesco Regazzoni, Luca Breveglieri, Paolo Ienne, and Israel Koren1 Francesco Regazzoni, UCL Crypto Group, Universit e catholique de Louvain, B-1348 Louvain-la-Neuve, Belgium and ALaRI - University of Lugano, CH-6904 Lugano,Switzerland2 Luca Breveglieri, DEI - Politecnico di Milano, 20133 Milano, Italy3 Paolo Ienne, Ecole Polytechnique F ed erale de Lausanne (EPFL) School of Computer andCommunication Sciences CH-1015 Lausanne, Switzerland4 Israel Koren, University of Massachusetts, Amherst, MA 01003, USA1 AbstractMost of the countermeasures against fault attacks on cryptographic systems that havebeen developed so far are based on the addition of information redundancy. Whilethese countermeasures have been evaluated with respect to their cost (implementa-tion overhead) and efficiency (fault coverage), little attention has been devoted to thequestion of the impact their use has on the effectiveness of other types of side-channelattacks, in particular power analysis attacks.

2 This chapter presents an experimentalstudy whose goal is to determine whether the added information redundancy canincrease the vulnerability of a cryptographic circuit to power analysis IntroductionIn this chapter we discuss in a comprehensive way the interaction between coun-termeasures against fault injection attacks and the vulnerability to power analysisattacks, using AES as an example. We focus in particular on the non-linear trans-formation (S-box) within AES since it is the preferred attack point. Specifically, weconcentrate on hardware implementations of AES to which error detection circuitshave been added. Considered are the basic parity check, double parity, residue checksmodulo 3 and 7, complementary parity and a Hamming error correcting code. Forall the considered error detection or correction circuits,we analyze the effects thatthe redundant check bits may have on power analysis attacks using different include an information theory based metric, the success rate of power analysisattacks based on correlation, and the effectiveness of the most common attacks basedon difference of means and Hamming Regazzoni, Luca Breveglieri, Paolo Ienne, and Israel KorenThe effects that one specific countermeasure can have on the resistance to adifferent type of attack was studied in very few previous publications.

3 Maingotetal.[5, 6] have analyzed the impact of four different error detection and correctionschemes on power analysis resistance. Their study focused on a register storing thestate of the AES encryption, which was enlarged to support the information redun-dancy necessary for each considered scheme. Using gate level simulations, theyshowed how the correlation between the value guessed by the adversary and thevalue of the register varies depending on the particular error detection code em-ployed. They compared four different error detection codesin search for the bestcode for secure chips, and based on the correlation, concluded that a complementaryparity scheme can improve the circuit robustness against power-based side channelattacks as level simulations were performed by Regazzoni et al. [10,11] to com-pare different error detection codes including parity codes and residue codes ( ,mod 3 and 7) using a 180nmtechnology.

4 As was done in [5], the authors focusedon the output register of the S-box transformation in AES, and they have analyzedthe impact that the considered codes may have on the resistance against power-basedattacks and the role played by measurement noise. Furthermore, they discussed thequestion whether the knowledge of the particular error detection code used in thecircuit affects the resistance against power-based side channel attacks and whetherthe redundancy helps the attacker even if he is unaware of Considered error detection and correction circuitsAlthough we focus in this chapter on theRijndael[3] block cipher (selected to be theAdvanced Encryption Standard [8]), our conclusions are general and applicable toother block ciphers. We concentrate on the S-box step because the output of this non-linear transformation is where the difference between the correct key hypothesis andthe wrong ones is highest, and thus it is the preferred attackpoint for an adversary [7].

5 Figure 1 depicts the basic configuration used in our experimental power analysisattacks. This configuration is a commonly used simplified implementation of oneround of the AES plaintext is added (modulo 2) to the secret key and the result of thisxorop-eration is used as input to the S-box. The output of the substitution step is stored intoa register. In order to always have the same initial condition, a reset signal is appliedto the register at the end of each write operation. Although areal implementationof the full algorithm would be somewhat different from this simplified diagram, ourpurpose is only to estimate the impact of error detection circuits (concatenated tothe S-box) on the resistance to power analysis attacks. Thisapproximation (shownin Figure 1) is accepted as sufficiently accurate for analyzing attacks on the mostvulnerable portion of the cipher and is therefore, adequatefor our 2 shows, as an example, an S-box with a parity bit.

6 In this figure, the addedcheck bits are used to detect the presence of errors in two different instances: onceat the input and then at the output of the S-box. When new data enters the S-box,Interaction between Fault Attack Countermeasures and DPA3 SubstitutionTableRegisterPlainTextSecret KeyPoint of AttackFig. of the considered part of the AES check bits are separated from the data bits and an error detection is no error is detected, the data bits enter the S-box circuit. The S-box then producesthe result of the non-linear transformation plus the corresponding check bits. At thispoint the second check is performed, again as described before. If no error is detectedin both checks, the output of the S-box is forwarded to the next round transformation;otherwise, a faulty output composed of all zeros except the right most bit is generatedto signal the diagram of the parity error detection scheme applied to an 8-bit have implemented several versions of the non-linear function in the AES S-box, each with a different error detection or correction code.

7 The following circuitsare considered: Reference version. This circuit implements the non-linear transformation asde-scribed in the standard and is used as the reference version. Single parity-based error code. The single byte parity circuit implements theerror detection scheme described by Bertoni et al. [1]. Double parity-based error codes. This code computes two parities: one for thebits with even indices and one for the bits with odd indices. Residue-based codes. These are the residue codes that use the moduli 3 and 7. Error codes based on complementary parity. In this scheme, both the evenand the odd byte parity bits are computed. Hamming error correcting code. We consider a (12,4) Hamming code de-scribed by the following parity matrix:4 Francesco Regazzoni, Luca Breveglieri, Paolo Ienne, and Israel KorenH= 1 1 1 0 0 0 1 1 1 0 0 01 0 0 1 1 0 1 1 0 1 0 00 1 0 1 0 1 1 0 0 0 1 00 0 1 0 1 1 0 1 0 0 0 1 4 Experimental SetupFigure 3 depicts the complete setup we have used for our evaluation procedure, whichis similar to the one presented by Regazzoni et al.

8 In [9]. It is composed of a standardElectronic Design Automation (EDA) flow and includes a simulation environmentfor generating the power consumption traces which are used to provide a measureof the resistance against power analysis attacks. The inputto the process is the Reg-ister Transfer Level (RTL) description of the S-box and one of the considered errordetection/correction circuits. The output is a text file which stores the noise-free in-stantaneous current consumption of the circuit simulated at a very high resolution ofboth time and all our circuit implementations, the S-box module has been described usingVHDL at the behavioral level. Because of this, it has been synthesized by the tool asa combinatorial circuit rather then a memory-based look-uptable. It is therefore, notnecessary to protect the address decoder against injected faults since this componentis not present in the synthesized implementation of the substitution function.

9 Thisapproach does not constitute a limitation since it reflects atypical situation whendesigning a cryptographic unit, where the entire unit is specified using a hardwaredescription language and then synthesized by an EDA tool with no specific imple-mentation constraints imposed. In such cases, the S-box module is often realized asa combinatorial VHDL description is synthesized using the ST-Microelectronics 90nm CMOS standard cell library [13] andSynopsys Design Compiler[14]. If the synthesis tool isset to minimize the circuit s area, it is possible that during the optimization phase ofthe synthesis process the redundant parts of the circuits ( , the circuit generatingthe complementary parity bit) will be removed. In order to prevent this from happen-ing, we first synthesized each component of the circuit separately and then connectedthe individual components together forcing the tool to not further optimize the inter-nal design of the individual components.

10 The number of equivalent two-input NAND gates of each circuit is reported in Table resulting circuit is then placed and routed using Cadence Design SystemsSoC Encounter[2]. A parasitics file (in spef format) is produced, along with theVerilog netlist of the circuit and an sdf file for back annotation of the delays. Theflow produces the spef and sdf files and the verilog netlists ofthe entire simulation is then performed usingModelSim,with the pre-viously generated sdf files to verify the functionality of the circuit and to generatetest vectors for transistor-level simulation that will be used to produce the simu-lated power Nanosimis then executed to perform transistor-levelsimulation, using the spef file, the relative verilog netlist, the SPICE models of theInteraction between Fault Attack Countermeasures and DPA5S-Box with error correction/detectionHDL codeRTL validationCMOS Libraryfront-end back-end viewsynthesis(Synopsys)synthetized netlistfloorplanP&R(Encounter)routed netlistparasitic(spef)post-synthvalidati onpost-P& vector(VCD format)SPICE level simulation(Synopsys Nanosim)transistor modelsVdd current filesi-vdd(t)Fig.