Advances in Cryptology - Report Example

?Table of Contents Table of Contents Introduction 2 MD5 Algorithm 2 Data filling 2 Add length 2 Initialing of variables 3 SHA Algorithm 3 Principle of operation of the two algorithms 3 Collision Attacks 4 Cipher text Attack 4 Chosen Plaintext Attack 5 Known Plaintext Attack 5 Replay Attack 5 Thwarting Collisions 7 Streaming data 7 Message whitening and self interleaving 8 Security analysis 9 Summary and conclusion 10 References 12 Introduction In the recent years, information communication technologies have been on a steady growth thanks to the innovations in technology coupled with increasing needs of users to communicate. There is a growing demand for the implementation of cryptographic algorithms and encryption that are robust and reliable. Each and every communication protocol that exists usually has a given number of layers that define the security of the protocol. In order for the cryptography to provided, there is usually a need for different types of encryption algorithms which help by supporting the communication protocols as well as ensuring security in the network (Duams, 2005). Hash functions are arguably the most important of all the encryption algorithms since they help in the prevention of external attacks. They are usually used in most of the applications that require very high security. They are also widely used in the specification of most communication protocols like IPsec and WAP. They typically serve message authentication codes and also help in provision of digital signatures or in some cases, they generate random numbers. MD5 and SHA-1 are the most common of the hash functions (Biham and Chen, 2004). MD5 Algorithm Data filling The MD5 algorithm usually adds the supplement immediately after inputting of the data thereby making the whole length of the mod 512=448. This can be represented as K*512+448 BITS WHERE K IS an integer. Add length Usually, a sixty four bit data b is used to dente the original length of the data while an independent b is used to two thirty two bit blocks. In the event that b>264, we will have to extend the length to multiples of five hundred and twelve. This implies that the length will become times of sixteen double bytes. MD5 algorithm usually saves the data in an array. The syntax of such an array is given by M [0…N-1] Where N is in time of sixteen. Initialing of variables If four thirty two but variable named A, B, C, and D were to be defined, they would be initialized as A=0*01234567, B=0/889abcdef, C=0*fedcba98 and D=0*76543210. In this case, the data will be output in the same sequence that is, A, B, C, D. SHA-1 Algorithm This is also an important hash algorithm which is actually based on the MD4 principle. The algorithm actually produces 160 bit output which means that SHA-1 usually needs a set of five thirty two bit registers. However, the similarity between SHA-1 and MD5 is that both of them use a similar approach to message digesting. The SHA-1 algorithm has a total of four distinct rounds of iterative. Each of these rounds has its own twenty steps of operations. If you were to initialize five variables namely A, B, C, D, and you would have:- A= 0x67452301 B=0xefcdab89 C=0x98badcfe D=0x10325476 E=0xc3d2e1f0 SHA-1 was traditionally thought to be the most secure hash algorithm and it is probably one of the main reasons why it is the current FIPS secure hash standard (Merkle,1990). Principle of operation of the two algorithms Generally the design of the hash algorithms is usually based on the Merkle-Damgard iterative structure. This is since the structure allows for arbitrary length in the messages that are sent. The hash algorithms typically work by dividing the input into different blocks of predetermined lengths. Each of the blocks that are formed is then affixed to the previous state using a form of a compression function in order to compute the updated state. This entire process is usually referred as chaining of a variable. After the processing of the message is completed, the output is given as the last step of the process. The state vectors for SHA-1 is usually in one hundred and sixty bits while the state vectors of the MD5 is usually in one hundred and twenty eight bits (Niels et al.,2000) Ideally, compression functions are comprised of two main components namely, the message expansion and the round operations. SHA-1 compression mechanism is based on a five hundred and twelve bit message blocks. It utilizes a one hundred and sixty state variable that is typically represented by 5 thirty two bit words (represented as A, B, C, D, and E). The five hundred and twelve bits blocks are usually expanded to two thousand five hundred bits that are typically represented by eighty words each carrying thirty two bits. The words are typically used for the update of the internal state of the round update function. MD5 also follows a similar approach but unlike the SHA-1 algorithm, it uses the 128 bit state variable. MD5 also implements a sixty four round system unlike SHA-1 which uses eighty (Lenstra et al., 2005). Collision Attacks Cipher text Attack This is an attack that occurs when a malicious person gets access to cipher texts. It is thought to be the easiest of all attacks since all it takes is for one to listen to a communication that has not been secured. However, it can also be said to be the most difficult to execute since the adversary has little information. Chosen Plaintext Attack This refers to any type of cryptanalysis that presumes that the enemy has the knowhow of choosing random plaintexts to be encrypted thereby coming up with cipher texts. It might appear as a very unrealistic model but it is important to note that modern day cryptography is done by software and is applicable in a wide range of scenarios. Known Plaintext Attack In this kind of attack, the enemy not only has samples of the plaintext but also the cipher text. He can therefore use the information he has to leak secret information. This was the main attack witnessed at Bietchley Park during the second world war. Replay Attack In this scenario, a valid transmission is replicated for malicious intentions. It can either happen on the originators side or on the enemy’s side who might intercept the data and resend it. This is a very difficult to detect attack and is therefore quite risky. The successful implantation of the hash algorithms is usually based more on trying to locate collisions than inversion of the hash functions. There have been attempts over the years to introduce message medication techniques as described by Halevi (2005).in addition to this, Wang et al (2005) has also described the collisions in MD4, MD5, and RIPEMD HAVAL-128. As they describe, the complexity if MD5 is in the approximate range of 22 to 230. Research reveals that finding of collisions in SHA-1 is of the complexity 269. There have been concerns by some experts that the collisions that have been established by most of the research efforts is usually just about short binary strings and they therefore lack enough structure to be termed as meaningful inferences. This notwithstanding, it is possible to get meaningful collisions in the hash algorithms. A case in point would be the collisions found in two different X500 certificates as described by Lenstra et al (2005) based on MD5 (Florent, 1998). Both the SHA-1 as well as MD-5 usually breaks down the message that is to be hashed into five hundred and twelve bit blocks. Reference to a single block in such a subset is usually denoted by m. m is often subdivided into thirty two bit message words that is given by m0,m1…..,m15. The expanded messages on the other hand are denoted by w. SHA-1 usually subdivides its w into 80 thirty two bit message words. This can be denoted as w0,…,w79. On the other hand, MD5 expands its w into sixty four thirty two bit message words (Lenstra et al., 2005). The general idea in finding collision attacks is establishing the message difference between two different expanded messages such that the probability that C(m) will be the same as C(m1) is greater than what is to be expected. The possibility of this depends largely on the arrangement of the round computations in such a manner that the different state vectors do not deviate in a significant way and they can easily be “altered” for purposes of correction with a still high enough probability. The main tool that is used is local collision tool. It is typically a collection of a few rounds that a given number of small differences in the messages that have been expanded will be engulfed with a reasonable level of probability. As a result of the message expansion, there is usually a high rate of different words of m and m1. For this reason, it is important to sting the local collisions together. Disturbance vectors are the vectors that define how the local collisions will be joined. The whole set of the differences in the vector states is what is referred to as a differential path. The success in the entire probability largely hinges on the concurrent satisfaction of a group of conditions for the different local collisions. The structure of different attacks is comprised of an analysis of the different local collisions, a brute force search on the input messages, a search for a vector that has low hamming weight interference, as well as a collection of various techniques that are used in the boosting of the success probability. This usually includes the specification of the real conditions for the differential path and the message modification in order to ensure that some of the conditions are kept at a constant and that there will be two blocks that are used in the construction of collisions from the nearby ones. This describes how the SHA-1 but the MD5 has a slightly different approach (Matusiewicz and Pieprzyk, 2004). Thwarting Collisions Once one understands the collisions in terms of how they occur and how the different hash functions deal with them, it is possible to come up with some strategies that can help in the attempt of preventing the success of the algorithms. One of the easiest of methods is the prevention of nay of the good differential paths. A good differential path can be defined in this context as a path that will ultimately leads to near collisions with the probability of not greater than 2-n/2. It would also be a good idea as a precautionary measure to ensure that you have restrained the ability of modification of messages. This will result in the reduction of success to a great probability. Another approach would be the consideration of situations that Merkle-Demgard iterative structures cannot be fully utilized. An example is the case where single message bits have the potential of affecting multiple blocks (Lenstra et al., 2005). Streaming data Many applications are usually designed architecturally in a manner that would allow them to incrementally interpret a very large message whenever the message becomes available to be digested. For instance, in SHA-1 applications, it is possible to make SHA-1 update function calls over and over again as the different strips of the message continue streaming in. this is typically achieved when the message preprocessing can be done in a streaming way. For instance, the message can be streamed when it is divided into different blocks and each of it is then expanded. Z would be referred to as a local expansion If Z could be denoted by z(m0*,m1*,….mk*). In this case, we can say that if z is a local expansion, then the state of preprocessing of the function can actually be stored in the message digest scenario which means that the derived update function would also be in a position to call the SHA-1 update but only as a subroutine (Lenstra et al., 2005). Message whitening and self interleaving This is the process by which the message is altered by the insertion of fixed characters; the insertions are usually done at regular intervals. The main objective of message whitening is to reduce the flexibility in the process of seeking out good message differentials. The fixed characters that used in the process are usually taken to be words that are full of all zero bits hence the name whitening. In the event of a hash function that has a 512 bit block size; chunks of less than five hundred and twelve bits can be expanded sequentially until they reach the five hundred and twelve bit size. For instance, each of (16-t) 32 bit words m=(m0, m1, … ,m16-t,)could be denoted as m=(m0, m1, … ,m16-t, 0,…0). In this case, the last t words are actually fixed by the introduction of the zeros. Each of the execution of the function will therefore process (16-t) message words instead of the 16 words (Chabaud,1998). The implication of this is that it is therefore easier to calculate the slowdown in performance. One major advantage of this approach is that it is relatively easy to implement. Another important advantage is the fact the processing of less bits of the message ultimately allows for the message to be better mixed within the calculation. Another approach to this would be the election of a given set of words to whiten in order to further increase the difficulty of any possible attacks. It has been observed by some researchers that whitening the middle two words of the SHA-1 actually reduces the effects of message modification to a significant degree (Chabaud,1998).. In the message self interleaving technique, the main idea is the duplication of the word so that all of the bits will eventually appear twice. Just like in the message whitening method, the message interleaving technique results in fewer message bits to be delivered per each of the message blocks and this ultimately causes a better mixing. The two methods above have clear and distinct differences even though the differences are minor. The most important and obvious difference of the two is that each of the methods have their own choice of the bits to whiten. It is also possible to select the frequency of the interleaving could also be selected on character basis. Even though linear functions are always preferred, it is also possible to consider the usage of non-linear ones. This will call for the correct usage of an arbitrary local expansion. Irrespective of specific function, the different techniques typically attempt to improve the security by means of increasing of the structure if the message blocks. The idea is to make it less simple to find good differentials for the attacker. The other important objective of the different techniques is to disrupt any possible message modification techniques (Lenstra et al., 2005). Security analysis In SHA-1, the message interleaving technique works by taking of two hundred and fifty six bits instead of the two five hundred and twelve. These are expanded to the 80 words that are usually required by SHA-1 round operations. Ideally, the amount of data that is needed by the whitening technique relies on its calibration, that is, how many words or bits are whitened. The implication of this is that less data bits are usually processed for each of the execution of the function that is doing the compression. The overall effect of this is that the derived function will have greater chance of merging the data bits in a better and more complete manner (Chabaud and Joux, 1998). Summary and conclusion One of the best ways to understand how MD5 and SHA-1 differ in how whitening and interleaving are done is to examine the code of expanded messages. In SHA-1, each of the blocks (16x32 bits) is usually expanded to become 80x32 bits. On the flip side, the MD5 simply repeats the original message three times. It is therefore possible to compare and contrast the expanded messages of SHA-1 and MD5 as linear codes of the dimension 512. Even though they are different in their own different ways, one of the similarities is that the code is usually produced by the five hundred and twelve basis vectors E(1,0,…,0),E(0,1,…,0),…, E(1,0,…,0) (Naito and Kunihiro, 2005). In both cases, the whitening and interleaving approaches work by preventing the form of five hundred and twelve input messages. Another way of looking at the differences between the two hash algorithms is to look at the set of solutions given in a linearized hash function. This method was suggested by Oswald and Rijmen (2005). Apart from prevention of good differentials, the interleaving and whitening methods also work to make the processes of modification of messages less optimal. This ultimately increases the complexity of the collision attacks (NIST, 1993). SHA-1 was developed basing on the MD4 and MD5 architecture. For this reason, MD5 and SHA-1 are somewhat similar in most of their mode of operation. In addition to this, the most recent attacks on SHA-1 and MD5 also reveal some good degree of similarity. This notwithstanding, there are still some important differences in the two hash algorithms. The biggest difference that can be identified between MD5 and SHA-1 is in the message expansion. In MD5 for instance, the message block usually expands the 16x32bits into 64x32 bits (Chabaud,1998). In addition to this, the expansion function implemented in MD5 (denoted by E) works by repeating and reordering of the sixteen message words three times. Ideally, this can be said to be the main reason why MD5 is considered by many people to be much simpler as compared to SHA-1. It is also the major reason as to why MD5 offers better mixing than SHA-1.Another important difference between the two can be seen in the differential paths that were used in the most recent attacks. Apart from the basic fact that both algorithms are front loading, MD5 used a totally different path. It was created by first finding out what was the nearest collision that involves MSB in the 2nd half. This was then derived into a more complex collision path during the first half. The use of interleaving with MD5 makes reduces the chances of message modification to almost zero. Ideally, there are almost two hundred conditions that are to be associated with the path in the initial sixteen steps and all of these conditions have to be set true via message modification if one wants to reduce the complexity of the attack to approximately 230+. The implication of this is that message interleaving actually greatly increases the complexity of any existing attacks. This same explanation can hold water in the case of message whitening except for the fact that a greater parameter would be needed in order to totally rule out the possibility of having low hamming weight. References Biham, E. and Chen, R.2004. Near Collisions of SHA-0. In Advances in Cryptology – Crypto’04 , Springer-Verlag, August 2004. Chabaud and A. Joux. 1998. Di.erential Collisions in SHA-0. In Advances in Cryptology Crypto’98, Springer-Verlag, August 1998 Daum, Lucks. 2005. The Story of Alice and her Boss In Rump session of Eurocrypt’05. [online] available at http://www.cits.rub.de/MD5Collisions/. [accessed 29 April 2012] Florent Chabaud and Antoine Joux. 1998. Differential Collisions in SHA-0. CRYPTO 19(23)56–71 Halevi, Krawczyk. 2005. Strengthening Digital Signatures via Randomized Hashing,Internet-Draft. [Online] available at http://www.ietf.org/internet- drafts/draft-irtfcfrg-rhash-00.txt.[accessed on 28 April 2012] Lenstra, A and X. Wang and B. de Weger.2005. Colliding X.509 Certificates, IACR Eprint archive, Report 2005/067. [online] available at http://eprint.iacr.org/ [accessed 29 April 2012] Matusiewicz, K. and Pieprzyk, J. 2004. Finding Good Differential Patterns for Attacks on SHA-1. IACR Eprint archive. Merkle, R.1990. One Way hash Functions and DES, In Advances in Cryptology Crypto’89, Springer-Verlag, 1990. Niels Ferguson, Bruce Schneier, and Tadayoshi Kohno. 2000. Cryptography Engineering,London: John Wiley & Sons NIST.1993 Secure hash standard. Federal Information Processing Standard, FIPS 180, May 1993 Oswald E. and Rijmen. 2005. Update on SHA-1. RSA-CT’05, February 2005 Y. Naito, Sasaki and Kunihiro, K., Ohta.2005 Improved Collision Attack on MD4 IACR Eprint archive, Report 2005/151. Wang, X. Lai, F. Guo, H. Chen, X. Yu. 2005. Cryptanalysis for Hash Functions MD4 and RIPEMD. Advances in Cryptology – Eurocrypt’05, Springer-Verlag Read More