Method of building fast MACS from hash functions

Claim 2

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 1 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.

Claim 3

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.

Claim 4

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

Claim 5

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 2 ; (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 1 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.

Claim 6

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 2 ; (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 1 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.

Claim 7

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.

Claim 8

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 1 , 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 1 .

Claim 9

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

Claim 10

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

Claim 11

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

Claim 12

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.

Claim 13

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

Claim 14

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

Claim 15

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

Claim 16

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

Claim 17

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

Claim 18

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

Claim 19

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

Claim 20

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

Claim 21

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

Claim 22

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.

Claim 23

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

Claim 24

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

Claim 25

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

Claim 26

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

Claim 27

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