Method and apparatus for implementing a novel one-way hash function on highly constrained devices such as rfid tags

Abstract

A method and apparatus for implementing a novel one-way hash function with provable security properties for authentication and non-authentication applications on highly constrained devices, with particular application to RFID tags.

1 . A method for implementing a one-way hash function on a device having a processor and a memory in which is stored a secret S that comprises the steps of recording in the device memory non-transitory instructions for controlling the processor to compute a one-way hash function in response to an input to the device; inputting a message R to the device; said non-transitory instructions controlling the processor of the device to compute responsive to the input a numeric approximation A as output; wherein A is a selected subset of t<<k bits of the k bits in a Rabin ciphertext c defined by c=m 2  (mod n), where m=M(S,R), with n being an encryption key used to compute the ciphertext c, and M being a mixing function for combining S and R;
 wherein the selected subset of bits in the Rabin ciphertext is a selected window of t bits, and wherein the numeric approximation A consists of the selected window of t bits of c, denoted from a selected LSB to a selected MSB by computing the selected window of t bits from c, and assuming that no carry was entering into the computation of the selected least significant bit (LSB) from lower indexed bit computations which are not carried out; and   outputting the number approximation A.   
     
     
         2 . The method of  claim 1  wherein t bits in the selected window of t bits are consecutive. 
     
     
         3 . The method of  claim 1  including the further steps of computing an extended window of t+u bits from c, denoted from a selected LSB to a selected MSB and assuming that no carry was entering into the computation of the selected least significant bit from lower indexed bit computations which are not carried out, the numeric approximation A consisting of the last t bits in this extended window, and the first u bits in the extended window being discarded. 
     
     
         4 . The method of  claim 1  wherein the mixing function is a simple transformation selected from one of addition of and multiplication by a constant before approximating a selected subset of t bits. 
     
     
         5 . The method of  claim 1  wherein the modulus is of the form n=a*(2 k )±b, and including the further step of multiplying the ciphertext c by a before approximating a selected subset of t bits. 
     
     
         6 . The method of  claim 1  wherein the modulus n is of the form one of a*(2 k )+b and a*(2 k )−b where a and b are smaller than 2 k . 
     
     
         7 . The method of  claim 6  in which a=1 or b=1 or a=b=1. 
     
     
         8 . The method of  claim 1  including the step of each bit in the window being computed by a convolution involving the sum of products of input bits of the form m v *m {j−v(mod k)}  for various values of v. 
     
     
         9 . The method of  claim 1  wherein the input bits are defined by a pseudo-random generator, and are recreated on the fly whenever needed rather than stored explicitly in memory. 
     
     
         10 . The method of  claim 1  wherein the number approximation A uses bytes or words rather than bits and includes convolution of the bytes or words. 
     
     
         11 . A method for authenticating a device D to a reader E which share secret information S by an interactive challenge-response protocol comprising the steps of:
 a. receiving by D of a random challenge R sent from E;   b. combining by D of the secret S and the challenge R by a MIX function which produces a k-bit value m=MIX(S,R);   c. calculating a number approximation A of m according to  claim 1 , and sending A from D to E; and   d. verifying the number approximation A of m by E recomputing the value A, and accepting the proof of authenticity only if the computed and received values of A are the same.   
     
     
         12 . The method of  claim 11 , wherein the MIX function of step b is carried out by first combining R and S by a simple function of one of XOR'ing, adding and concatenating them, and then extending the result to k bits by using a simple reversible pseudo random bit generator or one of a nonlinear feedback shift register and a Feistel structure seeded with the combined value. 
     
     
         13 . A computer readable medium for a device having a processor and being part of a secure communication system comprised of the device D and a reader E, said medium containing non-transient executable instructions that program the processor contained in the device for authenticating the device D to a reader E, which share secret information S, by an interactive challenge-response protocol, the non-transient executable instructions program the device D for:
 a. receiving by D of a random challenge R sent from E;   b. combining by D of the secret S and the challenge R by a MIX function which produces a k-bit value m=MIX(S,R);   c. calculating a number approximation A of m according to  claim 1 , and sending the result A from D to E;   d. wherein E verifies the number approximation A by recomputing the value A, and accepts the proof of authenticity only if the computed and received values are the same.   
     
     
         14 . Apparatus for authenticating a device D to a reader E which share secret information S by an interactive challenge-response protocol, said device D containing a processor and circuitry configured to
 a. receive by D a random challenge R sent from E;   b. combine by D the secret S and the challenge R by a MIX function which produces a k-bit value m=MIX(S,R);   c. calculate a number approximation A of m by computing a one way hash function which accepts a k-bit message m as input, and computes as output a numeric approximation A to a selected subset of t<<k bits, out of the k bits in a Rabin ciphertext defined by c=m 2  (mod n) where n is a k-bit composite modulus, and wherein the selected subset of bits in the Rabin ciphertext is a window of t bits, and wherein the numeric approximation to the t bits of c, denoted from a selected LSB to a selected MSB by computing a window of t bits from c, assuming that no carry was entering into the computation of the least significant bit (LSB) from lower indexed bit computations which are not carried out, and outputting the number approximation A and sending to E; whereby E can verify the number approximation A of m by recomputing the value A, and can accept the proof of authenticity only if the computed and received values of A are the same.   
     
     
         15 . The apparatus according to  claim 14  wherein the circuitry of said device D is configured to combining R and S by a simple function of one of XOR'ing, adding and concatenating them, and then extending the result to k bits by using a simple reversible pseudo random bit generator or one of a nonlinear feedback shift register and a Feistel structure seeded with the combined value. 
     
     
         16 . The apparatus of  claim 14  wherein t bits in the selected window of t bits are consecutive. 
     
     
         17 . The apparatus of  claim 14  wherein the circuitry is further configured to control the processor to compute an extended window of t+u bits from c, denoted from a selected LSB to a selected MSB and assuming that no carry was entering into the computation of the selected least significant bit from lower indexed bit computations which are not carried out, the numeric approximation A consisting of the last t bits in this extended window, and the first u bits in the extended window being discarded. 
     
     
         18 . The apparatus of  claim 14  wherein the circuitry is further configured to control the processor to compute the mixing function as a simple transformation selected from one of addition and of multiplication by a constant before approximating a selected subset of t bits.