Leak-resistant cryptographic method and apparatus

• US 6,304,658 B1
• Filed: 12/31/1998
• Issued: 10/16/2001
• Est. Priority Date: 01/02/1998
• Status: Expired due to Term

• Current Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Inventors: Kocher, Paul C., Jaffe, Joshua M.
• Primary Examiner(s): Swann, Tod
• Assistant Examiner(s): Darrow, Justin T.
• Application Number:
  US09/224,682
• Time in Patent Office: 1,020 Days
• Field of Search: 380/28, 380/30, 380/44, 380/45, 380/46, 380/47, 380/286, 713/172, 713/174, 713/191
• US Class Current: 380/30
• CPC Class Codes: G06F 21/556 involving covert channels, i.e. data leakage between processes inhibiting the analysis of circuitry or operation with measures against power attack G06F21/755
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• CPC Class Codes: G06F 21/755 with measures against power attack
• CPC Class Codes: G06F 2207/7219 Countermeasures against side channel or fault attacks
• CPC Class Codes: G06F 2207/7257 Random modification not requiring correction
• CPC Class Codes: G06F 7/723 Modular exponentiation G06F7/724, G06F7/727, G06F7/728 take precedence
• CPC Class Codes: G06Q 20/367 involving electronic purses or money safes
• CPC Class Codes: H04L 2209/56 Financial cryptography, e.g. electronic payment or e-cash
• CPC Class Codes: H04L 63/1441 Countermeasures against malicious traffic countermeasures against attacks on cryptographic mechanisms H04L9/002
• CPC Class Codes: H04L 9/002 Countermeasures against attacks on cryptographic mechanisms network architectures or network communication protocols for protection against malicious traffic H04L63/1441
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• CPC Class Codes: H04L 9/3013 involving the discrete logarithm problem, e.g. ElGamal or Diffie-Hellman systems
• CPC Class Codes: H04L 9/302 involving the integer factorization problem, e.g. RSA or quadratic sieve [QS] schemes
• CPC Class Codes: H04L 9/3247 involving digital signatures

Abstract

The present invention provides a method and apparatus for securing cryptographic devices against attacks involving external monitoring and analysis. A “self-healing” property is introduced, enabling security to be continually re-established following partial compromises. In addition to producing useful cryptographic results, a typical leak-resistant cryptographic operation modifies or updates secret key material in a manner designed to render useless any information about the secrets that may have previously leaked from the system. Exemplary leak-proof and leak-resistant implementations of the invention are shown for symmetric authentication, certified Diffie-Hellman (when either one or both users have certificates), RSA, ElGamal public key decryption, ElGamal digital signing, and the Digital Signature Algorithm.

Claims

1. A method for implementing RSA with the Chinese Remainder Theorem for use in a cryptographic system, with resistance to leakage attacks against said cryptographic system, comprising the steps of:

(a) obtaining a representation of an RSA private key corresponding to an RSA public key, said private key characterized by secret factors p and q;

(b) storing said representation of said private key in a memory;

(c) obtaining a message for use in an RSA cryptographic operation;

(d) computing a first modulus, corresponding to a multiple of p, where the value of said multiple of p and the value of said multiple of p divided by p are both unknown to an attacker of said cryptographic system;

(e) reducing said message modulo said first modulus;

(f) performing modular exponentiation on the result of step (e);

(g) computing a second modulus, corresponding to a multiple of q, where the value of said multiple of q and the value of said multiple of q divided by q are both unknown to an attacker of said cryptographic system;

(h) reducing said message modulo said second modulus;

(i) performing modular exponentiation on the result of step (h);

(j) combining the results of said steps (e) and (h) with a multiple of p<sup>−

1</sup> mod q to produce a result which, if operated on with an RSA public key operation using said RSA public key, yields said message; and

(k) repeating steps (c) through (j) a plurality of times using different values for said multiple of p and for said multiple of q and for said multiple of p<sup>−

1</sup> mod q.

2. The method of claim 1 where:

(i) said step (b) includes storing an exponent d_p of said RSA private key in said memory as a plurality of parameters;

(ii) an arithmetic function of at least one of said plurality of parameters is congruent to d_p, modulo (p−

1);

(iii) none of said parameters comprising said stored d_p is equal to d_p;

(iv) an exponent used in said step (f) is at least one of said parameters;

(v) at least one of said parameters in said memory changes with said repetitions of said steps (c) through (j).

3. The method of claim 2 where said plurality of parameters includes a first parameter equal to said d_p plus a multiple of phi(p), and also includes a second parameter equal to a multiple of phi(p), where phi denotes Euler'"'"'s totient function.

4. The method of claim 1 where the value of said multiple of p divided by p is equal to the value of said multiple of q divided by q.

5. The method of claim 1 where said multiple of p and said multiple of q used in said steps (c) through (j) are updated and modified in said memory after said step (b).

6. The method of claim 1 performed in a smart card.

7. A method for implementing RSA for use in a cryptographic system, with resistance to leakage attacks against said cryptographic system, comprising the steps of:

(a) obtaining an RSA private key corresponding to an RSA public key, said RSA public key having an RSA modulus n;

(b) storing said private key in a memory in a form whereby a secret parameter of said key is stored as an arithmetic combination of phi(x) and a first at least one key masking parameter, where

(i) an operand x in said phi(x) is an exact multiple of at least one factor of said modulus n of said RSA public key; and

(ii) said first key masking parameter is unknown to an attacker of said cryptosystem;

(iii) a representation of said first key masking parameter is stored in said memory; and

(iv) phi denotes Euler'"'"'s totient function;

(c) receiving a message;

(d) deriving an RSA input from said message;

(e) performing modular exponentiation to raise said RSA input to a power dependent on said secret parameter, modulo an RSA modulus stored in said memory, to produce an RSA result such that said RSA result raised to the power of the public exponent of said RSA public key, modulo the modulus of said RSA public key, equals said RSA input;

(f) modifying said stored secret parameter to produce a new secret parameter and a new masking parameter where;

(i) said new secret parameter is derived from at least said stored masking parameter and said stored secret parameter, and

(ii) said modification is performed in a manner such that an attacker with partial useful information about said stored secret parameter has less useful information about said new secret parameter;

(g) updating said memory with representations of said new secret parameter and said new masking parameter; and

(h) repeating said steps (d) through (g) a plurality of times, where the power used for each of said modular exponentiation steps (e) is different.

8. The method of claim 7 where said operand x in said phi(x) corresponds to said RSA modulus n of said RSA public key.

9. The method of claim 7 where said operand x in said phi(x) corresponds to a prime factor of said RSA modulus n of said RSA public key, and where said modular exponentiation of said step (e) is performed using the Chinese Remainder Theorem.

10. The method of claim 7 wherein all secret portions of said private key are stored as arithmetic combinations updated pursuant to said step (f).

11. The method of claim 10 applied to an RSA operation using the Chinese Remainder Theorem.

12. The method of claim 7 where said step (e) includes verifying that said RSA result raised to said power of said public exponent of said RSA key, modulo said modulus of said RSA public key, equals said RSA input.

13. A method for implementing exponential key exchange for use in a cryptographic system, with resistance to leakage attacks against said cryptographic system, comprising the steps of:

(a) obtaining, and storing in a memory, exponential key exchange parameters g and p, and a plurality of secret exponent parameters on which an arithmetic relationship may be computed to produce an exponent x;

(b) using a key update transformation to produce a plurality of updated secret exponent parameters while maintaining said arithmetic relationship thereamong;

(c) receiving a public value y from a party with whom said key exchange is desired;

(d) using said updated secret exponent parameters to perform a cryptographic computation yielding an exponential key exchange result z=y{circumflex over ( )}x mod p;

(e) using said result z to secure an electronic communication with said party; and

(f) performing said steps (b), (c), (d), and (e) in a plurality of transactions.

14. The method of claim 13 where each of said transactions involves a different said party.

15. The method of claim 13 where said arithmetic relationship is such that said exponential key exchange result is a product of certain of said secret exponent parameters, both before and after said step (b).

16. The method of claim 13 where said key update transformation includes choosing a random key update value r;

and where said step (b) includes multiplying one of said secret exponent parameters by r and another of said secret exponent parameters by an inverse of r, said multiplication being performed modulo phi(p), where phi is Euler'"'"'s totient function.

17. The method of claim 13 where said key update transformation includes choosing a random key update value r;

and where said step (b) includes adding r to one of said secret exponent parameters and subtracting r from another of said secret exponent parameters.

18. The method of claim 17 where said secret exponent parameters include two values x₁ and x₂ such that x₁+x₂ is congruent to x, modulo phi(p), where phi is Euler'"'"'s totient function, and where said step of performing said cryptographic computation yielding said exponential key exchange result includes computing z₁=y{circumflex over ( )}x₁ mod p, z₂=y{circumflex over ( )}x₂ mod p, and z=z₁z₂ mod p.

19. A method for securely managing and using a private key in a computing environment where information about said private key may leak to attackers, comprising the steps of:

(a) using a first private key, complementary to a public key, to perform first asymmetric cryptographic operation;

(b) reading at least a portion of said first private key from a memory;

(c) transforming said read portion of said first private key to produce a second private key;

(i) said second private key usable to perform a subsequent asymmetric cryptographic operation in a manner that remains complementary to said public key, and

(ii) said transformation enabling said asymmetric cryptographic operations to be performed in a manner such that information leaked during said first asymmetric cryptographic operation does not provide incrementally useful information about said second private key;

(d) obtaining a datum;

(e) using said second private key to perform said subsequent asymmetric cryptographic operation on said datum.

20. The method of claim 19 where said asymmetric cryptographic operation includes a digital signing operation.

21. The method of claim 20 where said signing operation is an RSA operation.

22. The method of claim 20 where said signing operation is an DSA operation.

23. The method of claim 20 where said signing operation is an ElGamal operation.

24. The method of claim 19 where said asymmetric cryptographic operation includes a decryption operation.

25. The method of claim 24 where said decryption operation is an RSA operation.

26. The method of claim 24 where said decryption operation is an ElGamal operation.

27. The method of claim 19 further comprising the step, after at least said step (c), of replacing said private key in said memory with said second private key.

28. The method of claim 19, performed in a smart card.

29. The method of claim 19, further comprising the steps of:

prior to at least said step (c), incrementing a counter stored in a nonvolatile memory and verifying that said counter has not exceeded a threshold value; and

after at least said step (c) has completed successfully, decreasing a value of said counter.

30. A method for performing cryptographic transactions while protecting a stored cryptographic key against compromise due to leakage attacks, comprising the steps of:

(a) retrieving a stored private cryptographic key stored in a memory, said stored key having been used in a previous cryptographic transaction;

(b) using a first cryptographic function to derive from said stored key an updated key, about which useful information about said stored key obtained through monitoring of leaked information is effectively uncorrelated to said updated key;

(c) replacing said stored key in said memory with said updated key;

(d) using an asymmetric cryptographic function, cryptographically processing a datum with said updated key; and

(e) sending said cryptographically processed datum to an external device having a public key corresponding to said stored key.

31. The method of claim 30 where said stored key includes a first plurality of parameters, and where said updated key includes a second plurality of parameters.

32. The method of claim 31 where no secret value within said first plurality of parameters is included within said second plurality of parameters.

33. The method of claim 32 where said first plurality of parameters is different than said second plurality of parameters, yet a predetermined relationship among said first plurality of parameters is also maintained among said second plurality of parameters.

34. The method of claim 33 where said relationship among said plurality of parameters is an arithmetic function involving at least two of said plurality of parameters.

35. The method of claim 34 where said arithmetic function is the sum of said parameters.

36. The method of claim 34 where said relationship includes a bitwise combination of said parameters.

37. The method of claim 36 where said bitwise combination is an exclusive OR.

38. The method of claim 30 where said step (b) includes using pseudorandomness to derive said updated key.

39. A method for implementing a private key operation for an asymmetric cryptographic system with resistance to leakage attacks against said cryptographic system, comprising the steps of:

(a) encoding a portion of a private key as at least two component parts, such that an arithmetic function of said parts yields said portion;

(b) modifying said component parts to produce updated component parts, but where said arithmetic function of said updated parts still yields said private key portion;

(c) obtaining a message for use in an asymmetric private key cryptographic operation;

(d) separately applying said component parts to said message to produce an intermediate result;

(e) deriving a final result from said intermediate result such that said final result is a valid result of applying said private key to said message; and

(f) repeating steps (b) through (e) a plurality of times.

40. The method of claim 39 where said private key portion includes an exponent, and where said intermediate result represents the result of raising said message to the power of said exponent, modulo a second key portion.

41. The method of claim 40 where said private key operation is configured for use with an RSA cryptosystem.

42. The method of claim 40 where said private key operation is configured for use with an ElGamal cryptosystem.

43. The method of claim 39 where said private key operation is configured for use with a DSA cryptosystem.

44. The method of claim 43 where said private key is represented by secret parameters a_k and k whose product, modulo a predetermined DSA prime q for said private key, yields said private key portion.

45. The method of claim 39 implemented in a smart card.

46. The method of claim 39 where said private key is configured for use with an elliptic curve cryptosystem.

47. A method for performing cryptographic transactions in a cryptographic token while protecting a stored cryptographic key against compromise due to leakage attacks, including the steps of:

(a) retrieving said stored key from a memory;

(b) cryptographically processing said key, to derive an updated key, by executing a cryptographic update function that;

(i) prevents partial information about said stored key from revealing useful information about said updated key, and

(ii) also prevents partial information about said updated key from revealing useful information about said stored key;

(c) replacing said stored key in said memory with said updated key;

(d) performing a cryptographic operation using said updated key; and

(e) repeating steps (a) through (d) a plurality of times.

48. The method of claim 47 where said cryptographic update function of said step (b) includes a one-way hash operation.

49. The method of claim 47 where said cryptographic operation of said step (d) is a symmetric cryptographic operation;

and comprising the further step of sending a result of said cryptographic operation to a party capable of rederiving said updated key.

50. The method of claim 47 further comprising the step, prior to said step (a), of receiving from a second party a symmetric authentication code and a parameter;

and said where said step (b) includes iterating a cryptographic transformation a number of times determined from said parameter; and

where said step (d) includes performing a symmetric message authentication code verification operation.

51. The method of claim 49 where said step (d) of performing said cryptographic operation includes using said updated key to encrypt a datum.

52. The method of claim 49 where said updated key contains unpredictable information such that said updated key is not stored in its entirety anywhere outside of said cryptographic token;

and where the result of said step (d) is independent of said unpredictable information.

53. The method of claim 47 where said step (c) of replacing said stored key includes:

(i) explicitly erasing a region of said memory containing said stored key; and

(ii) strong said updated key in said region of memory.

54. The method of claim 47 performed within a smart card.