System and method for implementing a hash algorithm

• US 7,151,829 B2
• Filed: 04/22/2002
• Issued: 12/19/2006
• Est. Priority Date: 04/22/2002
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fayad, Camil, Condorelli, Vincenzo
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): To, Baotran N.
• Application Number:
  US10/127,393
• Publication Number:
  US 20030198342A1
• Time in Patent Office: 1,702 Days
• Field of Search: 380 25- 30, 380/37, 713180-181, 713/168
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/50 using hash chains, e.g. blockchains or hash trees

Abstract

A system and method for generating a message digest comprising: receiving a block of data and processing the block of data to 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.

Claims

1. A system generating a message digest, via a computer, said system comprising:

a memory storage location for receiving a block of data; and

a processor for processing said block of data to acquire said message digest, said processing of said block of data includes (i) evaluating said block of data at cycle=t in terms of cycle=(t−

x), wherein x is greater than or equal to 2, and (ii) skipping one cycle per iteration in order to reduce a total number of cycles utilized for said processing of said block of data;

wherein said block of data is 512-bits;

wherein said message digest comprises 160-bits;

wherein said processor performs the following;

E(t)=C(t−

2);

D(t)=S30 [B(t−

2)];

C(t)=S30 [A(t−

2)];

B(t)=S5(A(t−

2))+ft(B(t−

2),C(t−

2),D(t−

2))+E(t−

2)+Wt−

1+Kt−

1; and

$\begin{array}{c}A<br><br>\left(t\right)<br><br>=\mathrm{S5}<br><br>\left(\mathrm{S5}<br><br>\left(A<br><br>\left(t-2\right)\right)+\mathrm{ft}<br><br>\left(B<br><br>\left(t-2\right),C<br><br>\left(t-2\right),D<br><br>\left(t-2\right)\right)+E<br><br>\left(t-2\right)+\mathrm{Wt}-1+\mathrm{Kt}-1\right)+\\ <br><br>\mathrm{ft}<br><br>\left(A<br><br>\left(t-2\right),\mathrm{S30}<br><br>\left[B<br><br>\left(t-2\right)\right],C<br><br>\left(t-2\right)\right)+D<br><br>\left(t-2\right)+\mathrm{Wt}+\mathrm{Kt}=\\ <br><br>\mathrm{S5}<br><br>\left(B<br><br>\left(t\right)\right)+\mathrm{ft}<br><br>\left(A<br><br>\left(t-2\right),\mathrm{S30}<br><br>\left[B<br><br>\left(t-2\right)\right],C<br><br>\left(t-2\right)\right)+D<br><br>\left(t-2\right)+\mathrm{WT}+\mathrm{Kt};<br><br>\end{array}$

where A, B, C, D, E and W are words of a message, K is a constant word, f is a logical function, Sx represents a value circularly rotated by x bits;

said processor generating said message digest providing a message fingerprint for said data.

2. A system generating a message digest, via a computer, said system comprising:

a memory storage location for receiving a block of data; and

a processor for processing said block of data to acquire said message digest, said processing of said block of data includes (i) evaluating said block of data at cycle=t in terms of cycle=(t−

x), wherein x is greater than or equal to 2, and (ii) skipping one cycle per iteration in order to reduce a total number of cycles utilized for said processing of said block of data;

wherein said block of data is 512-bits;

wherein said message digest comprises 128-bits;

wherein said processor performs the following;

$\begin{array}{c}\begin{array}{c}D<br><br>\left[t-1\right]<br><br>=B<br><br>\left[t-2\right]+\left(\left(F<br><br>\left(B\right)<br><br>\left[t-2\right],C<br><br>\left[t-2\right],D<br><br>\left[t-2\right]\right)+A<br><br>\left[t-2\right]+M<br><br>\left[\mathrm{ja}\right]+T<br><br>\left[t-1\right]\right)<br><br><br><br>\langle <br><br>\langle <br><br>\langle <br><br>\\ <br><br>\mathrm{Sa})+\\ <br><br>((D<br><br>\left[t-2\right]+F((B<br><br>\left[t-2\right]+((F<br><br>\left(B<br><br>\left[t-2\right],C<br><br>\left[t-2\right],D<br><br>\left[t-2\right]+A<br><br>\left[t-2\right]+M<br><br>\left[\mathrm{ja}\right]+T<br><br>\left[t-1\right]\right)<br><br>\\ <br><br>\langle <br><br>\langle <br><br>\langle <br><br><br><br>\mathrm{Sa})),B<br><br>\left[t-2\right],C<br><br>\left[t-2\right])+M<br><br>\left[\mathrm{jb}\right]+T<br><br>\left[t-1\right])<br><br><br><br>\langle <br><br>\langle <br><br>\langle <br><br><br><br>\mathrm{Sb});<br><br>\mathrm{and}\end{array}\\ \begin{array}{c}B<br><br>\left[t\right]<br><br>=D<br><br>\left[t-1\right]+(\left(C<br><br>\left[t-1\right]+\mathrm{ft}<br><br>\left(D<br><br>\left[t-1\right],A<br><br>\left[t-1\right],B<br><br>\left[t-1\right]\right)+\mathrm{Mj}+\mathrm{Tt}-1\right)<br><br><br><br>\langle <br><br>\langle <br><br>\langle <br><br><br><br>S)+\\ <br><br>((B<br><br>\left[t-1\right]+\mathrm{ft}((D<br><br>\left[t-1\right]+(\left(C<br><br>\left[t-1\right]+\mathrm{ft}<br><br>\left(D<br><br>\left[t-1\right],A<br><br>\left[t-1\right],B<br><br>\left[t-1\right]\right)+\mathrm{Mj}+\mathrm{Tt}-1\right)\\ <br><br>\langle <br><br>\langle <br><br>\langle <br><br><br><br>S)),D<br><br>\left[t-1\right],A<br><br>\left[t-1\right])+\mathrm{Mj}+\mathrm{Tt})<br><br><br><br>\langle <br><br>\langle <br><br>\langle <br><br>S);<br><br>\end{array}\end{array}$

where A, B, C, D, E and W are words of a message, F is a function, M is a message block, T is a value from a table and S represents a shifting function;

said processor generating said message digest providing a message fingerprint for said data.

3. A system generating a message digest, via a computer, said system comprising:

a memory storage location for receiving a block of data; and

a processor for processing said block of data to acquire said message digest, said processing of said block of data includes;

if a message is less than m bits, then padding said message;

dividing said message into n words, said n words further comprising W[0] through W[n];

performing the following;

setting A equal to H0,

setting B equal to H1,

setting C equal to H2,

setting D equal to H3,

setting E equal to H4;

establishing a counter for storing a value used in performing iteration, said counter being referred to as t;

setting t to an initial value;

setting a terminal value to an initial value;

for t not equal to said terminal value, iteratively performing steps a–

e;

a. setting S equal to (T AND MASK);

b. if t is greater than or equal to a first defined value, then setting W[t]equal to a the value of a first shiftbit operation;

c. setting TEMP equal to the value of a second shiftbit operation+f(B,C,D)+E+W[s]+K_t, wherein K_t further comprises a constant value;

d. performing the following;

setting E equal to D,

setting D equal to C,

setting C equal to the value of a third shiftbit operation,

setting B equal to A,

setting A equal to TEMP;

e. incrementing t; and

performing the following;

setting H0 equal to H0+A,

setting H1 equal to H1+B,

setting H2 equal to H2+C,

setting H3 equal to H3+D,

setting H4 equal to H4+E;

said processor generating said message digest providing a message fingerprint for said data.

4. The system as in claim 3 wherein:

m is equal to 512,

n is equal to 8, and further wherein each word is equal to 64 bits.

5. The system as in claim 4 wherein said first defined value is equal to 8.

6. The system as in claim 4 wherein W[0] is the leftmost word.

7. The system as in claim 4 wherein said MASK is equal to 0×

00000007.

8. The system as in claim 4 wherein said initial value of t is equal to 0, further wherein said terminal value is less than or equal to 39.

9. The system as in claim 8, further comprising the following:

if t is greater than or equal to 0 and t is less than or equal to 9, then perform the following;

setting f_t (B,C,D) equal to (B AND C) OR (NOT(B) AND D),

setting f_t (A,B,C) equal to (A AND B) OR (NOT(A) AND C);

if t is greater than or equal to 10 and t is less than or equal to 19, then perform the following;

setting f_t (B,C,D) equal to (B XOR C XOR D),

setting f_t (A,B,C) equal to (A XOR B XOR C);

if t is greater than or equal to 20 and t is less than or equal to 29, then perform the following;

setting f_t (B,C,D) equal to (B AND C) OR (B AND D) OR (C AND D),

setting f_t (A,B,C) equal to (A AND B) OR (A AND C) OR (B AND C); and

if t is greater than or equal to 30 and t is less than or equal to 39, then perform the following;

setting f_t (B,C,D) equal to (B XOR C XOR D),

setting f_t (A,B,C) equal to (A XOR B XOR C).

10. The system as in claim 9 wherein said first shiftbit operation, further comprises the following:

shift1bitleft( W[(t+6) AND MASK] XOR W[(t+3) AND MASK] XOR W[(t+1) and MASK] XOR W[(t+0)]).

11. The system as in claim 10 wherein said second shiftbit operation further comprises the following:

shift5bitsleft(A).

12. The system as in claim 11 wherein said third shiftbit operation further comprises the following:

shift30bitsleft(B).