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

• US 20040064695A1
• Filed: 09/26/2002
• Published: 04/01/2004
• Est. Priority Date: 09/26/2002
• Status: Active Grant

• Current Assignee: Atreus Labs LLC
• Original Assignee: International Business Machines Corporation
• Inventors: Lotspiech, Jeffrey Bruce
• Granted Patent: US 7,240,200 B2
• Time in Patent Office: Days
• US Class Current: 713/168
• 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, unique hardware-based secret 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 message and at least one appended value; and

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

that depends on said transmission and at least one stored secret value, where K′

selectively enables successful further processing of said message.

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

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

4. The system of claim 3 wherein said modulus pq is a product of two prime numbers p and q, neither of said prime numbers 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 the likelihood of a product (p−

1)(q−

1) and an odd-valued correct hash value h₁ of said transmitted 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 said correct hash value 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₁^x g₂^a mod M, where x=s^h mod pq, h is a hash value of said message computed by said user device in a similar manner as said correct hash value h₁, M is a public modulus, a is a stored digital signet, and g₁ and g₂ are preferably unique stored secret values.

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 said hash value h matches said correct hash value h₁, guaranteeing the integrity of said message.

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

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

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

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

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

together comprise a complete software program.

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

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

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

14. The system of claim 5 wherein said correct hash value h₁ is forced to be odd, if initially even, by predetermined means.

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

16. The system of claim 1 wherein said secret values include a predetermined integrity value K=g₁^h0 g₂^a mod M, where a is a digital signet, M is a public modulus, and g₁ and g₂ are preferably unique secret values.

17. A system for guaranteeing message integrity, comprising:

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

a distribution center that transmits a message and an encryption of said additional integrity value h₀, where said encryption uses a key based on a hash of said message.

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

19. The system of claim 18 wherein said digital signets allow the calculation of values used in a content protection scheme.

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

21. The system of claim 17 wherein said message comprises a software program and associated data.

22. A computer program product for guaranteeing message integrity, comprising a computer-readable medium tangibly embodying computer-executable code means thereon, said code means including:

a first code means for transmitting a message and at least one appended value from a distribution center;

a second code means for receiving said transmission with a user device; and

a third code means for computing an integrity value K′

that depends on said transmission and at least one stored secret value, where K′

selectively enables successful further processing of said message.

23. A method for guaranteeing message integrity, comprising:

transmitting a message together with an encrypted integrity value h₀, said encrypted integrity value h₀ being encrypted with a key based on the hash of said message;

decrypting said encrypted integrity value h₀;

using said integrity value h₀ together with stored integrity values to perform an integrity calculation; and

using the result of said integrity calculation for further processing.

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

25. The method of claim 23 wherein said integrity calculation is a digital signet calculation.

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

27. The method of claim 23 wherein said message comprises a software program and associated data.

28. A method for conducting electronic commerce, comprising:

transmitting a message and at least one appended value from a distribution center;

receiving said transmission with a user device; and

computing an integrity value K′

that depends on said transmission and at least one stored secret value, where K′

selectively enables successful further processing of said message,

wherein said further processing completes an electronic commerce transaction.

29. A method for guaranteeing message integrity, comprising:

transmitting a message and at least one appended 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 stored value, where K′

selectively enables successful further processing of said message.

30. The method of claim 29 wherein said appended values include a modulus pq and an authentication value s.

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

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

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

1)(q−

1) and an odd-valued correct hash value h₁ of said transmitted 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 said correct hash value h₁ is a public RSA key corresponding to said private RSA key z.

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

equals g₁^x g₂^a mod M, where x=s^h mod pq, h is a hash value of said message computed by said user device in a similar manner as said correct hash value h₁, M is a public modulus, a is a stored digital signet, and g₁ and g₂ are preferably unique stored secret values.

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

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

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

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

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

39. The method of claim 29 wherein said message includes a software program portion, and said integrity value K′

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

together comprise a complete software program.

40. The method of claim 29 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, a database.

42. The method of claim 33 wherein said correct hash value h₁ is forced to be odd, if initially even, by predetermined means.

43. The method of claim 29 wherein said secret values are stored in tamper-resistant hardware.

44. The method of claim 29 wherein said secret values include a predetermined integrity value K=g₁^h0 g₂^a mod M, where a is a digital signet, M is a public modulus, and g₁ and g₂ are preferably unique secret values.