Method and apparatus for hiding crytographic keys utilizing autocorrelation timing encoding and computation

• US 6,041,122 A
• Filed: 02/27/1998
• Issued: 03/21/2000
• Est. Priority Date: 02/27/1998
• Status: Expired due to Term

• Current Assignee: Honeyman Cipher Solutions LLC (Bradley David Liddle)
• Original Assignee: Intel Corporation
• Inventors: Graunke, Gary L., Aucsmith, David W.
• Primary Examiner(s): Hayes, Gail O.
• Assistant Examiner(s): Tucker, Christopher M.
• Application Number:
  US09/032,594
• Time in Patent Office: 753 Days
• Field of Search: 380/21, 380/24, 380/23, 380/30, 380/44
• US Class Current: 713/168
• CPC Class Codes: G06F 2207/7219 Countermeasures against side channel or fault attacks
• CPC Class Codes: H04L 2209/08 Randomization, e.g. dummy operations or using noise
• CPC Class Codes: H04L 2209/16 Obfuscation or hiding, e.g. involving white box
• CPC Class Codes: H04L 9/0872 using geo-location information, e.g. location data, time, relative position or proximity to other entities

Abstract

A method and apparatus for hiding cryptographic keys based on autocorrelation timing attacks is provided. The method and apparatus of the present invention utilize a autocorrelation timing attack to allow independent software entities to authenticate themselves without storing a private cryptographic key. This is accomplished by storing timing statistics related to the evaluation of an equation in the software entity rather than the cryptographic key itself. When the software entity authenticates itself, the cryptographic key is derived based on information provided by the timing statistics contained in the software entity.

Claims

1. A method comprising:

generating a plurality of timing statistics based on an amount of time required to evaluate a particular function given a known input for a series of computations used in deriving the cryptographic key;

deriving the cryptographic key in a bitwise fashion based, at least in part, on a comparison of the generated timing statistics and timing statistics stored in the electronic device to determine whether bits of a derived cryptographic key correspond to bits in the cryptographic key; and

using a subset of the derived cryptographic key for authentication prior to complete derivation of the cryptographic key.

2. The method of claim 1, further comprising storing the timing statistics in the electronic device, such that the cryptographic key is not stored in the electronic device.

3. The method of claim 1, further comprising deriving the cryptographic key each time the cryptographic key is required.

4. The method of claim 1, wherein generating the plurality of timing statistics comprises:

generating a total expected time for derivation of the cryptographic key based on a plurality of starting values; and

generating a variance of the total expected time.

5. The method of claim 1, wherein evaluating the function comprises finding a pseudo-prime number that is the lowest pseudo-prime number greater than the known input.

6. The method of claim 1, wherein evaluating the function comprises finding a prime number that is the lowest prime number greater than the known input.

7. A method comprising:

storing a plurality of timing statistics based on an amount of time required for a series of computations used in deriving the cryptographic key;

deriving the cryptogaphic key in a bitwise fashion in the electronic device by

(a) generating a predetermined number of seed values;

(b) evaluating a function for each of the predetermined number of seed values combined with a set bit, wherein the seed values combined with a set bit correspond to a first child node of a current node;

(c) evaluating the function for each of the predetermined number of seed values combined with a clear bit, wherein the seed values combined with a clear bit correspond to a second child node of the current node;

(d) computing a statistical measure for a time required for each evaluation corresponding to the first child node and the second child node;

(e) selecting between the first and second child nodes a parent node of the current node based on the statistical measure;

(f) repeating (b) through (f) until a third predetermined number of nodes have been selected; and

(g) repeating (f) a predetermined number of times;

using the timing statistics stored in the electronic device to determine whether the derived bits correspond to bits in the cryptographic key.

8. The method of claim 7, wherein the statistical measure is a variance.

9. A method for encoding a cryptographic key in an electronic device comprising:

(a) generating a plurality of seed values;

(b) combining one or more bits from a predetermined string of bits with a respective seed value;

(c) repeating (a) and (b) a predetermined number of times, wherein each iteration of (a) and (b) is designated as a sample;

(d) performing a function for each seed value;

(e) determining a period of time required to perform the functions for each seed value in a sample;

(f) repeating (d) through (f) for each sample;

(g) computing statistical measures based on the periods of time;

(h) storing the statistical measures in the electronic device.

10. The method of claim 9, wherein the seed values are random numbers of a predetermined size.

11. The method of claim 9, wherein the seed values are pseudo-random numbers of a predetermined size.

12. The method of claim 9, wherein the predetermined string comprises the cryptographic key of a predetermined size.

13. The method of claim 9, wherein the predetermined string comprises the cryptographic key of a first predetermined size combined with a set of bits of a second predetermined size.

14. The method of claim 9, wherein performing the function comprises determining a prime number greater than a particular seed value provided to the function.

15. The method of claim 9, wherein performing the function comprises determining a pseudo-prime number greater than a particular seed value provided to the function.

16. The method of claim 9, wherein the electronic device comprises a node in a video-on-demand network.

17. The method of claim 9, wherein the electronic device comprises a computer.

18. The method of claim 9, wherein the statistical measures comprise a total expected time required to derive the cryptographic key and a variance across the total expected time for the predetermined number of samples.

19. A method for hiding a cryptographic key in an electronic device comprising:

(a) generating a first plurality of seed values;

(b) combining one bit from a predetermined string of bits with a respective seed value;

(c) mixing an order of the seed values and bits;

(d) repeating (a) through (c) a predetermined number of times, wherein each iteration of (a) through (c) is designated as a sample;

(e) sending the samples and a function to the electronic device for evaluation;

(f) receiving, from the electronic device, results from the functions performed, a period of time required to perform the function for each result obtained, and a variance for each sample;

(g) placing the seed values and bits in an original order;

(h) selecting, from the first plurality of seed values for each sample, a subset of seed values corresponding to the cryptographic key;

(i) generating an expected period of time to perform the functions for the subset of seed values for the predetermined number of samples;

(j) generating a variance for the expected period of time to perform the functions for the predetermined number of samples; and

(k) sending the results from (i) and (j) in the electronic device.

20. The method of claim 19, wherein the seed values are random numbers of a predetermined size.

21. The method of claim 19, wherein the seed values are pseudo-random numbers of a predetermined size.

22. The method of claim 19, wherein the predetermined string comprises the cryptographic key of a predetermined size.

23. The method of claim 19, wherein the predetermined string comprises the cryptographic key of a first predetermined size combined with a set of bits of a second predetermined size.

24. The method of claim 19, wherein performing the function comprises determining a prime number greater than a particular seed value provided to the function.

25. The method of claim 19, wherein performing the function comprises determining a pseudo-prime number greater than a particular seed value provided to the function.

26. The method of claim 19, wherein the electronic device comprises a node in a video-on-demand network.

27. The method of claim 19, wherein the electronic device comprises a computer.

28. A method for deriving a cryptographic key in an electronic device having stored therein a plurality of statistics corresponding to a time required for a function to be evaluated for a first predetermined number of samples and a variance for the time for evaluation for each sample, wherein each sample comprises a second predetermined number of seed values, the method comprising:

(a) generating a second predetermined number of seed values;

(b) evaluating the function for each of the second predetermined number of seed values combined with a set bit, wherein the seed values combined with a set bit correspond to a first child node of a current node;

(c) evaluating the function for each of the second predetermined number of seed values combined with a clear bit, wherein the seed values combined with a clear bit correspond to a second child node of the current node;

(d) computing a statistical measure for a time required for each evaluation corresponding to the first child node and the second child node;

(e) selecting between the first and second child nodes a parent node of the current node based on the statistical measure;

(f) repeating (b) through (f) until a third predetermined number of nodes have been selected; and

(g) repeating (f) a predetermined number of times.

29. The method of claim 28, wherein the statistical measure is a variance.

30. A device for controlling request and viewing of audio/video programming comprising a control unit configured to communicate with an audio/visual server and configured to generate an output, the device having associated with it a particular cryptographic key, wherein a plurality of original timing statistics previously generated to derivation of the cryptographic key based on evaluation of a given function having as an input a plurality of original seed values are stored in the device and the cryptographic key is not stored in the device, the device comprising:

a processor; and

a memory coupled to the processor, wherein the device authenticates itself to the audio/visual server by evaluating the given function with a set of seed values and comparing the plurality of original timing statistics to a plurality of timing statistics generated in response to the set of seed values to determine whether bits of a derived cryptographic key correspond to bits in the cryptographic key.

31. A machine readable medium having stored thereon sequences of instructions that when executed by one or more processors cause one or more electronic devices to:

generate a plurality of timing statistics based on an amount of time required to evaluate a particular function given a known input for a series of computations used in deriving the cryptographic key;

derive the cryptographic key in a bitwise fashion based, at least in part, on a comparison of the generated timing statistics and timing statistics stored in the electronic device to determine whether bits of a derived cryptographic key correspond to bits in the cryptographic key; and

use a subset of the derived cryptographic key for authentication prior to complete derivation of the cryptographic key.

32. The machine readable medium of claim 31, wherein the sequence of instructions that cause the one or more electronic devices to evaluate the function further comprise sequences of instructions that when executed cause the one or more electronic devices to find a pseudo-prime number that is the lowest pseudo-prime number greater than the known input.

33. The machine readable medium of claim 31, wherein the sequence of instructions that cause the one or more electronic devices to evaluate the function further comprise sequences of instructions that when executed cause the one or more electronic devices to find a pseudo-prime number that is the lowest prime number greater than the known input.

34. A machine readable medium having stored thereon sequences of instruction that, when executed by one or more processors, cause one or more electronic devices to:

generate the plurality of timing statistics based on an amount of time required for a series of computations used in deriving the cryptographic key;

derive the cryptographic key in a bitwise fashion in the electronic device by

(a) generating a predetermined number of seed values;

(b) evaluating a function for each of the predetermined number of seed values combined with a set bit, wherein the seed values combined with a set bit correspond to a first child node of a current node;

(c) evaluating the function for each of the predetermined number of seed values combined with a clear bit, wherein the seed values combined with a clear bit correspond to a second child node of the current node;

(d) computing a statistical measure for a time required for each evaluation corresponding to the first child node and the second child node;

(e) selecting between the first and second child nodes a parent node of the current node based on the statistical measure;

(f) repeating (b) through (f) until a third predetermined number of nodes have been selected; and

(g) repeating (f) a predetermined number of times;

use the timing statistics stored in the electronic device to determine whether the derived bits correspond to bits in the cryptographic key.

35. The machine readable medium of claim 34, wherein the statistical measure is a variance.

36. A machine readable medium having stored thereon sequences of instruction that, when executed by one or more processors, cause one or more electronic devices to:

(a) generate a plurality of seed values;

(b) combine one or more bits from a predetermined string of bits with a respective seed value;

(c) repeat (a) and (b) a predetermined number of times, wherein each iteration of (a) and (b) is designated as a sample;

(d) perform a function for each seed value;

(e) determine a period of time required to perform the functions for each seed value in a sample;

(f) repeat (d) through (f) for each sample;

(g) compute statistical measures based on the periods of time;

(h) store the results from (g) in the electronic device.

37. The machine readable medium of claim 36, wherein the seed values are random numbers of a predetermined size.

38. The machine readable medium of claim 36, wherein the seed values are pseudo-random numbers of a predetermined size.

39. The machine readable medium of claim 36, wherein the predetermined string comprises the cryptographic key of a predetermined size.

40. The machine readable medium of claim 36, wherein the predetermined string comprises the cryptographic key of a first predetermined size combined with a set of bits of a second predetermined size.

41. The machine readable medium of claim 36, wherein the sequences of instructions that cause the one or more electronic devices to perform the function comprises sequences of instructions that cause the one or more electronic devices to determine a prime number greater than a particular seed value provided to the function.

42. The machine readable medium of claim 36, wherein the sequences of instructions that cause the one or more electronic devices to perform the function comprise sequences of instructions that cause the one or more electronic devices to determine a pseudo-prime number greater than a particular seed value provided to the function.

43. The machine readable medium of claim 36, wherein at least one of the one or more electronic devices comprises a node in a video-on-demand network.

44. The machine readable medium of claim 36, wherein at least one of the one or more electronic devices comprises a computer system.

45. The machine readable medium of claim 36, wherein the statistical measures comprise a total expected time required to derive the cryptographic key and a variance across the total expected time for the predetermined number of samples.

46. A machine readable medium having stored thereon sequences of instruction that, when executed by one or more processors, cause one or more electronic devices to:

(a) generate a first plurality of seed values;

(b) combine one bit from a predetermined string of bits with a respective seed value;

(c) mix an order of the seed values and bits;

(d) repeat (a) through (c) a predetermined number of times, wherein each iteration of (a) through (c) is designated as a sample;

(e) send the samples and a function to the electronic device for evaluation;

(f) receive, from the electronic device, results from the functions performed, a period of time required to perform the function for each result obtained, and a variance for each sample;

(g) place the seed values and bits in an original order;

(h) select, from the first plurality of seed values for each sample, a subset of seed values corresponding to the cryptographic key;

(i) generate an expected period of time to perform the functions for the subset of seed values for the predetermined number of samples;

(j) generate a variance for the expected period of time to perform the functions for the predetermined number of samples; and

(k) send the results from (i) and

     0) in the electronic device.

47. The machine readable medium of claim 46, wherein the seed values are random numbers of a predetermined size.

48. The machine readable medium of claim 46, wherein the seed values are pseudo-random numbers of a predetermined size.

49. The machine readable medium of claim 46, wherein the predetermined string comprises the cryptographic key of a predetermined size.

50. The machine readable medium of claim 46, wherein the predetermined string comprises the cryptographic key of a first predetermined size combined with a set of bits of a second predetermined size.

51. The machine readable medium of claim 46, wherein the sequences of instructions that cause the one or more electronic devices to perform the function comprises the step of determining a prime number greater than a particular seed value provided to the function.

52. The machine readable medium of claim 46, wherein the sequences of instructions that cause the one or more electronic devices to perform the function comprise sequences of instructions that cause the one or more electronic devices to determine a pseudo-prime number greater than a particular seed value provided to the function.

53. The machine readable medium of claim 46, wherein the electronic device comprises a node in a video-on-demand network.

54. The machine readable medium of claim 46, wherein the electronic device comprises a computer.

55. A machine readable medium having sequences of instructions, that when executed, cause one or more electronic devices to derive a cryptographic key based, at least in part, on statistics corresponding to a time required for a function to be evaluated for a first predetermined number of samples and a variance for the time for evaluation for each sample, wherein each sample comprises a second predetermined number of seed values, the sequences of instructions causing the one or more electronic devices to:

(a) generate a second predetermined number of seed values;

(b) evaluate the function for each of the second predetermined number of seed values combined with a set bit, wherein the seed values combined with a set bit correspond to a first child node of a current node;

(c) evaluate the function for each of the second predetermined number of seed values combined with a clear bit, wherein the seed values combined with a clear bit correspond to a second child node of the current node;

(d) compute a statistical measure for a time required for each evaluation corresponding to the first child node and the second child node;

(e) select between the first and second child nodes a parent node of the current node based on the statistical measure;

(f) repeat (b) through (f) until a third predetermined number of nodes have been selected; and

(g) repeat (f) a predetermined number of times.

56. The machine readable medium of claim 55, wherein the statistical measure is a variance.