Development of Cryptography Studies

Development of Cryptography Studies 0.1 Abstract This report is an overview of some structures that have heavily influence the course and study of Cryptography the last decades. Initially, we will analyse the structure of some important ciphers such as DES, 3DES and AES by underlying some dark and complicated points and emphasizing the critical  functions called S-boxes. We will then expand of some basic attributes of these block ciphers, for example the running time of them and their hardware and software performance. Finally, we will focus on a highly important aspect of these cryptosystems, security by exploring some of the most significant attacks that have been discovered against them. The paper is concluded with a presentation of the most important results of our investigation. 1 Introduction Cryptography has a very rich history, rooted back in the ancient years. Even Greeks of classical times have demonstrated understanding of ciphers, with the example of Herodotus to be the most well known, who tattooed a message to his slave head on a slaves shaved head and hide it under his regrown hair. Before the modern era, cryptography had an absolute target the achievement of confidentiality of a message. The most crucial years for cryptography were undoubtedly the last century. The decisive step was an investigation of Claude Shannon, the father of information security. In his seminar at 1949, Shannon analysed and illustrated block ciphers and suggest that, if they are combined with some operations that can provide the whole cipher with permutation and substitution, they should be a reasonable option. A block cipher, is an encryption scheme that belongs in the branch of Cryptography that is called symmetric-key Cryptography. This name is justified by the fact that the parties th at are involved in the communication through the cipher use the same secret key. Later designed as iterated product ciphers, block ciphers are deterministic algorithms that operate on fixed length groups of bits, called blocks. The major attribute for a block cipher is that the length of the input, called plaintext, and the length of the output, called ciphertext, is always the same. They take as an input a key of k-bits length and the this key is expanded to many different keys following a sequence of operations, the so called round keys. Typically, a block cipher is built by iteration, using a function called round function. In every round, the round function takes as an input the corresponding message and the round key and produces a new outcome which is oriented to be used in the next round. The final round will produce the ciphertext. Block ciphers have been widely used and dramatically influence the new era of humanity, and more importantly for commercial reasons in industry a nd banking. There is a remarkable variety of examples from block ciphers, although for the rest of this paper we will focus on the most famous examples that dominated the whole area of symmetric-key Cryptography in the new era. These are called DES, 3DES, AES. Blowfish has also attracted the attention since there isnt still any known vulnerability but it will remain outside of the scope of this report. 2 Analysis and Description 2.1 Data Encryption Standard (DES) Nowadays, DES is considered to be insecure, but it had a huge impact in the development of the symmetric-key cryptography for many decades after its invention. It has been designed back in 1976, when the government of the United States realized the overwhelming necessity of an algorithm that could effectively protect government data and safely used for buying products from the international markets. The most interesting difference of DES with its predecessor, Lucifer, which has been designed by Horst Fiestel, is that the key length and the block length has been reduced significantly. Nevertheless, the key length, especially, was from the time that DES was published, under heavy criticism and was actually badly broken in 1997 with the so-called exhaustive search attack. That means that a machine was able to search all the possible keys and find the correct one. DES has a very rich history of attacks and we will examine some of these attacks in more detail later in this paper. The core idea behind DES is the so-called Feistel Network, where a block cipher can built up with the use of some arbitrary functions f0,f1,fd : {0,1}n → {0,1}n. There is a wide variety of block ciphers that have a similar construction, although AES has a completely different construction. The critical point in these kinds of constructions is the structure of these functions, which can vary significantly. Abstractly speaking, the main target is to construct an invertible function F : {0,1}2n → {0,1}2n in order to able to decrypt the ciphertext. DES is basically a 16-round Fiestel network. More specifically, the input is exactly 64 bits, so R0 and L0 are 32 bits each. Obviously, from the diagram above, in every the half of the bits remains unchanged. The other half comes with a sequence of operations. Initially, as specified by the protocol, a permutation of the whole input takes place, followed by a 16-round Fiestel Network. Each function f0,f1,f16 : {0,1}16 → {0 ,1}16 that is used at each round is computed by using the corresponding subkey, fi(x) = F(ki,x) ,in order to make the decryption circuit feasible and manageable from a hardware perspective of view. This subkey is produced by the main key, in the following way: 56 bits are selected from the 64 bits that contains the key, the 56 bits are divided into two 28 bit halves and each half is treated afterwards separately. In every round, both halves are rotated form the left to the right by one or two bits and then 48 bits are selected, 24 from the left and 24 from the right to build the corresponding subkey. After these 16 rounds of the Fiestel network, there is one more permutation before the final output is computed. The following image describes the construction of the fi function. Initially, the input of 32-bits replicates 48-bits with some simple calculations and then the result is XOR with the 48-bits subkey. The 48-bits are splitted to 8 blocks of 6 bits and passed to the S-boxes. This is the most critical point of a block cipher and bad implementation of S-boxes can easily compromise security. A S-box is a function {0,1}6 → {0,1}4 and acts like a look-up table. The selection of these tables is of vital importance and has been a controversial matter for many years. It has been proved that linear S-boxes is definitely not an option. Even a partly linear S-box can run under some kind of attacks. After the implementation of all the S-boxes, a last permutation that maps the 32-bits around, takes place. The decryption circuit follows exactly the inverse procedure. Obviously, the encryption and decryption circuit are almost identical as the only actual difference is the order that the f1,f2,,fd functions are applied. This fact made DES very attractive to hardware developers because they had to implement just one algorithm for both procedures. 2.2 Triple Data Encryption Standard (3DES) As already mentioned, DES has been proved to be vulnerable under certain types of attacks so significant has been made in order to improve the security of DES. For this reason, DES has been replaced by 3DES, which was published in 1998 To begin with, let E : KXM → M be a block cipher and lets define the function 3E : K3 → M as 3E((k1,k2,k3),m) = E(k1,D(k2,E(k3,m))), where D denotes the decryption algorithm. Actually, there are three encryption steps. The main question that arises here is why the middle one is a decryption algorithm and not and encryption algorithm. The answer is simple; this would have lead to the implementation of a single DES, beacause the first and the second DES operations cancel out. will cancel the other. Obviously, the key-size, as it was intended, has been increased to 168-bits, as each of the keys is 56-bits. There are three options for keys; in the first key options all the keys are independent, in the second option k1andk2 are independent and k3 = k1 and in the third all three key are identical, k1 = k2 = k3. The third option is no longer recommended by the NIST( National Institute of Standards and Technology), the first key option is the strongest with a total number of 168 key bits as mentioned above, and the second option is stronger that simply implementing DES twice. 2.3 Why not double DES? 3DES is considered to be a secure block cipher. Nevertheless, a normal question is why 2DES in not an option, as it may not seem easy to beak by brute force with a key-length space 2112. A 2DES can be defined in the following way; 2E(k1,k2),m) = E(k1,E(k2,m)) with a key length 112 bits. This construction turns out to be completely insecure and the reason for this is the meet-in-the-middle attack. Basically, if an attacker has at his disposal an actual message and the corresponding ciphertext, which will be of the same length, he will try to find a pair of key (k1,k2) that E(k1,E(k2,M)) = C. If we apply at both parts of this equation the decryption algorithm, then we get the get E(k2,M) = D(k1,C). So, the attacker will try to figure out which is the appropriate pair of key in order to map the message M and ciphertext C at the same point this also justifies the name of the attack meet-in-themiddle. The attack is structured in two steps: Firstly, the attacker has to build up a table wi th all the 2112 keys and the corresponding encryptions and then sort this list, and secondly, for all possible key that belongs to {0,1}56, he calculates D(k,C) and he looks for a match at the previous table. Whenever he finds the first match, his goal has been achieved. The running time of this attack is 256log(256) + 256log(256) < 263, time that is much smaller than the time that is necessary for brute force attack. 2.4 Advanced Encryption Standard(AES) It is widely acceptable AES has been adopted by the U.S. government and nowadays is used worldwide. As DES was proved insecure and 3DES quite slow, the demand for a more effective encryption scheme grew rapidly and at 1997 NIST requested a new proposal. After some investigation, NIST chose Rijndael as AES at 2000, a cipher that was designed in Belgium. AES, unlikely to its predecessor, its not a Feistel Network. In contrast, it is called a substitution-permutation network because both actions of permutation and substitution take place. AES has a fixed block size of 128-bits, although the key length can vary, 128,192 or 256 bits. Additionally, in every round of AES all bits change while in every round of DES half of the bits remain unchanged. Generally, a substitution permutation networks initial input is operated with an XOR with the corresponding round subkey, then goes through a substitution layer where there are some blocks, configured depending on what the substitution table says and finally a permutation layer follows where all bits are permuted. This procedure is repeated many times until the final outcome is produced. All steps of a substitution permutation network must be reversible in order to be able to decrypt. Specifically for AES, the 128-bits, which are equal to 16-bytes, are handled with the help of a 4X4 matrix with ten repeated rounds to follow. Each element of this matrix is one byte. Each byte comes under the XOR operation with the corresponding round subkey, and then a function is applied in every round that consists of three steps: (1) The Sub-Bytes step, according to which all bytes are replaced with other coming from a look-up table, named Rijndael S-box. This S-box is associated with the Galois Field(28) which is considered to have goo properties. This is a critical operation for the overall structure, as it provides AES with non-linearity. (2) The Shift-Rows step, where the last three rows of the current state are moved some certain positions to the left while the first row remains stable and (3) the Mix-Columns step, where all the bytes of each column of the current state are combined under a linear transformation. The last two steps provide AES with diffusion, a vital property for a secure cipher according to which if we change one bit of the plaintext then almost half of the bits o f the ciphertext will change. It is also considerable that the step Mix-Columns is omitted at the last round of AES. Each subkey is produced by the main key with some kind of expansion similar to the DES. The key expansion is introduced with a number of operations named rotate, Rcon, and S-box and then follows an inner loop in key schedule before the final subkey is produced. 3 Comparison and Attacks 3.1 Running time A real concern about which algorithm is appropriate, especially for commercial use, is the effectiveness and its running time. In general, the larger the block size is, the faster is the algorithm, obviously because larger amount of data is encrypted in one round of operations. Similarly, the smaller the key size is, the faster is the encryption algorithm, because the less key bits are involved in the operations and thus the complexity of them is reduced. A series of experiments have taken place to verify which of the famous encryption algorithms, AES,DES,3DES. Most of these experiments implement these encryption algorithms in Java, although there are some others that used C, most of them at a machine of Pentium 2 or Pentium 4. At most of these experiments, the fastest of these algorithms has been proved to be DES, followed by AES and finally from the 3DES, as it is three times slower than DES. It obviously doesnt make sense to examine the running time of these block ciphers in compl ete isolation with the security that they provide although it is definitely a factor that must be taken into consideration. 3.2 Software and Hardware Implementation Another important aspect that must be examined is the performance of these block ciphers in combination with the available hardware. Again, a lot of study has been carried out and provide us with some clear evidence. In compact architecture, 3DES, DES and AES have displayed very similar performance. In contrast, in high-speed architecture, AES is considered to be almost 4-times than the 3DES and DES. This is happening due to a variety of reasons, amongst them there is no hardware support for DES in modern CPUs, when from the other side there is for AES in increasingly many CPUs, including most targeting servers; hence hardware DES is oà ¯Ã‚ ¬Ã¢â‚¬Å¾oaded to a distant IC, when AES is often in-core. Additionally, DES is often used in CBC mode which makes parallelization inevitable and processed in advance during encryption when AES is mainly used in CTR mode where the possibility of parallelization is available. Finally, DES, and its expansion 3DES is much slower in software than AES, obviously because it was designed back at 1976 before the 8086 processor was designed and uses a lot of bit operations that are not implemented suà ¯Ã‚ ¬Ã†â€™ciently in a processor with a word oriented instruction set. 3.3 Attacks on DES and 3DES As already mentioned earlier at this paper, 2DES has been collapsed from the meet-in-the-middle-attack. Simultaneously, DES, despite its contribution to the overall development of cryptography, has also been defeated by a quite popular attack named exhaustive search. Exhaustive search means that the attacker will search the whole key space and he will find the appropriate, which is unique, in suà ¯Ã‚ ¬Ã†â€™cient amount of time. There are some cases, even in the real world where the attacker can obtain some pairs (mi,ci), where m denotes a message and c the corresponding ciphertext. Under this small requirement, DES was badly broken. To be specific, a company named RSA, back at 1997 announced a problem with the name DES challenge. The company announced six ciphertexts and in parallel announced the first three actual messages and asked for the scientific community to search for the key and use it to obtain the other messages. The same year of the request the challenge had been solved. To go further, the rapid hardware  development was able to create a machine that find the key and solve the problem, equivalently crack DES, within less than one day at the year 1999 with exhaustive search, leading to the assumption that 56-bits length block ciphers should not be used any more. As DES is one of the most famous and controversial block ciphers, it is not entirely surprising that there is a variety of attacks developed against DES, some of them even faster than exhaustive search. Back at 1998, Kocher and Jun demonstrated a very innovative idea by making a side channel attack, introducing a new era for cryptography. Side channels attacks extract information from the physical implementation of the cipher. This type of attack was specifically against smart cards, and is based in power measurement. They actually measured precisely the running time of the smart cards and analysed the diagrams that they obtain from this measurement. In this way, they were able to learn wa s much time was consumed by in each operation from the smart card and find exactly the key. Nowadays, even smart cards are equipped with mechanisms that dont reveal any information of the power consumption there is an attack called differential power analysis, which can steal the secret key after running a lot of time the smart card. It should me mentioned that these attacks are quite general and not for smart cards. In addition, there is another type of a quite highly surprising class of attacks called fault attacks. In this occasion, the attacker can cause a malfunction to a mechanism, lets say to a smart card, for example by warming it up. If he manage to cause and recognise an error at the last round of DES he will be able to discover the secret key. The last attack that we would like to point out is the so called linear cryptanalysis. This is a generic attack and was introduced by Matsui at 1993 and is one of the most realistic, sophisticated and quick attacks on the DES. His a ttacks, and generally in linear cryptanalysis, one tries to find probalistic linear relations between the plaintext, the ciphertext and the secret key. He starts by examining linear relations at the S-boxes of one round and if he succeeds, he will use the to find out linear relations in one-round and then finally them iteratively to find multi-round relations. These relations from round to round are not independent. By combining all these linear relations, the attacker should be able to retrive the secret key. Matsui attack used 244 known plaintexts to find 13 bits of the secret key with a high probability . A similar method was applied to find another 13 bits and then for the remaining 30-bits he applied exhaustive search, he applied exhaustive search, reducing significantly the time that the initial exhaustive search demands. Today, linear cryptanalysis is considered to be, with some improvements, one of the most powerful attacks on DES. Although DES is considered to be faultless and no specific technical vulnerabilities has been found, a high level of linearity at the fifth box of DES has created the possibility for someone to generate this type of attack. Most of the previously referred attacks can also be implemented against 3DES, as the two block ciphers are obviously, highly related. To begin with, an exhaustive search is not suà ¯Ã‚ ¬Ã†â€™cient any more as the key space, if we use three totally independent keys, is huge, especially if we take into consideration the computational power that a strong mahine can demonstrate nowadays. The meet-in-the middle-attack can be applied in a very similar mode, as the attacker can still create a sorted table with the first implementation of DES between one element of the table and the implementation of twice the DES at the opposite direction. The time needed for this attack is 2112, which is considered to be a high level of security, as nowadays a satisfactory level of security against a certain attack is approximately 290, although is still faster in comparison with exhaustive search. Lately, a new attack against block ciphers has been displayed, mainly intended against 3DES and Blowfish and exploits well known kind of vulnerabilities like collision and birthday attacks. Since this is currently under examination and was published only this year, we are not going to expand more. Overall, till today there is not a known and widely acceptable attack that cracks 3DES in a reasonable amount of time. 3.4 Attacks on AES Rijndael has outplayed all other candidates suggested for the AES and so has been analysed quite a bit the last decade. A lot of attacks have been introduced although none of them has hurt AESs security significantly. To begin with, there is a lot of analysis around the meet-in-the-middle attack and some possible improvements of it over the last five years. Gilbert and Minier have proved a very interesting distinguishing property for the first four rounds of AES with the following proposition; lets consider a set of 256 plaintexts where the entry a11 takes all byte values between 0 and 255 exactly once over a given set of plaintexts and all other entries are equal to a constant. If we encrypt this set with three rounds of AES then the function that maps a11 to C11 is determind by 9 fixed 1-byte parameters. C11 denotes the byte values at row i, column j. This proposition was used by them to implement the same idea of the meet-in-the-middle attack. Some further investigation have shown that the number of the parameters, and specifically for 13 or 14 bytes, and this is able to be reduced so the number of the required plaintexts will be minimized. Another famous class of attacks are called cache attacks. Cache is a small part of high speed memory and it aims to keep the CPU as much busy as possible. The catch parameters influence the running time of an algorithm. Specifically, when an element of a data array is called, then we have two possible outcomes. Id the element lies n the cache memory,then the access is instant. In a different situation, the element must be accessed from the main memory. This operation will be executed in significantly different running times and reveal valuable information. We can separate this class of attacks into three families; cold start misses, which arise for the first reference of the data, capacity misses which the magnitude of the element is bigger than the size o the cache and the conflict misses, which may happen in the case of accessing recently accessed data. 4 Conclusion In this paper we examined the structure of popular block ciphers that heavily influenced the development of Cryptography, like DES,3DES and AES and we have compared them in means of running time and software and hardware implementation. We have also considered some basic attacks that have been applied on these cryptosystems. We come to the conclusion that AES is the most safe and practical block ciphers, and this is justified by the fact that is has been chosen for encryption at a series of important applications nowadays. IS it estimated that AES will fully replace 3DES until 2030. There is not any doubt that AES is the most practical and convenient cipher from a hardware and running time perspective. Nevertheless, further investigation must definitely be carried out to ensure the the safety of AES, especially under the increasing enhancement of the technological means, is guaranteed. Finally, the attack Sweet32 is a newly invented attack and must carefully be examined, mainly becau se it is really compromise 3DES security, countermeasures must be taken DES will fully replaced by AES. 5 References [1] Dan Boneh and Victor Shoup, A Graduate Course of Cryptography, August 2015. [2] Diaa Salama Abd Elminaam,Hatem Mohamed Abdual Kader and Mohiy Mohamed Hadhoud, Evaluating The Performance of Symmetric Encryption Algorithms, Higher Technological Institute 10th of Ramadan City, Egypt, (Received Feb. 16, 2009; revised and accepted May 12, 2009) [3] Aamer Nadeem, Dr M. Younus Javed, A Performance Comparison of Data Encryption Algorithms, Department of Computer Engineering, College of Electrical and Mechanical Engineering, National University of Sciences and Technology, Rawalpindi, Pakistan. [4] Akashi Satoh and Sumio Morioka, Hardware-Focused Performance Comparison for the Standard Block Ciphers AES, Camellia, and Triple-DES, Tokyo Research Laboratory IBM Japan Ltd. [5] Huseyin Demirci, Ihsan TaskÄ ±n, Mustafa Coban, and Adnan Baysal, Improved Meet-in-the-Middle Attacks on AES, 2011. [6] Daniel J. Bernstein, Cache-timing attacks on AES, Department of Mathematics, Statistics, and Computer Science (M/C 249) The University of Illinois at Chicago, 2005. [7] Eran Tromer, Dag Arne Osvik and Adi Shamir, Computer Science and Artificial Intelligence Laboratory, Massachusetts Institute of Technology, 32 Vassar Street, G682, Cambridge, MA 02139, USA and Laboratory for Cryptologic Algorithms, Station 14,  ´Ecole Polytechnique F ´ed ´erale de Lausanne, 1015 Lausanne, Switzerland Received 20 July 2007 and revised 25 June 2009. [8] Anne Canteaut, C ´edric Lauradoux and Andr ´e Seznec, Understanding cache attacks, April 2006. [9] Johannes Blomer and Volker Krummel, Analysis of countermeasures against access driven cache attacks on AES, Faculty of Computer Science, Electrical Engineering and Mathematics University of Paderborn, Germany 2009. [10] Hamdan.O.Alanazi, B.B.Zaidan, A.A.Zaidan, Hamid A.Jalab, M.Shabbir and Y. Al-Nabhani, New Comparative Study Between DES, 3DES and AES within Nine Factors, Journal of Computing, Volume 2, Issue 3, March 2010. [11] Henri Gi lbert and Thomas Peyrin, Super-Sbox Cryptanalysis:Improved Attacks for AES-like Permutations, Orange Labs, France [12] Elisabeth Oswald, Stefan Mangard, Norbert Pramstaller and Vincent Rijmen, Institute for Applied Information Processing and Communciations (IAIK), Austria, 2005. [13] Kai Schramm, Gregor Leander, Patrick Felke and Christof Paar, A Collision-Attack on AES Combining Side Channel and Differential Attack, Horst Gortz Institute for IT Security, Germany 2005. [14] Alex Biryukov and Dmitry Khovratovich, Related-Key Cryptanalysis of the Full AES-192 and AES-256, University of Luxembourg 2011. [15] A Chosen-Plaintext Linear Attack on DES, Lars R. Knudsen and John Erik Mathiassen Department of Informatics, University of Bergen, N5020 Bergen, Norway, 2000. [16] Jawahar Thakur and Nagesh Kumar, DES, AES and Blowfish: Symmetric Key Cryptography, Algorithms Simulation Based Performance Analysis, International Journal of Emerging Technology and Advanced Engineering Website: www.ije tae.com (ISSN 2250-2459, Volume 1, Issue 2, December 2011) [17] Stefan Tillich and Christoph Herbst, Attacking State-of-the-Art Software Countermeasures A Case Study for AES, Institute for Applied Information Processing and Communications, Inffeldgasse 16a, A-8010 Graz, Austria