Commits

RomanGol  committed 5348fc4

Camera Ready Nighty Release

2012.07.01

  • Participants
  • Parent commits e733c7e

Comments (0)

Files changed (6)

File FDTC2012/main.tex

 
 \input{title.tex}
 
-\section{Introduction}
-% no \IEEEPARstart
-Fault analysis is a kind of side-channel attack that seriously threats the security of cryptographic devices in real world.
-When an encryption is executed under faulty condition, error occurs on intermediate states so the normal output changes to a \emph{faulty output}.
-The faulty output is then used as a side-channel leakage to help retrieving secret information.
-Since the idea was first suggested in 1997 by D. Boneh, et al.\cite{boneh1997importance},
-various of fault analysis methods have been proposed and studied.
-Among them, Differential Fault Analysis(DFA) \cite{biham1997differential} is the most well studied.
-In a DFA attack, the secret key is recovered by using some pairs of correct and faulty output.
-The relationship between the common output and the specific faulty output provides extra information.
-Various of DFA methods have been developed against blockciphers include the AES\cite{piret2003differential}\cite{derbez2011meet},
-Camellia and ARIA. Some of them have already reached the information limitation that the fault model could provide\cite{li2010information}.
+\input{sec_intro.tex}
 
-Most of the DFA target to antepenultimate or penultimate round and take an impossible-and-eliminate method to exclude wrong key candidates.
-That is to say, it relies on the property that on a subset of the last round(e.g., one or two bytes), the input differential only contains a subset of all possible values.
-The attacker uses this restriction to solve some differential equation and excludes wrong key candidates.
-If the fault is in an earlier round and therefore the subset of the last round's input differential covers all possible values then the DFA technique is not suitable.
-From this point, DFA is a deterministic analysis while differential cryptanalysis is statistical.
-If the fault attack could take advantage of the statistical analysis technique, it is expected to exploit more information leakage.
+\input{sec_pre.tex}
 
-In 2006, Phan and Yen proposed an amplified side-channel attack enhanced by traditional cryptanalysis techniques\cite{phan2006amplifying}.
-In 2009, Matthieu Rivain first proposed an DFA on middle round DES\cite{rivain2009differential}.
-Inspired by their work, in this paper we adopt the idea of statistical and impossible differential cryptanalysis to enhance fault analysis of lightweight blockcipher.
-We propose fault analysis of the lightweight SPN blockcipher with bit-permutation and presents specific fault attacks against PRESENT-80 and PRINT\scriptsize{CIPHER} \normalsize-48.
-The research of fault attack against lightweight blockciphers such as PRESENT\cite{bogdanov2007present} and PRINT\scriptsize{CIPHER} \normalsize \cite{knudsen2010printcipher} are reported recent years.
-In 2009, Li et al. first proposed a DFA on PRESENT-80 \cite{juan2009present} which needs 40-50 pairs of faulty ciphertexts occurred at round 29.
-In 2010, Wang et al.\cite{wang2010differential} proposed a DFA on PRESENT key-schedule,
-which needs a single nibble fault on the round key and can recover the secret key with 64 pairs of correct and faulty ciphertexts on average and the computational complexity is $2^{29}$.
-These two attacks both required a penultimate or an antepenultimate round faulty encryption.
-In 2011, Zhao, et al.\cite{zhao2011fault} proposed fault attacks against PRESENT and PRINT\scriptsize{CIPHER} \normalsize.
-However, their results didn't analyze the situation of an earlier round fault either.
-To the best of our knowledge, no fault attacks on earlier rounds are proposed and these attacks generally adopted one nibble error model.
-
-We notice that in many lightweight SPN blockciphers with bit-permutation,
-the fault propagation process is slow and after many rounds, and it is available to employ fault attack to construct an effective distinguisher.
-This fault based distinguisher helps attacker determine key with high probability and low data complexity.
-With the distinguisher, more rounds of the whole cipher are vulnerable to fault attack.
-
-We discuss the fault based differential distinguishers,
-%then we analyze the transformation of the original non-uniform distribution after iterative round function and give the probability estimating method.
-Based on the distinguishers, we can retrieve round key and estimate which rounds are vulnerable to fault attack.
-We simulated the fault attack against PRESENT-80 and PRINT\scriptsize{CIPHER}\normalsize-48,
-The attack needs practical amount of ciphertexts and only a few hours with commodity computers.
-
-The rest of this paper is organized as follows.
-In Section~\ref{prelimi} we briefly review the structure of PRESENT and PRINT\scriptsize{CIPHER} \normalsize, the common fault injection technique and fault model.
-In Section~\ref{attk}, we describes the principle and analysis technique of our fault attack.
-Then we present two practical attacks against PRESENT-80 and PRINT\scriptsize{CIPHER} \normalsize-48.
-Section~\ref{concl} concludes the paper.
-% You must have at least 2 lines in the paragraph with the drop letter
-% (should never be an issue)
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-\section{Preliminaries}
-\label{prelimi}
-PRESENT is a lightweight block cipher designed by Bogdanov et al. in 2007 for extremely constrained environments such as RFID tags and sensor networks.
-It is a 31-round SPN blockcipher with 64 bits block size and supports 80 and 128 bits key.
-The encryption process of PRESENT is described in Algorithm~\ref{prs_algo}.
-There are three stages involved in each round function,
-$\sf{addRoundKey}$, $\sf{sBoxlayer}$ and $\sf{permutationLayer}$.
-For more information about PRESENT, the interested reader may refer to \cite{bogdanov2007present}
-
-\begin{algorithm}
-\label{prs_algo}
-\caption{PRESENT}
-\KwIn{$u_{1}, K_{1}-K_{32}$}
-\KwOut{$u_{32}$}
-    \For{$i$ = 1 $to$ 31}
-    {
-        $\sf{addRoundKey}$$(u_{i}, K_{i})$ \\
-        $\sf{sBoxlayer}$$(u_{i})$ \\
-        $\sf{permutationLayer}$$(u_{i})$ \\
-    }
-    $addRoundKey(u_{32},K_{32})$ \\
-    return $u_{32}$
-\end{algorithm}
-
-\begin{figure}
-\label{prs_func}
-    \centering
-    \includegraphics[width=0.5\textwidth]{present.png}
-    \caption{Round function of PRESENT}
-\end{figure}
-
-
-\subsection{Blockcipher PRINT\scriptsize{CIPHER}\normalsize}
-PRINT\scriptsize{CIPHER} \normalsize is an ultra-lightweight blockcipher proposed by L.Knudsen et al. in 2010.
-It is a 48/96-round SPN blockcipher with 48/96 bits block size and supports 80/160 bits key.
-PRINT\scriptsize{CIPHER} \normalsize uses key-dependent permutation and very simple key-schedule.
-The encryption process of PRINT\scriptsize{CIPHER} \normalsize is described in Algorithm~\ref{print_algo}.
-For more information about PRINT\scriptsize{CIPHER} \normalsize, readers may refer to \cite{knudsen2010printcipher}
-
-\begin{algorithm}
-\label{print_algo}
-\caption{PRINT\scriptsize{CIPHER} \normalsize}
-\KwIn{$u_{1}, K_{1}-K{r}$}
-\KwOut{$u_{r}$}
-    \For{$i$ = 1 $to$ r}
-    {
-        $\sf{addRoundKey}$$(u_{i}, K_{i})$ \\
-        $\sf{linearDiffusion}$$(u_{i})$ \\
-        $\sf{xorRoundCounter}$$(u_{i})$ \\
-        $\sf{keyedPermutation}$$(u_{i})$ \\
-        $\sf{sBoxlayer}$$(u_{i})$
-    }
-    return $u_{r}$
-\end{algorithm}
-
-
-
-\subsection{Fault Injection Techniques}
-Lightweight blockciphers are used in cryptographic devices such as smart cards and RFID tags in real world.
-Previous research shows that certain round of the encryption could be affected when clock faults occur,
-and devices such as FPGA using a DLL-based FPGA platform is vulnerable to fault attack\cite{agoyan2010clocks}.
-Although nowadays advanced smartcards are claimed to be protected by fault detection circuit,
-it is still not common, especially for those low cost devices, to add protection.
-
-Under the fault attack, it is a reasonable assumption that a cryptographic device with fixed secret key is controlled by an attacker.
-The attacker could ask the device to encrypt(or even decrypt) arbitrary plaintext(or even ciphertext).
-What's more,
-the attacker deliberately interferes the normal encryption by changing the power supply voltage or the frequency of the external clock,
-or using laser attack, and collects the faulty output\cite{barenghifault}.
-In \cite{agoyan2010clocks}, Agoyan et al. demonstrated how to inject single bit fault in a reproducible way,
-despite the optical precision of the equipment was not able to target the smallest features of the target chip.
-We may assume that more than one faulty output are available for fault attack.
-However, fault attack is more or less harmful to devices, and due to most popular devices' lifetime(for instance, a sim card is able to do the encryption for at most 50000-60000 times),
-it is expect to obtain 1000-10000 pairs of correct-faulty output on average.
-What's more, although fault attack may affect the certain round, it is often hard for the attacker to know which parts of the internal state are changed.
-The most possible situation is that one S-box or small number of S-boxes of one round are affected and the fault is random.
-Another situation is that in a parallel $n$ different S-boxes, one of them is most vulnerable to unstable circumstance such as low voltage.
-However, in this paper we do not consider this model.
-%And this leads to a fixed S-box fault model.
-We will show the fault model used in detail in the next subsection.
-
-
-\subsection{Fault Model}
-Our attack considers two fault models: \emph{Single Random S-box}, and \emph{Multi S-boxes} fault model.
-We can recover the secret key within the faults injected after a specific rounds depending on the fault model used.
-
-%\subsection{Single Specific S-box Fault Model}
-%This model requires one fixed S-box of a certain round are repeatedly and randomly disturbed thus produces a set of different faulty outputs.
-
-\subsubsection{Single Random S-box Fault Model}
-A single random S-box fault model requires following assumption.
-\begin{itemize}
-    \item
-    The input of \textbf{one} S-box in a certain round is switched to a random and uniformly distributed value due to the fault injection.
-    \item
-    For a pair of correct ciphertext and its corresponding faulty ciphertext, they are encrypted from the same plaintext and the same key.
-    \item
-    Multiple pairs of correct and faulty ciphertexts (may from different plaintext) provided to attacker are encrypted by the same key.
-\end{itemize}
-
-The frequently mentioned single bit model can be seen as a special case of this model.
-
-%Because the fault attack changes only one S-box of the internal state,
-%the original differential distribution from the fault encryption is obviously non-uniform.
-
-\subsubsection{Multi S-boxes Fault Model}
-A multi S-boxes fault model requires following assumption.
-\begin{itemize}
-    \item
-    The input of \textbf{multiple} S-boxes in a certain round are switched to random and uniformly distributed values due to the fault injection.
-    The number of corrupted S-boxes is a small part compared to the total S-boxes used in one round.
-    \item
-    For a pair of correct ciphertext and its corresponding faulty ciphertext, they are encrypted from the same plaintext and the same key.
-    \item
-    Multiple pairs of correct and faulty ciphertexts (may from different plaintext) provided to attacker are encrypted by the same key.
-\end{itemize}
-
-%In the case of PRESENT and PRINT\small{CIPHER}\normalsize this number can be up to 4.
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-
-\section{Fault Attack}
-\label{attk}
-
-\subsection{General Attack Technique}
-Fault attack against lightweight blockcipher often encounter two problems.
-First, Lightweight blockciphers would generally have smaller S-boxes and more iterative rounds to enhance the security for the lack of complicated round function.
-The fast encryption speed of device makes fault injection hard to locate accurate rounds or certain S-box, especially for fault attack focusing on last one or two rounds or requiring single S-box error model.
-Second, due to the device's lifetime, attackers may not acquire enough amount of faulty ciphertext.
-Thus to take advantage of multiple S-boxes fault and earlier round fault is meaningful for fault analysis.
-
-For lightweight SPN blockciphers such as PRESENT and PRINT\small{CIPHER}\normalsize,
-a popular design methodology of bit-permutation is adopted because it is simple and easy to be implemented.
-The bit-permutation often brings a relatively slow diffusion.
-Our fault attack exploits this weakness to attack some middle rounds.
-
-%Under the single S-box fault model, each time there's only one affected faulty S-box.
-
-\subsubsection{Build Fault-based Distinguisher}
-The basic idea of our fault attack is to acquire an effective distinguisher based on fault injection and employ distinguishing attack.
-We found single random S-box fault model and multi S-boxes fault model are both suitable for attacking.
-Due to the design of the blockcipher with bit-permutation,
-it takes several rounds for a single S-box fault differential to be diffused and yet change the output "randomly".
-If the fault is not well diffused due to the lack of enough round encryption, the differential distribution is non-uniform
-even on a subset(e.g. a single S-box) of the penultimate or an antepenultimate block.
-This non-uniform distribution provides a good distinguisher for attacker.
-
-The distinguisher is based on the fact that the differential distribution is significantly different from uniform.
-The fault-based distinguisher, compared with traditional distinguisher, has following restrictions:
-\begin{itemize}
-    \item
-    According to the fault model, the input is coarse grained. Attackers could not precisely control the internal state.
-    \item
-    The amount of available output is limited. Unlike theoretical model, an attacker could not do the encryption unlimited. The allowed number of encryption is restricted by devices' lifetime.
-    \item
-    Analysis is complex. To precisely describe the probability of the distinguisher model is hard. In this paper, we adopt a simulation-based technique to avoid probability calculation of the distinguisher.
-\end{itemize}
-
-
-\subsubsection{Attack description}
-According to the {\it Wrong Key Randomisation Hypothesis}, the attacker guesses part of the ultimate round(or plus penultimate round) key and partially decrypt the ciphertext.
-The incorrect key decryption is expected to have the same affect of encrypting one more round. That is to say, the partially decrypted distribution should be a uniform one.
-If the guessed key is correct, the distance between partially decrypted distribution and the uniform distribution could be a well distinguisher.
-
-This attack is effective to the blockcipher with the bit-permutation rather than byte-oriented permutation.
-%Because even the fault on a single S-box is random, the bit-permutation make this randomness weak by diffuse each bit to different S-boxes.
-
-%In an SPN blockcipher with the common bit-permutation design,
-%even if the input of an S-box is random, after one round of permutation, $l$ S-boxes are to be affected according to S-box's bit number $l$,
-%and each affected S-box has a single bit input differential.
-%Thus the distribution of these affected S-box becomes far to uniform.
-%This non-uniform distribution may need more rounds of diffusion to become uniform again compared with byte-oriented permutation design.
-
-When we focus on the Single Random S-box Fault Model in an m-round SPN blockcipher with the common bit-permutation design, even if the input of an S-box is random, after one round of permutation, $l$ S-boxes are to be affected according to S-box's bit number $l$,
-and each affected S-box has a single bit input differential.
-Thus the distribution of these affected S-box becomes far to uniform.
-The Multi S-boxes Fault model shows different properties but the fault differential's non-uniform distribution still exists.
-In both cases the non-uniform distribution may need more rounds of diffusion to become random again compared with byte-oriented permutation design.
-
-
-\begin{figure}[h]
-\label{attack}
-    \centering
-    \includegraphics[width=0.5\textwidth]{attack.png}
-    \caption{Fault-based distinguishing attack}
-\end{figure}
-
-
-Our fault analysis relies on the non-uniform distribution when a single random S-box fault transferring for several rounds.
-An empirical and simple attack is to just partially decrypt the ciphertext and test the distribution of some subsets with all possible key candidates.
-If the distribution is non-uniform, the chosen key is considered to be the correct one.
-
-In practice,
-the attack against lightweight blockcipher generally do the partial decryption of two rounds instead of one because the partial key size is relatively small(e.g., 16 bits).
-
-
-Several distinguishers like Likelihood distinguisher and Squared Euclidean Imbalance (SEI) distinguisher \cite{rivain2009differential} can be used here to select the correct key.
-Consider the situation of not having exact knowledge about the fault propagation, especially for multiple S-boxes fault model and simplicity.
-We just adopt SEI method which picks the guessed key achieving strongest bias to uniform distribution as the correct one.
-The distinguisher $d(k)$ uses the squared Euclidean distance to the uniform distribution and is defined as:
-
-\begin{displaymath}
-d(k) = \sum_{\delta=0}^{2^m-1}\left(\frac{\#\{n; g_{i}(C_{n},\mbox{\~{C}}_{n},k)=\delta\} }{N}-\frac{1}{2^m}\right)^2
-\end{displaymath}
-
-In this formula $N$ is the number of correct and faulty ciphertexts pairs, $C$ and $\mbox{\~{C}}$ are correct and faulty ciphertexts, $g_{i}$ is the fault differential for the intermediate nibbles which has biased distribution and $k$ is subkeys which are sufficient to recovery the specific $g_{i}$. 
-$m$ is the number of bits for corresponding S-box. 
-For instance, for PRESENT the value of $m$ is 4.
-
-%We take the distance threshold as \textbf{0.001}.
-
-
-\subsection{Fault Attack Against PRESENT}
-
-%\begin{figure}
-%    \centering
-%    \includegraphics[width=0.5\textwidth]{present_fas.png}
-%    \caption{FAS propagation of PRESENT}
-%\end{figure}
-
-The diffusion property of PRESENT is relatively weaker because of the smaller S-box and bit permutation.
-This provides convenience of attacking middle rounds of encryption.
-%However, according to the design document[?], any five-round differential characteristic of PRESENT has a minimum of 10 active S-boxes and thus the maximum differential probability is $2^{-20}$.
-For the restriction of fault injection,
-it is hard to use small amount of faulty ciphertexts to distinguish the correct key with significant probability if the fault propagates too many rounds.
-In order to verify how many rounds are not immune to the fault attack, we simulate the fault propagation from two rounds to six rounds with a reasonable 10000 random inputs.
-By computing the output differential's squared Euclidean distance to the uniform distribution, we can observe the effectiveness of each round's fault injection.
-We simulate both single random S-box fault model and multiple S-boxes fault model.
-
-
-\subsubsection{Single Random S-box Fault Attack}
-
-\input{single_prs.table.frgament.tex}
-The distinguishing attack relies on the fact that the squared Euclidean distance acquired from correct subkey decryption is significantly greater than those acquired with incorrect key.
-We simulated the fault injection and tested the results.
-First, we tested the average squared Euclidean distance using 10000 pairs of random ciphertexts and found under random circumstance, the average squared Euclidean distance is about 0.0001-0.0005.
-Then, we do the simulation of fault injection and table~\ref{single_prs_tb} gives the simulation result of the distinguisher $d(k)$ uses the squared Euclidean distance on each nibble before penultimate round(using 10000 pairs of correct and faulty ciphertexts).
-As shown in table~\ref{single_prs_tb},
-if the fault injection position is earlier than round 25, even using the correct subkey to decrypt, 
-the squared Euclidean distance is ineffective for a distinguishing attack.
-Thus a 5-round fault and 2-round partial decryption attack is acceptable under this circumstance.
-That is to say, for PRESENT with 31 rounds, it is allowed to inject the fault before round 25 and then employs a two round partial decryption.
-
-Our experiments support the simulation well. The correct key gives a significant high squared Euclidean distance value(about 0.006).
-While for incorrect keys, the average squared Euclidean distance is about 0.0001-0.0003 and the most significant is only about 0.0006.
-For a full attack process, the attacker should guess four group of each 16+4 subkey bits (16 bits from penultimate round and 4 bits from antipenultimate round)independently to find the correct key.
-The attack complexity is about $4$ $\cdot$ $2^{16+4}$ $\cdot$ $10000$ $\cdot$ $2$ = $2^{36.3}$ partial decryption.
-We simulate the attack for fixed key and 10000 pairs of random correct-faulty ciphertexts.
-Using two IBM xServer(\emph{Intel Xeon E5420 4 core@2.5Ghz}) the attack takes about 2 hours and successfully obtain the last round subkey and four nibble of penultimate round subkey.
-
-An interesting observation is that nibble 5, 7, 13 and 15 of PRESENT's block have farther distance from uniform than any other nibbles after fault propagation.
-In other words, when employing distinguishing attack, the attacker should make use of these nibble to better distinguish correct keys.
-Another observation is that if the fault injection is restricted to half of the whole block(e.g., from nibble 0-7 rather than 0-15),
-An effective distinguishing attack is allowed to be employed with one round earlier fault injection(injecting the fault before round 23).
-
-%The property is because these nibbles are only affected by 2nd and 4th bit of last round S-box's output.
-%of PRESENT tends to influence least significant bits when the input differential are {1,2,4,8}.
-%So the left-most bits are suitable for attacking rather than the right-most bits with almost random distribution after 5 rounds(both in theoretical analysis and simulation).
-
-\subsubsection{Multi S-boxes Fault Attack}
-Under multiple S-boxes fault model, it is even harder to analyze the precise distribution.
-Thus we do the empirical simulation and test the distribution. 
-The results are shown in table~\ref{double_prs_tb},~\ref{triple_prs_tb} and ~\ref{qua_prs_tb}.
-According to the simulation, For Two, Three and Four S-boxes fault model, separately a 4+2, 3+2 and 2+2 fault propagation and partial decryption distinguishing attack could be employed. 
-Also, due to the observed property that nibble 5, 7, 13 and 15 of PRESENT's block could be used in 3 S-boxes fault model to employ a 4+2 fault propagation and partial decryption distinguishing attack.
-
-And the results show that if the number of affected S-boxes increases by one, the upper-bounds of the fault injection round within which we can accomplish the attack decrease by one.
-Though the strict computation and explanation is complex,
-we can discover that begin with less faults directly injected in the earlier round after one round function the affected S-boxes increase and this intermediate state has some similarity with the one which is produce by more faults directly injected in this later round.
-
-
-\input{multiple_prs.table.frgament.tex}
-
-Our attack is obviously not optimal because we don't have a precise knowledge of the fault model and is hence not able to estimate the precise distribution,
-but it does exploit the capability of multi S-boxes fault attack against PRESENT under our attack.
-
-
-\subsection{Attack against PRINT\small{CIPHER}\normalsize-48}
-\label{pcattack}
-The attack process against PRINT\small{CIPHER}\normalsize-48 is almost the same as the process against PRESENT.
-A slight difference is that PRINT\scriptsize{CIPHER} \normalsize uses the key-dependent permutation.
-However, We found that the key-dependent permutation doesn't make our fault attack more complex.
-Because in the situation of PRINT\scriptsize{CIPHER} \normalsize, the distribution keeps the same on each bit even with four different secret permutation.
-Thus it is possible to do the estimation using any of the permutation.
-
-%The principle is that for the distinguisher is irrelevant to S-box. Using Different S-boxes doesn't change our
-%The original distribution on each bit $Pr(\Delta=1) = 1 / ? = 0.035$:
-%Then after six rounds the distribution turns to be:
-
-
-\subsection{Single Random S-box Fault Attack}
-\input{single_prt.table.frgament.tex}
-
-According to Table~\ref{single_prt_tb},
-For single random S-box fault attack, a 7-round fault and 2-round partial decryption distinguishing attack is suggested.
-That is to say, in PRINT\small{CIPHER}\normalsize-48, 9 of 48 rounds are threatened by our fault attack.
-
-For a distinguishing attack, the attacker should guess not only the subkey but also the secret key-permutation key.
-Each time a group of (9+3)+(6+2)=25 subkey bits are guessed.
-One convenience is that in PRINT\scriptsize{CIPHER} \normalsize each round key is exactly the same.
-This reduces the complexity of recovering full secret key.
-Commonly for five independent distinguishing attack the attacker could acquire the key.
-The attack complexity is about $5$ $\cdot$ $2^{25}$ $\cdot$ $2^{11}$ $\cdot$ $2$ $\approx$ $2^{39}$ partial decryption.
-The attack takes us about 4-6 hours to obtain the correct key.
-% using some techniques to avoid repeatedly guess
-
-\subsection{Multi S-boxes Fault Attack}
-\input{multiple_prt.table.frgament.tex}
-
-According to Table~\ref{double_prt_tb} and ~\ref{triple_prt_tb},
-For two and three random S-box fault attacks, separately a 6+2, 5+2 fault propagation and partial decryption distinguishing attack could be employed.
-And the results is as same as the one of PRESENT: 
-if the number of affected S-boxes increases by one, the upper-bounds of the fault injection round within which we can accomplish the attack decrease by one.
-
-
-
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-
-
-\section{Conclusion}
-\label{concl}
-In this paper we propose differential fault analysis combining with statistical cryptanalysis technique to deal with middle round and multiple S-boxes fault injection of lightweight blockciphers.
-The basic idea is that both single random S-box fault and multiple S-boxes fault lead to an effective distinguisher which is useful for obtaining subkey.
-We describe how to attack the lightweight SPN blockciphers and give two practical attacks against PRESENT-80 and PRINT\scriptsize{CIPHER}\normalsize-48.
-The results show that our attack is powerful for exploiting vulnerability of lightweight blockciphers under the fault attack.
-Compared with existing DFA methods,
-our analysis extends the vulnerable rounds of these lightweight blockciphers and is able to deal with multiple S-boxes fault injection.
-%We show that bit-permutation weaken the security under side-channel attack.
-Our attack against PRINT\scriptsize{CIPHER} \normalsize reveals that even with secret bit-permutation the weakness still exists.
-We also open-sourced our simulation source code and hope more analysis could be found by other researchers.
-%We also released the attacking simulation source code at http://bitbucket.org/ with GIT form and hope more analysis could be found by other researchers.
-% conference papers do not normally have an appendix
+\input{sec_attack.tex}
 
+\input{sec_conl.tex}
 
 % use section* for acknowledgement
 %\section*{Acknowledgment}
 
 \input{biblo.tex}
 
-% that's all folks
 \end{document}
-
+% that's all folks
 

File FDTC2012/sec_attack.tex

+\section{Fault Attack}
+\label{attk}
+
+\subsection{General Attack Technique}
+Fault attack against lightweight block cipher often encounter two problems.
+First, Lightweight block ciphers would generally have smaller S-boxes and more iterative rounds to enhance the security for the lack of complicated round function.
+The fast encryption speed of device makes fault injection hard to locate accurate rounds or certain S-box, especially for fault attack focusing on last one or two rounds or requiring single S-box fault model.
+Second, due to the device's lifetime, attackers may not acquire enough amount of faulty ciphertext.
+Thus to take advantage of multiple S-boxes fault and earlier round fault is meaningful for fault analysis.
+
+For lightweight SPN block ciphers such as PRESENT and PRINT\small{CIPHER}\normalsize,
+a popular design methodology of bit-permutation is adopted because it is simple and easy to be implemented.
+The bit-permutation often brings a relatively slow diffusion.
+Our fault attack exploits this weakness to attack some middle rounds.
+
+%Under the single S-box fault model, each time there's only one affected faulty S-box.
+
+\subsubsection{Build Fault-based Distinguisher}
+The basic idea of our fault attack is to acquire an effective distinguisher based on fault injection and employ distinguishing attack.
+We found single random S-box fault model and multi S-boxes fault model are both suitable for attacking.
+Due to the design of the block cipher with bit-permutation,
+it takes several rounds for a single S-box fault differential to be diffused and yet change the output "randomly".
+If the fault is not well diffused due to the lack of enough round encryption, 
+the differential distribution is non-uniform \textbf{even on a subset}(e.g. a single S-box) of the penultimate or an antepenultimate block.
+This non-uniform distribution provides a good distinguisher for attacker.
+
+The distinguisher is based on the fact that the differential distribution is significantly different from uniform.
+The fault-based distinguisher, compared with traditional distinguisher, has following restrictions:
+\begin{itemize}
+    \item
+    According to the fault model, the input is coarse grained. Attackers could not precisely control the internal state.
+    \item
+    The amount of available output is limited. Unlike theoretical model, an attacker could not do the encryption unlimited. The allowed number of encryption is restricted by devices' lifetime.
+    \item
+    Analysis is complex. To precisely describe the probability of the distinguisher model is hard. In this paper, we adopt a simulation-based technique to avoid probability calculation of the distinguisher.
+\end{itemize}
+
+
+\subsubsection{Attack description}
+According to the {\it Wrong Key Randomisation Hypothesis}, 
+the attacker guesses part of the ultimate round(or plus penultimate round) key and partially decrypt the ciphertext.
+The incorrect key decryption is expected to have the same affect of encrypting one more round. 
+That is to say, the partially decrypted distribution should be a uniform one.
+If the guessed key is correct, the distance between partially decrypted distribution and the uniform distribution could be a well distinguisher.
+
+%Because even the fault on a single S-box is random, the bit-permutation make this randomness weak by diffuse each bit to different S-boxes.
+
+%In an SPN blockcipher with the common bit-permutation design,
+%even if the input of an S-box is random, after one round of permutation, $l$ S-boxes are to be affected according to S-box's bit number $l$,
+%and each affected S-box has a single bit input differential.
+%Thus the distribution of these affected S-box becomes far to uniform.
+%This non-uniform distribution may need more rounds of diffusion to become uniform again compared with byte-oriented permutation design.
+
+When we focus on the Single Random S-box Fault Model in an m-round SPN blockcipher with the common bit-permutation design, even if the input of an S-box is random, after one round of permutation, $l$ S-boxes are to be affected according to S-box's bit number $l$,
+and each affected S-box has a single bit input differential.
+Thus the distribution of these affected S-box becomes far to uniform.
+The Multi S-boxes Fault model shows similar property and the fault differential's non-uniform distribution still exists.
+In both cases the non-uniform distribution may need more rounds of diffusion to become random again compared with byte-oriented permutation design.
+
+
+\begin{figure}[h]
+\label{attack}
+    \centering
+    \includegraphics[width=0.5\textwidth]{attack.png}
+    \caption{Fault-based distinguishing attack}
+\end{figure}
+
+
+Our fault analysis relies on the non-uniform distribution when a single random S-box fault transferring for several rounds.
+An empirical and simple attack is to just partially decrypt the ciphertext and test the distribution of some subsets with all possible key candidates.
+If the distribution is non-uniform, the chosen key is considered to be the correct one.
+
+In practice,
+the attack against lightweight blockcipher generally do the partial decryption of two rounds instead of one because the partial key size is relatively small(e.g., 16 bits).
+
+
+Several distinguishers like Likelihood distinguisher and Squared Euclidean Imbalance (SEI) distinguisher \cite{rivain2009differential} can be used here to select the correct key.
+Consider the situation of not having exact knowledge about the fault propagation, especially for multiple S-boxes fault model and simplicity.
+We just adopt SEI method which picks the guessed key achieving strongest bias to uniform distribution as the correct one.
+The distinguisher $d(k)$ uses the squared Euclidean distance to the uniform distribution and is defined as:
+
+\begin{displaymath}
+d(k) = \sum_{\delta=0}^{2^m-1}\left(\frac{\#\{n; g_{i}(C_{n},\mbox{\~{C}}_{n},k)=\delta\} }{N}-\frac{1}{2^m}\right)^2
+\end{displaymath}
+
+In this formula $N$ is the number of correct and faulty ciphertexts pairs, $C$ and $\mbox{\~{C}}$ are correct and faulty ciphertexts, $g_{i}$ is the fault differential for the intermediate nibbles which has biased distribution and $k$ is subkeys which are sufficient to recovery the specific $g_{i}$.
+$m$ is the number of bits for corresponding S-box.
+For instance, for PRESENT the value of $m$ is 4.
+
+%We take the distance threshold as \textbf{0.001}.
+
+
+\subsection{Fault Attack Against PRESENT}
+
+%\begin{figure}
+%    \centering
+%    \includegraphics[width=0.5\textwidth]{present_fas.png}
+%    \caption{FAS propagation of PRESENT}
+%\end{figure}
+
+The diffusion property of PRESENT is relatively weaker because of the smaller S-box and bit permutation.
+This provides convenience of attacking middle rounds of encryption.
+%However, according to the design document[?], any five-round differential characteristic of PRESENT has a minimum of 10 active S-boxes and thus the maximum differential probability is $2^{-20}$.
+For the restriction of fault injection,
+it is hard to use small amount of faulty ciphertexts to distinguish the correct key with significant probability if the fault propagates too many rounds.
+In order to verify how many rounds are not immune to the fault attack, we simulate the fault propagation from two rounds to six rounds with a reasonable 10000 random inputs.
+By computing the output differential's squared Euclidean distance to the uniform distribution, we can observe the effectiveness of each round's fault injection.
+We simulate both single random S-box fault model and multiple S-boxes fault model.
+
+
+\subsubsection{Single Random S-box Fault Attack}
+
+\input{single_prs.table.frgament.tex}
+The distinguishing attack relies on the fact that the squared Euclidean distance acquired from correct subkey decryption is significantly greater than those acquired with incorrect key.
+We simulated the fault injection and tested the results.
+First, we tested the average squared Euclidean distance using 10000 pairs of random ciphertexts and found under random circumstance, the average squared Euclidean distance is about 0.0001-0.0005.
+Then, we do the simulation of fault injection and table~\ref{single_prs_tb} gives the simulation result of the distinguisher $d(k)$ uses the squared Euclidean distance on each nibble before penultimate round(using 10000 pairs of correct and faulty ciphertexts).
+As shown in table~\ref{single_prs_tb},
+if the fault injection position is earlier than round 25, even using the correct subkey to decrypt,
+the squared Euclidean distance is ineffective for a distinguishing attack.
+Thus a 5-round fault and 2-round partial decryption attack is acceptable under this circumstance.
+That is to say, for PRESENT with 31 rounds, it is allowed to inject the fault before round 25 and then employs a two round partial decryption.
+
+Our experiments support the simulation well. The correct key gives a significant high squared Euclidean distance value(about 0.006).
+While for incorrect keys, the average squared Euclidean distance is about 0.0001-0.0003 and the most significant is only about 0.0006.
+For a full attack process, the attacker should guess four group of each 16+4 subkey bits (16 bits from penultimate round and 4 bits from antipenultimate round)independently to find the correct key.
+The attack complexity is about $4$ $\cdot$ $2^{16+4}$ $\cdot$ $10000$ $\cdot$ $2$ = $2^{36.3}$ partial decryption.
+We simulate the attack for fixed key and 10000 pairs of random correct-faulty ciphertexts.
+Using two IBM xServer(\emph{Intel Xeon E5420 4 core@2.5Ghz}) the attack takes about 2 hours and successfully obtain the last round subkey and four nibble of penultimate round subkey.
+
+An interesting observation is that nibble 5, 7, 13 and 15 of PRESENT's block have farther distance from uniform than any other nibbles after fault propagation.
+In other words, when employing distinguishing attack, the attacker should make use of these nibble to better distinguish correct keys.
+Another observation is that if the fault injection is restricted to half of the whole block(e.g., from nibble 0-7 rather than 0-15),
+An effective distinguishing attack is allowed to be employed with one round earlier fault injection(injecting the fault before round 23).
+
+%The property is because these nibbles are only affected by 2nd and 4th bit of last round S-box's output.
+%of PRESENT tends to influence least significant bits when the input differential are {1,2,4,8}.
+%So the left-most bits are suitable for attacking rather than the right-most bits with almost random distribution after 5 rounds(both in theoretical analysis and simulation).
+
+\subsubsection{Multi S-boxes Fault Attack}
+Under multiple S-boxes fault model, it is even harder to analyze the precise distribution.
+Thus we do the empirical simulation and test the distribution.
+The results are shown in table~\ref{double_prs_tb},~\ref{triple_prs_tb} and ~\ref{qua_prs_tb}.
+According to the simulation, For Two, Three and Four S-boxes fault model, separately a 4+2, 3+2 and 2+2 fault propagation and partial decryption distinguishing attack could be employed.
+Also, due to the observed property that nibble 5, 7, 13 and 15 of PRESENT's block could be used in 3 S-boxes fault model to employ a 4+2 fault propagation and partial decryption distinguishing attack.
+
+And the results show that if the number of affected S-boxes increases by one, the upper-bounds of the fault injection round within which we can accomplish the attack decrease by one.
+Though the strict computation and explanation is complex,
+we can discover that begin with less faults directly injected in the earlier round after one round function the affected S-boxes increase and this intermediate state has some similarity with the one which is produce by more faults directly injected in this later round.
+
+
+\input{multiple_prs.table.frgament.tex}
+
+Our attack is obviously not optimal because we don't have a precise knowledge of the fault model and is hence not able to estimate the precise distribution,
+but it does exploit the capability of multi S-boxes fault attack against PRESENT under our attack.
+
+
+\subsection{Attack against PRINT\small{CIPHER}\normalsize-48}
+\label{pcattack}
+The attack process against PRINT\small{CIPHER}\normalsize-48 is almost the same as the process against PRESENT.
+A slight difference is that PRINT\scriptsize{CIPHER} \normalsize uses the key-dependent permutation.
+However, We found that the key-dependent permutation doesn't make our fault attack more complex.
+Because in the situation of PRINT\scriptsize{CIPHER} \normalsize, the distribution keeps the same on each bit even with four different secret permutation.
+Thus it is possible to do the estimation using any of the permutation.
+
+%The principle is that for the distinguisher is irrelevant to S-box. Using Different S-boxes doesn't change our
+%The original distribution on each bit $Pr(\Delta=1) = 1 / ? = 0.035$:
+%Then after six rounds the distribution turns to be:
+
+
+\subsection{Single Random S-box Fault Attack}
+\input{single_prt.table.frgament.tex}
+
+According to Table~\ref{single_prt_tb},
+For single random S-box fault attack, a 7-round fault and 2-round partial decryption distinguishing attack is suggested.
+That is to say, in PRINT\small{CIPHER}\normalsize-48, 9 of 48 rounds are threatened by our fault attack.
+
+For a distinguishing attack, the attacker should guess not only the subkey but also the secret key-permutation key.
+Each time a group of (9+3)+(6+2)=25 subkey bits are guessed.
+One convenience is that in PRINT\scriptsize{CIPHER} \normalsize each round key is exactly the same.
+This reduces the complexity of recovering full secret key.
+Commonly for five independent distinguishing attack the attacker could acquire the key.
+The attack complexity is about $5$ $\cdot$ $2^{25}$ $\cdot$ $2^{11}$ $\cdot$ $2$ $\approx$ $2^{39}$ partial decryption.
+The attack takes us about 4-6 hours to obtain the correct key.
+% using some techniques to avoid repeatedly guess
+
+\subsection{Multi S-boxes Fault Attack}
+\input{multiple_prt.table.frgament.tex}
+
+According to Table~\ref{double_prt_tb} and ~\ref{triple_prt_tb},
+For two and three random S-box fault attacks, separately a 6+2, 5+2 fault propagation and partial decryption distinguishing attack could be employed.
+And the results is as same as the one of PRESENT:
+if the number of affected S-boxes increases by one, the upper-bounds of the fault injection round within which we can accomplish the attack decrease by one.
+
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+

File FDTC2012/sec_conl.tex

+\section{Conclusion}
+\label{concl}
+In this paper we propose differential fault analysis combining with statistical cryptanalysis technique to deal with middle round and multiple S-boxes fault injection of lightweight block ciphers.
+The basic idea is that both single random S-box fault and multiple S-boxes fault lead to an effective distinguisher which is useful for obtaining subkey.
+We describe how to attack the lightweight SPN block ciphers and give two practical attacks against PRESENT-80 and PRINT\scriptsize{CIPHER}\normalsize-48.
+The results show that our attack is powerful for exploiting vulnerability of lightweight block ciphers under the fault attack.
+Compared with existing DFA methods,
+our analysis extends the vulnerable rounds of these lightweight block ciphers and is able to deal with multiple S-boxes fault injection.
+%We show that bit-permutation weaken the security under side-channel attack.
+Our attack against PRINT\scriptsize{CIPHER} \normalsize reveals that even with secret bit-permutation the weakness still exists.
+
+It is noteworthy that for block ciphers with byte-oriented design such as the AES and ARIA, neither single random S-box fault nor multiple S-boxes fault model leads to such an effective attack.
+
+This attack is effective to the block cipher with the bit-permutation rather than byte-oriented permutation.
+If the fault is not well diffused due to the lack of enough round encryption,
+the differential distribution is non-uniform \textbf{even on a subset}(e.g. a single S-box) of the penultimate or an antepenultimate block.
+This non-uniform distribution provides a good distinguisher for attacker.
+
+
+
+
+Finally, we also released the attacking simulation source code at http://bitbucket.org/ with GIT form and hope more analysis could be found by other researchers.
+% conference papers do not normally have an appendix

File FDTC2012/sec_intro.tex

+\section{Introduction}
+% no \IEEEPARstart
+Fault analysis is a kind of side-channel attack that seriously threats the security of cryptographic devices in real world.
+When an encryption is executed under faulty condition, error occurs on intermediate states so the normal output changes to a \emph{faulty output}.
+The faulty output is then used as a side-channel leakage to help retrieving secret information.
+Since the idea was first suggested in 1997 by D. Boneh, et al.\cite{boneh1997importance},
+various of fault analysis methods have been proposed and studied.
+Among them, Differential Fault Analysis(DFA) \cite{biham1997differential} is the most well studied.
+In a DFA attack, the secret key is recovered by using some pairs of correct and faulty output.
+The relationship between the common output and the specific faulty output provides extra information.
+Various of DFA methods have been developed against block ciphers include the AES\cite{piret2003differential}\cite{derbez2011meet},
+Camellia and ARIA. Some of them have already reached the information limitation that the fault model could provide\cite{li2010information}.
+
+Most of the DFA target to antepenultimate or penultimate round and take an impossible-and-eliminate method to exclude wrong key candidates.
+That is to say, it relies on the property that on a subset of the last round(e.g., one or two bytes), the input differential only contains a subset of all possible values.
+The attacker uses this restriction to solve some differential equation and excludes wrong key candidates.
+If the fault is in an earlier round and therefore the subset of the last round's input differential covers all possible values then the DFA technique is not suitable.
+From this point, DFA is a deterministic analysis while differential cryptanalysis is statistical.
+If the fault attack could take advantage of the statistical analysis technique, it is expected to exploit more information leakage.
+
+The research of fault attack against lightweight block ciphers such as PRESENT\cite{bogdanov2007present} and PRINT\scriptsize{CIPHER} \normalsize \cite{knudsen2010printcipher} are reported recent years.
+In 2009, Li et al. first proposed a DFA on PRESENT-80 \cite{juan2009present} which needs 40-50 pairs of faulty ciphertexts occurred at round 29.
+In 2010, Wang et al.\cite{wang2010differential} proposed a DFA on PRESENT key-schedule,
+which needs a single nibble fault on the round key and can recover the secret key with 64 pairs of correct and faulty cipher texts on average and the computational complexity is $2^{29}$.
+These two attacks both required a penultimate or an antepenultimate round faulty encryption.
+In 2011, Zhao, et al.\cite{zhao2011fault} proposed fault attacks against PRESENT and PRINT\scriptsize{CIPHER} \normalsize.
+However, their results didn't analyze the situation of an earlier round fault either.
+To the best of our knowledge, no fault attacks on earlier rounds are proposed and these attacks generally adopted one nibble error model.
+
+
+Traditional statistical cryptanalysis focused on full block ciphers and the attack is of impractical high complexity. 
+However, under the situation of fault attack, statistical cryptanalysis is effective for the attack actually exploits a reduced-round cipher model. 
+In 2006, Phan and Yen proposed an amplified side-channel attack enhanced by traditional cryptanalysis techniques\cite{phan2006amplifying}.
+In 2009, Matthieu Rivain first proposed an DFA on middle round DES\cite{rivain2009differential}.
+Inspired by their work, in this paper we adopt the idea of statistical cryptanalysis to enhance fault analysis of lightweight block cipher.
+In detail We propose fault analysis of the lightweight SPN block cipher with bit-permutation and present specific fault attacks against PRESENT-80 and PRINT\scriptsize{CIPHER} \normalsize-48.
+We notice that in many lightweight SPN block ciphers with bit-permutation,
+the fault propagation process is relatively slow, and it is available to employ fault attack to construct an effective distinguisher.
+This fault based distinguisher helps attacker determine key with high probability and low data complexity.
+With the distinguisher, more rounds of the whole cipher are vulnerable to fault attack.
+
+
+In his thesis, Pascal Junod gave a thorough discussion of statistical cryptanalysis of block ciphers\cite{???}.
+This distinguisher based attack is considered as a statistical hypothesis testing problem.
+We here discuss the fault based differential distinguishers.
+%then we analyze the transformation of the original non-uniform distribution after iterative round function and give the probability estimating method.
+Based on the distinguishers, we can retrieve round key and estimate which rounds are vulnerable to fault attack.
+We simulated the fault attack against PRESENT-80 and PRINT\scriptsize{CIPHER}\normalsize-48 to prove the statistical hypothesis,
+and the result supported our analysis. 
+Only a practical amount of ciphertexts and a few hours with commodity computers are needed.
+
+The rest of this paper is organized as follows.
+In Section~\ref{prelimi} we briefly review the structure of PRESENT and PRINT\scriptsize{CIPHER} \normalsize, the common fault injection technique and fault model.
+In Section~\ref{attk}, we describe the principle and analysis technique of our fault attack.
+Then we present two practical attacks against PRESENT-80 and PRINT\scriptsize{CIPHER} \normalsize-48.
+Section~\ref{concl} concludes the paper.
+% You must have at least 2 lines in the paragraph with the drop letter
+% (should never be an issue)
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

File FDTC2012/sec_pre.tex

+\section{Preliminaries}
+\label{prelimi}
+PRESENT is a lightweight block cipher designed by Bogdanov et al. in 2007 for extremely constrained environments such as RFID tags and sensor networks.
+It is a 31-round SPN block cipher with 64 bits block size and supports 80 and 128 bits key.
+The encryption process of PRESENT is described in Algorithm~\ref{prs_algo}.
+There are three stages involved in each round function,
+$\sf{addRoundKey}$, $\sf{sBoxlayer}$ and $\sf{permutationLayer}$.
+For more information about PRESENT, the interested reader may refer to \cite{bogdanov2007present}
+
+\begin{algorithm}
+\label{prs_algo}
+\caption{PRESENT}
+\KwIn{$u_{1}, K_{1}-K_{32}$}
+\KwOut{$u_{32}$}
+    \For{$i$ = 1 $to$ 31}
+    {
+        $\sf{addRoundKey}$$(u_{i}, K_{i})$ \\
+        $\sf{sBoxlayer}$$(u_{i})$ \\
+        $\sf{permutationLayer}$$(u_{i})$ \\
+    }
+    $addRoundKey(u_{32},K_{32})$ \\
+    return $u_{32}$
+\end{algorithm}
+
+\begin{figure}
+\label{prs_func}
+    \centering
+    \includegraphics[width=0.5\textwidth]{present.png}
+    \caption{Round function of PRESENT}
+\end{figure}
+
+
+\subsection{Blockcipher PRINT\scriptsize{CIPHER}\normalsize}
+PRINT\scriptsize{CIPHER} \normalsize is an ultra-lightweight block cipher proposed by L.Knudsen et al. in 2010.
+It is a 48/96-round SPN blockcipher with 48/96 bits block size and supports 80/160 bits key.
+PRINT\scriptsize{CIPHER} \normalsize uses key-dependent permutation and very simple key-schedule.
+The encryption process of PRINT\scriptsize{CIPHER} \normalsize is described in Algorithm~\ref{print_algo}.
+The interested reader is referred to \cite{knudsen2010printcipher} for further information about PRINT\scriptsize{CIPHER} \normalsize. 
+
+\begin{algorithm}
+\label{print_algo}
+\caption{PRINT\scriptsize{CIPHER} \normalsize}
+\KwIn{$u_{1}, K_{1}-K{r}$}
+\KwOut{$u_{r}$}
+    \For{$i$ = 1 $to$ r}
+    {
+        $\sf{addRoundKey}$$(u_{i}, K_{i})$ \\
+        $\sf{linearDiffusion}$$(u_{i})$ \\
+        $\sf{xorRoundCounter}$$(u_{i})$ \\
+        $\sf{keyedPermutation}$$(u_{i})$ \\
+        $\sf{sBoxlayer}$$(u_{i})$
+    }
+    return $u_{r}$
+\end{algorithm}
+
+
+
+\subsection{Fault Injection Techniques}
+Lightweight block ciphers are used in cryptographic devices such as smart cards and RFID tags in real world.
+Previous research shows that certain round of the encryption could be affected when clock faults occur,
+and devices such as FPGA using a DLL-based FPGA platform are vulnerable to fault attack\cite{agoyan2010clocks}.
+Although nowadays advanced smartcards are claimed to be protected by fault detection circuit,
+it is still not common, especially for those low cost devices, to add protection.
+
+Under the fault attack, it is a reasonable assumption that a cryptographic device with fixed secret key is controlled by an attacker.
+The attacker could ask the device to encrypt(or even decrypt) arbitrary plaintext(or even ciphertext).
+What's more,
+the attacker deliberately interferes the normal encryption by changing the power supply voltage or the frequency of the external clock,
+or using laser attack, and collects the faulty output\cite{barenghifault}.
+In \cite{agoyan2010clocks}, Agoyan et al. demonstrated how to inject single bit fault in a reproducible way,
+despite the optical precision of the equipment was not able to target the smallest features of the target chip.
+We may assume that more than one faulty output are available for fault attack.
+However, fault attack is more or less harmful to devices, and due to most popular devices' lifetime(for instance, a sim card is able to do the encryption for at most 50000-60000 times),
+it is expect to obtain 1000-10000 pairs of correct-faulty output on average.
+What's more, although fault attack may affect the certain round, it is often hard for the attacker to know which parts of the internal state are changed.
+The most possible situation is that one S-box or small number of S-boxes of one round are affected and the fault is random.
+Another situation is that in a parallel $n$ different S-boxes, one of them is most vulnerable to unstable circumstance such as low voltage.
+However, in this paper we do not consider this model.
+%And this leads to a fixed S-box fault model.
+We will show the fault model in detail in the next subsection.
+
+\subsection{Fault Model}
+Our attack considers two fault models: \emph{Single Random S-box}, and \emph{Multi S-boxes} fault model.
+We can recover the secret key within the faults injected after specific rounds depending on the fault model used.
+
+%\subsection{Single Specific S-box Fault Model}
+%This model requires one fixed S-box of a certain round are repeatedly and randomly disturbed thus produces a set of different faulty outputs.
+
+\subsubsection{Single Random S-box Fault Model}
+A single random S-box fault model requires following assumption.
+\begin{itemize}
+    \item
+    The input of \textbf{one} S-box in a certain round is switched to a random and uniformly distributed value due to the fault injection.
+    \item
+    For a pair of correct ciphertext and its corresponding faulty ciphertext, they are encrypted from the same plaintext and the same key.
+    \item
+    Multiple pairs of correct and faulty ciphertexts (may from different plaintext) provided to attacker are encrypted by the same key.
+\end{itemize}
+
+The frequently mentioned single bit model can be seen as a special case of this model.
+
+%Because the fault attack changes only one S-box of the internal state,
+%the original differential distribution from the fault encryption is obviously non-uniform.
+
+\subsubsection{Multi S-boxes Fault Model}
+A multi S-boxes fault model requires following assumption.
+\begin{itemize}
+    \item
+    The input of \textbf{multiple} S-boxes in a certain round are switched to random and uniformly distributed values due to the fault injection.
+    The number of corrupted S-boxes is a small part compared to the total S-boxes used in one round.
+    \item
+    For a pair of correct ciphertext and its corresponding faulty ciphertext, they are encrypted from the same plaintext and the same key.
+    \item
+    Multiple pairs of correct and faulty ciphertexts (may from different plaintext) provided to attacker are encrypted by the same key.
+\end{itemize}
+
+%In the case of PRESENT and PRINT\small{CIPHER}\normalsize this number can be up to 4.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+

File FDTC2012/title.tex

 
 \author
 {
-Submitted to FDTC 2012
-%\IEEEauthorblockN {Dawu Gu, Juanru Li, Shen Li}
-%\IEEEauthorblockA
-%{
-%Dept. Computer Science and Engineering\\
-%Shanghai Jiao Tong University\\
-%Shanghai, China\\
-%Email: jarod@sjtu.edu.cn
-%}
-%\and
-%\IEEEauthorblockN{Zheng Guo}
-%\IEEEauthorblockA
-%{
-%School of Microelectronic\\
-%Shanghai Jiao Tong University\\
-%Shanghai, China\\
-%Email: guo@sjtu.edu.cn}
+    \IEEEauthorblockN {Dawu Gu, Juanru Li, Shen Li, Zhouqian Ma}
+    \IEEEauthorblockA
+    {
+        Dept. Computer Science and Engineering\\
+        Shanghai Jiao Tong University\\
+        Shanghai, China\\
+        Email: dwgu@sjtu.edu.cn
+    }
+
+    \and
+
+    \IEEEauthorblockN{Zheng Guo}
+    \IEEEauthorblockA
+    {
+        School of Microelectronic\\
+        Shanghai Jiao Tong University\\
+        Shanghai, China
+    }
+    
+    \IEEEauthorblockN{Junrong Liu}
+    \IEEEauthorblockA
+    {
+        School of Information Security\\
+        Shanghai Jiao Tong University\\
+        Shanghai, China
+    }    
 }
 
 % conference papers do not typically use \thanks and this command