Leak-resistant cryptographic indexed key update

• US 6,539,092 B1
• Filed: 07/02/1999
• Issued: 03/25/2003
• Est. Priority Date: 07/02/1998
• Status: Expired due to Term

• Current Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Original Assignee: Cryptography Research, Inc. (Rambus Inc.)
• Inventors: Kocher, Paul C.
• Primary Examiner(s): Hayes, Gail
• Assistant Examiner(s): Seal, James
• Application Number:
  US09/347,493
• Time in Patent Office: 1,362 Days
• Field of Search: 380/252, 380/1, 713/193, 713/194
• US Class Current: 380/252
• 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 using an indexed key update technique are disclosed. In one embodiment, a cryptographic client device maintains a secret key value as part of its state. The client can update its secret value at any time, for example before each transaction, using an update process that makes partial information that might have previously leaked to attackers about the secret no longer usefully describe the new updated secret value. 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 (and in some embodiments is provably secure) against attacks involving analysis of measurements of the device'"'"'s power consumption, electromagnetic characteristics, or other information leaked during transactions. The present invention can be used in connection with a client and server using such a protocol. To perform a transaction with the client, the server obtains the client'"'"'s current transaction counter. The server then performs a series of operations to determine the sequence of transformations needed to re-derive the correct session key from the client'"'"'s initial secret value. These transformations are performed, and the result is used as a transaction session key. The present invention includes a sequence of client-side updating processes that allow for significant improvements in the performance of the corresponding server operations.

Claims

1. A computer-implemented process for securing a first device while performing transactions with at least one second device, wherein said first device includes a computer-readable memory having an internal secret state, and wherein said at least one second device has access to a base secret cryptographic value corresponding to said internal secret state, comprising the steps of:

(a) using an index parameter associated with said internal secret state to select at least one state transformation operation;

(b) applying at least said selected transformation operation to said internal secret state to produce an updated secret state;

(i) having associated therewith an updated secret cryptographic value derivable from said secret state, and

(ii) in a manner inhibiting leaked partial statistical information about said internal secret state from usefully describing said updated secret state;

(c) replacing in said memory;

(i) said internal secret state with said updated secret state, and

(ii) said index parameter with an updated index parameter;

(d) performing a cryptographic transaction with said at least one second device by transmitting said updated index parameter and at least one datum secured using said updated cryptographic value to said at least one second device configured to;

(i) regenerate said updated cryptographic value from said base cryptographic value, and

(ii) use said updated cryptographic value to process said secured datum;

(e) said steps (a) through (d) being repeated a plurality of times, and said regeneration in (d)(i) being performable in substantially fewer applications of state transformations than a total number of repetitions of said steps (a) through (d).

2. The process of claim 1 wherein values for said updated secret cryptographic value are never recreated more than a fixed number of times when said step (b) is repeated a large number of times.

3. The process of claim 2 wherein said fixed number is three.

4. The process of claim 1 wherein it is provable that said step (b)(ii) prevents combining said partial information from multiple transactions to compromise said secret state.

5. The process of claim 1 further comprising a step of verifying that said selected transformation was computed correctly.

6. The process of claim 1 further comprising steps of incrementing a failure counter prior to said step (b), halting if said failure counter exceeds a maximum value, and resetting said failure counter after said step (b) has completed.

7. The process of claim 1 implemented in an ISO 7816-compliant smartcard.

8. The process of claim 7 where said smartcard is a stored value card.

9. The process of claim 1 where said transactions include secure payment for a purchase.

10. The process of claim 1 where said transactions include authorizing access to a service.

11. The process of claim 10 where said service includes access to web server.

12. The process of claim 11 implemented in an ISO 7816-compliant smartcard.

13. A cryptographic device comprising:

(a) at least one memory containing a value of a secret parameter; and

(b) a processor configured to perform a plurality of cryptographic transactions with a receiving cryptographic processing device, each said transaction involving a cryptographically processed datum, where;

(i) each of said cryptographic transactions is performed using a key derived from said secret parameter,

(ii) between said transactions, the usefulness of information related to said secret parameter that could have been previously gathered through external monitoring of said cryptographic device is reduced by updating the value of said secret parameter by performing a cryptographic key update operation; and

(iii) after said update operation, the updated value of said secret parameter is stored in said at least one memory for use in at least one subsequent transaction; and

(c) an interface configured to transmit said datum to said receiving device in which the updated value of said secret parameter after said processor has performed a plurality of update operations can be derived from the value of said secret parameter before said plurality of update operations.

14. The device of claim 13 wherein said cryptographic device is an ISO 7816-compliant smartcard.

15. The device of claim 13 wherein:

(i) said plurality of update operations is performed n times; and

(ii) the value of said updated secret parameter after said processor has performed said n update operations can be derived by said receiving device from the value of said secret parameter before said n operations with substantially less computational effort than would be required to perform n update operations.

16. The device of claim 15 wherein n is larger than 50.

17. The device of claim 15 wherein said key update operation has a cycle length x, and the effort required by said receiving device to derive said updated secret parameter from said secret parameter before said update operations requires computational effort of at most O(log x).

18. The device of claim 15 wherein said cryptographic device is an ISO 7816-compliant smartcard.

19. The device of claim 15 wherein said at least one memory further contains an index parameter, and where said processor is configured to increment the value of said index parameter each time the value of said secret parameter is updated.

20. The device of claim 19 wherein said processor is configured to update the value of said secret parameter by selecting at least one cryptographic transformation from a plurality of predefined cryptographic transformations, and applying said at least one cryptographic transformation to said secret parameter.

21. The device of claim 20 wherein said at least one memory further contains a depth parameter D and where said processor is configured to select said at least one cryptographic transformation based on the current value of said index parameter and said parameter D.

22. The device of claim 21 wherein said secret parameter includes D subelements, and said at least one cryptographic transformation modifies at least one of said subelements, and where the selection of said at least one subelement to modify depends on said index parameter.

23. The device of claim 20 wherein said plurality of predefined cryptographic transformations includes at least two transformations and the inverses of said two transformations.

24. The device of claim 23 wherein said plurality of cryptographic transformations includes a block cipher.

25. The device of claim 22 wherein said memory is initialized such that the initial value of said index parameter is zero, and said processor is configured to select a first cryptographic transformation when the current value of said index parameter is less than D−

1.

26. The device of claim 25 wherein said processor is configured to select the inverse of said first cryptographic transformation when the current value of said index parameter is equal to D−

1, and wherein said processor is configured to select a second cryptographic transformation when the current value of said index parameter is equal to D, and wherein said processor is configured to select the inverse of said second cryptographic transformation when the current value of said index parameter is equal to D+1.

27. The device of claim 19 wherein said processor includes overflow detection logic configured to verify that the current value of said index parameter is valid.

28. A cryptographic server device comprising:

(a) an interface for receiving a value of an index parameter and cryptographic transaction data; and

(b) a processor configured to derive a current value of a secret parameter from an initial value of said secret parameter, said value of said index parameter, and a value D representing the depth of a secret parameter transformation loop, within O(D) iterations of said secret parameter transformation loop and where the number of acceptable values for said index parameter is substantially larger than D.

29. The server device of claim 28 where said received cryptographic transaction data has been secured with a key derived from said current value of said secret parameter.

30. The device of claim 29 wherein said server comprises an ISO 7816-compliant smartcard.

31. The device of claim 29 wherein said server is a merchant terminal for a payment system.

32. The device of claim 28 wherein said processor is configured to derive said current value of said secret parameter by, for each said iteration of said secret parameter transformation loop, using a value derived from said index parameter to select at least one cryptographic transformation from a plurality of cryptographic transformations, and applying said at least one cryptographic transformation to said secret parameter.

33. A cryptographic system comprising a first device and a second device for performing transactions therebetween:

(a) wherein said first device includes;

(i) a memory for storing a value of a first secret parameter and a value of an index parameter; and

(ii) a processor configured to perform a plurality of cryptographic transactions where;

(a1) each of said transactions between said first device and said second device is secured using a transaction key derived from said first secret parameter,

(a2) between transactions the usefulness of information related to said first secret parameter that could have been previously gathered through external monitoring of said first device is reduced by updating the value of said first secret parameter by performing a cryptographic key update operation;

(a3) the value of said updated first secret parameter after said processor has performed n of said key update operations can be derived from the value of said first secret parameter before said n operations with substantially less computational effort than would be required to perform said n operations; and

(a4) said updated first parameter is stored in said memory for use in subsequent transactions; and

(b) wherein said second device includes;

(i) a memory containing a second secret parameter;

(ii) an interface for receiving from said first device a representation of said index parameter and cryptographic transaction data, where said transaction data is secured using said transaction key;

(iii) a processor configured to use said received index parameter to select a sequence of predetermined cryptographic transformations and to use said sequence of transformations to derive said transaction key from at least said second secret parameter in an efficient manner such that, if said first device has transformed said first secret parameter n times, the number of transformations required for said second device to derive said transaction key is substantially less than n; and

(iv) logic to process said transaction data using said transaction key.

34. The system of claim 33 wherein the number of transformations required by said second device is less than 40 for all values of n.

35. A method of performing a cryptographic transaction with a receiving party, using a secret parameter stored in a memory, comprising:

(a) performing a cryptographic transaction using a key derived from said secret parameter;

(b) applying a cryptographic key update operation to reduce the usefulness of information about the value of said secret parameter that could have been previously gathered through external monitoring attacks, such that after n update operations have been performed, said receiving party knowing the value of said secret parameter prior to said n update operations can derive the value of said updated secret parameter in substantially less than O(n) operations; and

(c) replacing said secret parameter with said updated secret parameter in said memory.

36. The method of claim 35 wherein said steps (b) and (c) are performed at regular time intervals.

37. The method of claim 35 implemented in an ISO 7816-compliant smartcard.

38. The method of claim 35 implemented in a device that regulates access to an encrypted television signal.

39. The method of claim 35 implemented in a payment metering device.

40. A method of securing a cryptographic transaction between a first device and a second device using a secret parameter, comprising the steps of:

(a) initializing a memory contained in said first device with an initial value of said secret parameter;

(b) initializing a memory contained in said second device with a value usable to derive said initial value of said secret parameter;

(c) said first device securing a datum with a transaction key derived from said secret parameter;

(d) said first device transmitting transaction data including said secured datum and an index parameter to said second device;

(e) said first device applying a cryptographic key update operation to reduce the usefulness of information about the value of said secret parameter that could have been previously gathered through external monitoring attacks;

(f) said first device replacing said secret parameter in said memory with said updated secret parameter;

(g) said second device receiving said transaction data;

(h) said second device using at least said index parameter to derive said transaction key from said value stored in the memory of said second device, where said deriving requires substantially less than n transformation operations, where n represents the total number of times that said step (e) has been applied by said first device to update said secret parameter; and

(i) using said transaction key derived in said step (h) to process said secured datum.

41. The method of claim 40 wherein the maximum number of said transformation operations performed at said step (h) is O(log x), where x is the maximum number of transactions that could be observed by an attacker of said first device.

42. The method of claim 40 where said first device is an ISO 7816-compliant smartcard.

43. The method of claim 40 wherein said first device and said second device are components of a larger device.

44. The method of claim 40 wherein said second device also contains an index parameter, and comprising the further steps of:

(a) selecting the larger index parameter of the two devices,

(b) using said larger index value to secure said transaction, and

(c) both of said devices incrementing and storing said larger index value for use in subsequent transactions.

45. The method of claim 40 wherein steps (a) through (i) are performed in a different order.

46. The method of claim 40 wherein said cryptographic transformation includes:

(a) dividing the value of said secret parameter into at least two subvalues;

(b) encrypting a first of said subvalues to generate an encrypted subvalue;

(c) using an exclusive OR operation to combine said encrypted subvalue with a second of said subvalues to form a first portion of the result of said transformation;

(d) encrypting said result first portion; and

(e) exclusive ORing said encryption of said first result portion with said first subvalue to produce a second portion of the result of said transformation.

47. The method of claim 46 wherein said steps of encrypting involve the DES algorithm.