FORM - 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENTS RULES, 2003
PROVISIONAL
Specification
(See section 10 and rule 13)
CRYPTOGRAPHY AND INFORMATION THEORY
TATA CONSULTANCY SERVICES LTD.
an Indian Company
of Bombay House, 24, Sir Homi Mody Street, Mumbai 400 001,
Maharashtra, India
THE FOLLOWING SPEC IFICATION DESCRIBES THE INVENTION.

Field of Invention
The invention relates to the field of cryptography and Information Theory .
Background of Invention:
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 algorithms 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 21 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 algorithms 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 algorithms is flawed, one option to counter this threat is to
2

upgrade to a stronger hash function. Alternatively message pre-processing 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 algorithm resists collision attacks in Hash functions. In this algorithm, 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 algorithm. 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:
3

A brute force attempt to find a collision should require at least 2n 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) hash functions are five cryptographic hash functions designed by the National Security0 Agency (NSA) and published by the NIST as a U.S. Federal Information Processing Standard. SHA consists of five algorithms: 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.
4

United States Patent 58922829 by William A. Aiello et al
discloses a desgin of secure hash function based on stretch function and
compression function.
United States Patent 6021201 by 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.
European Patent EP1556781 by 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) algorithm to produce a fixed length output word.
United States Patent 6091821 by Mark Leonard Buer discloses a pipelined hardware implementation of hash functions.
United States Patent 6141421 by Hiroyuki Kurumatani et al discloses a method and apparatus for generating hash value.
United States Patent 6052698 by Bennet et al discloses the reorganization of collisions in a hash bucket of a hash table to improve system performance.
United States Patent 20060294386 by Yual Gideon et al discloses a system to strengthen secure hash functions.
5

These inventions are not of much use to avoid hash collisions. Thus message pre-processing for hash function was needed to detect the hash collision errors.
Objects of invention:
The broad object of the invention is to protect Information security systems during transmission of the data.
The object of this invention is to provide a method for preventing hash collisions.
Another object of this invention is to provide a method for detecting hash collisions.
The object of this invention is to provide a method for pre- processing for hash functions.
Another object of this invention is to provide a method for transmission of data which is reliable.
Still one more object of this invention is to provide a method of pre- processing which is simple and easy to implement.
Summary of the Invention:
The method in accordance with this invention envisages a means for avoiding hash collisions by means of message pre- processing.
In accordance with one practical embodiment of this invention, a new message
pre-processing function is used to increase randomness and reduce redundancy
6

of an input message. With the help of the message pre-processing operations, hash collisions are avoided if it is applied before hashing any message.
In accordance with one practical embodiment of this invention, the message pre-processing function comprises 4 steps: Shuffling of bits, Compression, T-function and LFSR. These steps increase the entropy of the input message. At the end of 4 rounds, the output becomes more random.
In accordance with one practical embodiment of this invention, the output of pre- processing is passed into a hash function, which gives the hash output. The output of this method reduces hash collision and gives unique results.
Thus, the entire process reduces the chances of collision of the hash outputs. Further, the invented process is extended to signature protocols which make them more secure.
Brief Description of Drawings:
The invention will now be described with reference to the accompanying
drawing, in which
Figure 1 illustrates process in accordance with this invention.
Figure 2 illustrates Message Pre-processing steps in accordance with this
invention.
Figure 3 illustrates Hash process without collisions in accordance with this
invention.
Figure 4 illustrates Signature protocols with message pre-processing in
accordance with this invention.
Figure 5 illustrates Adversary attacks on the signature protocols in accordance
with this invention.
7

Detailed Description of the Drawings:
The methods by which hash functions can avoid collisions. In our invention, we have designed and analyzed a new message pre-processing function used to increase randomness and reduce redundancy of an input message. It is shown that such pre-processing, if applied before hashing any message, helps to avoid collisions that might otherwise occur.
Fig 1 in accordance with the accompanying drawings illustrates the flow of the method in accordance with this invention. The input message is given as 'm'. 'MP' is the message pre-processing function used to randomize the input message. Hash function is carried over the output of the pre-processing function which gives the final hash output. The hash output so obtained has very less probability of collision.
Fig 2 in accordance with the accompanying drawings illustrates the steps in message pre-processing function which reduces the redundancy in the input data and randomizes the input message. This results in a lower probability of a collision. The said pre-processing function comprises 4 steps: Shuffling of bits, Compression, T-function and LFSR. Each round of the MP function n explained as follows.
Shuffling of bits
The shuffling function is simple one to keep the overall algorithm fast and it has
a significant statistical effect on the output - the shuffling of bits helps to
improve the diffusion. Diffusion refers to the property that redundancy in the
statistics of the input is "dissipated" in the output. The inverse of the shuffle
operation can easily be accomplished by performing the swaps in reverse order.
8

Therefore, the shuffling operation is bijective.
For example,
the input message = abed efgh ijkl mnop ABCD EFGH IJKL MNOP.
After shuffling,
the output = aAbB cCdD eEfF gGhH iljj kKIL mMnN oOpP.
Compression
The output of the shuffling function is the input to the compression function. The compression algorithm has the property of being able to have any bit of the input affect, both directly and indirectly, any later bit of output causing a fast avalanche effect.
Unlike hash functions, the compression is used in this design only once. The compression function is used to further remove the redundancies in the data, and thus to increase randomness. Reversible lossless compression algorithm is used for this purpose. The reason for choosing a reversible compression mechanism is to avoid data loss. Since the compression function is bijective, it does not cause any collision.
T-Function
After the execution of the compression function, the output of the compression function is input to a T-function. The T-function is a bijective mapping that updates every bit of the state in a way that can be described as X1'= X1+f(X0….X1-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.
9

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 non-linearity between the input and output bits, and specifies that the hashes of messages from a close neighborhood are dispersed over the whole space.
In accordance with the invention, the T-function used, is the composition of primitive operations so that the T-function is invertible. Since the T-function is bijective, there are no collisions, and hence no entropy loss regardless of the Boolean functions and regardless of the selection of inputs.
The T-function used is (2x +x) mod 2 , where 32 is the number of bits (of x). This is an invertible mapping, which contain all the 2 possible states on a single cycle for any word size 32.
LFSR (Linear Feedback Shift Register)
The output of the T function is given as input to the LFSR. Primitive polynomials over GF (2n) are useful in the design of LFSRs for generating sequences of maximum period. All generated primitive polynomials are highly dense as well as random (highly dense means more number of tabs).
Each time the 32-bit input is executed with a primitive polynomial of degree 32 and the linear shift process undergoes for different cycles. Thus, even if the input bits are identical, the output will be random.
The primitive polynomial used in LFSR is x32 + x26 + x22 + x16 +x12 +x11
+ x10 + x8 + x7 +x5 + x4 + x2 + x + 1 over GF(232 ). This is an irreducible
10

polynomial of degree 32 whose period is 2~ -1. Experimentally, it is tested that the output of LFSR round gets more random, when each 32-bit input is shifted with the given primitive polynomial for 4 to 15 cycles.
Inverse of LFSR can be obtained with respect to the same primitive polynomial used for LFSR as well as output of LFSR. Therefore LFRS is bijective. Th^ inverse operation consumes a little bit time.
Thus the above four steps of Message Pre-processing function provide diffusion, avalanche effect, statistical irrelevance and randomness. It further removes the redundancies of a message (input) and make the message non linear and more random.
Since each round of the message pre-processing function is bijective, the overall message pre-processing function is also bijective. This means that it is impossible to have any two messages m and m' such that they give the same output after message pre-processing. If MP is the message pre-processing function, then MP(m) ^ MP(m') for any two different messages m and m'.
Therefore, the MP function (algorithm) contributes to provide randomness and reduce redundancy (diffusion of data). We have tested that the MP function performs well over SHA (SHA-1 & SHA-256).
Message Pre-processing function - Bijective
The Message Pre-processing (MP) is neither a hash function nor an encryption
algorithm. It cannot be called a hash function because the output file size of the
MP function is either the original file size or slightly more than the size. The
size of the file after shuffling remains the same or has a very slight expansion
11

due to padding. Then compression algorithm reduces the file size. Due to the functional properties of T-function and LFSR, the file size increases after compression round. At the end of four rounds, the output file becomes either the same size of the input file or slightly more. In encryption, the sender and th-^ receiver share some secret information, which is used to encrypt and decrypt the data in order to maintain confidentiality. But in Message Pre-processing, there is no such secret information (trapdoor function) used to compute the output. Also, the entire process can be reversed by anyone, since the MP function is bijective. It is shown in Fig. 3 that H(m) and H(MP(m)) are different for any message m.
Signature Protocols with Message pre-processing
The protocol starts with A sending to B the message m || MP(m), Hash of message preprocessing of the message H(MP(m)) and the signature of the hash {sig(H(MP(m)}. Even if the attacker finds another message m' different from m such that H(m) = H(MP(m')), the result is mathematically proved that it is not possible to find a message m' such that MP(m)=MP(m'). Therefore, the proposed protocol is secure.
Fig. 4 and Fig 5 in accordance with the accompanying diagrams depict the flow and attacks of the invented signature protocols.
IMPLEMENTATION RESULTS
Entropy and randomness tests were performed on the input and output files. The entropy of the output file is in the range 7.3 to 7.99 and it was always higher than that of the corresponding input file.
12

The following results are analyzed using Statistical tests on the input and output files of message pre-processing.
Result 1:
(a) Statistical results of Input file 1
Entropy = 4.264957 bits per byte.
Optimum compression would reduce the size of this 60228 byte file by 46
percent.
Chi square distribution for 60228 samples is 2671484.33, and randomly would
exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 67.1896 (127.5 = random).
Monte Carlo value for Pi is 3.369994023 (error 7.27 percent).
Serial correlation coefficient is 0.593774 (totally uncorrelated = 0.0).
(b) Statistical results of Output file 1
Entropy = 7.987451 bits per byte.
Optimum compression would reduce the size of this 14548 byte file by 0
percent.
Chi square distribution for 14548 samples is 250.55, and randomly would
exceed this value 50.00 percent of the times.
Arithmetic mean value of data bytes is 128.0510 (127.5 - random).
Monte Carlo value for Pi is 3.120462046 (error 0.67 percent).
Serial correlation coefficient is 0.003850 (totally uncorrelated = 0.0).
Result 2:
(a) Statistical results of Input file 2 Entropy = 3.450423 bits per byte.
Optimum compression would reduce the size of this 61764 byte file by 56
13

percent.
Chi square distribution for 61764 samples is 5756458.10, and randomly would
exceed this value 0.01 percent of the times.
Arithmetic mean value of data bytes is 37.4918 (127.5 = random).
Monte Carlo value for Pi is 3.855838352 (error 22.74 percent).
Serial correlation coefficient is 0.291492 (totally uncorrelated = 0.0).
(b) Statistical results of Output file 2 Entropy = 7.982900 bits per byte.
Optimum compression would reduce the size of this 10575 byte file by 0 percent.
Chi square distribution for 10575 samples is 247.86, and randomly would exceed this value 50.00 percent of the times.
Arithmetic mean value of data bytes is 126.8490 (127.5 = random). Monte Carlo value for Pi is 3.144154370 (error 0.08 percent). Serial correlation coefficient is 0.007816 (totally uncorrelated = 0.0).
INDUSTRIAL APPLICATIONS
The Message Pre-processing function described above finds a number of applications in Information Security. The MP function can be applied before hashing to avoid collisions. Wherever Hash function is applicable, the invention process m —> MP —» H —> HV can be used instead of Hash. Some specific areas where our process can be applied are:
1. Signature protocols
2. Digital Identity
3. Access Control
4. Multifactor Authentication
14

5. Message Authentication Code (MAC)
6. Data integrity in a relational database
While considerable emphasis has been placed herein on the particular features of method for pre-processing for a hash function, the improvisation with regards to it, it will be appreciated that various modifications can be made, and that many changes can be made in the preferred embodiment without departing from the principles of the invention. These and other modifications in the nature of the invention or the preferred embodiments will be apparent to those skilled in the art from the disclosure herein, whereby it is to be distinctly understood that the foregoing descriptive matter is to be interpreted merely as illustrative of the invention and not as a limitation.
15