Method of building fast MACS from hash functions

• US 5,664,016 A
• Filed: 10/17/1995
• Issued: 09/02/1997
• Est. Priority Date: 06/27/1995
• Status: Expired due to Term

• Current Assignee: Entrust Incorporated (Entrust Corp.)
• Original Assignee: Northern Telecom Limited (Nortel Networks Corporation)
• Inventors: Preneel, Bart K. B., Van Oorschot, Paul C.
• Primary Examiner(s): Tarcza, Thomas H.
• Assistant Examiner(s): LAUFER, PINCHUS M
• Application Number:
  US08/544,150
• Time in Patent Office: 686 Days
• Field of Search: 380/28, 380/29, 380/30, 380/23, 380/25, 380/49
• US Class Current: 380/28
• 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 2209/30 Compression, e.g. Merkle-Damgard construction
• 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

Hash functions are important in modern cryptography. Main applications are their use in conjunction with digital signature schemes and message authentication. Hash functions, commonly known as message authentication codes (MACs), have received widespread use in practice for data integrity and data origin authentication. New and inventive ways of building fast MACs from hash functions involve keyed hash functions in which secret keys are used at certain locations of the compression process and the keys are also hashed.

Claims

1. In an iterated hash function operation in data encryption and authentication, a method of performing a compression function H_i =f(H_i-1, X_i) to an input data block X_i having a plurality of data segments X_i [j], each data segment being of a predetermined bitlength of p, p being a positive integer and H_i being an updated chaining variable of H_i-1, the invention being characterized in that the compression function comprises multiple iterated internal steps, and each internal step comprises:

(i) a preparing step of introducing working variables to a data segment;

(ii) a keying step of introducing a subkey K₁ or a portion thereof to a predetermined constant y to generate a key dependent constant; and

(iii) a processing step of treating the prepared data segment with the key dependent constant.

2. The method according to claim 1, wherein the keying step (ii) and/or the processing step (iii) comprise a step of involving one or more arithmetic or logical functions, including a modulo addition or the like.

3. The method according to claim 2, wherein the initial value H₀ of the chaining variable is dependent on a subkey K₀, further comprising steps of generating subkeys K₀ and K₁ by the use of other hash functions to a main key K and predetermined constants U₀ and U₁ respectively.

4. In a method of generating a message authentication code for a message X which comprises steps of dividing X into X_i data blocks, i=1 to t and t being an integer, each data block being a predetermined number of bits long and data block X_t having padding bits if needed, the invention being characterized in further steps of:

(a) generating a data block X_t+1 of the predetermined number of bits long under a subkey K₂ ;

(b) appending data block X_t+1 to data block X_t ;

(c) performing iteratively a compression function H_i =f(H_i-1, X_i) to data blocks X_i for i=1 to t+1 to generate an n-bit chaining variable H_i, each data block having p-bit data segments X_i [j], p being a positive integer and H_i being an updated chaining variable of H_i-1, the compression function comprising multiple iterated internal steps in that each internal step comprises;

(i) a preparing step of introducing working variables to a data segment,

(ii) a keying step of introducing a subkey K₁ or a portion thereof to a predetermined constant y to generate a key dependent constant, and

(iii) a processing step for treating the prepared data segment with the key dependent constant; and

(d) transforming the final chaining variable H_t+1 to an m-bit final output g(H_t+1), which is the message authentication code for message X, where m and n are positive integers and m≦

n.

5. The method according to claim 4, wherein the keying step (ii) and/or the processing step (iii) comprise a step of involving one or more arithmetic or logical functions, including a modulo addition or the like.

6. The method according to claim 5 wherein the keying step (ii) involves a step of introducing the predetermined constant y of p bits long and a p-big portion of subkey K₁, the latter of which has been generated by a first subkey function using a main key K of k bits, k being an integer, and a predetermined constant U₁.

7. The method according to claim 6 whereto the initial value H₀ of the chaining variable is dependent on a subkey K₀ and comprising further steps of generating an initial chaining variable H₀ under subkey K₀ and generating subkey K₀ by the use of a second subkey function, to the main key K and a predetermined constant U₀.

8. The method according to claim 7 comprising further steps of generating data block X_t+1 under subkey K₂ and a predetermined constant T and generating subkey K₂ by the use of a third subkey function, to the main key K and a predetermined constant U₂.

9. The method according to claim 8 wherein the third subkey function is a hash function.

10. The method according to claim 9 wherein the hash function of the third subkey function is selected from a group consisting of any iterated hash function based on MD4 or of similar structure to MD4, including MD5, RIPEMID and SHA.

11. The method according to claim 10 wherein the hash function of the third subkey function is SHA, n=160 and m≦

160.

12. The method according to claim 11 wherein m is one of 160, 128, 80 and 64.

13. The method according to claim 10 wherein the main key K has k bits where k≦

128.

14. The method according to claim 8 where m=n and g is a permutation or the identity function.

15. The method according to claim 8 where m=n/2.

16. The method according to claim 7 wherein the second subkey function is a hash function.

17. The method according to claim 7 wherein the first and the second subkey functions are the same.

18. The method according to claim 8 wherein any two or three of the first, second and third subkey functions are the same.

19. The method according to claim 6 wherein the first subkey function is a hash function.

20. The method according to claim 19 wherein the hash function is selected from a group consisting of any iterated hash function based on MD4 or of similar structure to MD4, including MD5, RIPEMD and SHA.

21. The method according to claim 20 wherein the hash function is SHA, n=160 and m≦

160.

22. The method according to claim 21 wherein m is one of 160, 128, 80 and 64.

23. The method according to claim 20 wherein the main key K has k bits where k≦

128.

24. The method according to claim 4 where m=n and g is a permutation or the identity function.

25. The method according to claim 4 where m=n/2.