## 2 Literature Review
### Linear Cryptanalysis Attack (also Known as Known Plaintext Attack)  
Linear cryptanalysis (or known plaintext attack) is a strong technique introduced by [PERSON] in 1993 to attack cryptographic algorithms [1]. The attack was first implemented on the cryptographic algorithm called the Data Encryption Standard (DES), but an untimely adaptation of the linear cryptanalysis attack, introduced by [PERSON] and [PERSON], was previously used to successfully attack FEAL in 1992 [2]. The attacker analyzes the linear probability relations (linear approximations) of known plaintext to search for a secret key. \begin{table}
\begin{tabular}{l l l} \hline
**Algorithm** & **Linear Cryptanalysis** & **Number of Rounds Attacked** \\ \hline AES & Yes [24; 25] & 2 rounds [25] \\ \hline BLOWFISH & Yes [26; 27] & 18 rounds with week keys [26; 27] \\ \hline CAMELLIA & Yes [27; 28] & 9 rounds [27] \\ \hline CAST & Yes [29] & 6 and 18 rounds [29] \\ \hline CLEFIA & Yes [31] & 11, 12, 14 and 15 rounds [31] \\ \hline DES & Yes [32] & 3, 5, 8, 12 and 16 rounds [32] \\ \hline MMB & Yes [33] & All rounds [33] \\ \hline RC5 & Yes [34] & All rounds [34] \\ \hline SERPENT & Yes [35] & 11 rounds [35] \\ \hline SKIPJACK & Yes [36] & All rounds [36] \\ \hline \end{tabular}
\end{table} 
Table 1: Summary of literature review. Cryptographic algorithms routinely use non-linear S-Boxes in their structures [1; 2; 3]. In DES, the only non-linear building blocks are the S-boxes [3]. The rest of the building blocks are linear and can be easily attacked [3]. A linear probability relation (linear approximation) of known plaintext is used to obtain the secret key and is calculated by XORing many pairs of plaintext, and the results are tabled for analysis [4]. Attackers do not attack the entire algorithm at once [4]. In the linear cryptanalysis attack, the attacker first analyzes the linear vulnerabilities of an S-Box. For example, let us consider the simplified S-Box of DES shown in Table 1, where the input bits are X = [\(X_{1}\)\(X_{2}\)\(X_{3}\)\(X_{4}\)] and the output bits are Y = [\(Y_{1}\)\(Y_{2}\)\(Y_{3}\)\(Y_{4}\)]. The attacker examined all possibilities of the events that S-Box conducted. Every linear approximation can be calculated to discover its functionality by examining the probability for each event using Equation (1) [5]. \[Probability[\ X_{1}\ \oplus\ X_{2}\oplus\ldots\oplus X_{U}\oplus Y_{1}\oplus Y_{ 2}\oplus\ldots\oplus Y_{V}=0]=P \tag{1}\]  
From Equation (1), if is much greater than half (1/2), there is a high probability of occurrence to guess the key, whereas if is much lesser than half, the S-Box has a low probability of occurrence [1]. Therefore, the probability bias of the S-Box can be calculated using Equation (1) [2; 3; 4]. Figure 1 shows the four input bits X = [\(X_{1}\)\(X_{2}\)\(X_{3}\)\(X_{4}\)] and the four output bits Y = [\(Y_{1}\)\(Y_{2}\)\(Y_{3}\)\(Y_{4}\)] of the simplified S-Box of DES defined in Table 2. The input and output bits are used to define the S-Box size. The S-Box size in Figure 1 and Table 2 is a 4 \(\times\) 4 S-Box. For example, From Table 2 and Figure 1, S-Box is 4 \(\times\) 4, meaning that it has four bits of input and four bits of output. To calculate the linear probability, if an event of \(X_{1}\)\(\oplus\)\(X_{4}\)\(\oplus\)\(Y_{2}\) = 0 is analyzed, Table 3 can be drawn, and a total of eight zeros are counted. See Table 3. Therefore, from Equation (2), derived from Equation (1),  
\[Probability[\ X_{1}\ \oplus\ X_{4}\oplus Y_{2}=0]=\frac{8}{16}=\frac{1}{2}=PL \tag{2}\] \begin{table}
\begin{tabular}{c c c c c c c c c c c c c c c} \hline X & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & A & B & C & D & E & F \\ S(X) = Y & E & 4 & D & 1 & 2 & F & B & 8 & 3 & A & 6 & C & 5 & 9 & 0 & 7 \\ \hline \end{tabular}
\end{table} 
Table 2: Simplified S-Box of DES [5]. Figure 1: Sample of S-Box [4]. The denominator value of 16 is calculated from the size of the S-Box, which is \(4\times 4=16\).