International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: [email protected] Volume 3, Issue 3, March 2014 ISSN 2319 - 4847

A Proposed Framework for Enhancing Security of SHA-2

1

Rahul Saxena, 2Dr.C.S. Lamba

1

Research Schollor, NIMS University 2 Research Guide, NIMS University

Abstract
In the world of information system, maintaining integrity of communication or message is more important for some businesses and organizations compared to confidentiality. This requirement is fulfilled by hashing the message before its transmitted over unreliable medium. Hashing ensures that even a minor change in the message is reflected largely in its corresponding hash. The length of a hash must remain constant for any message size. This leads to possibility of collision attacks, brute force and rainbow table attacks. One commonly used algorithm resistant to these attacks is SHA-512. But some attacks on SHA-512 like rainbow table and brute force are theoretically possible. To prevent these attacks some modifications in the structure of algorithm are proposed. These modifications include the usage of salt, switch function and making a tree structure for the algorithm.

Keywords: Hash, SHA, Enhanced SHA, Salt, Tree structure

1. INTRODUCTION
Communication systems have one component vital to them which is information. In todays communication centric world the value of information is much more than the assets it commands. Any communication system be it organization network or personal network cant survive if reliable transmission cant be provided. Thus integrity of data has gained importance over confidentiality as organizations are focusing on relaying correct and complete data rather than keeping it a secret. This demand for ensuring integrity is met by hashing of data. Hashing is a one way procedure in which a variable sized data input is transformed into a fixed size hash value also called message digest. This hash value is dependent upon entirely the message and even a slight change in message content must reflect by the corresponding drastic change in its hash value. Hash functions are essentially one way functions and original data cant be retrieved from the hash value. Thus original data is accompanied by its hash value which acts as a verification message. The receiver of the message computes hash value from the original message it has received and then matches computed hash with received hash, for correct match- integrity of message is said to be intact, else the message is said to be modified either by accident or deliberate change. MD5 and SHA have been most popularly used hash functions. MD5 is not currently used as it has been cracked [1], SHA-2 is the current standard. The work on improvement of SHA came as a series of different versions of SHA developed by National Security Agency (NSA). To counter the calls of backdoor being present in these algorithms NIST organized a competition for development of SHA-3 which called from public to develop a robust hashing technique. NIST has selected Keccaks algorithm (to be renamed as SHA-3) to become FIPS standard in 2014[2]. SHA-3 has not yet been standardized and NIST doesnt created it as a replacement of SHA -2 thereby providing us with the scope of further using SHA-2. SHA-2 requires some improvements because of perceived theoretical attacks on it. The improvements made by [3] are for speeding up the hashing process. The work in [4] also provides us improvement in speed and security of SFHA-256. The paper is organized as follows: Section 2 contains attacks on hash functions, Section 3 contains brief introduction to popular hashing algorithm SHA, and Section 4 contains our proposed technique followed by final conclusion and future scope in Section 5.

2. ATTACKS ON HASH FUNCTION

As with other information security procedures hash functions also have to deal with dedicated attacks on breaking them. Some ways are to divide up the cracking process to different computer or exploit CPU architecture to take advantage of multiple cores on one processor or multiple processors on a single machine. Below mentioned attacks are most prevalent on hashing functions [5]. A. Brute Force Attack Brute force attack is the most fundamental attack against every security procedure. Brute force is often used against hash value as hash function generates a one way hash value. In brute force attack, attacker tries every combination to generate a given hash value. However, such method is very time consuming as the search space may be very huge thus requiring immense computing power on behalf of attacker. B. Rainbow Table Attack Another common attack is by using rainbow table to to identify the original message given a hash value. Unlike brute force that attempts to match every single character, rainbow table attack uses tables which offer time-memory-trade-off to lookup for the particular message. Table contains large number of entries usually commonly used passwords and their

Volume 3, Issue 3, March 2014

Page 98

International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: [email protected] Volume 3, Issue 3, March 2014 ISSN 2319 - 4847

corresponding hash value. The table content does not depend on the hash value to be inverted. It is created once and then repeatedly used for the lookups unmodified. As the number of table entries increase the time required to perform lookups also increases. This process of cracking is based on heuristics as the attack probability will directly depend upon number of entries in the rainbow table as well as quality of entries. C. Preimage Attack This attack is used to find a message that has a given hash value i.e. given hash value y, find message x such that h(x) = y. Second preimage attack requires finding message x given combination of x and y such that h(x) = h (x ) = y while x x . An ideal hash function producing n-bit hash has a time complexity of 2n for the preimage attack. But this complexity is not achieved as researchers have shown theoretical attacks on them [7][8][9] which reduce this time. The attacks are said to be theoretical because no practical attack has yet been demonstrated on whole steps of the hashing functions. These attacks are specific to hash functions and are dependent on inherent weaknesses in the structure of these functions. D. Collision Attack Collision attack requires an attacker to find two input messages producing the same hash. Its different from preimage as unlike in preimage attacks where hash values are given, this attack do not contain any given hash value. The attacker need to determine the two messages x and x which must hash to same value. A variant of collision attack called chosenprefix collision attack requires finding two message fragments (m1 and m2) such that given prefix p1 appended to fragment m1 hashes to same value as another given prefix p2 appended to fragment m2.

3. SECURED HASH ALGORITHM

Secure Hash Algorithm (SHA) was introduced by NIST as federal information processing standard (FIPS) [6] used for providing hashing. It is a series of hashing algorithms. SHA was first introduced in 1993. With the subsequent years, new versions were introduced to counter various attacks possible on SHA namely Brute force attack, Rainbow table attack, Preimage attack and Collision attack. These attacks occur with more probability on smaller hash value compared to larger ones, so the subsequent versions of algorithm need to produce larger hash values to counter the possibility of different types of attacks due to increased computation power available with attackers. SHA-1 and SHA-2 are based on same structure called Merkle-Damgard construction. SHA3 differs from previous two versions as it is based on sponge construction. Table 1 provides comparison of SHA versions with respect to when they were published and number of hash bits they produce. TABLE 1 :COMPARISON OF DIFFERENT SHA VERSIONS

Algorithm Message digest

SHA-1 160 1993

Year

SHA-2 224, 256, 384, 512 2001

SHA-3 224, 256, 384, 512 2012

4. PROPOSED SCHEME
In the proposed scheme we have retained the sound base structure i.e. rounds, which are resistant to attacks on hashing functions. The detailed study of structure was made from [10] and hence for modifications the base diagrams are derived from the same source. The modifications were made on three fronts: A. Use of salt Salt is pseudo-random sequence generated for padding in the same way as zeroes are used for traditional algorithms. In all hashing systems a receiver cant distinguish between same message sent by sender and the attacker, as he can generate the same hash sent by actual sender. Attacker can do so because hash functions provide integrity of message and not authentication of sender. But if we provide a simple mechanism which can combine integrity with authentication inside the hashed value then the technique will provide a good level of security without requiring separate authentication measures. Salt in place of zero provides this authentication of sender because pseudo-random sequence used for salt is known only to communicating entities. Attacker doesnt know this sequence so he will not be able to send the message with same hash as done by authenticated sender. Figure 1 provides the modified structure of padding using salt instead of zeroes. In this diagram we are padding original message with salt which is variable. Number of salt bits depends upon original message so as to make its total length a multiple of 1024 bits.

Figure 1: SHA-512 Padding

Volume 3, Issue 3, March 2014

Page 99

International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: [email protected] Volume 3, Issue 3, March 2014 ISSN 2319 - 4847

B. Permutation Function It has been argued that insufficient change in bits in subsequent rounds may expose some weaknesses as attacker can guess partially the structure of bits after each round. To counter this we propose a Permutation function which permutes 8 registers (64 bit each) after 20 rounds in the total 80 rounds of algorithm. The 20 rounds were chosen as a trade-off between time complexity incurred after applying PBox in between rounds and security provided as a result of more number of P-boxes. Figure 2 shows the internal structure of the modified SHA-512 after the addition of P-boxes. C. Tree Structure The original structure of cascade used in SHA512 at single level is modified by using multilevel tree structure. Number of compression functions is same at first level as in previous algorithm but at subsequent levels these are half than that at previous level. Input from registers formed at one level are further inputted to compression function at next level thus halving the further bits. So a tree structure is formed that decreases down the levels. Figure 3 shows the overall cascading of bits in a tree structure.

Figure 2: Modified compression function

Figure 3: Modified tree based structure of SHA-512

Volume 3, Issue 3, March 2014

Page 100

International Journal of Application or Innovation in Engineering & Management (IJAIEM)

Web Site: www.ijaiem.org Email: [email protected] Volume 3, Issue 3, March 2014 5. CONCLUSION AND FUTURE SCOPE
NIST has recommended the usage of SHA-3 which was lately finalized to be a new standard for hashing. SHA-3 is not meant to replace SHA-2 as no practical attack has yet been successful in breaking SHA-2 for its complete 80 rounds. Yet, organizations are wary of using SHA-2 in its current form as theoretical attacks are said to be possible by the attacker provided he has enough resources which are not difficult to gather for a dedicated attacker or a group of attackers coordinating their work. The proposed technique utilizes the sound base of SHA-512, while introducing few changes in the overall structure of algorithm which theoretically can reduce the probability of SHA-512 getting compromised. The generated hashed value as a result of this technique can provide authentication of sender, enabling only genuine person to send the message and communicate by matching hash with receiver, without using any computationally expensive dedicated cryptographic procedures. The extent to which the attacks on SHA-512 will be prevented can be verified as part of the future work which will provide us with a clearer vision of the further changes to be made to increase the life of SHA-512 while gradually adopting the SHA-3 standard as recommended by NIST. Further work can be done on utilizing the parallelism provided by a tree structured approach to improve the speed of hashing which is a limitation in all Merkle-Damgard constructions.

ISSN 2319 - 4847

REFERENCES
[1] H. Dobbertin, The Status of MD5 After a Recent Attack, CryptoBytes,Vol.2(2), 1996. [2] Assessed from: http://csrc.nist.gov/groups/ST/hash/sha-3/index.html on 10 Feb 2014 [3] Assessed from: http://software.intel.com/enus/articles/improving-the-performance-of-thesecure-hash-algorithm-1 on 10 Feb 2014 [4] S. Agarwal, A. Rungta, R. Padmavathy, M. Shankar and N. Rajan, An Improved Fast and Secure Hash Algorithm, Journal of Information Processing Systems, Vol. 8(1), pp. 119-132, 2012. [5] Assessed from: http://2012.sharcs.org/slides/stevens.pdf on 10 Feb 2014 [6] Assessed from: http://csrc.nist.gov/publications/fips /fips180-2/fips180-2.pdf on 10 Feb 2014 [7] S. Knellwolf and D. Khovratovich, New Preimage Attacks Against Reduced SHA-1, International Association for Cryptologic Research, Crypto-2012, Vol. 7417, pp.367383,2012. [8] K. Aoki and Y. Sasaki, Meet-in-the-Middle Preimage Attacks Against Reduced SHA-0 and SHA-1, Advances in Cryptology- CRYPTO 2009, Vol. 5677, pp. 70-89, 2009 [9] C. D. Canniere and C. Rechberger, Preimages for Reduced SHA-0 and SHA-1, Advances in Cryptology- CRYPTO 2008, Vol. 5157, pp. 179202, 2008. [10] W. Stallings, Cryptography and Network Security: Principles and Practices: Upper Saddle River, NJ: Prentice-Hall, 2006.

Volume 3, Issue 3, March 2014

Page 101