Leak-resistant cryptographic payment smartcard

• US 7,506,165 B2
• Filed: 04/29/2002
• Issued: 03/17/2009
• Est. Priority Date: 01/02/1998
• Status: Expired due to Fees

• Current Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Inventors: Kocher, Paul C., Jaffe, Joshua M.
• Primary Examiner(s): Barron, Jr.; Gilberto
• Assistant Examiner(s): Nobahar; Abdulhakim
• Application Number:
  US10/136,012
• Publication Number:
  US 20030028771A1
• Time in Patent Office: 2,514 Days
• Field of Search: 713/155, 713/172, 713/174, 713/194, 713/340, 713/159, 713/185, 705/75, 705/41, 705/65, 705/66, 380/75, 726/9, 726/20
• US Class Current: 713/194
• 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

We disclose methods and apparatuses 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 are shown for symmetric authentication, certified Diffie-Hellman (when either one or both users have certificates), RSA, ElGamal public key decryption.

Claims

1. A method for performing a plurality of secure payment transactions using a smartcard, where said smartcard and a verifier of said payment transaction share an initial secret starting key value, comprising:

(a) initializing said smartcard, where said initializing includes;

(i) storing said starting key value in a nonvolatile key storage memory location; and

(ii) storing an initial value in a nonvolatile transaction counter memory location;

(b) for each of a plurality of payment transactions;

(i) computing an updated key value;

(x) by cryptographically transforming at least said stored key value and said transaction counter;

(y) where said transforming at least obscures partial information about said stored key, thereby deterring attacks that combine partial information leaked in said plurality of transactions;

(ii) updating said nonvolatile memory locations including;

(x) updating said key storage location with said updated key value; and

(y) incrementing said value of said transaction counter location;

(iii) using said updated key value to compute a message authentication code authenticating said transaction; and

(iv) sending said computed message authentication code and said transaction counter to a third party for use in verifying said payment transaction.

2. The method of claim 1 where:

(1) after step (a) and prior to one of said payment transactions in step (b), said smartcard receives an authentication code and a parameter from said third party, and verifies said authentication code; and

(2) said step (b)(i) includes performing one or more cryptographic key update operations based on said received parameter.

3. A computer readable memory containing a program for performing a plurality of secure payment transactions between a tamper-resistant device and a verifier that share an initial secret starting key value, comprising:

(a) logic instructions for computing an updated key value for a subsequent transaction;

(i) by cryptographically transforming at least a key value and a transaction counter value stored in nonvolatile memory locations in said tamper-resistant device;

(ii) where said transforming at least obscures partial information about said stored key, thereby deterring attacks that combine partial information leaked in said plurality of transactions;

(b) logic instructions for updating said nonvolatile memory locations including;

(i) replacing said key value with said updated key value; and

(ii) incrementing said transaction counter value;

(c) logic instructions for using said updated key value to compute a message authentication code authenticating said transaction; and

(d) logic instructions for sending said computed message authentication code and said transaction counter to a third party for use in verifying said payment transaction.

4. The computer readable memory of claim 3 further comprising:

(1) logic instructions for receiving an authentication code and an updated value of said transaction counter from said third party, and verifying said authentication code;

wherein

(2) said (b)(i) includes logic instructions for performing one or more cryptographic key update operations based on said received transaction counter.

5. A smartcard for performing a secure payment transaction, comprising:

(a) a microprocessor;

(b) a nonvolatile memory area initially configured to store a secret parameter;

(c) a nonvolatile memory area initially configured to store an indexing indicia;

(d) a memory storing logic instructions capable of being executed using said processor to;

(i) compute an updated secret parameter for a subsequent transaction by cryptographically transforming at least said stored secret parameter and said indexing indicia, where said transforming at least obscures partial information about said stored secret parameter;

(ii) replace said stored secret parameter with said updated value thereof;

(iii) compute a value authenticating transaction information by cryptographically transforming at least said updated secret parameter and said transaction information; and

(e) an output interface configured to transmit representations of said value and said indexing indicia to a payment transaction verifier.

6. The smartcard of claim 5 wherein:

(1) said memory further stores logic instructions capable of being executed using said processor to receive an authentication code and an updated value of said indexing indicia from said payment transaction verifier for use m said (d)(i), and verifies said authentication code; and

(2) said (d)(i) includes logic instructions for performing one or more secret parameter update operations based on said received indexing indicia.