Commits

RomanGol  committed 841eaa4

Camera Ready

almost ok

  • Participants
  • Parent commits 5348fc4

Comments (0)

Files changed (8)

File FDTC2012/fdtc.bib

   author={Barenghi, A. and Breveglieri, L. and Koren, I. and Naccache, D.},
   year={2012},
   institution={Politecnico di Milano, Milan, Italy}
+}
+
+@phdthesis{junod2005statistical,
+  title={Statistical cryptanalysis of block ciphers},
+  author={Junod, P.},
+  year={2005},
+  school={{\'E}COLE POLYTECHNIQUE F{\'E}D{\'E}RALE DE LAUSANNE}
+}
+
+@article{heys2002tutorial,
+  title={A tutorial on linear and differential cryptanalysis},
+  author={Heys, H.M.},
+  journal={Cryptologia},
+  volume={26},
+  number={3},
+  pages={189--221},
+  year={2002},
+  publisher={Taylor \& Francis}
 }

File FDTC2012/main.bbl

   perspective on the differential fault analysis against aes,'' \emph{IACR
   eprint archive}, vol.~32, p. 2010, 2010.
 
-\bibitem{phan2006amplifying}
-R.~Phan and S.~Yen, ``Amplifying side-channel attacks with techniques from
-  block cipher cryptanalysis,'' \emph{Smart Card Research and Advanced
-  Applications}, pp. 135--150, 2006.
-
-\bibitem{rivain2009differential}
-M.~Rivain, ``Differential fault analysis on des middle rounds,''
-  \emph{Cryptographic Hardware and Embedded Systems-CHES 2009}, pp. 457--469,
-  2009.
-
 \bibitem{bogdanov2007present}
 A.~Bogdanov, L.~Knudsen, G.~Leander, C.~Paar, A.~Poschmann, M.~Robshaw,
   Y.~Seurin, and C.~Vikkelsoe, ``Present: An ultra-lightweight block cipher,''
   present and printcipher,'' Cryptology ePrint Archive, Report 2011/086, Tech.
   Rep., 2011.
 
+\bibitem{phan2006amplifying}
+R.~Phan and S.~Yen, ``Amplifying side-channel attacks with techniques from
+  block cipher cryptanalysis,'' \emph{Smart Card Research and Advanced
+  Applications}, pp. 135--150, 2006.
+
+\bibitem{rivain2009differential}
+M.~Rivain, ``Differential fault analysis on des middle rounds,''
+  \emph{Cryptographic Hardware and Embedded Systems-CHES 2009}, pp. 457--469,
+  2009.
+
 \bibitem{agoyan2010clocks}
 M.~Agoyan, J.~Dutertre, D.~Naccache, B.~Robisson, and A.~Tria, ``When clocks
   fail: On critical paths and clock faults,'' \emph{Smart Card Research and
   attacks on cryptographic devices: Theory, practice and countermeasures,''
   Politecnico di Milano, Milan, Italy, Tech. Rep., 2012.
 
+\bibitem{heys2002tutorial}
+H.~Heys, ``A tutorial on linear and differential cryptanalysis,''
+  \emph{Cryptologia}, vol.~26, no.~3, pp. 189--221, 2002.
+
+\bibitem{junod2005statistical}
+P.~Junod, ``Statistical cryptanalysis of block ciphers,'' Ph.D. dissertation,
+  {\'E}COLE POLYTECHNIQUE F{\'E}D{\'E}RALE DE LAUSANNE, 2005.
+
 \end{thebibliography}

File FDTC2012/sec_attack.tex

 \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.
+Fault attacks against lightweight block cipher often encounter two problems.
+First, Lightweight block ciphers would generally use 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, in practice attackers may not acquire a huge amount of faulty ciphertexts.
+Thus to take advantage of limited faulty ciphertexts, 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.
+Our fault attack exploits this weakness.
 
 %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.
+We found single random S-box fault model and multi S-boxes fault model are both suitable for our attack.
+For those block ciphers with bit-permutation, 
+we can exploit middle round fault is mainly because it takes several rounds for a single S-box or multi S-boxes fault differential to be fully diffused, 
+and yet changes the output differential to be "random".
+If the fault is not well diffused due to the lack of enough round iteration,
+the differential distribution is non-uniform \textbf{even on a subset}(e.g. a single S-box) of the penultimate or an antepenultimate state.
 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.
 
 
 \subsubsection{Attack description}
-According to the {\it Wrong Key Randomisation Hypothesis}, 
+Our attack is similar to basic differential cryptanalysis\cite{heys2002tutorial}.
+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.
+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 uniform.
 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,
+%In an SPN block cipher 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$,
+When we focus on the Single Random S-box Fault Model in an m-round SPN block cipher 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.
+Thus the input differential's distribution of each 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.
+In other words, the fault propagates from random byte to some random bits and then to the whole block.
+This process slows the diffusion. 
+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.
+Fault propagation is faster because the any random byte fault is directly diffused to the whole block and the distinguisher on single S-box is ineffective.
 
 
 \begin{figure}[h]
     \caption{Fault-based distinguishing attack}
 \end{figure}
 
+Our fault analysis relies on the non-uniform distribution of the input differential of a single S-box.
+The attack process is to just partially decrypt the ciphertext and test the distribution of the input differential of an S-box with all possible key candidates.
+If the distribution is obviously non-uniform, the chosen key is considered to be the correct one.
+In practice, 
+the attack against lightweight block ciphers generally do the partial decryption of two rounds instead of one because the partial key size is relatively small(e.g., 16 bits).
 
-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).
-
-
+In his thesis, Pascal Junod gave a thorough discussion of statistical cryptanalysis of block ciphers\cite{junod2005statistical}.
 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.
 %We take the distance threshold as \textbf{0.001}.
 
 
+
+
 \subsection{Fault Attack Against PRESENT}
 
 %\begin{figure}
 %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.
+In order to verify how many rounds are not immune to the fault attack, 
+we simulated 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 simulated both single random S-box fault model and multiple S-boxes fault model.
 
 
 \subsubsection{Single Random S-box Fault Attack}

File FDTC2012/sec_conl.tex

 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.
+For these two lightweight ciphers, about one fifth of the iterative rounds are needed to be protected according to our results.
+Finally, we released the attacking simulation source code at https://bitbucket.org/RomanGol/faultattack and hope more analysis could be found by other researchers.
 % conference papers do not normally have an appendix

File FDTC2012/sec_intro.tex

 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. 
+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. 
+We simulated the fault attack against PRESENT-80 and PRINT\scriptsize{CIPHER}\normalsize-48 to prove the 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.
+In Section~\ref{prelimi} we briefly review the structure of PRESENT and PRINT\scriptsize{CIPHER} \normalsize, the common fault injection technique and two fault models.
+In Section~\ref{attk}, we describe the principle and 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

File FDTC2012/sec_pre.tex

 \end{figure}
 
 
-\subsection{Blockcipher PRINT\scriptsize{CIPHER}\normalsize}
+\subsection{Block cipher 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.
+It is a 48/96-round SPN block cipher 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. 
+The interested reader is referred to \cite{knudsen2010printcipher} for further information about PRINT\scriptsize{CIPHER} \normalsize.
 
 \begin{algorithm}
 \label{print_algo}

File FDTC2012/title.tex

         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
 
 
 \begin{abstract}
-Differential fault analysis is one of the most efficient side channel attack techniques that threat the security of blockcipher.
+Differential fault analysis is one of the most efficient side channel attack techniques that threat the security of block cipher.
 However, it often requires a penultimate or an antepenultimate round faulty encryption and is not suitable for middle round fault.
-This paper presents attacks combining differential fault analysis with statistical cryptanalysis techniques to attack lightweight ciphers.
+This paper presents attacks combining differential fault analysis with statistical cryptanalysis techniques against lightweight ciphers.
 The analysis makes use of statistical cryptanalysis techniques in practice rather than theoretically,
-and exploits the weakness of bit-permutation adopted by many lightweight blockciphers under fault attack.
+and exploits the weakness of bit-permutation adopted by many lightweight block ciphers under fault attack.
 Specific attacks against PRESENT and PRINT\scriptsize{CIPHER} \normalsize are given to prove the validity.
 The result shows that about one fifth of the iterative rounds are needed to be protected for these lightweight ciphers with bit-permutation.
 \end{abstract}

File FDTC2012/tx.bat

+copy /Y main.bbl output\
+pdflatex.exe -output-directory output -halt-on-error "main.tex"
+output\\main.pdf