System and method for implementing a hash algorithm

• US 20030198342A1
• Filed: 04/22/2002
• Published: 10/23/2003
• Est. Priority Date: 04/22/2002
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Fayad, Camil, Condorelli, Vincenzo
• Granted Patent: US 7,151,829 B2
• Time in Patent Office: Days
• US Class Current: 380/37
• 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 method of generating a message digest, comprising:

receiving a block of data; and

processing said block of data to achieve a message digest, said processing of said block of data including evaluating said block of data at cycle=t in terms of cycle=(t−

x), wherein x is greater than or equal to 2.

2. A method as in claim 1, wherein said block of data is 512-bits.

3. A method as in claim 1, wherein said block of data is received and/or processed in 64-bit increments.

4. A method as in claim 2, wherein said message digest comprises 160-bits.

5. A method as in claim 2, wherein said message digest comprises 128-bits.

6. A method as in claim 4 wherein said processing further comprises 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

7. A method as in claim 5, wherein said processing further comprises the following:

8. An improvement upon an SHA hashing algorithm, comprising:

generating a message digest, said generation comprising;

processing a block of data to achieve said message digest, said processing of said block of data including evaluating said block of data at cycle=t in terms of cycle=(t−

x), wherein x is greater than or equal to 2.

9. An improvement as in claim 8, wherein said generation further comprises:

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

10. An improvement upon an MD5 hashing algorithm, comprising:

generating a message digest, said generation comprising;

processing a block of data to achieve said message digest, said processing of said block of data including evaluating said block of data at cycle=t in terms of cycle=(t−

x), wherein x is greater than or equal to 2.

11. An improvement as in claim 10, wherein said generation further comprises:

12. A system for generating a message digest, comprising:

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

a processor for processing said block of data to achieve a message digest, said processing of said block of data including evaluating said block of data at cycle=t in terms of cycle=(t−

x), wherein x is greater than or equal to 2.

13. A system as in claim 12, wherein said block of data is 512-bits.

14. A system as in claim 12, wherein said memory storage location receives and/or processes said block of data in 64-bit increments.

15. A system as in claim 13, wherein said message digest comprises 160-bits.

16. A system as in claim 13, wherein said message digest comprises 128-bits.

17. A system as in claim 15 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

18. A system as in claim 16, wherein said processor performs the following:

19. An article of manufacture comprising:

a computer useable medium having computer readable program code embodied therein for generating a message digest, comprising;

computer readable program code for receiving a block of data; and

computer readable program code for processing said block of data to achieve a message digest, said processing of said block of data including evaluating said block of data at cycle=t in terms of cycle=(t−

x), wherein x is greater than or equal to 2.

20. A method for generating a message digest, comprising:

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.

21. A method as in claim 20 wherein:

m is equal to 512,

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

22. A method as in claim 21 wherein said first defined value is equal to 8.

23. A method as in claim 21 wherein W[0] is the leftmost word.

24. A method as in claim 21 wherein said MASK is equal to 0×

00000007.

25. A method as in claim 21 wherein said initial value of t is equal to 0, further wherein said terminal value is less than or equal to 39.

26. A method as in claim 25, 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).

27. A method as in claim 26 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)]).

28. A method as in claim 27 wherein said second shiftbit operation further comprises the following:

shift5bitsleft(A).

29. A method as in claim 28 wherein said third shiftbit operation further comprises the following:

shift30bitsleft(B).