CRYPTOGRAPHIC TOKEN WITH LEAK-RESISTANT KEY DERIVATION

• US 20120017089A1
• Filed: 09/26/2011
• Published: 01/19/2012
• Est. Priority Date: 07/02/1998
• Status: Active Grant

• Current Assignee: Paul C. Kocher
• Original Assignee: Paul C. Kocher
• Inventors: KOCHER, PAUL C.
• Granted Patent: US 9,852,572 B2
• Time in Patent Office: Days
• US Class Current: 713/172
• 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 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, comprising:

(a) a key cache configured to include a top-level key, a plurality of intermediate-level keys, and a lowest-level key, each key having a key value;

(b) at least one key updater configured to receive as an input the key value for a particular level, and to operate on that key value using a block cipher to generate a value for a key one level below said particular 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 transactions with the server based on values derived from said lowest-level key values.

2. The device of claim 1 where said token'"'"'s key index value is produced using said timer.

3. The device of claim 1 where said values derived from said lowest-level key values are produced by encrypting.

4. The device of claim 1 where said values derived from said lowest-level key values are produced by hashing.

5. The device of claim 1 in combination with said server, where said server is configured to authenticate said token by:

(a) obtaining a candidate for 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 (c) through (e) with another candidate key index value close to said key index value obtained in (a).

6. The device of claim 5 where said candidate for said token'"'"'s key index value is obtained directly from said token.

7. The device of claim 5 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 a token and a server while providing protection against external monitoring attacks in said token, said method implemented in said 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 said update in said key index value are updated; and

(c) deriving a value from said lowest level key to secure a transaction with said server.

9. The method of claim 8 where said server is configured to authenticate said token by:

(a) obtaining a candidate for 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 (c) through (e) with another candidate key index value close to said key index value 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 a lowest-level key, a cryptographic authentication code for securing said transaction, the method comprising:

(a) obtaining a candidate for 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 being tried, 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 another candidate key index value close to said key index value 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 candidate for said key index value to be tried is obtained directly from said token.

19. The method of claim 15 where said candidate for said key index value to be tried is obtained indirectly.

20. The method of claim 19 where said candidate for said key index value to be tried is produced using a timer.

21. A computer-readable medium containing program instructions that when executed by a processor implement a method for a server to secure a transaction 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 a lowest-level key, a cryptographic authentication code for securing said transaction, the method comprising:

(a) obtaining a candidate for 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 another candidate key index value close to said key index value obtained in (a).

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

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

24. The method of claim 21 where said candidate for said key index value to be tried is obtained directly from said token.

25. The method of claim 21 where said candidate for said key index value to be tried is obtained indirectly.

26. The method of claim 25 where said candidate for said key index value to be tried is produced using a timer.