Key derivation functions to enhance security

• US 20060034457A1
• Filed: 08/12/2004
• Published: 02/16/2006
• Est. Priority Date: 08/12/2004
• Status: Active Grant

• Current Assignee: CMLA LLC
• Original Assignee: CMLA LLC
• Inventors: Pedersen, Torben Pryds, Rijmen, Vincent, Damgaard, Ivan Bjerre
• Granted Patent: US 7,577,250 B2
• Time in Patent Office: Days
• US Class Current: 380/44
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

Key derivation algorithms are disclosed. In one key derivation application, a segment of the master key is hashed. Two numbers of derived from another segment of the master key. A universal hash function, using the two numbers, is applied to the result of the hash, from which bits are selected as the derived key. In another embodiment, an encoded counter is combined with segments of the master key. The result is then hashed, from which bits are selected as the derived key.

Claims

1. An apparatus comprising:

an input port to receive a master key;

an implementation of a universal hash algorithm;

an implementation of a hash algorithm;

means for generating a derivative key from said master key using the implementation of said universal hash algorithm and said hash algorithm; and

an output port to output said derivative key.

2. An apparatus according to claim 1, wherein the implementation of said universal hash algorithm includes:

a divider to divide said master key into a first segment and a second segment;

a repeater to repeat said counter to form an encoded counter as a longer bit pattern;

an implementation of a first bitwise binary function operative on said first segment and said encoded counter to produce a first result;

an implementation of a second bitwise binary function operative on said second segment and said encoded counter to produce a second result; and

a combiner to combine said first result, said second result, and said encoded counter to produce said result.

3. An apparatus according to claim 1, wherein:

the apparatus further comprises a divider to divide said master key into a first segment and a second segment;

the implementation of said hash algorithm includes;

a combiner to combine said first segment with said counter to produce a modified first segment; and

means for using the implementation of said hash algorithm to hash said modified first segment into a hash value; and

the implementation of said universal hash algorithm includes;

a determiner to determine a first number and a second number from said second segment;

a calculator including an implementation of an arithmetic formula to compute a result using said hash value, said first number, and said second number; and

a bit selector to select a set of bits from said result as a derivative key.

4. An apparatus according to claim 1, wherein the means for generating includes:

means for using the implementation of said universal hash algorithm with said master key to produce a result; and

means for using the implementation of said hash algorithm with said result and a counter to produce said derivative key.

5. An apparatus according to claim 4, wherein the implementation of said universal hash algorithm includes:

a divider to divide said master key into a first segment and a second segment;

a repeater to repeat said counter to form an encoded counter as a longer bit pattern;

an implementation of a first bitwise binary function operative on said first segment and said encoded counter to produce a first result;

an implementation of a second bitwise binary function operative on said second segment and said encoded counter to produce a second result; and

a combiner to combine said first result, said second result, and said encoded counter to produce said result.

6. An apparatus according to claim 1, wherein the means for generating includes:

means for using the implementation of said hash algorithm with said master key and a counter to produce a result; and

means for using the implementation of said universal hash algorithm with said result to produce said derivative key.

7. An apparatus according to claim 6, wherein:

the apparatus further comprises a divider to divide said master key into a first segment and a second segment;

the means for using the implementation of said hash algorithm includes;

a combiner to combine said first segment with said counter to produce a modified first segment; and

means for using the implementation of said hash algorithm to hash said modified first segment into a hash value; and

the means for using the implementation of said universal hash algorithm includes;

a determiner to determine a first number and a second number from said second segment;

a calculator including an implementation of an arithmetic formula to compute a result using said hash value, said first number, and said second number; and

a bit selector to select a set of bits from said result as a derivative key.

8. An apparatus comprising:

an input port to receive a master key;

a first calculator to implement a universal hash algorithm;

a second calculator to implement a hash algorithm;

a key deriver to generate a derivative key from said master key using the first calculator and the second calculator; and

an output port to output said derivative key.

9. An apparatus according to claim 8, wherein the key deriver includes:

a divider to divide said master key into a first segment and a second segment;

a repeater to repeat said counter to form an encoded counter as a longer bit pattern;

a third calculator to implement a first bitwise binary function operative on said first segment and said encoded counter to produce a first result;

a fourth calculator to implement a second bitwise binary function operative on said second segment and said encoded counter to produce a second result; and

a combiner to combine said first result, said second result, and said encoded counter to produce said result.

10. An apparatus according to claim 8, wherein:

the apparatus further comprises a divider to divide said master key into a first segment and a second segment;

the second calculator includes;

a combiner to combine said first segment with said counter to produce a modified first segment; and

a fifth calculator to implement said hash algorithm to hash said modified first segment into a hash value; and

the first calculator includes;

a determiner to determine a first number and a second number from said second segment;

a sixth calculator to implement an arithmetic formula to compute a result using said hash value, said first number, and said second number; and

a bit selector to select a set of bits from said result as a derivative key.

11. An apparatus according to claim 8, wherein the key deriver includes:

a third calculator to implement said universal hash algorithm with said master key to produce a result; and

a fourth calculator to implement said hash algorithm with said result and a counter to produce said derivative key.

12. An apparatus according to claim 11, wherein the first calculator includes:

a divider to divide said master key into a first segment and a second segment;

a repeater to repeat said counter to form an encoded counter as a longer bit pattern;

a fifth calculator to implement a first bitwise binary function operative on said first segment and said encoded counter to produce a first result;

a sixth calculator to implement a second bitwise binary function operative on said second segment and said encoded counter to produce a second result; and

a combiner to combine said first result, said second result, and said encoded counter to produce said result.

13. An apparatus according to claim 8, wherein the key deriver includes:

a third calculator to implement said hash algorithm with said master key and a counter to produce a result; and

a fourth calculator to implement said universal hash algorithm with said result to produce said derivative key.

14. An apparatus according to claim 13, wherein:

the apparatus further comprises a divider to divide said master key into a first segment and a second segment;

the third calculator includes;

a combiner to combine said first segment with said counter to produce a modified first segment; and

a third calculator to implement said hash algorithm to hash said modified first segment into a hash value; and

the fourth calculator includes;

a determiner to determine a first number and a second number from said second segment;

a fifth calculator including an implementation of an arithmetic formula to compute a result using said hash value, said first number, and said second number; and

a bit selector to select a set of bits from said result as a derivative key.

15. An apparatus, comprising:

an input port to receive a master key;

a divider to divide said master key into a first segment and a second segment;

a concatenator to concatenate said first segment and a counter to produce a modified first segment;

a hasher to hash said modified first segment into a hash value;

a determiner to determine a first number and a second number from said second segment;

a calculator including an implementation of an arithmetic formula to compute a result using said hash value, said first number, and said second number; and

a bit selector to select a set of bits from said result as a derivative key.

16. An apparatus according to claim 15, further comprising an output port to output said derivative key.

17. An apparatus according to claim 15, wherein the calculator includes:

an implementation of a first function to compute a product of said hash value and said first number;

an implementation of a second function to compute a sum of said product and said second number; and

an implementation of a third function to compute said result of said sum modulo a modulus.

18. An apparatus according to claim 17, wherein the determiner is operative to determine said first number and said second number modulo said modulus.

19. An apparatus according to claim 17, wherein the implementation of said third function includes an implementation of said third function to compute said result of said sum modulo a prime modulus.

20. An apparatus according to claim 15, wherein the bit selector is operative to select as said derivative key a set of least significant bits from said result.

21. A data security device, comprising:

a key deriver, including;

an input port to receive a master key;

a divider to divide said master key into a first segment and a second segment;

a concatenator to concatenate said first segment and a counter to produce a modified first segment;

a hasher to hash said modified first segment into a hash value;

a determiner to determine a first number and a second number from said second segment modulo a modulus;

a calculator including an implementation of an arithmetic formula to compute a result using said hash value, said first number, and said second number; and

a bit selector to select a set of bits from said result as a derivative key; and

an encrypter to encrypt data using said derivative key.

22. A data security device according to claim 21, further comprising a data transformer.

23. A data security device according to claim 22, wherein the data transformer is operative to transform an original master key into said master key.

24. A data security device according to claim 22, wherein the data transformer is operative to transform said derivative key into a transformed derivative key.

25. A data security device according to claim 21, wherein the calculator includes:

an implementation of a first function to compute a product of said hash value and said first number;

an implementation of a second function to compute a sum of said product and said second number; and

an implementation of a third function to compute said result from said sum modulo said modulus.

26. A data security device according to claim 21, wherein the implementation of said third function includes an implementation of said third function to compute said result from said sum modulo a prime modulus.

27. A method for performing key derivation, comprising:

hashing a master key to produce a hash value;

determining a first number and a second number from the master key;

computing a universal hash function of the hash value, the first number, and the second number to produce a result; and

selecting a derivative key from bits in the result.

28. A method according to claim 27, wherein:

the method further comprises dividing the master key into a first segment and a second segment;

hashing a master key includes hashing the first segment to produce the hash value; and

determining a first number and a second number includes determining the first number and the second number from the second segment.

29. A method according to claim 28, wherein:

the method further comprises determining a counter; and

hashing the first segment includes combining the first segment and the counter.

30. A method according to claim 27, wherein determining a first number and a second number includes:

deriving a third number and a fourth number from the master key;

computing the first number as the third number modulo a modulus; and

computing the second number as the fourth number modulo the modulus.

31. A method according to claim 27, wherein computing a universal hash function includes:

computing a product of the first number and the hash value;

computing a sum of the product and the second number; and

computing the result as the sum modulo a modulus.

32. A method according to claim 31, wherein computing the result includes computing the result as the sum modulo a prime divisor.

33. A method according to claim 31, wherein selecting a derivative key includes selecting the derivative key from a set of least significant bits in the result.

34. A method for encrypting a derivative key, comprising:

generating the derivative key, including;

dividing the master key into a first segment and a second segment;

hashing the first segment to produce a hash value;

determining a first number and a second number from the second segment;

computing a product of the first number and the hash value;

computing a sum of the product and the second number; and

computing a result as the sum modulo a modulus; and

selecting the derivative key from bits in the result; and

encrypting data using the derivative key.

35. A method according to claim 34, further comprising applying a data transformation to the master key before generating the derivative key.

36. A method according to claim 35, wherein applying a data transformation includes:

dividing the master key into a third segment and a fourth segment, each of the third segment and the fourth segment including at least one bit;

organizing the bits in the fourth segment into a number of groups, the number of groups equal to a number of bits in the third segment;

each group having a same number of bits;

associating each of the groups with a bit in the third segment;

applying a permutation function to at least one of the groups according to the associated bit in the third segment; and

constructing the transformed master key from the third segment and the permuted groups.

37. A method according to claim 35, wherein applying a data transformation includes:

dividing the master key into a third segment and a fourth segment, each of the third segment and the fourth segment including at least one bit;

computing a power as a function of the third segment, the power being relatively prime to a function of a second modulus;

computing a result of raising a function of the fourth segment to the power;

computing an exponential permutation as the result modulo the second modulus; and

constructing the transformed master key from the third segment and the computed exponential permutation.

38. A method according to claim 34, further comprising applying a data transformation to the derivative key.

39. A method according to claim 34, wherein applying a data transformation includes:

dividing the master key into a third segment and a fourth segment, each of the third segment and the fourth segment including at least one bit;

organizing the bits in the fourth segment into a number of groups, the number of groups equal to a number of bits in the third segment;

each group having a same number of bits;

associating each of the groups with a bit in the third segment;

applying a permutation function to at least one of the groups according to the associated bit in the third segment; and

constructing the transformed master key from the third segment and the permuted groups.

40. A method according to claim 38, wherein applying a data transformation includes:

dividing the master key into a third segment and a fourth segment, each of the third segment and the fourth segment including at least one bit;

computing a power as a function of the third segment, the power being relatively prime to a function of a second modulus;

computing a result of raising a function of the fourth segment to the power;

computing an exponential permutation as the result modulo the second modulus; and

constructing the transformed master key from the third segment and the computed exponential permutation.

41. A method according to claim 34, further comprising encrypting the derivative key.

42. A method according to claim 41, further comprising transmitting the encrypted derivative key.

43. A method according to claim 34, further comprising transmitting the encrypted data.

44. A method according to claim 34, wherein:

the method further comprises determining a counter; and

hashing the first segment includes combining the first segment and the counter.

45. A method according to claim 34, wherein determining a first number and a second number includes:

deriving a third number and a fourth number from the second segment;

computing the first number as the third number modulo a modulus; and

computing the second number as the fourth number modulo the modulus.

46. A method according to claim 34, wherein selecting a derivative key includes selecting the derivative key from a set of least significant bits in the result.

47. An apparatus, comprising:

an input port to receive a master key;

a combiner to combine said master key and a value to produce a modified master key;

a hasher to hash said modified master key into a hash value; and

a bit selector to select a set of bits from said hash value as a derivative key.

48. An apparatus according to claim 47, wherein:

the apparatus further comprises a repeater to repeat said value to form an encoded value as a longer bit pattern; and

the combiner is operative to combine said master key and said encoded value to produce a modified master key;

49. An apparatus according to claim 47, wherein:

the combiner includes a divider to divide said master key into a first segment and a second segment; and

the combiner is operative to combine said encoded value, said first segment, and said second segment to produce said modified master key.

50. An apparatus according to claim 49, wherein the combiner further includes:

an implementation of a first bitwise binary function operative on said first segment and said encoded value to produce a first result;

an implementation of a second bitwise binary function operative on said second segment and said encoded value to produce a second result; and

a combiner to combine said first result and said second result to produce said modified master key.

51. An apparatus according to claim 50, wherein the combiner includes a concatenator to concatenate said first result and said second result to produce said modified master key.

52. An apparatus according to claim 47, wherein the bit selector is operative to select a set of least significant bits from said hash value as said derivative key.

76. An apparatus according to claim 47, wherein the combiner is operative to said master key and a counter to produce said modified master key.

53. A data security device, comprising:

a key deriver, including;

an input port to receive a master key;

a divider to divide said master key into a first segment and a second segment;

a repeater to repeat a value to form an encoded value as a longer bit pattern;

an implementation of a first bitwise binary function operative on said first segment and said encoded value to produce a first result;

an implementation of a second bitwise binary function operative on said second segment and said encoded value to produce a second result;

a combiner to combine said first result, said second result, and said encoded value to produce said modified master key;

a hasher to hash said modified master key into a hash value; and

a bit selector to select a set of bits from said result as a derivative key; and

an encrypter to encrypt data using said derivative key.

54. A data security device according to claim 53, further comprising a data transformer.

55. A data security device according to claim 54, wherein the data transformer is operative to transform an original master key into said master key.

56. A data security device according to claim 54, wherein the data transformer is operative to transform said derivative key into a transformed derivative key.

77. A data security device according to claim 53, wherein the repeater is operative to repeat a counter to form said encoded value as a longer bit pattern.

57. A method for performing key derivation, comprising:

combining a master key with a value to produce a modified master key;

hashing the modified master key to produce a hash value; and

selecting a derivative key from bits in the hash value.

58. A method according to claim 57, further comprising repeating a bit pattern in the value to form a longer bit pattern.

59. A method according to claim 57, wherein combining a master key with a value includes computing a bitwise binary function using the master key and the value.

60. A method according to claim 57, wherein combining a master key with a value includes:

dividing the master key into a first segment and a second segment;

combining the first segment with the value to produce a first result;

combining the second segment with the value to produce a second result; and

combining the first result and the second result to produce the modified master key.

61. A method according to claim 60, wherein combining the first result and the second result includes concatenating the first result and the second result to produce the modified master key.

62. A method according to claim 57, wherein selecting a derivative key includes selecting the derivative key from a set of least significant bits from the hash value.

78. A method according to claim 57, wherein combining a master key with a value to produce a modified master key includes combining said master key with a counter to produce said modified master key.

63. A method for encrypting a derivative key, comprising:

combining a master key with a value to produce a modified master key;

hashing the modified master key to produce a hash value;

selecting a derivative key from bits in the hash value; and

encrypting data using the derivative key.

64. A method according to claim 63, further comprising applying a data transformation to the master key before generating the derivative key.

65. A method according to claim 64, wherein applying a data transformation includes:

dividing the master key into a third segment and a fourth segment, each of the third segment and the fourth segment including at least one bit;

organizing the bits in the fourth segment into a number of groups, the number of groups equal to a number of bits in the third segment;

each group having a same number of bits;

associating each of the groups with a bit in the third segment;

applying a permutation function to at least one of the groups according to the associated bit in the third segment; and

constructing the transformed master key from the third segment and the permuted groups.

66. A method according to claim 64, wherein applying a data transformation includes:

dividing the master key into a third segment and a fourth segment, each of the third segment and the fourth segment including at least one bit;

computing a power as a function of the third segment, the power being relatively prime to a function of a predefined modulus;

computing a result of raising a function of the fourth segment to the power;

computing an exponential permutation as the result modulo the predefined modulus; and

constructing the transformed master key from the third segment and the computed exponential permutation.

67. A method according to claim 63, further comprising applying a data transformation to the derivative key.

68. A method according to claim 67, wherein applying a data transformation includes:

dividing the master key into a third segment and a fourth segment, each of the third segment and the fourth segment including at least one bit;

organizing the bits in the fourth segment into a number of groups, the number of groups equal to a number of bits in the third segment;

each group having a same number of bits;

associating each of the groups with a bit in the third segment;

applying a permutation function to at least one of the groups according to the associated bit in the third segment; and

constructing the transformed master key from the third segment and the permuted groups.

69. A method according to claim 67, wherein applying a data transformation includes:

dividing the master key into a third segment and a fourth segment, each of the third segment and the fourth segment including at least one bit;

computing a power as a function of the third segment, the power being relatively prime to a function of a predefined modulus;

.

computing a result of raising a function of the fourth segment to the power;

computing an exponential permutation as the result modulo the predefined modulus; and

constructing the transformed master key from the third segment and the computed exponential permutation.

70. A method according to claim 63, further comprising encrypting the derivative key.

71. A method according to claim 70, further comprising transmitting the encrypted derivative key.

72. A method according to claim 63, further comprising transmitting the encrypted data.

73. A method according to claim 63, wherein combining a master key with a value includes:

dividing the master key into a first segment and a second segment;

combining the first segment with the value to produce a first result;

combining the second segment with the value to produce a second result; and

combining the first result and the second result to produce the modified master key.

74. A method according to claim 73, wherein combining the first result and the second result includes concatenating the first result and the second result to produce the modified master key.

75. A method according to claim 63, wherein combining a master key with a value includes:

dividing the master key into a first segment and a second segment;

combining the first segment with the value to produce a first result; and

combining the first result with the second segment to produce the modified master key.

79. A method according to claim 63, wherein combining a master key with a value to produce a modified master key includes combining said master key with a counter to produce a modified master key.