FORM-2
THE PATENT ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
PROVISIONAL SPECIFICATION
(See section 10 and Rule 13)
CRYPTOGRAPHY
TATA CONSULTANCY SERVICES LIMITED
an Indian Company
of Bombay House, 24, Sir Homi Modi Street, Mumbai-400 001,
Maharashtra, India
THE FOLLOWING SPECIFICATION DESCRIBES THE INVENTION

Field of the Invention:
This invention relates to the field of cryptography.
Background of the Invention:
In cryptography, a cryptographic hash function is a transformation that takes an input and returns a fixed-size string, which is called the hash value. Hash functions with this property are used for a variety of computational purposes, including cryptography. The hash value is a concise representation of the longer message or document from which it was computed. The message digest is a sort of "digital fingerprint" of the larger document. Cryptographic hash functions are used to do message integrity checks and digital signatures in various information security applications, such as authentication and message integrity.
A hash function takes a string (or 'message') of any length as input and produces a fixed length string as output, sometimes termed a message digest or a digital fingerprint. A hash value (also called a "digest" or a "checksum") is a kind of "signature" for a stream of data that represents the contents. One analogy that explains the role of the hash function would be the "tamper-evident" seals used on an application package.
When two messages have the same hash value, this is known as a collision. A good hashing functionality minimizes collisions for a given set of likely data inputs. There is a need for a means for designing and analyzing a hash function that could be used for digital signature technology.

In various standards and applications, MD (Message Digest) and SHA (Secure Hash Algorithm) versions have been consistently evolved, implemented and used.
The MDl, MD2, MD3, MD4, MD5 (Message-Digest) are a series of structured functions; widely used, cryptographic hash functions with a 128-bit hash value.
The SHA (Secure Hash Algorithm) versions (SHA-160, SHA- 224, SHA-256, SHA-384, SHA-512 bits) are five cryptographic hash functions designed by the National Security Agency (NSA) and published by the NIST as a U.S. Federal Information Processing Standard. Hash functions compute a fixed-length digital representation (known as a message digest) of an input data sequence (the message) of any length. They are called "secure" when (in the words of the standard), "it is computationally infeasible to:
1. find a message that corresponds to a given message digest, or
2. find two different messages that produce the same message digest. Any change to a message will, with a very high probability, result in a different message digest."
The recent advances in cryptanalysis of hash functions have been spectacular, and the collision attacks on MD5 and SHA-1 are of particular importance since these are so widely deployed.
MD5 collisions can be easily found. The analytical attack was reported to take one hour on an IBM p690 cluster. MD5 has been known to be weak for a long time but it is still used with no catastrophic consequences.


SHA-1 is also widely deployed but has collision-resistance problems. SHA-1 collisions are found if the number of rounds is reduced from 80 to about 50. In theory, collisions in SHA-1 can be found in 269 attempts or hash evaluations. But this is only for a reduced-round version, and even then it is too expensive. So far no one has found collisions for SHA-1 using all rounds.
SHA-1 is derived from SHA-0, and SHA-256 is derived from SHA-1. These functionalities depend on intuition-based design that failed twice for SHA-0 and SHA-1. Given the attacks on the collision resistance of SHA-1 and the close relationship between the designs of SHA-1 and SHA-256, there is not much confidence on the collision resistance of SHA-256. Evaluation of SHA-256 is also difficult because it not known which attacks it was designed to protect against, or the safety margins assumed.
Thus, there is doubt over the design philosophy of the MD/SHA-family. Since the current class of functions is flawed, one option to counter this threat is to upgrade to a stronger hash function. Alternatively message preprocessing is a method that can be used for the above purpose. This technique can be combined with MD5 or SHA-1 so that applications are no longer vulnerable to the known collision attacks. The pre-processing function resists collision attacks in Hash functions. In this method, the given message (input) is pre-processed before being hashed. The rationale behind pre-processing is that the given message is made more random before being passed into the hash function. This reduces the redundancy in the input data,

thus leading to a lower probability of finding a collision. This method is called Message Pre-processing.
A hash function is a one-way function that maps an arbitrary length message into a fixed length sequence of bits. There are two basic requirements for a secure hash function, namely, the collision resistance property that is, it should be hard to find two different messages with the same hash result and the pre-image resistance property, which means, given a hash value, it should be hard to find a message that would generate that hash value.
The definitions designated are:
The hash value of a message m as H(m).
Collision: find two distinct messages m, m' such that H(m) = H(m').
1st pre-image: Given a hash value HV, find m such that H(m) = HV. 2nd pre-image: Given a message m, find another message m’ such that H(m') = H(m).
In a hash function of length n:
A brute force attempt to find a collision should require at least 2n/2
hash operations.
Brute force attempts to find 1st and 2nd pre-images should require at
most 2n hash operations.
A cryptographic hash function is a function with certain additional security properties to make it suitable for information security applications such as

authentication and message integrity.
In 1990, Ronald Rivest proposed the MD4 Hash function (RFC 1320). Hans Dobertin published collision attacks on MD4 in 1996.
In 1991, Ronald Rivest improved MD4 and called it MD5 Hash function. The output of MD5 is 128 bits. Later, in the year of 2004, Xiaoyun Wang, Dengguo Feng, Xuejia Lai, and Hongbo Yu published collisions of full MD5.
The SHA (Secure Hash Algorithm) versions are five cryptographic hash functions designed by the National SecurityO Agency (NSA) and published by the NIST as a U.S. Federal Information Processing Standard. SHA consists of five functionalities: SHA-1, SHA-224, SHA-256, SHA-384 and SHA-512. In the year of 1992, NIST published SHS (Secure Hash Standard) called now SHA-0. Joux, Carribault, Lemuet, and Jalby published collisions for full SHA-0 in 2004. In February 2005, an attack by Xiaoyun Wang, Yiqun Lisa Yin, and Hongbo Yu was announced. The attacks can find collisions in the full version of SHA-1, requiring fewer than 269 operations.
The recent attacks on MD-5, SHA-0 and SHA-1 by Wang et al has given a huge impetus to research in designing practical cryptographic hash functions as well as cryptanalysis of existing functions. Hitachi Ltd. has patented special purpose hash functions using collision free and one-way properties. IBM has published SHA-IME (improved message expansion) to avoid


differential attacks in SHA. Microsoft R&D has performed cryptanalysis of hash functions using Boolean Satisfiability (SAT) solvers. Tata Consultancy Services (TCS) has a patent pending regarding a cryptographic research work, which introduces a message pre processing function (MP) that is bijective and is used to reduce hash collisions.
Prior Art:
European patent Number 886399 by Takaragi, Kazuo et al describes Hash value generating method and device, data encryption method and device, data decryption method and device.
United States Patent Number 7240210 granted to M. Kivanc Mihcak and R. Venkatesan describes Hash value computer of content of digital signals.
United States Patent Application Number 20060294386 by Yuval, Gideon A. and Venkatesan, Ramarathnam describes strengthening secure hash functions.
United States Patent Number 7124408 granted to Parthasarathy, Srivatsan et al discloses blinding by hash.
European Patent Number 0483424 granted to Scott, Jonathan Andrew discloses key hashing in data processors.
United States Patent Number 7151829 granted to Vincenzo Condorelli and Camil Fayad discloses a system and method for generating a message digest comprising: receiving a block of data and processing the block of data to
7

achieve a message digest, the processing of the block of data including evaluating the block of data at time (t) in terms of time (t-x), wherein x is greater than or equal to 2.
European Patent Number 0149067 granted to Carter, John L. and Wegman, Mark N discloses polynomial hash.
United States Patent Number 5892829 granted to Aiello, William A. and Venkatesan, Ramarathnam discloses method and apparatus for generating secure hash functions.
United States Patent Number 6125445 granted to David Arditti, Henri Gilbert, Jacques Stern and David Pointcheval discloses Public key identification process using two hash functions.
United States Patent Number 6226629 granted to Cossock, David describes method and apparatus determining and using hash functions and hash values.
United States Patent Number 6275919 granted to Peter Johnson describes memory storage and retrieval with multiple hashing functions.
United States Patent Application Number 20080046741 granted to Mironov, Ilya describes protecting signatures using collision-resistant hash functions.
United States Patent Number. 4588985 granted to Carter, John L. Wegman, Mark N. describes polynomial hash. The data element to be hashed is separated into individual sub-strings xl through xn of no more than log2(b)

bits in length, where b is an integer, and the hashing functionality is a polynomial of the form fy(x)=(yoX1+y1x2+ ... +yn-1xn) (mod b).
United States Patent Number 5892829 granted to William A. Aiello et. al. discloses a desgin of secure hash function based on stretch function and compression function. The stretch function is one-way. The compression function is a cryptographic primitive selected from a family of compression functions. A standard key scheduling functionality of the cryptographic compression function (such as DES) is replaced and an output of the stretch function is used as the key. The stretch function output randomizes the input string. Further the security constraints on the compression function are less stringent.
United States Patent Number 6021201 granted to Derek L. Davis et. al. discloses a cryptography unit having a cipher unit and a hash unit, both are coupled in parallel for simultaneous ciphering and hashing. The cipher unit implements a cipher functionality that operates on a data block having a first predetermined size M. The hash unit implements a hash functionality on a data block having a second predetermined size N. Buffers of a size Q, where Q is an integer multiple of M and N, are employed to receive the input data into the invention. A security unit ensures that the cipher unit and the hash unit operate on the same data block of size Q.
European Patent Number 1556781 granted to Plessier et. al. discloses an apparatus which is arranged to accept digital data as an input, and to process

said data according to one of either the Secure Hash Algorithm (SHA-1) or Message Digest (MD5) functionality to produce a fixed length output word.
United States Patent Number 6091821 granted to Mark Leonard Buer discloses a pipelined hardware implementation of hash functions.
United States Patent Number 6141421 granted to Hiroyuki Kurumatani et al discloses a method and apparatus for generating hash value. The method transforms input data to data having an arbitrary length so that the resultant data is difficult to be inversely transformed. The method generates a hash value of data generated from the input data and random number data, executes a one to one transformation to a part of the input data by using the hash value as a parameter and outputs the intermediate generation data as a part of masking data; and executes the one to one transformation to a part of the input data by using intermediate generation data obtained during the one to one transformation.
United States Patent Number 6052698 granted to Bennet et al discloses the reorganization of collisions in a hash bucket of a hash table to improve system performance.
United States Patent Application Number 20060294386 granted to Yual Gideon et al discloses a system to strengthen secure hash functions.
India Patent Application Number 1937/MUM/2007 by Natarajan Vijayarangan, discloses a message pre processing method is used to reduce hash collisions.

There is a need for a secure, more robust secure hash function with reduced rate of hash collisions.
Object of the Invention:
An object of this invention is to provide a system and method to prevent hash collisions.
Another object of this invention is to provide a system and method which provide a secure hash function.
Summary of the Invention:
The present invention envisages a system and method for designing a secure hash functionality SHA-3 using message pre processing (MP) methods, and to help reduce hash collisions.
In accordance with this invention, there is envisaged a system and method for designing and implementing a secure hash functionality SHA-3, which is different from the existing hash functionalities. This SHA-3 is a one-way hash function, which is a combination of message pre processing (bijective function) and cipher block chaining (CBC) mode. Cipher block chaining refers to a means for providing a symmetric function for carrying out encryption and decryption which operated on blocks of data having a fixed length; the CBC mode especially relates to a method wherein each block of plaintext is XORed with the previous ciphertext block before being

encrypted. This way, each ciphertext block is dependent on all plaintext blocks processed up to that point. Also, to make each message unique, an initialization vector (IV) must be used in the first block. The system and method includes two stages carried out by a padding means and a computation means respectively, performed in a sequential manner; a padding means is adapted to perform padding and a computation means is adapted to perform hash computation. The padding divides an incoming message into m blocks of a fixed length and adds an initialization vector (IV) to the message. The message pre processing involves performing bijective operations viz.: Shuffling, T-function and Linear Feedback Shift Register (LFSR). These operations are used in the hash computation, which is performed on each input block of a fixed length in Cipher Block Chaining (CBC) mode with iterative rounds. The final value generated by the proposed hashing is used to determine the message digest / hash value. The SHA-3 functionalities takes an input message of any size and returns a fixed size output (224 / 256 / 384 / 512-bits). The hash functionality provided by the system and method in accordance with this invention is an iterative, one-way hash function in which padding, message pre processing and hash computation are involved. The functionality comprises the following operations to perform: Padding, Message Pre processing (Shuffling, T-function, LFSR) in CBC mode with iterative rounds. The given message is passed into respective means performing the above operations, which produce a hash output. The three operations: Shuffling, T-function and LFSR are part of message pre processing.
In accordance with an embodiment of this invention, there is provided a padding means. Padding operation divides any message into m-blocks of a

fixed length (224 / 256 / 384 / 512-bits). If the message size is less than the length of message digest, the given message is added with an initialization vector (IV) having the same message digest length. Otherwise, there is no IV added to a given message. For instance, SHA-3 (224 bits) functionality is used to compute hash for a given message less than 224 bits. Then the given message is XORed with the initialization vector (IV) = 2223 = 1000...0 (1 followed by 223 zeros). Hence the given message becomes 224 bits, which will be passed into the CBC mode with iterative rounds (hash computation).
In accordance with another embodiment of this invention, there is provided a hash computation means. After padding, the hash computation process starts. It is based on CBC mode with iterative rounds. In the CBC mode, the input message is divided into w-blocks of fixed size (which depends upon the message digest length) and each block of input is XORed with the output of the previous message pre processing operation. This process / round takes place 6 times in the hash computation using CBC mode. In the first round of CBC mode, a constant value (whose bit length < message digest length) must be XORed to the first block of the input message and the outcome is passed into the MP operation, which is again XORed with the second block of the input message. This XORing process continues till the end of the last block and produces a message digest of fixed size that is the output of first round. From second round to sixth, the output of previous round is XORed with the same constant value, then the outcome is passed into the MP operation (that is known as first step) and the same process continues till the end of the last step. After completing six rounds, the CBC operation produces a hash output.


For instance, the given message is divided into a sequence of equal sized blocks and the total number of blocks is m. The size of each block is chosen to be 32 x n, where n (7 / 8 / 12 / 16) depends upon a message digest length (224 / 256 / 384 / 512 bits). There is no loss of generality to put a constant value = 0 in all rounds of CBC operation so that the first block of the input message is directly passed into the first round and the XORing process continues till the end of mth block. From second round to sixth, the output of previous round is passed into the MP operation and the same process goes up to s steps, where s denotes the number of blocks. After completion of six rounds, the hash output of fixed length size (32 x n) is obtained. The number of blocks for first round is not always the same as the number of blocks for second round onward.
In accordance with still another embodiment of this invention, there is provided a Message Pre processing means which further includes:
- Shuffling means;
- T-functioning means; and
- Linear Feedback Shift Registering means
The shuffling means is adapted to perform shuffling operation which divides the message into 32-bit words and shuffles them. It interleaves the bits in two halves of each word. The shuffling procedure used is an outer perfect shuffle, which means the outer (end) bits remain in the outer positions. If the 32 bit word is (where each element denotes a single bit) denoted by:

, then the outer perfect shuffle makes it as:

In a similar manner, the shuffling means performs the shuffling operation on each 32-bit word of the entire padded message. The shuffling operation is simple to keep the overall method fast and yet to have a statistical effect on the output. The Shuffling of bits helps to improve the diffusion property of the input. The inverse of the shuffle operation can easily be accomplished by performing the swaps in reverse order. Therefore, the shuffling operation is bijective.
The T-functioning means is adapted to perform a T-function which is a bijective mapping that updates every bit of the state in a way that can be described as yi = Xi+f(xo,...,Xi-1), or in simple words is an update function in which every bit of the state is updated by a linear combination of the same bit and a function of a subset of its less significant bits. If every single less significant bit is included in the update of every bit in the state, such a T-function is called triangular. All the boolean operations and most of the numeric operations in modern processors are T-functions, and all their compositions are also T-functions. The T-function helps to achieve the avalanche effect. The avalanche effect tries to mathematically abstract the much desirable property of highly nonlinearity between the input and output bits, and specifies that the hashes of messages from a close neighborhood are dispersed over the whole space. Because T-functions are bijective, there are no collisions, and hence no entropy loss regardless of the boolean functions and regardless of the selection of inputs. Therefore there is no entropy loss. After shuffling, the T-function takes the input from the output of shuffling and brings to perform the avalanche effect on the input. The T function used


by us is (2x2+x) mod 232, where x is a 32-bit word. This is an invertible mapping, which contain all the 2n possible states on a single cycle for any word size n (where n = 32).
The Linear Feedback Shift Registering (LFSR) means is adapted to perform Linear Feedback Shift Register function. Primitive polynomials over GF(2n) are useful in the design of LFSRs for generating sequences for maximum period. More number of taps in primitive polynomials that are random have
^_
been used. The primitive polynomial used is

This is an irreducible polynomial of degree 32 whose period is 232-l. Each time the 32-bit input is executed for different number of rounds. Thus, even if the input bits are identical, the output will be random.
The method for generating the code for LFSR can be listed as follows:
1. Input: f(x) = xn + xsl+ xs2+ ... + x + 1
2. Write: xn = xsl+ xs2+ ... + x + 1 and express in binary form.
3. Compute one left shift for the entire binary value of xn
3.1 PI: Left shifting for all bits except nth position bit
3.2 P2: Left shifting on every nonzero nth position bit = binary
expression of xn
3.3 Compute: xn+1 = PI + P2 (mod 2)
In the above LFSR method, every bit in the binary expression of xn should be shifted into left except the «th position bit. For «th position bit, the same binary expression of xn is to be taken. On adding these two binary expressions with respect to mod 2, xn+1 could be obtained. The LFSR takes

the input from the output of T-function and produces the output containing a maximal period cycle.
The method for generating the code for SHA-3 can be listed as follows:
1. Fix the message digest length.
2. Select the SHA-3 in terms of number of bits.
3. Input the message for padding.
4. Engage the padding means for performing the padding function, typically to have w-block having size equal to the message digest length.
5. Engage a comparator means for comparing the size of message with the message digest length.
5.1 Is message size is lesser than message digest size, create the initialization vector (IV).
6. Engage the hash computation means in CBC mode with iterative rounds.
6.1 message pre processing occurs in first iterative round.
6.2 further iterative rounds follow.
7. Typically, after 6 iterative rounds, the system belches a hash value of the
message.
Applications of Message Pre processing (MP) in S-box construction:
Typically, an S-box (Substitution box) for AES functionalities can be constructed using message pre processing methods. This S-box would be adapted to typically produce 16x16 matrices derived from an 8-bit message pre processing method and S"'-box can be obtained by reversing the S-box entries. The benefits of the S-box models are: the Rijndael S-box is costly to

implement and there is no theory proposed for the Rijndael S-box. It is proved that this S-box is equivalent to the Rijndael S-box in terms of security and can easily be implemented.
The S-box would typically be a 16x16 dimensional S-box which has 256 values. The steps for construction of an S-box are as follows.
1. Initialize a 16x16 matrix.
2. Engage the shuffling means to perform an 8.bit message pre processing
3. Engage the T-functioning means over the output of the shuffling means
4. Engage the Linear Feedback Shift Registering means over the results of the T-functioning means.
5. Repeat the action for 16 times
Implementation results:
The following results are based on the hash functionalities in accordance with this invention with respect to 224,256, 384 and 512 bits.
For SHA-3 (224-bit):
Al.
Let the message be the 24-bit ASCII string "abc ", which is equivalent to the
following binary string: 01100001 01100010 01100011.
The resulting 224-bit message digest is



A2.
SHA-3 (224-bits) ("The quick brown fox jumps over the lazy dog") =
Even a small change in the message will (with overwhelming probability) result in a completely different hash, example changing d to c:
SHA-3 (224-bits) ("The quick brown fox jumps over the lazy cog") =
A3.
The hash value of Null string / Zero-length message ("") is =
f9a39cb8b7alffdla9e9al5bcb06e666fc9746bd9177cll38908e37a
For SHA-3 (256-bit):
Bl.
Let the message be the 24-bit ASCII string "abc ", which is equivalent to the following binary string: 01100001 01100010 01100011. The resulting 256-bit message digest is
B2.
SHA-3 (256-bits) ("The quick brown fox jumps over the lazy dog") =

Even a small change in the message will (with overwhelming probability)
result in a completely different hash, example changing d to c:

TCS_SHA-3 (256-bits) ("The quick brown fox jumps over the lazy cog") =
B3.
The hash value of Null string / Zero-length message ("") is =

For SHA-3 (384-bit):
CI.
Let the message be the 24-bit ASCII string "abc ", which is equivalent to the
following binary string: 01100001 01100010 01100011.
The resulting 384-bit message digest is
b8990ecef405285ae43865f8a2c02c7fcl68035dc64d7cl4c7270f99a0973cl3
8754104ef6805edbb6d2e65497ffdfb3.
C2.
SHA-3 (384-bits) ("The quick brown fox jumps over the lazy dog") =
e7cfeb098697e9139684387ecff2cfebbe3314aca2a5137fd0397c34ff8df97ad0
lad3cdb9041a30ae3d3dbcda46de41
Even a small change in the message will (with overwhelming probability)
result in a completely different hash, example changing T to r:
SHA-3 (384-bits) ("rhe quick brown fox jumps over the lazy dog") =
aa3346448a3dc7dea87d7ac2f24b542fd8a425969d0cca21d23236e5bdb0779
bd98f60ecccf2457 Ib2cd2e3cbbf94f0c.

C3.
The hash value of Null string / Zero-length message ("") is =
bfb48357ffd878alf3a5fe45f0326f8eefD9ed59808acf75b755d4b3da6868fb96
46a9ef9f73101bb349866de088eaal
For SHA-3 (512-bit):
Dl.
Let the message be the 24-bit ASCII string "abc ", which is equivalent to the
following binary string: 01100001 01100010 01100011.
The resulting 512-bit message digest is
a99ecd56fabc87f5e9011d81bc8ee609dd5ef5f7bl547a7981d528eeda030518
a32d745d8cf80c96c6aef9dbf025fa32d7d694a5e7f4fc5cbclb50e2c659fde6.
D2.
SHA-3 (512-bits) ("The quick brown fox jumps over the lazy dog") =
80894ee98d03c039e8f92f48a33e441787b8fe0bc52bflfdbd293f51a9a0222ca
D26999ae751fa29c487b9d2adle7b2e86755463db8f2a80f0c8c2468c6be5ff
Even a small change in the message will (with overwhelming probability)
result in a completely different hash, example changing T to r:
SHA-3(512-bits) ("rhe quick brown fox jumps over the lazy dog") =
e8377cf7d9a71747a79810c3c609268db92eb22cb76b2408e03fa9fa9b27f9fa
C01fmfefabe576ed6b69acbalal0f0ceel70d65b35afdbfblla7flc96533f62

D3.
The hash value of Null string / Zero-length message ("") is =
e3e065acb071e655fbl 17ceeabf4cda4b54d7a6bdl 1619aeeb62b7c2bcfl64alf
6e0c304a943c620e0f4b60564914bfi33ad97da549a6clcde403a3b5f6b464.
Statistical random test for SHA-3:
The output of hash value behaves like a random number that can be used in digital signature protocols. For instance, consider H = concatenation of 100 distinct hash values for SHA-3 (256-bit) = 25600 bits and then compute cipher text C = (H + M) mod 2, where M is a large size message. It is observed that the cipher text C behaves like random due to distinct hash values.
The following statistical reports satisfy the relationship C = (H+M) mod 2.
Entropy of the original file (M)
Entropy = 3.124613 bits per byte.
Optimum compression would reduce the size of this 28672 byte file by 60 percent.
Chi square distribution for 28672 samples is 2489498.79, and randomly would exceed this value 0.01 percent of the times. Arithmetic mean value of data bytes is 71.1914 (127.5 = random).

Monte Carlo value for Pi is 3.174550021 (error 1.05 percent). Serial correlation coefficient is 0.806530 (totally uncorrelated = 0.0).
Entropy of the cipher text = (H+M) mod 2, where H = 100 different Hash values
Entropy = 6.045497 bits per byte.
Optimum compression would reduce the size of this 28672 byte file by 24 percent.
Chi square distribution for 28672 samples is 157791.80, and randomly would exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 98.8841 (127.5 = random). Monte Carlo value for Pi is 3.506906656 (error 11.63 percent). Serial correlation coefficient is 0.589537 (totally uncorrelated = 0.0).
Survey of Hash functionalities
The following table shows SHA-3 functionality produced by the system and method in accordance with this invention as compared with other hash functionalities.

Name of the hash Block size Word size (bits) Output size Rounds Year of the standard /

functionality (bits) publication
MD4 512 32 128 48 1990
MD5 512 32 128 64 1992
SHA-0 512 32 160 80 1993
SHA-1 512 32 160 80 1995
RIPEMD-160 512 32 160 5 19%
SHA-224 512 32 224 64 2004
SHA-256 512 32 256 64 2002
SHA-384 1024 64 384 80 2002
SHA-512 1024 64 512 80 2002
Whirlpool 512 - 512 10 2003
SHA-3 (224) 224 32 224 6 2008
SHA-3 (256) 256 32 256 6 2008
SHA-3(384) 384 32 384 6 2008
SHA-3(512) 512 32 512 6 2008
Table-1

Industrial applications


The hash function produced by the system and method in accordance with this invention described above finds a number of applications in Information Security. Some specific areas where our invention can be applied are:
1. Signature protocols
2. Digital Identity
3. Access Control
4. Multifactor Authentication
5. Message Authentication Code (MAC)
6. Data integrity in a relational database
Brief Description of the Accompanying Drawings:
The invention is described with reference to the accompanying drawings in which:
Figure 1 illustrates hash process produced by the system and method in accordance with this invention;
Figure 2 illustrates CBC round one of the hash function in accordance with this invention;
Figure 3 shows CBC mode with iterative rounds of the hash function in accordance with this invention;

Figure 4 shows the SHA-3 functionality for the system and method to provide the hash value in accordance with this invention;
Figure 5 shows different versions of SHA-3 in accordance with their bit lengths; and
Figure 6 shows S-box construction.
Detailed Description of the Accompanying Drawings:
Figure 1 illustrates hash process produced by the system and method in accordance with this invention. This system and method outlines a designing and implementation scheme for a secure hash functionality SHA-3. SHA-3 is a one-way hash function, which is a combination of message pre processing (bijective function) and cipher block chaining (CBC) mode. The system and method in accordance with this invention includes two stages carried out by a padding means and a computation means respectively, performed in a sequential manner. A padding means is adapted to perform padding and a computation means is adapted to perform hash computation. The padding divides an incoming message into m blocks of a fixed length and adds an initialization vector to the message. The message pre processing involves performing bijective operations viz.: Shuffling, T-function and Linear Feedback Shift Register (LFSR). These operations are used in the hash computation, which is performed on each input block of a fixed length in Cipher Block Chaining (CBC) mode with iterative rounds. The final value generated by the proposed hashing is used to determine the message digest / hash value.

The SHA-3 functionality takes an input message of any size and returns a fixed size output (224 / 256 / 384 / 512-bits). The hash functionality provided by the system and method in accordance with this invention is an iterative, one-way hash function in which padding, message pre processing and hash computation are involved. The functionality comprises the following operations to perform: Padding, Message Pre processing (Shuffling, T-function, LFSR) in CBC mode with iterative rounds. The given message is passed into respective means performing the above operations, which produce a hash output. The three operations: Shuffling, T-function and LFSR are part of message pre processing.
Figure 2 illustrates CBC round one of the hash function in accordance with this invention. After padding, the hash computation process starts. It is based on CBC mode with iterative rounds. In the CBC mode, the input message is divided into m-blocks of fixed size (which depends upon the message digest length) and each block of input is XORed with the output of the previous message pre processing operation.
Figure 3 shows CBC mode with iterative rounds of the hash function in accordance with this invention. This process / round takes place 6 times in the hash computation using CBC mode. In the first round of CBC mode, a constant value (whose bit length < message digest length) must be XORed to the first block of the input message and the outcome is passed into the MP operation, which is again XORed with the second block of the input message. This XORing process continues till the end of the last block and produces a message digest of fixed size that is the output of first round. From second round to sixth, the output of previous round is XORed with the

same constant value, then the outcome is passed into the MP operation (that is known as first step) and the same process continues till the end of the last step. After completing six rounds, the CBC operation produces a hash output.
For instance, the given message is divided into a sequence of equal sized blocks and the total number of blocks is m. The size of each block is chosen to be 32 x n, where « (7 / 8 / 12/ 16) depends upon a message digest length (224 / 256 / 384 / 512 bits). There is no loss of generality to put a constant value = 0 in all rounds of CBC operation so that the first block of the input message is directly passed into the first round and the XORing process continues till the end of wth block. From second round to sixth, the output of previous round is passed into the MP operation and the same process goes up to s steps, where s denotes the number of blocks. After completion of six rounds, the hash output of fixed length size (32 x n) is obtained. The number of blocks for first round is not always the same as the number of blocks for second round onward.
Figure 4 shows the SHA-3 functionality for the system and method to provide the hash value in accordance with this invention. The method for generating the SHA-3 can be listed as follows:
1. Fix the message digest length.
2. Select the SHA-3 in terms of number of bits.
3. Input the message for padding.

4. Engage the padding means for performing the padding function, typically to dive the message into w-block having size equal to the message digest length.
5. Engage a comparator means for comparing the size of message with the message digest length.
5.1 If message size is lesser than message digest size, create the initialization vector (IV)
6. Engage the hash computation means in CBC mode with iterative rounds
6.1 message pre processing occurs in first iterative round
6.2 further iterative rounds follow
7. Typically, after 6 iterative rounds, the system belches a hash value of the
message.
Figure 5 shows different versions of SHA-3 in accordance with their bit lengths. Typically, a SHA-3 (224) functionality produces a 224 bit output. Similarly, a SHA-3 (256) functionality produces a 256 bit output, a SHA-3 (384) functionality produces a 384 bit output, and a SHA-3 (512) functionality produces a 512 bit output.
Figure 6 shows S-box construction. The steps are as follows:
1. Initialize a 16x16 matrix.
2. Engage the shuffling means to perform an 8-bit message pre processing

3. Engage the T-functioning means over the output of the shuffling means
4. Engage the Linear Feedback Shift Registering means over the results of the T-functioning means.
5. Repeat the action for 16 times.
Although the invention has been described in terms of particular embodiments and applications, one of ordinary skill in the art, in light of this teaching, can generate additional embodiments and modifications without departing from the spirit of or exceeding the scope of the claimed invention. Accordingly, it is to be understood that the drawings and descriptions herein are proffered by way of example to facilitate comprehension of the invention and should not be construed to limit the scope thereof.