Performance efficiency of modified AES algorithm using multiple S-Boxes.
In 1997, the National Institute of Standards and Technology (NIST) started a process to identify a replacement for the Data Encryption Standard (DES) which was generally recognized to be not secured due to fast advances in computer processing power. The goal of NIST was to define a replacement for DES that could be used for nonmilitary information security applications by US government agencies. Additionally, commercial and other non-government users could also benefit from the technology as it can also generally adopted for commercial use.
The NIST invited experts in the field of cryptography and data security from around the world to participate in the discussion and in the selection process. There were five encryption algorithms that made to the final round of the screening process. Ultimately, the encryption algorithm proposed by the Belgium cryptographers Joan Daeman and Vincent Rijmen was selected. Prior to selection, Daeman and Rijmen used the name Rijndael (derived from their names) for the algorithm. After adoption, the encryption algorithm was given the name Advanced Encryption Standard (AES) which is in common use today .
In 2000, the NIST formally adopted the AES encryption algorithm and published it as a federal standard under the designation FIPS-197. It was chosen because of its security, performance, efficiency, implementability, and low memory requirements.
The AES algorithm is primarily composed of four core functions that are repeatedly perform to the nth times depending on the keylength. The MixColumn function is an important property of the cipher. Generally, it provides strength against differential and linear attacks due to the complexity of its mathematical operations. These complex mathematical operations may require computational resources in software implementation. We assume that by replacing the MixColumn function, the speed performance of the AES algorithm will be improved.
In light of this study, this paper aims to determine the execution time performance efficiency of the proposed modified AES algorithm using multiple S-Boxes against the original AES algorithm. It will also attempt to evaluate security properties of both algorithm versions.
2 REVIEW OF RELATED STUDIES
Modifying the AES algorithm to improve its performance, either in speed or in security and both, has been the subject of numerous studies that were previously conducted. However, most of these studies were focused in changing the original substitution box as designed by Daeman and Rijmen unto different version of the S-Box. For instance,  proposed a substitution box that made use of the RC4 key schedule algorithm (KSA). The resulting matrix is a key-dependent S-Box that is dynamically generated based from some key. In their work, they constructed the S-box-RC4 by:
* Running the RC4 KSA to construct 256! S-boxes depend on input key; and
* Perform an affine transformation to the RC4-KSA S-Box to produce the final S-Box.
After they created their new RC4-generated S-Box, they use it to replace the Rijndael S-Box during the encryption and decryption processes.
In  proposed for yet another key-dependent S-Box that they intend to substitute for the Rijndael S-Box. In their paper, they modified the AES algorithm by placing another phase in the beginning of every round. They call the extra phase as the S-Box Rotation. The purpose of which is to rearrange the original matrix by way of rotating the Rijndael Sbox according to some round key. The round key is derived from the cipher key using the key schedule algorithm. The rotation value is dependent on the entire round key.
The results of their study showed that the enhancement on the original AES does not violate the security of the cipher. The enhanced version introduces confusion without violating the diffusion property.
In , proposed an enhanced version of the AES128 algorithm by reducing the number of rounds from 10 rounds to 8 rounds. Their assumption was that with the less number of rounds, it will result in less processing time of the AES algorithm, and therefore increase the speed performance of the cipher. However, they also acknowledge that the reduction in the number of rounds to 8 is risky in as far as security attacks are concerned as such as differential attack and distinguishing attack. To offset such risk, their proposed enhanced AES-128 algorithm used a hashing function to compensate the attacks being mentioned. Hence, their enhanced AES algorithm, while less in the number of rounds yet an extra phase for the hashing function using the SHA-256 in every round is included. The result of their experiment revealed that the hashing function improved the security aspects of the cipher but required more number of operations.
3 BASIC CONCEPT OF THE AES ALGORITHM
The AES algorithm is a block cipher with a block length of 128 bits. The key which is provided as the input is expanded into an array of key schedule words, with each word has a size of four bytes. The total key schedule for the 128-bit key is 44 words.
AES allows for three different key lengths: 128, 192, or 256 bits. The encryption and decryption is consists of 10 rounds of processing for a 128-bit keys, 12 rounds for 192-bit keys, and 14 rounds for 256-bit keys. During the encryption and decryption processes, the 16 bytes of data will form a changeable (4*4) array called the state array .
For the encryption, the state array consists initially of the input data. This array will keep changing until the final encrypted data is reach. In the decryption process, the state array start from the enciphered data and will keep changing until the original data is produced. The encryption of AES is carried out in blocks with a fixed block size of 128 bits each. The AES cipher calculation is specified as a number of repetitions of transformation rounds that convert the input plaintext into the final output of cipher text. Figure 1 shows the AES cipher structure.
Except for the last round in each case, all other rounds are identical. Inside each round are four different stages. These are:
3.1 Substitute Bytes (SubBytes Operation)
The SubBytes transformation is a non-linear byte substitution that operates independently on each byte of the State using a substitution table (Sbox). This is a major reason for the security of the AES. With the help of this lookup table, the 16 bytes of the state (the input data) are substituted by the corresponding values found in the table. Figure 2 shows the SubBytes operation.
3.2 Shift Rows (ShiftRows Operation)
The ShiftRows operation (figure 3) provides inter-column diffusion where the bytes in the last three rows of the states are shifted. Hence, the second row of the states is shifted by one byte position to the left of the matrix; the third row of the states is shifted by two bytes position to the left of the matrix; and the fourth row of the states is shifted by three bytes position to the left .
3.3 Mix Columns (MixColumns Operation)
Figure 4 shows the MixColumns operation that provides inter-byte diffusion where each column vector is multiplied by a fix matrix. The Galois Field is used in this operation. The bytes are treated as polynomials rather than numbers.
3.4 Add Round Key (AddRoundKey Operation)
The AddRoundKey operation is simple. In this transformation, a round key is added to the state by a simple bitwise XOR operation. Each round key consists of Nb words from the key schedule . It is performed by XOR-ing each byte of the state and the round key. Figure 5 shows the AddRoundKey operation.
For encryption, the individual transformations for the pseudocode computation consist of SubBytes(), ShiftRows(), MixColumns() and AddRoundKey(). These transformations play a role in processing the state . The transformation (number of rounds) is performed depending on the key length. However, the final round is only consists of three stages: SubBytes, ShiftRows and AddRoundKey in producing the final encrypted data or ciphertext.
The decryption process is essentially the same structure as the encryption, following the nine rounds of Inverse ShiftRows, Inverse SubBytes, Inverse AddRoundKey and Inverse MixColumns transformation. In the final round, the Inverse MixColumns is no longer performed.
4 PROPOSED ENHANCED AES ALGORITHM USING MULTIPLE S-BOXES
In our previous paper , we proposed to modify the existing AES algorithm using two substitution boxes to enhance speed performance of the cipher. The SubBytes operation is less accessible from the standpoint of linear algebra because it is use to provide a non-linear step in the Rijndael cipher. A non-linear step in the cipher greatly increases its complexity and makes cryptanalysis more difficult .
On the other hand, among the four core functions of the AES algorithm, the MixColumns function is perceive to be requiring more computational resources in software implementation as compared to the other functions. This is due to the fact that the MixColumns function provides the critical security properties of the cipher to avoid from linear and/or differential attacks. It is through this assumption that replacing the MixColumns function by an alternative function, it may increase the speed performance of the AES algorithm.
The proposed enhanced version will become lightweight as it will employ two S-Boxes. The first S-Box is the Rijndael S-Box that is the default in the original structure of the cipher. It will be used as it is implemented in the original version. However, the second S-Box will be constructed and will replace the MixColumns function. It will be constructed using XOR operation and affine transformation.
In essence, the encryption process of the enhanced AES algorithm follows the sequence of SubBytes, ShiftRows, SubBytesXOR and AddRoundKey operations for nine rounds. In the final round, SubBytes, ShiftRows and the AddRoundKey operations will be performed to produce the ciphertext.
To decrypt, the enhanced AES algorithm is performed using the sequence of Inverse ShiftRows, Inverse SubBytes, Inverse AddRoundKey and Inverse SubBytesXOR operations for nine rounds. In the final round, the Inverse SubBytesXOR is drop to produce the plaintext. Figure 6 shows the proposed modified AES algorithm structure using multiple S-Boxes.
5 CONSTRUCTION OF THE NEW S-BOX
The second S-Box is derived from the original S-Box as designed in the AES (hereafter referred as AES-Rijndael). It is constructed using the following process:
5.1 Exclusive OR Operation
The first step is to do an XOR operation to the AES-Rijndael using some Key[i]. The Key[i] shall be any hexadecimal value between 00 to FF. In this particular matrix, the key used was 7F. Hence, the new S-Box shall be referred to as AES-[2SboxXOR.sub.7F]. For the initial values of the AES-[SboxXOR.sub.7F], each cell in the AES-Rijndael will be XORed with 7F (AES-Rijndael[x,y] [cross product] 7F).
5.2 Affine Transform Operation
After creating the initial values of AES2SboxXOR, each cell will be subjected to affine transformation, as applied to the Sbox-Rijndael, to avoid any fix points and to make the new S-box invertible.
To scramble the bits in each byte value, we next apply the following transformation to each bit bi as stored in the initial AES-2SboxXOR7F:
[b'.sub.i] = [b.sub.i][cross product][b.sub.(i+4)mod8][cross product][b.sub.(i+5)mod8][cross product] [b.sub.(i+6)mod8][cross product][b.sub.(i+7)mod8] [cross product][c.sub.i] (1)
where [c.sub.i] is the ith bit of a specially designated byte c whose hex value is 0x63 (c7c6c5c4c3c2c1c0 = 01100011 ).
For the inverse AES-2SboxXOR, the following transformation to each bit was used for bit scrambling:
[b'.sub.i] = [b.sub.(i+2)mod8] [cross product] [b.sub.(i+5)mod8] [cross product] [b.sub.(i+7)mod8] [cross product] [d.sup.i] (2)
where [d.sub.i] is the ith bit of a specially designated byte d whose hex value is 0x05 (d7d6d5d4d3d2d1ddc0 = 00000101).
5.3 Matrix Mapping Operation
At the end of the affine transformation, the final values are known. The next step is to map each value to the matrix as appropriate to create the final lookup tables. Table 1 shows the final AES-[2SboxXOR.sub.7F] while table 2 shows the final Inverse AES-[2SboxXOR.sub.7F].
6 EXPERIMENTS METHODOLOGY
6.1 Test File
To test the speed performance of the proposed modified AES algorithm using multiple SBoxes, a text file with a size of 59 kilobytes was used in the experiment. The file was subjected to the encryption and decryption processes for 20 trials to encourage the reliability of the results.
The time trials were noted and subsequently subjected to statistical analysis to determine the performances of both versions.
6.2 Implementation Environment
In the conduct of experiments, the following implementation environment was used:
Processor: Intel(R) Core(TM) i3-4010U CPU @ 1.70GHz
Main Memory: 4.00 Gb
Operating System: 64-bit
Runtime Environment: JRE7
Development Platform: Eclipse SDK 3.6.0
7 EVALUATION RESULTS
7.1 Speed Performance Difference
For the encryption, the AES-Rijndael version obtained a mean of 171.75ms while the proposed AES-2SBox obtained a mean of 139.65ms. Using the Data Analysis Tool from the Microsoft Excel 2010[TM], the t-Test for independent samples was used to statistically compute the significant difference in the speed performance. Based from the result of the test, the obtained P-value was 5.33936E-07. This is lower than the 0.05 level of significance, hence there is indeed a significant difference in the speed performance. Table 3 shows the t-Test Statistics for Independent Samples of the encryption process.
For the decryption process, the AES-Rijndael obtained a mean of 195.00ms while the AES2SBox version obtained a mean of 92.95ms. Similarly, the t-Test for Independent samples was used for statistical computation. Based from the result of the test, the P value obtained was 3.9442E-25 which is lower than the 0.05 level of significance. Again, there is a significant difference in the speed performance. Table 4 shows the t-Test statistics for independent samples of the decryption process.
7.2 Time Execution Performance Efficiency
To compare the execution time performance efficiency (TEPE) of the two versions, the means were subjected to speedup comparison. Speedup is a metric for relative performance improvement when executing a task. The execution time of a program can be seen as a latency quantity type of the speedup comparison because it is in seconds per program .
For latency values, speedup is defined by the following formula:
ETPE(%) = (Latency([T.sub.old])/Latency([T.sub.new]) - 1)*100 (3)
where ETPE(%) is the resultant execution time performance efficiency in percent; Latency([T.sub.old]) is the old mean execution time (i.e., without the improvement) and Latency([T.sub.new]) is the new mean execution time (i.e., with the improvement) 10].
Based from the obtained mean values of the AES-Rijndael and the AES-2SBox during encryption with 171.75ms and 139.65ms respectively, the execution time performance efficiency showed that the AES-2SBox is 22.986% more efficient than the AES-Rijndael version. Similarly, the obtained mean values of the AES-Rijndael and the AES-2SBox during decryption with 195.00ms and 92.95ms respectively, the execution time performance efficiency also revealed that the AES2SBox is 109.79% more efficient that the AESRijndael version.
7.3 Test for Avalanche Effect
The avalanche effect refers to a desirable property of cryptographic algorithms. The avalanche effect is evident if, when an input is changed slightly (for example, flipping a single bit) the output changes significantly with at least half the output bits will be flip.
In , the calculation of avalanche effect can be derived by using equation:
Avalanche Effect (%) = (NC/TN) * 100 (4)
where NC is the number of changed bits in ciphertext and TN is the total number of bits in the ciphertext.
Here, we start to calculate the avalanche effect of the AES-2Sbox. The tests were performed by changing the plaintext bit from "11" to "10" and from "FF" to "F0". The results obtained were 24.219% with 31 bits that were changed and 19.531% with a flip of 25 bits respectively. The following table shows the result of the test for avalanche effect for AES-2Sbox.
This paper presents a proposed modified AES algorithm using multiple Sboxes. The first Sbox (AES-Rijndael) stand as is in the cipher structure. Meanwhile, a new Sbox was constructed using XOR operation and affine transformation. This Sbox, which we call AES-2SBoxXOR, replaced the MixColumns step in the AES cipher rounds.
Two set of tests were conducted to the original version and the modified version of the AES algorithm. In the speed performance test, where the two versions, through an implementation model, encrypted and decrypted a file with a size of 59Kb for 20 trials. The t-Test statistics set at 0.05 level of significance revealed that in both encryption and decryption, there were significant differences in the speed performance between the two versions with the obtained P-values 5.33936E07 and 3.94442E-25 respectively. For the execution time performance efficiency, it was found out that both in the encryption and decryption processes, the AES-2SBox was more efficient by 22.986% and 109.79% respectively that the original AES algorithm.
We also performed the test using avalanche effect on the proposed AES-2SBox algorithm. The results of the simulation revealed that the avalanche effect is slightly lower than the minimum expected output of at least 50% bit flip when 1 bit input is altered. The obtained changes in the bit sequence were computed at 24.219% and 19.531% for two set of plaintext.
From these results, we observed that the speed performance significantly increased in the modified AES algorithm using multiple S-Boxes, while the security side has slightly weakened.
 Townsend Security: Introduction to AES Encryption: White Paper, TownSendSecurity.com, https://townsendsecurity.com/sites/default/files/AES_Introduction.pdf (2010).
 Abd-ElGhafar, I., Rohiem, A., Diaa, A. and Mohammed, F.: Generation of AES Key Dependent SBoxes using RC4 Algorithm. In: 13 International Conference on Aerospace Sciences & Aviation Technology (ASAT- 13). May 26 - 28, 2009, Military Technical College, Kobry Elkobbah, Cairo, Egypt, (2009).
 Juremi, J., Mahmod, R., Sulaiman, S. and Ramli, J.: Enhancing Advanced Encryption Standard S-Box Generation Based on Round Key, In: International Journal of Cyber-Security and Digital Forensics (IJCSDF) 1(3): The Society of Digital Information and Wireless Communications (SDIWC) 2012 (ISSN: 2305-0012), pp. 183-189 (2012).
 Manasa, S., Mullaimalar, P., Gnanaprakash Singh, G. B. and Manivannan, S. S.: Reducing the Key Generation Time Using Enhanced AES-128 Algorithm to Secure the Data over Wireless Networks. In: International Journal of Applied Engineering Research, ISSN 0973-4562, Vol. 8, No. 19, pp. 2453-2456 (2013).
 Pachori, V., Ansari, G., and Chaudhary, N.: Improved Performance of Advance Encryption Standard using Parallel Computing. In: International Journal of Engineering Research and Applications. Vol. 2, Issue 1, Jan-Feb 2012, pp. 967-971 (2012).
 Federal Information Processing Standards Publication 197, Announcing the Advanced Encryption Standard, http://csrc.nist.gov/publications/fips/fips197/ fips197.pdf
 Man Young Rhee, Internet Security: Cryptographic Principles, Algorithms and Protocols. John Wiley & Sons Ltd: England, p.114 (2003).
 Wenceslao, F., Gerardo, B., and Tanguilig, B.: Modified AES Algorithm Using Multiple S-Boxes. In: Proceedings of the Second International Conference on Electrical, Electronics, Computer Engineering and their Applications (EECEA2015), Manila, Philippines, pp. 71-78 (2015).
 Sears, I.: Rijndael AES. http://www.unc.edu/~marzuola/Math547_S13/Math547 _S13_Projects/I_Sears_Section003_AdvancedEncryptionStandard.pdf
 WikiPedia.Com: SpeedUp. http://en.wikipedia.org/w/index.php?title=Speedup&oldid=648990695
 Martin, M.: Performance and Benchmarking. Retrieved on February 21, 2015, Retrieved from: http://www.cis.upenn.edu/~milom/cis501Fall12/lectures/04_performance .pdf
 WikiPedia.Com: Avalanche Effect. http://en.wikipedia.org/wiki/Avalanche _effect, 2014.
 Patidar, G, Agrawal, N. and Tarmakar, S.: A block based Encryption Model to improve Avalanche Effect for Data Security. In: International Journal of Scientific and Research Publications, Volume 3, Issue 1, January (2013).
Felicisimo V. Wenceslao, Jr.
Institute of Information and Computer Studies, Northern Iloilo Polytechnic State College, Estancia, Iloilo, Philippines
Felicisimo V. Wenceslao, Jr. finished his Bachelor of Science in Computer Science at the Computer College of the Visayas, Iloilo City, Philippines (1993) and his Master of Science in Information Technology at Hannam University, Republic of Korea (2005). He is currently pursuing his Doctor in Information Technology at the Technological Institute of the Philippines, Quezon City, Philippines. He is currently the Director of the Institute of Information and Computer Studies at Northern Iloilo Polytechnic State College, Estancia, Iloilo, Philippines. His research interests are in network security, mobile development, data mining and e-learning.
Table 1. AES-[2SboxXOR.sub.7F] 0 1 2 3 4 0 13 0C 2D 32 6F 1 E2 FD DC C3 9E 2 F0 EF CE D1 8C 3 01 1E 3F 20 7D 4 D4 CB EA F5 A8 5 25 3A 1B 04 59 6 37 28 09 16 4B 7 C6 D9 F8 E7 BA 8 9C 83 A2 BD E0 9 6D 72 53 4C 11 A 7F 60 41 5E 03 B 8E 91 B0 AF F2 C 5B 44 65 7A 27 D AA B5 94 8B D6 E B8 A7 86 99 C4 F 49 56 77 68 35 5 6 7 8 9 0 70 51 4E EB F4 1 81 A0 BE 1A 05 2 93 B2 AD 08 17 3 62 43 5C F9 E6 4 B7 96 89 2C 33 5 46 67 78 DD C2 6 54 75 6A CF D0 7 A5 84 9B 3E 21 8 FF DE C1 64 7B 9 0E 2F 30 95 8A A 1C 3D 22 87 98 B ED CC D3 76 69 C 38 19 06 A3 BC D C9 E8 F7 52 4D E DB FA E5 40 5F F 2A 0B 14 B1 AE A B C D E F 0 D5 CA 97 88 A9 B6 1 24 3B 66 79 58 47 2 36 29 74 6B 4A 55 3 C7 D8 85 9A BB A4 4 12 0D 50 4F 6E 71 5 E3 FC A1 BE 9F 80 6 F1 EE B3 AC 8D 92 7 00 1F 42 5D 7C 63 8 5A 45 18 07 26 39 9 AB B4 E9 F6 D7 C8 A B9 A6 FB E4 C5 DA B 48 57 0A 15 34 2B C 9D 82 DF C0 E1 FE D 6C 73 2E 31 10 0F E 7E 61 3C 23 02 1D F 8F 90 CD D2 F3 EC Table 2. Inverse AES-[2SboxXOR.sub.7F] 0 1 2 3 4 0 7A 30 EE A4 53 1 DE 94 4A 00 F7 2 33 79 A7 ED 1A 3 97 DD 03 49 BE 4 E8 A2 7C 36 C1 5 4C 06 D8 92 65 6 A1 EB 35 7F 88 7 05 4F 91 DB 2C 8 5F 15 CB 81 76 9 FB B1 6F 25 D2 A 16 5C 82 C8 3F B B2 F8 26 6C 9B C CD 87 59 13 E4 D 69 23 FD B7 40 E 84 CE 10 5A AD F 20 6A B4 FE 09 5 6 7 8 9 0 19 C7 8D 28 62 1 BD 63 29 8C C6 2 50 8E C4 61 2B 3 F4 2A 60 C5 8F 4 8B 55 1F BA F0 5 2F F1 BB 1E 54 6 C2 1C 56 F3 B9 7 66 B8 F2 57 1D 8 3C E2 A8 0D 47 9 98 46 0C A9 E3 A 75 AB E1 44 0E B D1 0F 45 E0 AA C AE 70 3A 9F D5 D 0A D4 9E 3B 71 E E7 39 73 D6 9C F 43 9D D7 72 38 A B C D E F 0 BC F6 01 4B 95 DF 1 18 52 A5 EF 31 7B 2 F5 BF 48 02 DC 96 3 51 1B EC A6 78 32 4 2E 64 93 D9 07 4D 5 8A C0 37 7D A3 E9 6 67 2D DA 90 4E 04 7 C3 89 7E 34 EA A0 8 99 D3 24 6E B0 FA 9 3D 77 80 CA 14 5E A D0 9A 6D 27 F9 B3 B 74 3E C9 83 5D 17 C 0B 41 B6 FC 22 68 D AF E5 12 58 86 CC E 42 08 FF B5 6B 21 F E6 AC 5B 11 CF 85 Table 3. Speed Performance Between the AES-Rijndael and AES-2SBox During Encryption t-Test: Two-Sample Assuming Unequal Variances AES-Rijndael AES-2SBox Mean 171.75 139.65 Variance 359.1447368 190.7657895 Observations 20 20 Hypothesized 0 Mean Difference Df 35 t Stat 6.121727783 P(T<=t) one-tail 2.66968E-07 t Critical one-tail 1.689572458 P(T<=t) two-tail 5.33936E-07 t Critical two-tail 2.030107928 Table 4. Speed Performance Between the AES-Rijndael and AES-2SBox During Encryption t-Test: Two-Sample Assuming Unequal Variances AES-Rijndael AES-2SBox Mean 195 92.95 Variance 168.6315789 167.5236842 Observations 20 20 Hypothesized 0 Mean Difference Df 38 t Stat 24.89190009 P(T<=t) one-tail 1.97221E-25 t Critical one-tail 1.68595446 P(T<=t) two-tail 3.94442E-25 t Critical two-tail 2.024394164 Table 5. Execution Time Performance Efficiency Algorithm Mean ETPE% Latency([T.sub.old]) Latency([T.sub.new]) (AES-Rijndael) (AES-2SBox) Encryption 171.75 139.65 22.986% Decryption 195.00 92.95 109.79% Table 6. Avalanche Effect of the AES-2SBox Plaintext Ciphertext Avalanche Effect 111111111111111 FE88B9C6D624C 24.219% (31) 111111111111111 203A4345796445 11 3.20E+06 111111111111111 40A3CFC6D624 111111111111111 C2D972345796B 10 15320A4 00112233445566 9E53C352DBDF 19.531% (25) 778899AABBCC 8A4F1034CABE DDEEFF AC05B1FB 00112233445566 37F1B112DBDF8 778899AABBCC A221034848DAC DDEEF0 05B1FB
|Printer friendly Cite/link Email Feedback|
|Title Annotation:||advanced encryption standard|
|Author:||Wenceslao, Felicisimo V., Jr.|
|Publication:||International Journal of New Computer Architectures and Their Applications|
|Date:||Jan 1, 2015|
|Previous Article:||Design of a reversible fused 32-point Radix-2 floating point FFT unit using 3:2 compressor.|
|Next Article:||A new approach for solving equations systems inspired from brainstorming.|