Variable Length Hash Algorithm Using RC6

Hash_RC6 – Variable Length Hash Algorithm using RC6

• Kirti Aggarwal
• Dr. Harsh K. Verma

ABSTRACT

In this paper, we present a hash algorithm using RC6 that can generate hash value of variable length. Hash algorithms play major part in cryptographic security as these algorithms are used to check the integrity of the received message. It is possible to generate hash algorithm using symmetric block cipher. The main idea behind this is that if the symmetric block algorithm is secure then the generated hash function will also be secure [1]. As RC6 is secure against various linear and differential attacks algorithm presented here will also be secure against these attack. The algorithm presented here can have variable number of rounds to generate hash value. It can also have variable block size.

Keywords: Cryptography, Symmetric Encryption, Asymmetric Encryption, Data Integrity, Authentication, Confidentiality, Non-Repudiation, Access Control, Hash, RC6

INTRODUCTION

Cryptography is the ability of keeping message secure form others while sending information between participants (Confidentiality). There are many cryptographic algorithms categorized as symmetric encryption algorithm and asymmetric encryption algorithm. Symmetric encryption algorithm is the one that use same shared key from encryption and decryption, while asymmetric algorithm is the one that use different keys from encryption and decryption.

With the Confidentiality cryptography also provide other services known as data integrity, authentication, non-repudiation, access control etc. Data Integrity is assuring that data received is same as sent by the sender. Authentication is the ability to assure that communicating party is who that it claims to be. Non-Repudiation is the prevention against the denial by entities involved in the communication. Access Control is the prevention against the unauthorized use of resources [2].

Figure 1. Fundamental of Cryptography

Hash Function

A cryptographic hash function is any algorithm or subroutine that maps large data sets of variable length to smaller data sets of a fixed length. The values returned by a hash function are called hash values, hash codes, hash sums, checksums or simply hashes.

Where h has fixed length. An (accidental or intentional) change to the data will (with very high probability) change the hash value.

For a hash function to be considered secure, it must be computationally infeasible to find has a predefined hash value and similarly it must be computationally infeasible to find two messages having same hash value.

RC6

RC6 is a symmetric block cipher based on RC5 and designed by Rivest, Sydney, and Yin for RSA security [3]. Like RC5, RC6 is a parameterized algorithm where the block size, the key size, and the number of rounds are variable; again, the upper limit on the key size is 2040 bits [4]. RC6 was designed to meet the requirements of the Advanced Encryption Standard (AES)competition. RC6 proper has ablock sizeof 128 bits and supportskey sizesof 128, 192 and 256 bits, but, like RC5. RC6 can be viewed as interweaving two parallel RC5 encryption processes. It uses an extra multiplication operation not present in RC5 in order to make the rotation dependent on every bit in a word.

SHA-256

SHA-256 operates on eight 32-bit words. The message to be hashed is first

1. padded with its length in such a way that the result is a multiple of 512 bits long, and then
2. parsed into 512-bit message blocks M⁽¹⁾;M⁽²⁾; : : :;M^(N).

The message blocks are processed one at a time: Beginning with a fixed initial hash value H⁽⁰⁾, sequentially compute

Where C is the SHA-256 compression function and + means word-wise mod 264 addition. H^(N) is the hash of M [5].

SHA-512

SHA-512 is a variant of SHA-256 which operates on eight 64-bit words and block size of 1024 bits. It uses different shift amounts and additive constants, but its structure is otherwise virtually identical, differing only in the number of rounds, which are 80 for SHA-512[15].

HASH FUNCTION

A cryptographic hash function is a mathematical transformation that takes a message of arbitrary length and computes a fixed length value also known as hash value, message digest, hash code, hash sum, checksum, etc.

Where H is Hash Function, M is variable length message; H is fixed size hash value. Creating hash function is accomplished by iteration. Instead of using a hash function with variable-size input, a function with fixed size input is created and is used a necessary number of times. This fixed size input function is known as compression function. It compresses an n-bit string to create a m-bit string where n is normally greater than m. This scheme is referred to as an iterated cryptographic hash function [6]. These compression function fall into two categories: a function specially designed for the hash function or a symmetric block cipher [2].

Figure 2. Iterated Cryptographic hash Function

Characteristics of one way Hash Function:

1. Given M, it is easy to compute h.
2. Given h, it is hard to compute M such that.
3. Given M, it is hard to find another message, M’, such that

The whole point of one way hash function is to provide a finger print of M that is unique. In some application one wayness is insufficient; we need an additional requirement called collision-resistance (It is hard to find two random messages, M and M’, such that [1]).

Figure 3. Basic Hash Algorithm at sender and receiver

Hash Function takes message and an initial value as an input and produces the hash value. The hash value is appended to the message at a time when the message is assumed or known to be correct. The receiver authenticates the message by generating the hash value with the same procedure and compares it with the hash value send by the sender. If both the value matches then the received message is same as it is send by the sender otherwise message has been tampered with.

RC6

RC6 [7] is a fully parameterized family of encryption algorithms. A version of RC6 is more accurately specified as RC6-w r bwhere the word size is wbits, encryption consists of a nonnegative number of roundsr, andbdenotes the length of the encryption key in bytes. Since the AES submission is targeted atw= 32 andr= 20, we shall use RC6 as shorthand to refer to such versions. When any other value ofworris intended in the text, the parameter values will be specified as RC6-w r. Of particular relevance to the AES effort will be the versions of RC6 with 16-, 24-, and 32-byte keys [4].

Figure 4. RC6 Encryption

For all variants, RC6-w r boperates on units of fourw-bit words using the following six basic operations.

integer addition modulo

integer subtraction modulo

bitwise exclusive-or of w-bit words

integer multiplication modulo

Rotate to the left by the amount given by the least significant bits of

Rotate A to the right, similarly

parallel assignment

Key Expansion

Use two magic constants:-

Where:-

…….(base of natural logarithm)

……..()

is the odd integer nearest to .

INPUT

byte key that is preloaded into word array

denotes the no of rounds.

OUTPUT

w-bit round keys .

ALGORITHM

1. 
2. 
3. 
4. 
5. 
6. For do
7. 
8. 
9. 
10. 

Encryption

Four w-bit registers A, B, C, D contain the initial input plain-text as well as the output ciphertext at the end of encryption. The first byte of plaintext is placed in the least significant byte of A; the last byte of plaintext is placed into the most significant byte of D [6].

INPUT

Plaintext stored in four w-bit input registers

Number r of rounds w-bit round keys

OUTPUT

Ciphertext stored in

ALGORITHM

1. 
2. 
3. 
4. 
5. 
6. 
7. 
8. 
9. 
10. C = C + S[2r + 3]

Decryption

For decryption of cipher-text load these cipher text into registers A, B, C, D Algorithm uses integer subtraction modulo 2w and right rotation on registers for getting plain text.

INPUT

Ciphertext stored in four w-bit input registers

Number r of rounds

w-bit round keys

OUTPUT

Plaintext stored in

ALGORITHM

HASH FUNCTION USING RC6

RC6 is a uses 44 words of key material making it more complex to break. RC6 parameterized cipher; the block size can be grown in a straightforward manner to 256 bits and beyond.RC6 has maximum key size of 2040 bits, making the corresponding hash function very fast.20 rounds using RC6 will have all these features which make the hash more efficient and secure.

It is possible to use a symmetric block cipher algorithm as a hash function. If the block algorithm is secure, then the one-way hash function will also be secure. One approach is to encrypt the message with the algorithm in CBC mode, a fixed key and an initial vector (IV), the last cipher text block is the hash value. Another more better approach uses the message block as the key, the previous hash value as the output. Here we will use second approach.

Algorithm presented here has variable parameters i.e. different parameter value can be taken according to the need. Block size (b), Number of rounds (r), length of hash value (l) are the different variable parameters that are the inputs of the algorithm. The length of hash value (l) should be multiple of 256.

First of all padding is done. Message is padded with zeros in a way such that the padded message length is multiple of the block size (b).

Then initial vector is needed to generate the hash value. Initial Vector is a piece of data is needed to begin running an algorithm, and is not secret. There are two initial vectors in this algorithm which are used to generate initial hash value.

To generate the initial hash value combination of v (size of hash value divided by 256) 256 bits values calculated as follows:

After generating initial hash value from initial vectors the message (M) is divided into number of small chunks (n). The size of message chunks should be equal to block size b, after that RC6 key generation is applied on each message block to generate keys that will be used to encrypt the previous hash value to generate next hash value. Initial 256 bits v hash values are encrypted via RC6 using RC6 keys generated from first message block (M₁). This is then encrypted again from the keys generated from second message block (M2) and so on until all the message blocks (n) are used. At last all the v final hash values of length 256 bit each are concatenated to generate the final hash value of length l.

Number of rounds (r) is divided in to two parts, 3r/4 rounds are used to generate the RC6 keys from the message block and r/4 rounds are used to encrypt the previous hash value to generate next hash value. Figure 5 shows the procedure for hash value of size 512 bits.

Figure 5. Hash Value Generation using RC6

PSEUDO CODE

INPUT

Message M,

Number of rounds r,

Block size b,

Length of hash value l;

OUTPUT

Final hash value h;

ALGORITHM

1. 
2. 
3. Pad 0s (zeros) at the end of the message so the message length is multiple of b;
4. Divide message into chunks of size b;
5. 
6. 
7. 
8. Repeat step 7 to 21
9. Load
10. 
11. Repeat step 10 to 12
12. 
13. 
14. Repeat step 13 to 16
15. 
16. 
17. 
18. 
19. 
20. 
21. Repeat step 20
22. 
23. Repeat step 22 to 33
24. Load
25. 
26. 
27. Repeat step 26 to 30 for do
28. 
29. 
30. 
31. 
32. 
33. 
34. 
35. Load
36. Concatenate to get final hash value h

PERFORMANCE AND ANALYSIS

This algorithm was implemented using java in NetBeans IDE 7.0.1. Following results were obtained on Intel(R) Core(TM) i3 CPU M 370 @ 2.40 GHz 2.39 GHz 32 bit system with 4 GB of RAM running Windows 7 Ultimate.

Algorithm presented in this paper is compared with SHA-256 and SHA-512 respectively. Comparison between algorithm presented here and SHA are done on the basis of throughput of the algorithms and time to produce hash value for files of different sizes. To be more accurate the program is executed ten times for each input file and the average of those results are reported here.

Results in Figure 6 to Figure 9 and Table 1 for Hash using RC6 are obtained for r=64, b=512, l=256 and these results are compared with SHA-256 which has same value for these parameters.

Figure 6. Throughput of RC6_HASH and SHA-256.

Figure 7. Bar Graph of Hash value generation time of RC6_HASH and SHA-512

Figure 8. Line Graph of Hash generation time of HASH_RC6 (256) and SHA-256

Figure 9. Execution time saving caused by Hash_RC6

Table 1. Comparison of Hash_RC6 (256) & SHA-256 on the basis of Execution Time of different type of Files.

Figure 6 shows the throughput of RC6_HASH and SHA-256 the algorithms in KB/sec. Figure 7 shows the Bar Graph hash value generation time (in millisec) of both the algorithms for the file of different sizes (in KB).

Figure 8 shows the Line-Graph of execution time according to their file size for each file using algorithms Hash_RC6 (256) and SHA-256. Line graph is more convenient to show that Hash_RC6 (256) performs faster than SHA-256. This Graph also shows that for the file of small size both the algorithms performs approximately same i.e. there is not much of the difference but when the file size increases Hash_RC6 (256) performs much better than the SHA-256.

Bar chart in Figure 9 shows the execution time saving caused by Hash_RC6 in percentage in comparison with SHA-256 for different file sizes. It’s greater than 30% for almost all the file sizes and for some of the file sizes its approx 50% that is greater advancement. The average percent execution time saving by Hash_RC6 for hash value of 256 bits over SHA-256 is 40.26.

We compare the execution time of each algorithm on different file types like text file, audio file & video files, for this purpose we mainly used 10 files and recorded their hash value generation time in milliseconds for these algorithms. List of Input files and their size are given in Table 1.

Results in Figure 10 to Figure 13 and Table 2 for Hash using RC6 are obtained for r=80,b=1024,l=512 and these results are compared with SHA-512 which has same value for these parameters.

Figure 10. Throughput of RC6_HASH and SHA-512.

Figure 11. Bar Graph of Hash value generation time of RC6_HASH and SHA-512

Figure 12. Line Graph of Hash Generation Time of HASH_RC6 (512) and SHA-512

Figure 13. Execution Time saving caused by Hash_RC6

Table 2. Comparison of Hash_RC6 (512) & SHA-512 on the basis of Execution Time of different type of Files.

Figure 10 shows the throughput of RC6_HASH and SHA-512 the algorithms in KB/sec. Figure 11 shows the Bar Graph of hash value generation time (in millisec) of both the algorithms for the file of different sizes (in KB).

Figure 12 shows the Line-Graph of execution time according to their file size for each file using algorithms Hash_RC6 (512) and SHA-512. Line graph is more convenient to show that Hash_RC6 (512) performs faster than SHA-512. This Graph also shows that the difference is not so much for file of small size but when it comes to file of larger size Hash_RC6 (512) is much better than the SHA-512.

Bar chart in Figure 13 shows the execution time saving caused by Hash_RC6 (512) in percentage in comparison with SHA-512 for different file sizes. It’s greater than 15% for almost all the file sizes and for some of the file sizes its approx 35% that is greater advancement. The average percent execution time saving by Hash_RC6 for hash value of 512 bits over SHA-512 is 24.625.

We compare the execution time of each algorithm on different file types like text file, audio file & video files, for this purpose we mainly used 10 files and recorded their hash value generation time in milliseconds for these algorithms. List of Input files and their size are given in Table 2.

CONCLUSION

In this research paper a new algorithm for generating hash value is presented. This algorithm is generated on a symmetric block cipher known as RC6 and can generate hash value of different sizes. The algorithm can also operate on different block size and different number of rounds. The implementation of algorithm is done using JAVA in NetBeans IDE 7.0.1. on Intel(R) Core(TM) i3 CPU M 370 @ 2.40 GHz 2.39 GHz 32 bit system with 4 GB of RAM running Windows 7 Ultimate.

Hash value generated using algorithm presented here are secure against many attack because when a hash algorithm is generated using symmetric block cipher it inherit the properties of underlying cipher. The idea behind this is that if the symmetric block algorithm is secure then the generated hash function will also be secure [1].

Then the algorithm is compared with SHA-256 and SHA-512 for same parameter and on the same environment. The results of comparison conclude that the algorithm present here has better throughput