System and method for guaranteeing software integrity via combined hardware and software authentication

• US 7,721,098 B2
• Filed: 06/05/2008
• Issued: 05/18/2010
• Est. Priority Date: 09/26/2002
• Status: Expired due to Term

• Current Assignee: Atreus Labs LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Lotspiech, Jeffrey B.
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): HO, VIRGINIA T
• Application Number:
  US12/134,134
• Publication Number:
  US 20080313460A1
• Time in Patent Office: 712 Days
• Field of Search: 713/181, 713/180, 713/170, 713/176, 713/168
• US Class Current: 713/170
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06Q 10/087 Inventory or stock management, e.g. order filling, procurement or balancing against orders
• CPC Class Codes: H04L 2209/127 Trusted platform modules [TPM]
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 2209/603 Digital right managament [DRM]
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3236 using cryptographic hash functions
• CPC Class Codes: H04L 9/3249 using RSA or related signature schemes, e.g. Rabin scheme

Abstract

A system, method, and computer program product enabling individual user devices to authenticate and validate a digital message sent by a distribution center, without requiring transmissions to the distribution center. The center transmits the message with an appended modulus that is the product of two specially selected primes. The transmission also includes an appended authentication value that is based on an original message hash value, a new message hash value, and the modulus. The new message hash value is designed to be the center'"'"'s public RSA key; a corresponding private RSA key is also computed. Individual user devices combine a digital signet, a public modulus, preferably unique hardware-based numbers, and an original message hash to compute a unique integrity value K. Subsequent messages are similarly processed to determine new integrity values K′, which equal K if and only if new messages originated from the center and have not been corrupted.

Claims

1. A system for guaranteeing message integrity, comprising:

a distribution center that transmits a transmission wherein said transmission includes a message and an appended first value; and

a user device that receives said transmission and computes an integrity value K′

that depends on said transmission and at least one of a plurality of stored values where K′

selectively enables successful further processing of said message;

wherein said plurality of stored values include a predetermined integrity value K=g₁^h0g₂^a mod M, where a is a digital signet, M is a public modulus, and g₁ and g₂ are unique values and h₀ is an original first hash value.

2. The system of claim 1 wherein said appended first value includes a modulus pq and an authentication value s.

3. The system of claim 2 wherein said authentication value s is an encrypted version of h₀, said modulus pq, and a private RSA key z, where s=h₀^z mod pq.

4. The system of claim 3 wherein p and q are prime numbers, and said modulus pq is a product of p and q, neither of said p and q being separately included in said transmission.

5. The system of claim 4 wherein said prime numbers p and q are selected by said distribution center such that a likelihood of a product (p−

1)(q−

1) and an odd-valued correct second hash value h₁ of said message having a greatest common denominator other than 1 is substantially zero, whereby h₁z=1 mod Φ

(pq), where Φ

(pq)=(p−

1)(q−

1), and h₁ is a public RSA key corresponding to said private RSA key z.

6. The system of claim 5 wherein said integrity value K′

equals g₁^xg₂^a mod M, where x=s^h mod pq, and h is a third hash value of said message computed by said user device.

7. The system of claim 6 wherein said integrity value K′

is a value required to enable successful further processing of said message if and only if h matches h₁, guaranteeing the integrity of said message.

8. The system of claim 5 wherein h₁ is forced to be odd, if initially even.

9. The system of claim 1 wherein said message comprises a software program.

10. The system of claim 1 wherein said message comprises a software program portion.

11. The system of claim 1 wherein said message comprises a software program that controls access to protected information.

12. The system of claim 1 wherein said message includes a first software program portion, and said integrity value K′

includes a second software program portion, and said message and said integrity value K′

together comprise a complete software program.

13. The system of claim 1 wherein said message comprises protected information intended for use only by authorized recipients.

14. The system of claim 13 wherein said protected information comprises at least one of:

a text file, an audio file, a video file, an application, and a database.

15. The system of claim 1 wherein said stored values are stored in tamper-resistant hardware.

16. A system for guaranteeing message integrity, comprising:

a user device having at least one of a plurality of stored integrity values related to an additional integrity value h₀;

a distribution center that transmits a transmission wherein the transmission includes a message and an appended first value including an encryption of said additional integrity value h₀, where said encryption uses a key based on a hash of said message;

wherein the user device receives said transmission and computes an integrity value K′

that depends on said transmission and at least one of a plurality of stored second values, where K′

selectively enables successful further processing of said message; and

wherein said plurality of stored second values include a predetermined integrity value K=g₁^h0g₂^a mod M, where a is a digital signet, M is a public modulus, and g₁ and g₂ are unique instances of the stored second values.

17. The system of claim 16 wherein said plurality of stored integrity values are digital signet values, and said additional integrity value h₀ is a digital signet user number.

18. The system of claim 17 wherein said digital signet values allow the calculation of third values used in a content protection scheme.

19. The system of claim 16 wherein said encryption of said additional integrity value h₀ is an RSA encryption, and the distribution center additionally transmits an RSA modulus pq.

20. The system of claim 16 wherein said message comprises a software program and associated data.

21. A computer program product for guaranteeing message integrity, comprising a computer-readable storage medium tangibly embodying computer readable program code thereon, said computer-readable program code comprising:

computer readable program code configured to transmit a transmission wherein said transmission includes a message and an appended first value from a distribution center;

computer readable program code configured to receive said transmission with a user device; and

computer readable program code configured to compute an integrity value K′

that depends on said transmission and at least one of a plurality of stored second values where K′

selectively enables successful further processing of said message, wherein said plurality of stored second values include a predetermined integrity value K=g₁^h0g₂^a mod M, where a is a digital signet, M is a public modulus, and g₁ and g₂ are unique values, and h₀ is an original first hash value.

22. A method for guaranteeing message integrity, comprising:

transmitting a transmission from a distribution center wherein the transmission includes a message together with an appended first value including an encrypted integrity second value h₀, said encrypted integrity second value h₀ being encrypted with a key based on a hash of said message;

decrypting said encrypted integrity second value h₀;

using said encrypted integrity second value h₀ together with stored integrity third values to perform an integrity calculation;

using the result of said integrity calculation for further processing;

receiving said transmission by a user device and computing an integrity fourth value K′

that depends on said transmission and at least one of a plurality of stored fifth values, where K′

selectively enables successful further processing of said message;

wherein said plurality of stored values include a predetermined integrity sixth value K=g₁^h0g₂^a mod M, where a is a digital signet, M is a public modulus, and g₁ and g₂ are unique seventh values.

23. The method of claim 22 wherein said encryption of h₀ is an RSA encryption and an RSA modulus is also transmitted.

24. The method of claim 22 wherein said integrity calculation is a digital signet calculation.

25. The method of claim 24 wherein results of said digital signet calculation are eighth values used in a content protection scheme.

26. The method of claim 22 wherein said message comprises a software program and associated data.

27. A method for conducting electronic commerce, comprising:

transmitting a transmission wherein the transmission includes a message and an appended first value from a distribution center;

receiving said transmission with a user device; and

computing with the user device an integrity value K′

that depends on said transmission and at least one of a plurality of stored second values where K′

selectively enables successful further processing of said message,

wherein said further processing completes an electronic commerce transaction, and said plurality of stored second values include a predetermined integrity value K=g₁^h0g₂^a mod M, where a is a digital signet, M is a public modulus, g₁ and g₂ are unique third values and h₀ is an original first hash value.

28. A method for guaranteeing message integrity, comprising:

transmitting a transmission wherein the transmission includes a message and an appended first value from a distribution center;

receiving said transmission with a user device;

computing an integrity value K′

that depends on said transmission and at least one of a plurality of stored values, where K′

selectively enables successful further processing of said message;

wherein said plurality of stored values include a predetermined integrity value K=g₁^h0g₂^a mod M, where a is a digital signet, M is a public modulus and g₁ and g₂ are unique values, and h₀ is an original first hash value.

29. The method of claim 28 wherein said appended first value includes a modulus pq and an authentication second value s.

30. The method of claim 29 wherein said authentication second value s is an encrypted version of the original first hash value h₀, said modulus pq, and a private RSA key z, where s=h₀^z mod pq.

31. The method of claim 30 wherein p and q are prime numbers and said modulus pq is a product of p and q, neither p and q being separately included in said transmission.

32. The method of claim 31 wherein p and q are selected by said distribution center such that a likelihood of a product (p−

1)(q−

1) and an odd-valued correct second hash value h₁ of said message having a greatest common denominator other than 1 is substantially zero, whereby h₁z=1 mod Φ

(pq), where Φ

(pq)=(p−

1)(q−

1), and h₁ is a public RSA key corresponding to said private RSA key z.

33. The method of claim 32 wherein said integrity value K′

equals g₁^xg₂^a mod M, where x=s^h mod pq, h is a third hash value of said message computed by said user device, M is a public modulus, a is a stored digital signet, and g₁ and g₂ are unique stored third values.

34. The method of claim 33 wherein said integrity value K′

is a fourth value required to enable successful further processing of said message if and only if h matches h₁, guaranteeing the integrity of said message.

35. The method of claim 32 wherein h₁ is forced to be odd, if initially even.

36. The method of claim 28 wherein said message comprises a software program.

37. The method of claim 28 wherein said message comprises a software program portion.

38. The method of claim 28 wherein said message comprises a software program that controls access to protected information.

39. The method of claim 28 wherein said message includes a first software program portion, and K′

includes a second software program portion, and said message and K′

together comprise a complete software program.

40. The method of claim 28 wherein said message comprises protected information intended for use only by authorized recipients.

41. The method of claim 40 wherein said protected information comprises at least one of:

a text file, an audio file, a video file, an application, and a database.

42. The method of claim 28 wherein said plurality of stored values are stored in tamper-resistant hardware.