Cryptographic token with leak-resistant key derivation

A method for deriving cryptographic authentication codes in a portable cryptographic hardware token for securing transactions, where said method limits the number of times secret keys are used, thereby providing protection against external monitoring attacks, comprising:

• (a) storing in a memory a value for each of a plurality of keys, each of said plurality of keys associated with a different one of a plurality of levels, said plurality of keys comprising a top-level key, a plurality of intermediate-level keys, and a lowest-level key, said plurality of intermediate-level keys comprising at least
• a second-to-lowest level key,
• a third-to-lowest level key, and
• a fourth-to-lowest level key;
• (b) performing a key update operation in a processor configured to communicate with said memory, wherein said key update operation comprises receiving as an input from said memory a stored value of one of said keys at a particular one of said plurality of levels, and operating on said received value in said processor using a block cipher to generate a value for a key one level below said particular level;
• (c) periodically deriving new key values using said key update operation and a timer, said periodically deriving comprising:
• (i) deriving at least one new value for said lowest-level key where said stored value of said second-to-lowest level key is an input to said key update operation;
• (ii) deriving at least one new value for said second-to-lowest level key where said stored value of said third-to-lowest level key is an input to said key update operation, and where said at least one new value for said second-to- lowest level key is derived after deriving said at least one new value for said lowest-level key;
• (iii) deriving at least one new value for said third-to-lowest level key where said value of said fourth-to-lowest level key is an input to said key update operation, and where said at least one new value for said third-to-lowest level key is derived after deriving said at least one new value for said second-to-lowest level key;
• and
• (d) deriving a value from said at least one new value for said lowest-level key for securing a transaction with a server.

A method of deriving cryptographic authentication codes to secure transactions between a user of a hardware token and a server while providing protection against external monitoring attacks in said token, said token including a memory containing a plurality of key values from a top-level to a lowest-level, where said number of levels is at least four, comprising:

• in said token,
• (a) using a timer to update a key index value;
• (b) performing at least one key update operation based on said key index value to update at least a portion of said memory, where:
• (i) each key update operation in said at least one key update operation includes a block cipher operation;
• (ii) each key update operation in said at least one key update operation uses a parent key value as an input to derive a child key value at a level below said parent key value, where at least one child key value corresponds to the lowest-level key value;
• and
• (iii) only the key values affected by a change in said key index value are updated;
• and
• (c) deriving a value from said lowest-level key value to secure a transaction with a server.