METHOD AND APPARATUS FOR IMPLEMENTING A NOVEL ONE-WAY HASH FUNCTION ON HIGHLY CONSTRAINED DEVICES SUCH AS RFID TAGS

• US 20110271105A1
• Filed: 08/08/2008
• Published: 11/03/2011
• Est. Priority Date: 08/14/2007
• Status: Active Grant

• Current Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Original Assignee: Yeda Research and Development Co. Ltd. (Weizmann Institute of Science)
• Inventors: Shamir, Adi
• Granted Patent: US 8,291,221 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• CPC Class Codes: G08B 13/2417 having a radio frequency identification chip
• CPC Class Codes: G08B 13/2462 Asset location systems combined with EAS inventory, tracking, logistic G06Q10/00; entrance control systems G07C9/00
• CPC Class Codes: G08B 13/2482 EAS methods, e.g. description of flow chart of the detection procedure
• CPC Class Codes: H04L 2209/805 Lightweight hardware, e.g. radio-frequency identification [RFID] or sensor
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3221 interactive zero-knowledge proofs
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3271 using challenge-response

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.

Claims

1. A method for implementing a one-way hash function on a highly constrained device that comprises the step of providing computing capability to the highly constrained device, computing a one way hash function with provable security properties which accepts a k-bit message m as input, and computes as output a numeric approximation A to some small subset of t<

<

k out of the k bits in a Rabin ciphertext defined by c=m² (mod n) where n is a k-bit composite modulus, and outputting the number approximation A.

2. The method of claim 1, including the further step of modifying the Rabin ciphertext by simple transformations selected from one of the addition of or the multiplication by a constant before approximating a subset of t of its k bits.

3. The method of claim 2 wherein the modulus is of the form n=a*(2^k)±

b, and including the further step of multiplying the Rabin ciphertext c by a before approximating a subset of t of its k bits.

4. The method of claim 1, in which everyone uses the same universal modulus n, for which the complete factorization is unknown.

5. The method of claim 1 wherein the modulus n is of the form a*(2^k)+b or a*(2^k)−

b where a and b are much smaller than 2^k.

6. The method of claim 4 in which a=1 or b=1 or a=b=1.

7. The method of claim 1 wherein the subset of bits in the Rabin ciphertext is a window of t consecutive bits.

8. The method of claim 7 wherein the length of the window of bits is t>

=16.

9. The method of claim 7 wherein the numeric approximation to the t consecutive bits of C, denoted from LSB to MSB by c_{i+1}, c_{i+2}, . . . , c_{i+t}, is defined by the steps of computing an extended window of t+u bits from C, denoted from LSB to MSB by c_{i-u+1}, c_{i-u+2}, . . . , c_{i}, c_{i+1}, . . . c_{i+t}, and assuming that no carry was entering into the computation of the least significant bit c_{i-u+1} from lower indexed bit computations which are not carried out, the numeric approximation consisting of the last t bits in this extended window, and the first u bits in the extended window being discarded.

10. The method of claim 9 wherein the window is extended by u>

=16 bits.

11. The method of claim 9 including the step of each bit c_j in the extended 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.

12. The method of claim 11 wherein the input bits m_w are defined by a pseudo random generator, and are recreated on the fly whenever needed rather than stored explicitly in memory.

13. The method of claim 11 including the steps of computing the results as consecutive bytes or words of any size rather than as consecutive bits and using the same convolution method on larger chunks of data.

14. The method of claim 9 including the steps of, when n=2^k−

1, evaluating each bit c_{j} for (i−

u+1)<

=j<

=(i+t) by computing a bit convolution by starting with the previously computed carry, numerically adding to it all the products m_v*m_{{j-v(mod k)}} for v=0, 1, 2, . . . , k−

1, taking the least significant bit of the result as the computed value of c_j, and all the other bits as the next carry.

15. The method of claim 9 including the steps of, when n=2^k+1, evaluating each bit c_{j} for (i−

u+1)<

=j<

=(i+t) by computing a bit convolution by starting with the previously computed carry, numerically adding to it all the products m_v*m_{{j-v(mod k)}} for v=0, 1, 2, . . . , k−

1, taking the least significant bit of the result as the computed value of c_j, and all the other bits as the next carry, except that products m_v*m_{{j-v(mod k)}} in which j−

v is negative are subtracted from rather than added to the other values.

16. The method of claim 9 including the steps of, when n=a*2^k±

b, evaluating each bit c_{j} for (i−

u+1)<

=j<

=(i+t) by computing a bit convolution by starting with the previously computed carry, numerically adding to it all the products m_v*m_{{j-v(mod k)}} for v=0, 1, 2, . . . , k−

1, taking the least significant bit of the result as the computed value of c_j, and all the other bits as the next carry, except that products m_v*m_{{j-v(mod k)}} in which j−

v is negative are multiplied by a before being added to or subtracted from the result, and products m_v*m_{{j-v(mod k)}} in which j−

v is nonnegative are multiplied by b before being added to the result.

17. A method for authenticating a device D to a reader E which share some 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 the result A from D to E; and

d. verifying the number approximation A of m by recomputing the same value by E, and accepting the proof of authenticity only if the computed and received values are the same.

18. The method of claim 17, 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 of one of a nonlinear feedback shift register and a Feistel structure seeded with the combined value.

19. A computer readable medium for authenticating a device D to a reader E which share some secret information S by an interactive challenge-response protocol, the medium containing executable program instructions 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; and

d. verifying the number approximation A of m by recomputing the same value by E, and accepting the proof of authenticity only if the computed and received values are the same.

20. Apparatus for authenticating a device D to a reader E which share some secret information S by an interactive challenge-response protocol comprising:

a. means for receiving by D of a random challenge R sent from E;

b. means for 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. means for calculating a number approximation A of m by computing a one way hash function with provable security properties which accepts a k-bit message m as input, and computes as output a numeric approximation A to some small subset of t<

<

k out of the k bits in a Rabin ciphertext defined by c=m² (mod n) where n is a k-bit composite modulus, and outputting the number approximation A that is sent from D to E;

whereby E can verify the number approximation A of m by recomputing the same value, and can accept the proof of authenticity only if the computed and received values are the same.