Cryptographic token with leak-resistant key derivation

• US 9,852,572 B2
• Filed: 09/26/2011
• Issued: 12/26/2017
• Est. Priority Date: 07/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.
• Primary Examiner(s): Wu, Rutao
• Assistant Examiner(s): Mandel, Monica A
• Application Number:
  US13/245,054
• Publication Number:
  US 20120017089A1
• Time in Patent Office: 2,283 Days
• Field of Search: 705 64, 713161, 713172
• CPC Class Codes: G06F 2207/7219 Countermeasures against side channel or fault attacks
• CPC Class Codes: G06Q 20/341 Active cards, i.e. cards including their own processing means, e.g. including an IC or chip
• CPC Class Codes: G06Q 20/40975 using encryption therefor
• CPC Class Codes: G07F 7/1008 Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system
• CPC Class Codes: H04L 9/003 for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA]
• CPC Class Codes: H04L 9/0625 with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying

Abstract

Methods and apparatuses for increasing the leak-resistance of cryptographic systems are disclosed. A cryptographic token maintains secret key data based on a top-level key. The token can produce updated secret key data using an update process that makes partial information that might have previously leaked to attackers about the secret key data no longer usefully describe the new updated secret key data. By repeatedly applying the update process, information leaking during cryptographic operations that is collected by attackers rapidly becomes obsolete. Thus, such a system can remain secure against attacks involving analysis of measurements of the device'"'"'s power consumption, electromagnetic characteristics, or other information leaked during transactions. Transactions with a server can be secured with the token.

Claims

1. A portable cryptographic hardware token for deriving cryptographic authentication codes for securing transactions, said token operable to limit the number of times secret keys are used, thereby providing protection against external monitoring attacks, comprising:

(a) a memory configured to store 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) a processor configured to perform a key update operation, wherein said key update operation comprises

communicating with said memory,

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 key value using a block cipher to generate a value for a key one level below said particular level; and

(c) a timer;

wherein said processor is further configured to use said key update operation and said timer to periodically derive new key values comprising;

(i) 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) 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; and

(iii) at least one new value for said third-to-lowest level key, where said stored 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 wherein said token is operable to secure a transaction with a server based on a value derived from said at least one new value for said lowest-level key.

2. The portable cryptographic hardware token of claim 1 having a key index value produced using said timer.

3. The portable cryptographic hardware token of claim 1, where said value derived from said at least one new value for said lowest-level key is produced by encryption.

4. The portable cryptographic hardware token of claim 1, where said value derived from said at least one new value for said lowest-level key is produced by hashing.

5. A system comprising the portable cryptographic hardware token of claim 1 in combination with said a server, wherein said server is configured to authenticate said token by:

(a) obtaining a candidate key index value for said token;

(b) obtaining said token'"'"'s top-level key value;

(c) deriving a server-side second-to-top level key value, corresponding to said candidate key index value, by performing a server-side key update operation, where said token'"'"'s top-level key value is an input to said server-side key update operation;

(d) deriving a succession of server-side key values, including a server-side lowest-level key value, by performing a succession of server-side key update operations,

where each of said succession of server-side key values is associated with a different one of a plurality of server-side levels, and

where each server-side key value for a particular server-side level above said lowest-level is an input to a corresponding one of said succession of server-side key update operations for deriving a server-side key value one level below said particular server-side level;

(e) using a value derived from said server-side lowest-level key value during an attempt to authenticate said token; and

(f) if said attempt to authenticate said token fails, repeating (c) through (e) with another candidate key index value.

6. The system of claim 5, wherein said server is further configured to obtain said candidate key index value directly from said token.

7. The system of claim 5, wherein said server is further configured to obtain said candidate key index value indirectly.

8. 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.

9. The method of claim 8, having a key index value produced using said timer.

10. The method of claim 8, where said value derived from said at least one new value for said lowest-level key is produced by encryption.

11. The method of claim 8, where said value derived from said at least one new value for said lowest-level key is produced by hashing.

12. The method of claim 8, further comprising:

authenticating said token by said server when securing a transaction with said server by;

(a) obtaining a candidate key index value for said token;

(b) obtaining said token'"'"'s top-level key value;

(c) deriving a server-side second-to-top level key value corresponding to said candidate key index value, by performing a server-side key update operation, where said token'"'"'s top-level key value is an input to said server-side key update operation;

(d) deriving a succession of server-side key values, including a server-side lowest-level key value, by performing a succession of server-side key update operations,

where each of said succession of server-side key values is associated with a different one of a plurality of server-side levels, and

where each server-side key value for a particular server-side level above said lowest-level is an input to a corresponding one of said succession of server-side key update operations for deriving a server-side key value one level below said particular server-side key level;

(e) attempting to authenticate said token using a value derived from said server-side lowest-level key value; and

(f) if said attempt to authenticate said token fails, repeating steps (c) through (e) with another candidate key index value.

13. The method of claim 12, wherein said server obtains said candidate key index value directly from said token.

14. The method of claim 12, where said server obtains said candidate key index value indirectly.

15. 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.

16. The method of claim 15 where said server is configured to authenticate said token by:

(a) obtaining a candidate key index value for said token;

(b) obtaining a top-level key value for said token;

(c) deriving a second-to-top-level key value, corresponding to said candidate value, by performing at least one server-side key update operation, where said top-level key value is an input to said server-side key update operation;

(d) deriving a succession of child key values by performing a succession of server-side key update operations to derive a lowest-level server key value, where a parent key value is an input to each of said server-side key update operations deriving said succession child key values;

(e) using a value derived from said lowest-level server key value during an attempt to authenticate said token; and

(f) if said attempt to authenticate said token fails, repeating said steps (c) through (e) with one or more new candidate values.

17. The method of claim 15 where said token'"'"'s key index value is produced using said timer.

18. The method of claim 15 where said value derived from said lowest-level key value is produced by encrypting.

19. The method of claim 15 where said value derived from said lowest-level key value is produced by hashing.

20. The method of claim 16 where said candidate key index value is obtained directly from said token.

21. The method of claim 16 where said candidate key index value is obtained indirectly.