Leak-Resistant Cryptographic Token

Abstract

Chip cards are used to secure credit and debit payment transaction. To prevent fraudulent transaction, 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.

1 . A portable cryptographic token for deriving cryptographic authentication codes for securing transactions between a user of said token and a server, and which limits the number of times secret keys are used so as to provide protection against external monitoring attacks, compromising:
 (a) a key cache configured to include a top-level key, a plurality of intermediate-level keys, and a lowest-level key;   (b) at least one key updater configured to receive as an input a key value for a particular level, and to operate on that key using a block cipher to generate a value for a key one level below said input key's level;   (c) a timer;   (d) said token being configured to use said at least one key updater and said timer to derive periodically:
 (i) a new lowest-level key value, where said value of a second-to-lowest level key from said cache is an input to said key updater; 
 (ii) after a plurality of updates to said lowest-level key value, a new second-to-lowest level key value, where said value of a third-to-lowest-level key from said cache is an input to said key updater; 
 (iii) after a plurality of updates to said second-lowest-level key, a new third-to-lowest level key value, where said value of a fourth-to-lowest-level key from said cache is an input to said key updater; 
   
       said token being usable in securing operations with a server, based on values derived from said lowest-level key values. 
     
     
         2 . The device of  claim 1  in combination with said server, where said server is configured to authenticate said token by:
 (a) obtaining a value of said token's key index value to be tried; 
 (b) obtaining said token's top-level key value; 
 (c) re-deriving a second-to-highest level key value, corresponding to said key index value being tried, by performing at least one key update operation, where said top-level key value is an input to said key update operation; 
 (d) re-deriving a succession of child key values down to a lowest-level key value, by performing a succession of key update operations, where each child key's parent key is an input to said key update operation deriving said child key; 
 (e) using a value derived from said re-derived lowest-level key value to attempt to authenticate said token; and 
 (f) if said authentication attempt fails, repeating said steps (c) through (e) with one or more key index values close to said key index value originally tried in (a). 
 
     
     
         3 . The device of  claim 1  where said token's key index value is produced using said timer. 
     
     
         4 . The device of  claim 1  where said values derived from said lowest-level key values are produced by encrypting. 
     
     
         5 . The device of  claim 1  where said values derived from said lowest-level key values are produced by hashing. 
     
     
         6 . The device of  claim 2  where said candidate for said token's key index value is obtained directly from said token. 
     
     
         7 . The device of  claim 2  where said candidate for said token's key index value is obtained indirectly. 
     
     
         8 . A method of deriving cryptographic authentication codes to secure transactions between a user of said token and a server while providing protection against external monitoring attacks in a token, said method implemented in a token, said token including a key cache containing a plurality of keys from a highest level to a lowest level, where said number of levels is at least 4, comprising:
 (a) using a timer to update a key index value;   (b) performing at least one key update operation to update at least a portion of said key cache, where:
 (i) each key update operation includes a block cipher operation; 
 (ii) each key update operation uses a parent key to derive a child key; and 
 (iii) only those keys affected by the change in key index value are updated; and 
   (c) deriving a value from said lowest level key to secure a transaction with a server.   
     
     
         9 . The method of  claim 8  where said server is configured to authenticate said token by:
 (a) obtaining a value of said token's key index value to be tried; 
 (b) obtaining said token's top-level key value; 
 (c) re-deriving a second-to-highest level key value, corresponding to said key index value being tried, by performing at least one key update operation, where said top-level key value is an input to said key update operation; 
 (d) re-deriving a succession of child key values down to a lowest-level key value, by performing a succession of key update operations, where each child key's parent key is an input to said key update operation deriving said child key; 
 (e) using a value derived from said re-derived lowest-level key value to attempt to authenticate said token; and 
 (f) if said authentication attempt fails, repeating said steps (c) through (e) with one or more key index values close to said key index value originally obtained in (a). 
 
     
     
         10 . The method of  claim 8  where said token's key index value is produced using said timer. 
     
     
         11 . The method of  claim 8  where said values derived from said lowest-level key values are produced by encrypting. 
     
     
         12 . The method of  claim 8  where said values derived from said lowest-level key values are produced by hashing. 
     
     
         13 . The method of  claim 9  where said candidate for said token's key index value is obtained directly from said token. 
     
     
         14 . The method of  claim 9  where said candidate for said token's key index value is obtained indirectly. 
     
     
         15 . A method for a server to secure transactions involving a user of a cryptographic token, the token being configured to derive and cache a plurality of secret keys at different levels while limiting the number of times each secret key is used so as to provide protection against external monitoring attacks, and the token being further configured to produce (from the lowest-level keys) cryptographic authentication codes for securing said transactions, the method comprising:
 (a) obtaining a key index value to be tried;   (b) obtaining a top-level key for said token;   (c) re-deriving a second-to-highest key, corresponding to said key index value, by performing at least a block cipher operation using said top-level key;   (d) re-deriving a succession of child key values, at successively lower levels, by performing at least a block cipher operation using a parent key of each child key being derived, until a lowest-level key is obtained; and   (e) attempting to authenticate said token using a value derived from said lowest-level key, and if said authentication attempt fails, repeating said re-derivations in (c) and (d) with a key index close to said key index value originally obtained in (a).   
     
     
         16 . The method of  claim 15  where said value derived from said lowest-level key is produced by encrypting. 
     
     
         17 . The method of  claim 15  where said value derived from said lowest-level key is produced by hashing. 
     
     
         18 . The method of  claim 15  where said key index value to be tried is obtained directly from said token. 
     
     
         19 . The method of  claim 15  where said key index value to be tried is obtained indirectly. 
     
     
         20 . The method of  claim 19  where said key index value to be tried is produced using a timer.