Leak-resistant cryptographic method and apparatus

• US 6,381,699 B2
• Filed: 12/13/2000
• Issued: 04/30/2002
• 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): Peeso, Thomas R.
• Assistant Examiner(s): Darrow, Justin T.
• Application Number:
  US09/737,182
• Publication Number:
  US 20010002486A1
• Time in Patent Office: 503 Days
• Field of Search: 713/172, 713/174, 713/176, 713/340, 705/65, 705/75, 705/76, 380/29, 380/30
• US Class Current: 713/172
• 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 cryptographic token configured to perform cryptographic operations using a secret key in a secure manner, comprising:

(a) an interface configured to receive power from a source external to said token;

(b) a memory containing said secret key;

(c) a processor;

(i) configured to receive said power delivered via said interface;

(ii) configured to perform said processing using said secret key from said memory;

(d) said token having a power consumption characteristic;

(i) that is externally measurable; and

(ii) that varies over time in a manner measurably correlated with said cryptographic operations; and

(e) a source of unpredictable information configured for use in said cryptographic operations to make determination of said secret key infeasible from external measurements of said power consumption characteristic.

2. The cryptographic token of claim 1, in the form of a secure microprocessor.

3. The cryptographic token of claim 1, in the form of a smart card.

4. The cryptographic token of claim 3, wherein said cryptographic operations performed by said smart card enable a holder thereof to decrypt an encrypted communication received via a computer network.

5. The cryptographic token of claim 3, wherein said smart card is configured to store value in an electronic cash scheme.

6. The cryptographic token of claim 5, wherein said cryptographic operations include authenticating that a balance of said stored value has been decreased.

7. The cryptographic token of claim 1, wherein said cryptographic operations include asymmetric private key operations.

8. The cryptographic token of claim 7 wherein said cryptographic operations include exponential key agreement operations.

9. The cryptographic token of claim 7, wherein said cryptographic operations include DSA signing operations.

10. The cryptographic token of claim 7, wherein said cryptographic operations include ElGamal private key operations.

11. The cryptographic token of claim 7, wherein said asymmetric private key operations include RSA private key operations.

12. The cryptographic token of claim 11 wherein said private key operations include Chinese Remainder Theorem operations.

13. The cryptographic token of claim 1, wherein said cryptographic operations include symmetric encryption operations.

14. The cryptographic token of claim 1, wherein said cryptographic operations include symmetric decryption operations.

15. The cryptographic token of claim 1, wherein said cryptographic operations include symmetric authentication operations using said secret key.

16. The cryptographic token of claim 1, wherein said cryptographic operations include authenticating a payment.

17. The cryptographic token of claim 1, wherein said cryptographic operations include securing a broadcast communications signal.

18. The cryptographic token of claim 17, wherein said cryptographic operations include decrypting a satellite broadcast.