Key derivation functions to enhance security

• US 7,577,250 B2
• Filed: 08/12/2004
• Issued: 08/18/2009
• Est. Priority Date: 08/12/2004
• Status: Expired due to Fees

• Current Assignee: CMLA LLC
• Original Assignee: CMLA LLC
• Inventors: Pedersen, Torben Pryds, Rijmen, Vincent, Damgaard, Ivan Bjerre
• Primary Examiner(s): Parthasarathy; Pramila
• Application Number:
  US10/918,718
• Publication Number:
  US 20060034457A1
• Time in Patent Office: 1,832 Days
• Field of Search: None
• 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, including;

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;

an implementation of a secure hash algorithm;

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

an output port to output said derivative key.

2. An apparatus according to claim 1, wherein:

the implementation of said secure 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 secure 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.

3. 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 secure hash algorithm with said result and a counter to produce said derivative key.

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

means for using the implementation of said secure 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.

5. An apparatus according to claim 4, 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 secure 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 secure 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.

6. 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 secure hash algorithm;

a key denver to generate a derivative key from said master key using the first calculator and the second calculator, including;

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; and

an output port to output said derivative key.

7. An apparatus according to claim 6, wherein:

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 secure 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.

8. An apparatus according to claim 6, wherein the key denver includes:

the first calculator is operative to implement said universal hash algorithm with said master key to produce a result; and

the second calculator is operative to implement said secure hash algorithm with said result and a counter to produce said derivative key.

9. An apparatus according to claim 8, wherein the first calculator includes

the third calculator,

the fourth calculator, and

the combiner.

10. An apparatus according to claim 6, wherein the key denver includes:

a fifth calculator implements said secure hash algorithm with said master key and a counter to produce a result; and

a sixth calculator implements said universal hash algorithm with said result to produce said derivative key.

11. An apparatus according to claim 10, wherein:

the fifth calculator includes;

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

the third calculator implements said secure 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.

12. 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 concatenates 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, said derivative key thereby calculated using a secure hash and a universal hash.

13. An apparatus according to claim 12, further comprising an output port to output said derivative key.

14. An apparatus according to claim 12, 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.

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

16. An apparatus according to claim 14, 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.

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

18. A data security device, comprising:

a key denver, 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 encrypted to encrypt data using said derivative key, said derivative key thereby calculated using a secure hash and a universal hash.

19. A data security device according to claim 18, further comprising a data transformer.

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

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

22. A data security device according to claim 18, 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.

23. A data security device according to claim 18, 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.

24. A method for performing key derivation, comprising:

dividing a 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 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.

25. A method according to claim 24, wherein:

the method further comprises determining a counter; and

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

26. A method according to claim 24, 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.

27. A method according to claim 24 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.

28. A method according to claim 27, wherein computing the result includes computing the result as the sum modulo a prime modulus.

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

30. A method for encrypting data using 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;

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, the derivative key thereby calculated using a secure hash and a universal hash.

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

32. A method according to claim 31, 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.

33. A method according to claim 31, 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.

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

35. 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.

36. 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;

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.

37. A method according to claim 30, further comprising encrypting the derivative key.

38. A method according to claim 36, further comprising transmitting the encrypted derivative key.

39. A method according to claim 30, further comprising transmitting the encrypted data.

40. A method according to claim 30, wherein:

the method further comprises determining a counter; and

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

41. A method according to claim 30, 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.

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

43. An apparatus, comprising:

an input port to receive a master key;

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

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

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

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;

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, said derivative key thereby calculated using a secure hash and a universal hash.

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

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

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

47. A data security device, comprising:

a key denver, 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 encrypted to encrypt data using said derivative key, said derivative key thereby calculated using a secure hash and a universal hash.

48. A data security device according to claim 47, further comprising a data transformer.

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

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

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

52. A method for performing key derivation, comprising:

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

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;

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

selecting a derivative key from bits in the hash value, the derivative key thereby calculated using a secure hash and a universal hash.

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

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

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

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

57. A method according to claim 52, 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.

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

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

organizing the bits in the second segment into a number of groups, the number of groups equal to a number of bits in the first segment;

each group having a same number of bits;

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

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

constructing a transformed master key from the first segment and the permuted groups;

combining a the transformed 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, the derivative key thereby calculated using a secure hash and a universal hash.

59. A method according to claim 58, 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.

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

61. A method according to claim 60, 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.

62. A method according to claim 60, 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.

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

64. A method according to claim 63, further comprising transmitting the encrypted derivative key.

65. A method according to claim 58, further comprising transmitting the encrypted data.

66. A method according to claim 58, 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.

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

68. A method according to claim 58, 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.

69. A method according to claim 58, 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.