A Novel Parity Bit Scheme for SBox in AES Circuits

*'L1DWDOH0/)ORWWHV%5RX]H\UH
Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Université Montpellier II / CNRS UMR 5506
161 rue Ada, 34392 Montpellier Cedex 5, France
{dinatale,flottes,rouzeyre}@lirmm.fr

Abstract – This paper addresses an efficient concurrent fault processors, and it is appropriate for dedicated hardware
detection scheme for the SBox hardware implementation of the implementations. Hardware implementations can reach
AES algorithm. Concurrent fault detection is important not only throughput rates in the gigabit range.
to protect the encryption/decryption process from random and Several hardware implementations for AES circuit have
production faults. It will also protect the system against side-
been proposed [4]. No matter the type of implementation, the
channel attacks, in particular fault-based attacks, i.e. the
injection of faults in order to retrieve the secret key. We will most expensive part of the circuit in terms of area is the so
prove that our solution is very effective while keeping the area called SBox. Section 2 will describe in detail the algorithm of
overhead very low. the AES and in particular the definition and the characteristics
of the SBox. In this paper we focus on a novel parity bit
scheme to protect the SBox core.
Conversely to the other computational blocks of the AES
I. INTRODUCTION algorithm, the SBox performs an operation that is not linear
Cryptographic algorithms play a crucial role in the and is not invariant with respect to the parity of the processed
information society. When we use teller machines, home data, i.e., the parity bit is not preserved after the
banking services or credit cards, call someone on a mobile transformation. This is the reason why it is necessary to insert
phone, get access to health care services, or buy something on an additional circuit able to predict the value of the output
the web, cryptographic algorithms are used to offer protection. parity bit starting from the input value.
These algorithms guarantee that nobody can steal our money, In this paper, we present novel low cost concurrent error
place a call at our expense, eavesdrop on our phone calls, or detection (CED) S-Box architecture for the AES. Compared to
get unauthorized access to sensitive health data. Information previous works, our solution has higher fault coverage and
technology keeps changing and will become increasingly lower area overhead.
pervasive, while disappearing from the eye of the user. The paper is organized as follows. Section 2 describes the
However, this evolution keeps presenting new security characteristics of the Advanced Encryption Standard
challenges, and there is no doubt that cryptographic algorithms algorithm. Section 3 summarizes the state-of-the-art on this
and protocols will form an important part of the solution. topic. Section 4 presents the parity-based concurrent error
Fault detection and tolerance schemes for various detection approach, whereas Section 5 discusses the results in
implementations of cryptographic algorithm have recently terms of fault detection capability and area overhead, and
been considered. Several motivations led to increase the compares these results with those published in the literature.
reliability of these circuits. From one side the circuit Eventually, Section 6 concludes the paper.
implementation of cryptographic algorithms can be quite
complex, increasing the probability of device failures. Fault II. ADVANCED ENCRYPTION STANDARD
detection is therefore helpful in finding faults during the
The Rijndael algorithm used for the AES standard
production tests. In addition, fault tolerance schemes are very
implements a symmetric-key cryptographic function in which
useful to on-line tolerate faults during mission time. From the
both the sender and receiver use a single key to encrypt and
other side, intentional intrusions and attacks based on the
decrypt the information.
malicious injection of transient faults into the device are very
Although in [5], the block length of Rijndael can be 128,
efficient in order to extract the secret key [1] [2].
192, or 256 bits, the AES algorithm [3] only adopted the block
The Advanced Encryption Standard (AES) [3] is a block
length of 128 bits. Meanwhile, the key length can be 128,
cipher adopted as an encryption standard by the U.S.
192, or 256 bits. The AES algorithm’s internal operations are
government. AES began immediately to replace the data
performed on a two dimensional array of bytes called State.
encryption standard (DES), which had been in use since 1976.
The State consists of 4 rows of bytes and each row has Nb
AES outperforms DES in improved long-term security
bytes. Each byte is denoted by Si, j (0 ” i < 4, 0 ” j < Nb).
because of larger key sizes (128, 192, and 256 bits). Another
Since the block length is 128 bits, each row of the State
major advantage of AES is the possibility of efficient
contains Nb = 4 bytes. For sake of simplicity we focus on key
implementation on various platforms. AES is suitable for
length equal to 128 bits. The four bytes in each column of the
small 8-bit microprocessor platforms and common 32-bit
State array form a 32-bit word, with the row number as the

1-4244-1161-0/07/$25.00 ©2007 IEEE

index for the four bytes in each word. At the beginning of
encryption or decryption, the array of input bytes is mapped to Plaintext (128 bits)
the State array as illustrated in Fig. 1. The 128-bit block can
be expressed as 16 bytes: in0, in1, in2, … in15. Encryption and roundkey(0)
decryption processes are performed on the State, at the end of
which the final value is mapped to the output bytes array out0,
out1, out2, … out15. for i=1 to 9

Input bytes State array Output bytes

SubBytes
SubBytes
in0 in4 in8 in12 S0,0 S0,1 S0,2 S0,3 out0 out4 out8 out12 ShiftRows
in1 in5 in9 in13 S1,0 S1,1 S1,2 S1,3 out1 out5 out9 out13
ShiftRows
roundkey(10)
in2 in6 in10 in14 S2,0 S2,1 S2,2 S2,3 out2 out6 out10 out14 MixColumns
in3 in7 in11 in15 S3,0 S3,1 S3,2 S3,3 out3 out7 out11 out15
roundkey(i)

Fig. 1: Mapping of input bytes, State array and Ciphertext (128 bits)
output bytes
Fig. 2: AES Algorithm (encryption)

The AES algorithm is an iterative algorithm. Each

MixColumns Transformation
iteration is called a round. The total number of rounds is 10.
The MixColumns transformation is performed on the
At the start of encryption, input is copied to the State array.
State array column-by-column. Each column is considered as
After the initial roundkey addition, 10 rounds of encryption
a four-term polynomial over GF(28) and multiplied by a(x)
are performed. The first 9 rounds are the same, with small
modulo x4 + 1, where:
difference in the final round. As illustrated in Fig. 2, each of
a(x) = (00000011)2 x3 + (00000001)2 x2 +
the first 9 rounds consists of 4 transformations: SubBytes,
(00000001)2 x + (00000010)2
ShiftRows, MixColumns and AddRoundKey. The final round
excludes the MixColumns transformation.
AddRoundKey Transformation
The encryption structure in Fig. 2 can be inverted to get a
In AddRoundKey transformation, a roundkey is added to
straightforward structure for decryption.
the State array by bitwise XOR operation. Each roundkey
consists of 16 words generated from Key Expansion described
SubBytes Transformation
below.
The SubBytes transformation is a non-linear byte
substitution that operates independently on each byte of the
Key Expansion
State using a substitution table (SBox). This SBox is
The key expansion routine, as part of the overall AES
constructed by composing two transformations:
algorithm, takes the input key of 128 bits. The output is an
1. Take the multiplicative inverse in the finite field GF(28);
expanded key of 11*128 bits, i.e., the expanded key is
the element (00000000)2 is mapped to itself;
composed of the secret key and 10 roundkeys, one for each
2. Apply the following affine transformation (over GF(2)):
round. Details of the algorithm that allows determining the
bi' = bi ⊕ b(i + 4) mod 8 ⊕ b(i +5) mod 8 ⊕ value of each roundkey is described are given in [3].
b(i + 6) mod 8 ⊕ b(i +7 ) mod 8 ⊕ ci
III. STATE-OF-THE-ART
for 0 ” i < 8, where bi is the ith bit of the byte, and ci is the
ith bit of a byte c whose value is fixed and is equal to Since crypto chips are consumer products of mass
{01100011}. production, cheap solutions for concurrent error detection and
correction are of great importance [6] [7] [8] [9]. A natural
This transformation can be pre-calculated for each choice for concurrent error detection is the application of
possible input value since it works on a single byte, therefore parity codes. Concurrent checking for the AES by parity
there are only 256 values. Implementations of the SBox are prediction was first introduced in [11] and [12]. One of the
discussed in Section 3. main problems targeted in the literature is the prediction of the
output parity given the input state and the input parity bit.
ShiftRows Transformation The prediction of the parity bit (when a parity bit is added
In this transformation, the bytes in the first row of the to each byte) is almost straightforward for the ShiftRows,
State do not change. The second, third, and fourth rows shift MixColumns and AddRoundKey steps [11]. On the contrary,
cyclically to the left one byte, two bytes, and three bytes, the prediction of the parity bit is not trivial for the Sbox. In
respectively. this section we summarize the solutions based on the parity bit
for the SBox.
 The SBox is usually implemented either as a 256x8 bits able to target Address Faults as well. An Address Faults
memory consisting of a data storage section and an address typically causes that during a read operation an unexpected
decoding circuit, or a combinational circuit. The incoming cell is accessed by a given address. The use of detection codes
data bytes will normally have properly generated even parity based on both the address and the data allow the detection of
bits. A solution to generate the outgoing parity bits is proposed Address Faults [13].
in [12] and sketched in Fig. 3.a: an even parity bit is either One characteristic of the Sbox is that it implements an
stored with each data byte in the SBox (memory invertible function. This feature allows calculating the input
implementation), or on-line generated with an ad-hoc value starting from the output response. Therefore it is
combinational circuit (in the case of combinational logic possible to predict the parity bit of the input word starting
implementation for the SBox). This solution is not very from the output response of the SBox (without implementing
expensive and it guarantees acceptable fault coverage. the inverse function, see below for details).
The main idea is that we do not add any parity bit in the
memory that stores the SBox values (or into the combinational
logic that implements it). On the contrary, we calculate the
512x9
parity of the input value and we compare it with the parity bit
256x9 **

Parity
*
predicted starting from the output value of the Sbox. In
SBox SBox
* addition, we calculate the parity bit of the output of the SBox
** and we compare it with the prediction of this bit starting from
**
*
the input value. All works presented in the past were based on
the predictor of the output parity.
Parity
= We calculated the Output Parity Predictor and the Input
Parity
= Parity Predictor using the truth tables of the SBox and of the
parity bits, calculated for both the input value and the output
value. Fig. 4 shows the first elements of the truth tables.
(a) (b) This scheme allows double protection of the SBox circuit
Fig. 3: State-of-the-Art and it should allow covering more faults than the architectures
proposed in the literature. Section 5 will prove that actually
To increase the dependability and to detect additional this scheme is more effective.
input parity errors and some internal memory errors (data or
decode), [11] proposes replacing the original 8-bit decoder
with a 9-bit one, yielding a 512x9 bits memory (Fig. 3.b). If a
Parity
9-bit address with an even parity is decoded, the
corresponding output byte with its associated even parity bit is
produced. Otherwise, a constant word of 9 bits with a Output
deliberately odd parity is output, e.g., “00000000 1”. Thus, Parity
Prediction
half of the entries in the SBox memory will be deliberately
wrong (in the figure, all the rows marked with a ‘*’). In case
of a single error in the input value, a wrong cell will be
addresses. That cell will contain an erroneous parity bit that =
will be detected during the parity bit check. This solution SBox
guarantees higher fault coverage but it’s very expensive in
terms of used area. =
Section 5 gives some comparative results.
Input
IV. ARCHITECTURE DESCRIPTION Parity
Prediction
In this paper we focus on the use of the parity code for a
single Sbox. We propose a solution that is suitable for all the
schemes where there is a parity check for each byte element of Parity
the matrix S. The main problem in implementing the parity bit
for the SBox is related to the fact that the SBox transformation
is not invariant with respect to the parity bit. Hence, it is Fig. 4: Proposed solution
necessary to implement a method to predict the output parity,
given the input value.
In order to meet higher fault detection capability a code-
based fault detection approach has been adopted, consisting of
information redundancy applied to both data and address of
the memory storing the SBox values. With this solution we are
 single error affects the circuit. In this experiment we focused
Input Parity (Input) SBox Output Parity (Output) on single stuck-at faults. The obtained fault coverage is equal
00000000 0 01100011 0 to 99,20% for the circuit synthesised with area optimization
and 99,25% for the speed optimization.
00000001 1 01111100 1
TABLE ,
00000010 1 01110111 0
AREA
00000011 0 01111011 0 Area Speed
Optimization Optimization
... ... ... ...
Module Area Area
# Cells [µm2] # Cells [µm2]
SBox 555 34780 566 35672
InPrediction 90 5569 99 6061
OutPrediction 93 5879 94 5923
Parity 8 1420 8 1420
Comparators 2 124 2 124
Output Parity Prediction Input Parity Prediction

00000000 0 01100011 0 Table 2 summarizes some comparison between our

solution and the architectures proposed in [12] and [11],
00000001 1 01111100 1
sketched respectively in Fig. 3.a and Fig. 3.b. Those
00000010 0 01110111 1 architectures have been synthesized using the same
technological library. In both cases the SBox has been
00000011 0 01111011 0 implemented as combinational logic.
... ... ... ...
TABLE,,
COMPARISON
Fig. 5: Parity Predictions truth tables
Area Fault
Architecture Overhead Coverage

V. EXPERIMENTAL RESULTS Our approach 37,35% 99,20%

[12] (Fig. 3.a) 18,17% 91,95%
In this section we provide some results related to the area [11] (Fig. 3.b) 47,28% 93,43%
overhead and the fault coverage of the proposed approach. We
also compare these results with the architecture proposed in The solution proposed in [12] allows covering 91,95% of
[11] and [12]. the faults only, guaranteeing anyway a lower area overhead.
The architecture proposed in Fig. 4 has been described in The solution proposed in [11] guarantees higher fault
VHDL and synthesized using Synopsys Design Compiler. coverage than the solution proposed in [12], but it has a very
Both the SBox and the prediction circuits have been high area overhead (47,28%). In addition, the area overhead is
synthesized as combinational logic. However, the proposed even higher when the ROM is used to implement the SBox. In
solution can be implemented using a ROM for the SBox. this case the overhead is about 125%.
We used the 0.35µm CMOS library provided by Austria In any case, our solution guarantees higher fault coverage
Micro Systems [14]. and, thanks to the double prediction based on both address and
The architecture has been implemented in two different data, it would allow covering a percentage of address faults
ways in order to better assess the detection capabilities of the when the SBox is implemented as a ROM.
proposed approach. One synthesis has been performed posing
as a constraint the minimization of the area. The second VI. CONCLUSIONS
synthesis has been optimizing for the speed of the circuit.
Table 1 summarizes the area of the circuit described in Crypto-systems are inherently computationally complex,
Fig. 4, with both results (area optimization and speed and in order to satisfy the high throughput requirements of
optimization). many applications, they are often implemented by means of
The area overhead is 37,35% with area optimization and VLSI devices.
37,92% with speed optimization. The high complexity of such implementations raises
In order to measure the detection capability of the concerns regarding their reliability. Research is therefore
proposed architecture we used the fault simulator provided by needed to develop methodologies and techniques for designing
Synopsys (TetraMax). The circuit has been modified in such a robust cryptographic systems, and to protect them against both
way that the only output signals visible by the fault simulator accidental faults and intentional intrusions and attacks, in
are the comparator signals. In this way, the obtained fault particular those based on the malicious injection of faults into
coverage gives a measure of the detection capability when a the device for the purpose of extracting the secret information.
 The introduction of the parity bit prediction, both in input Standard”, Proc. 18th IEEE Int’l Symp. Defect and Fault Tolerance in
VLSI Systems, pp. 105-113, Nov. 2003
and output, increased significantly the fault coverage of the
[7] K. Wu, R. Karri, G. Kuznetsov, M. Goessel, “Low Cost Concurrent
circuit, without resorting to expensive solutions requiring Error Detection for the Advances Encryption Standard”, Proc. Int’l Test
large extra memory area. Conference, pp. 1242-1248, 2004
We consider as future work the development of a scheme [8] R. Karri, K. Wu, P. Mishra, Y. Kim, “Concurrent Error Detection
Schemes for Fault-Based Side-Channel Cryptanalysis of Symmetric
for concurrent error detection with double prediction of the Block Ciphers”, IEEE Trans. Computer-Aided Design of Integrated
parity bits using a pipelined architecture in order to lower even Circuits and Systems, vol. 21, no. 12, Dec. 2002, pp. 1509-1517
more the hardware overhead. [9] C. Yen, B. Wu, “Simple Error Detection Methods for Hardware
Implementation of Advanced Encryption Standard”, IEEE Trans
Computers, vol. 55, no. 6, June 2006, pp. 720-731
[10] G. Bertoni, L. Breveglieri, I. Koren, P. Maistri, V. Piuri, “A parity Code
Based Fault Detection for an Implementation of the Advanced
REFERENCES Encryption Standard”, Proc. IEEE Int. Symposium on Defect and Fault
Tolerance in VLSI, pp. 51-59, Nov. 2002
[1] D. Boneh, R. DeMillo, R. Lipton, “On the Importance of Eliminating [11] G. Bertoni, L. Breveglieri, I. Koren, P. Maistri, V. Piuri “Error Analysis
Errors in Cryptographic Computations”, Journal of Cryptology, vol. 14, and Detection Procedures for a Hardware Implementation of the
pp. 101-119, 2001 Advanced Encryption Standard”, IEEE Trans. Computers, vol. 52, no. 4,
[2] M. Akkar, C. Giraud, “An Implementation of DES and AES, Secure pp.492-505, Apr. 2003
against some Attacks”, Proc. Of CHES’01, pp. 315-325, 2001 [12] V. Ocheretnij, G. Kouznetsov, R. Karri, M. Gossel, “On-Line Error
[3] “Advanced Encryption Standard (AES)”, Federal Information Detection and BIST for the AES Encryption Algorithm with Different S-
Processing Standards Publication 197, November 26, 2001. Box Implementations”, Proc. IEEE Int. On-Line Testing Symposium,
[4] X. Zhang, K. K. Parhi, “Implementation Approaches for the Advanced 2005, pp. 141-146
Encryption Standard Algorithm”, IEEE Circuits and Systems Magazine, [13] A. Benso, S. Chiusano, G. Di Natale, M. Lobetti-Bodoni, P. Prinetto,
vol. 2, Issue 4, pp. 24-46, 2002 “On-line & Off-line BIST in IP-Core Design”, IEEE Design and Test of
[5] J. Daemen, R. Rijmen,, “AES Proposal: Rijndael”, version 2, 1999, Computers, September/October 2001, Vol. 18, N. 5, pp. 92 99
Available at [14] http://asic.austriamicrosystems.com/databooks/index.html
http://www.esat.kuleuven.ac.be/~rijmen/rijndael
[6] G. Bertoni, L. Breveglieri, I. Koren, P. Maistri, V. Piuri, “Detecting and
Locating Faults in VLSI Implementations of the Advanced Encryption