Payment smart cards with hierarchical session key derivation providing security against differential power analysis and other attacks
First Claim
1. A method for cryptographically authenticating a payment transaction conducted by a chip card configured for use with a compatible transaction verifier, comprising the steps performed by said chip card of:
- (a) retrieving from a nonvolatile memory in said chip card a transaction counter, and an intermediate key state corresponding to said transaction counter;
(b) deriving a new intermediate key by applying a cryptographic update operation;
(i) thereby preventing partial information about a plurality of predecessor intermediate keys from being combined to determine said new intermediate key;
(c) incrementing said transaction counter and updating said intermediate key state in said nonvolatile memory;
(d) using said new intermediate key to compute a cryptographic value authenticating at least an amount of a payment transaction; and
(e) outputting to an external device said transaction counter and said cryptographic authentication value;
where said transaction verifier, with knowledge of said counter and an initial key state for said chip card, will re-derive said new intermediate key used by said chip card in (d) by applying one or more key transformation steps, the maximum number of such step(s) depending logarithmically on a maximum value for said transaction counter.
1 Assignment
0 Petitions
Accused Products
Abstract
Chip cards are used to secure credit and debit payment transactions. To prevent fraudulent transactions, the card must protect cryptographic keys used to authenticate transactions. In particular, cards should resist differential power analysis and/or other attacks. To address security risks posed by leakage of partial information about keys during cryptographic transactions, cards may be configured to perform periodic cryptographic key update operations. The key update transformation prevents adversaries from exploiting partial information that may have been leaked about the card'"'"'s keys. Update operations based on a hierarchical structure can enable efficient transaction verification by allowing a verifying party (e.g., an issuer) to derive a card'"'"'s current state from a transaction counter and its initial state by performing one operation per level in the hierarchy, instead of progressing through all update operations performed by the card.
225 Citations
22 Claims
-
1. A method for cryptographically authenticating a payment transaction conducted by a chip card configured for use with a compatible transaction verifier, comprising the steps performed by said chip card of:
-
(a) retrieving from a nonvolatile memory in said chip card a transaction counter, and an intermediate key state corresponding to said transaction counter; (b) deriving a new intermediate key by applying a cryptographic update operation; (i) thereby preventing partial information about a plurality of predecessor intermediate keys from being combined to determine said new intermediate key; (c) incrementing said transaction counter and updating said intermediate key state in said nonvolatile memory; (d) using said new intermediate key to compute a cryptographic value authenticating at least an amount of a payment transaction; and (e) outputting to an external device said transaction counter and said cryptographic authentication value; where said transaction verifier, with knowledge of said counter and an initial key state for said chip card, will re-derive said new intermediate key used by said chip card in (d) by applying one or more key transformation steps, the maximum number of such step(s) depending logarithmically on a maximum value for said transaction counter. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method for authenticating chip card transactions, comprising the steps of:
-
(a) retrieving a transaction counter and a stored intermediate key state from a nonvolatile memory in said chip; (b) applying a hierarchical key update operation to said intermediate key state to produce a successor intermediate key state from among a sequence of intermediate key states, where; (i) said sequence includes a hierarchy of successive levels, where each lower level of said hierarchy contains at least twice as many keys as each predecessor level; (ii) each key in each said lower level is a predetermined function of at least one parent key in at least one said predecessor level; (iii) said key update operation includes (A) obtaining at least one parent key to a key included in said stored intermediate key state, (B) applying a key update transformation to derive a new lower-level key from said at least one parent key; (c) updating said intermediate key state in said nonvolatile memory with a result of said key update operation; (d) using said updated intermediate key state to compute a value cryptographically authenticating a transaction involving said chip card; (e) transmitting said cryptographic authentication value to a third party for verification. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18)
-
-
19. A chip card for cryptographically authenticating a payment transaction conducted by said chip card configured for use with a compatible transaction verifier, said chip card comprising:
-
(a) a microprocessor; (b) a nonvolatile memory including a transaction counter, and an intermediate key state corresponding to said transaction counter; (c) a memory containing program logic configured; (i) to retrieve from said nonvolatile memory said transaction counter and said intermediate key state; (ii) to derive a new intermediate key by applying a cryptographic update operation; (A) thereby preventing partial information about a plurality of predecessor intermediate keys from being combined to determine said new intermediate key; (iii) to increment said transaction counter and updating said intermediate key state in said nonvolatile memory; (iv) to use said new intermediate key to compute a cryptographic value authenticating at least an amount of a payment transaction; and (v) to output to an external device said transaction counter and said cryptographic authentication value; where said transaction verifier, with knowledge of said counter and an initial key state for said chip card, will re-derive said new intermediate key used by said chip card in (iv) by applying one or more key transformation steps, the maximum number of such step(s) depending logarithmically on a maximum value for said transaction counter.
-
-
20. A computer-readable medium for cryptographically authenticating a payment transaction conducted by a chip card configured for use with a compatible transaction verifier, said chip card comprising:
-
(a) a microprocessor; (b) a nonvolatile memory including a transaction counter, and an intermediate key state corresponding to said transaction counter; (c) a memory containing program logic configured; (i) to retrieve from said nonvolatile memory said transaction counter and said intermediate key state; (ii) to derive a new intermediate key by applying a cryptographic update operation; (A) thereby preventing partial information about a plurality of predecessor intermediate keys from being combined to determine said new intermediate key; (iii) to increment said transaction counter and updating said intermediate key state in said nonvolatile memory; (iv) to use said new intermediate key to compute a cryptographic value authenticating at least an amount of a payment transaction; and (v) to output to an external device said transaction counter and said cryptographic authentication value; where said transaction verifier, with knowledge of said counter and an initial key state for said chip card, will re-derive said new intermediate key used by said chip card in (iv) by applying one or more key transformation steps, the maximum number of such step(s) depending logarithmically on a maximum value for said transaction counter.
-
-
21. An automated method for authenticating a chip card transaction, comprising the steps of:
-
(a) receiving a transaction counter and a cryptographic value purporting to authenticate said transaction; (b) obtaining an initial key corresponding to said chip card; (c) applying a plurality of key update transformations determined by said transaction counter to produce an intermediate key; and (d) using said intermediate key to determine the validity of said cryptographic value; where the maximum number of key update operations depends logarithmically on a maximum value for said transaction counter. - View Dependent Claims (22)
-
Specification