Cryptographic token with leak-resistant key derivation

Patent metadata

Field	Value
Publication number	US-9852572-B2
Application number	US-201113245054-A
Country	US
Kind code	B2
Filing date	Sep 26, 2011
Priority date	Jul 2, 1998
Publication date	Dec 26, 2017
Grant date	Dec 26, 2017

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.

First claim

What is claimed is:

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 se

Assignees

• Kocher Paul C
• Cryptography Res Inc

Inventors

• Kocher Paul C

Classifications

• G06F2207/7219

  Countermeasures against side channel or fault attacks · CPC title

• H04L9/0891

  Revocation or update of secret information, e.g. encryption key update or rekeying · CPC title

• G07F7/1008 Primary

  Active credit-cards provided with means to personalise their use, e.g. with PIN-introduction/comparison system · CPC title

• H04L9/0625

  with splitting of the data block into left and right halves, e.g. Feistel based algorithms, DES, FEAL, IDEA or KASUMI · CPC title

• H04L9/003

  for power analysis, e.g. differential power analysis [DPA] or simple power analysis [SPA] · CPC title