Permutation data transform to enhance security

• US 8,077,861 B2
• Filed: 08/12/2004
• Issued: 12/13/2011
• Est. Priority Date: 08/12/2004
• Status: Expired due to Fees

• Current Assignee: CMLA LLC
• Original Assignee: CMLA LLC
• Inventors: Damgaard, Ivan Bjerre, Pedersen, Torben Pryds, Rijmen, Vincent
• Primary Examiner(s): Dada, Beemnet
• Assistant Examiner(s): Debnath, Suman
• Application Number:
  US10/918,717
• Publication Number:
  US 20060034455A1
• Time in Patent Office: 2,679 Days
• Field of Search: 380/28, 380/277, 380 42- 45, 382/173, 382254-308
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/20 Manipulating the length of blocks of bits, e.g. padding or block truncation
• CPC Class Codes: H04L 9/0631 Substitution permutation network [SPN], i.e. cipher composed of a number of stages or rounds each involving linear and nonlinear transformations, e.g. AES algorithms
• CPC Class Codes: H04L 9/0643 Hash functions, e.g. MD5, SHA, HMAC or f9 MAC
• CPC Class Codes: H04L 9/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords

Abstract

A data input is divided into two segments; the second segment is also divided into groups. Bits in the first segment are used to control the application of permutation functions to bit groups in the second segment. The transformed data is assembled from the first segment and the permuted groups of the second segment. This data transformation can be applied in combination with a key derivation algorithm, a key wrapping algorithm, or an encryption algorithm to enhance the security of these other applications.

Claims

1. A data transformer, comprising:

an input port to receive data;

a divider to divide said data into a first segment and a second segment and to divide said second segment into at least one group;

a permuter including an implementation of a permutation function to permute at least one of said groups into a permuted group according to a corresponding bit in said first segment; and

an output port to output said first segment and at least said permuted group as transformed data.

2. A data transformer according to claim 1, wherein the divider is operative to divide said second segment into groups so that a number of said groups in said second segment equals a number of bits in said first segment.

3. A data transformer according to claim 1, wherein the divider is operative to divide said second segment into said groups, each of said groups having a predefined size.

4. A data transformer according to claim 3, wherein the divider includes a padder to pad said second segment so that each of said groups have said predefined size.

5. A data transformer according to claim 1, wherein the permuter includes implementations of at least two permutation functions.

6. A data transformer according to claim 5, wherein a number of permutation functions is equal to a number of said groups in said second segment.

7. A data transformer according to claim 6, wherein the permuter is operative to permute each of said groups using one of said permutation functions according to the corresponding bit in said first segment.

8. A data transformer according to claim 5, wherein the implementations of said permutation functions includes:

an implementation of a base permutation function; and

implementations of powers of the base permutation function.

44. A data transformer according to claim 1, wherein said permuted group has a first size that is equal to a second size of said at least one group.

45. A data transformer according to claim 2, wherein each group of said second segment has a unique corresponding bit in said first segment.

46. A data transformer according to claim 45, wherein said first segment includes at least two bits and said divider is operative to divide said second segment into at least two groups.

47. A data transformer according to claim 46, wherein the output port is operative to output said first segment, said permuted groups, and any groups that were not permuted as transformed data.

48. A data transformer according to claim 45, wherein the permuter is operative to permute each group of the second segment if said unique corresponding bit in said first segment is set, and to not permute each group of the second segment if said unique corresponding bit in said first segment is not set.

64. A data transformer according to claim 1, wherein each of said groups includes a plurality of bits.

68. A data transformer according to claim 2, wherein said number of said groups in said second segment is greater than two.

9. A data security device, comprising:

a data transformer, including;

an input port to receive data;

a divider to divide said data into a first segment and a second segment and to divide said second segment into at least two groups, each group having a predefined size, so that a number of groups in said second segment equals a number of bits in said first segment;

a permuter including an implementation of a permutation function to permute at least one of said groups into a permuted group according to a corresponding bit in said first segment; and

an output port to output said first segment and at least said permuted group as transformed data; and

an implementation of a security algorithm to secure said transformed data.

10. A data security device according to claim 9, wherein:

said data includes a master key; and

the implementation of a security algorithm includes an implementation of a key derivation function to use said transformed data to generate a derivative key of said master key.

11. A data security device according to claim 9, wherein:

said data includes a key to be wrapped; and

the implementation of said security algorithm includes an implementation of a key wrapping function to wrap said transformed data.

12. A data security device according to claim 11, wherein the implementation of said key wrapping function includes an implementation of RSA to wrap said transformed data.

13. A data security device according to claim 9, wherein the implementation of said security algorithm includes an implementation of an encryption algorithm to use said transformed data to encrypt said data.

14. A data security device according to claim 13, wherein the implementation of said security algorithm includes an implementation of AES to use said transformed data to encrypt said data.

15. A data security device according to claim 9, further comprising a second divider to divide an input into at least two blocks, the data transformer operative separately on each block.

16. A data security device according to claim 15, further comprising a combiner to combine a result of the data transformer on each block into a single transformed data to be secured by the implementation of said security algorithm.

17. A data security device according to claim 9, wherein the permuter includes implementations of at least two permutation functions, a number of permutation functions is equal to a number of said groups in said second segment.

18. A data security device according to claim 17, wherein the permuter is operative to permute each of said groups using one of said permutation functions according to the corresponding bit in said first segment.

19. A data security device according to claim 17, wherein the implementations of said permutation functions includes:

an implementation of a base permutation function; and

implementations of powers of the base permutation function.

42. A data security device according to claim 10, further comprising an implementation of an encryption algorithm to use said transformed data to encrypt a second data using said derivative key.

49. A data security device according to claim 9, wherein said permuted group has a first size that is equal to a second size of said at least one group.

50. A data security device according to claim 9, wherein each group of said second segment has a unique corresponding bit in said first segment.

51. A data security device according to claim 50, wherein said first segment includes at least two bits and said divider is operative to divide said second segment into at least two groups.

52. A data security device according to claim 51, wherein the output port is operative to output said first segment, said permuted groups, and any groups that were not permuted as transformed data.

53. A data security device according to claim 50, wherein the permuter is operative to permute each group of the second segment if said unique corresponding bit in said first segment is set, and to not permute each group of the second segment if said unique corresponding bit in said first segment is not set.

65. A data security device according to claim 9, wherein each of said groups includes a plurality of bits.

69. A data security device according to claim 9, wherein said number of said groups in said second segment is greater than two.

20. A method for generating a data transform, comprising:

receiving data at an input port;

dividing the data 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 at least one group;

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

constructing the data transform from the first segment and at least the permuted groups.

21. A method according to claim 20, wherein organizing the bits in the second segment includes 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.

22. A method according to claim 20, wherein organizing the bits includes organizing the bits in the second segment into at least two groups, each group having a same number of bits.

23. A method according to claim 22, wherein organizing the bits includes padding the data so that the second segment can be organized into the groups, each of the groups including the same number of bits.

24. A method according to claim 20, further comprising defining the permutation function.

25. A method according to claim 24, wherein defining the permutation function includes defining a number of permutation functions, the number of permutation functions equal to a number of the groups.

26. A method according to claim 25, wherein applying a permutation function includes applying a different permutation function to each of the groups according to the corresponding bit in the first segment.

27. A method according to claim 26, wherein:

defining a number of permutation functions includes assigning an index to each of the permutation functions; and

applying a different permutation function includes selecting the permutation function with the index corresponding to a number for the bit in the first segment associated with the group.

28. A method according to claim 25, wherein defining a number of permutation functions includes:

defining a base permutation function; and

defining each of the remaining permutation functions as a power of the base permutation function.

54. A method according to claim 20, wherein applying a permutation function includes applying the permutation function to the at least one of the groups according to the associated bit in the first segment, each of the permuted groups having a first size that is equal to a second size of the at least one of the groups.

55. A method according to claim 21, wherein associating each of the groups with a bit in the first segment includes associating each of the groups with a unique corresponding bit in the first segment.

56. A method according to claim 55, wherein:

dividing the data into a first segment and a second segment includes dividing the data into the first segment and the second segment, the first segment including at least two bits; and

organizing the bits in the second segment into at least one group includes organizing the bits in the second segment into at least two groups.

57. A method according to claim 56, wherein constructing the data transform includes constructing the data transform from the first segment, the permuted groups, and any groups that were not permuted.

58. A method according to claim 55, wherein applying a permutation function to at least one of the groups includes applying the permutation function to each group of the second segment if the unique corresponding bit in the first segment is set, and not applying the permutation function to each group of the second segment if the unique corresponding bit in the first segment is not set.

66. A method according to claim 20, wherein organizing the bits in the second segment into at least one group includes organizing the bits in the second segment into at least one group, each group including a plurality of bits.

70. A method according to claim 21, wherein 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 includes organizing the bits in the second segment into the number of groups, the number of groups greater than two.

29. A method for enhancing security of data, comprising:

transforming the data, including;

receiving the data at an input port;

dividing the data 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;

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

constructing the data transform from the first segment and at least the permuted groups; and

applying an implementation of a security algorithm to the data transform to secure the data transform.

30. A method according to claim 29, wherein:

receiving the data includes receiving a master key from which to generate a derivate key; and

applying an implementation of a security algorithm includes applying an implementation of a key derivation function to the data transform to generate the derivative key of the master key.

31. A method according to claim 30, wherein applying an implementation of a key derivation function includes:

combining the transformed data with an encoded counter to produce a combined result;

securely hashing the combined result to produce a hash; and

selecting a subset of bits in the hash as the derivative key.

32. A method according to claim 30, wherein:

transforming the data further includes combining the master key with a counter to produce the data; and

applying an implementation of a key derivation function includes;

securely hashing the transformed data to produce a hash; and

selecting a subset of bits in the hash as the derivative key.

33. A method according to claim 29, wherein:

receiving the data includes receiving a key to be wrapped as the data; and

applying an implementation of a security algorithm includes applying an implementation of a key wrapping function to the data transform to wrap the key.

34. A method according to claim 33, wherein applying an implementation of a key wrapping function includes applying an implementation of RSA to the data transform to wrap the key.

35. A method according to claim 29, wherein applying an implementation of a security algorithm includes applying an implementation of an encryption algorithm using the data transform as a key to encrypt the data.

36. A method according to claim 35, wherein applying an implementation of an encryption algorithm includes applying an implementation of AES using the data transform as the key to encrypt the data.

37. A method according to claim 29, wherein organizing the bits includes organizing the bits in the second segment into the number of groups, the number of groups equal to the number of bits in the first segment, each group having a same number of bits.

38. A method according to claim 29, further comprising defining the permutation function.

39. A method according to claim 38, wherein defining the permutation function includes defining a number of permutation functions, the number of permutation functions equal to the number of groups.

40. A method according to claim 39, wherein defining a number of permutation functions includes:

defining a base permutation function; and

defining each of the remaining permutation functions as a power of the base permutation function.

41. A method according to claim 29, further comprising:

dividing an input into at least two blocks, transforming each block separately; and

combining a result of the data transformation on each block into a single transformed data to be secured by the application of the implementation of the security algorithm.

43. A method according to claim 30, further comprising applying an implementation of an encryption algorithm using the derivative key as a key to encrypt a second data.

59. A method according to claim 29, wherein applying a permutation function includes applying the permutation function to the at least one of the groups according to the associated bit in the first segment, each of the permuted groups having a first size that is equal to a second size of the at least one of the groups.

60. A method according to claim 29, wherein associating each of the groups with a bit in the first segment includes associating each of the groups with a unique corresponding bit in the first segment.

61. A method according to claim 60, wherein:

dividing the data into a first segment and a second segment includes dividing the data into the first segment and the second segment, the first segment including at least two bits; and

organizing the bits in the second segment into at least one group includes organizing the bits in the second segment into at least two groups.

62. A method according to claim 61, wherein constructing the data transform includes constructing the data transform from the first segment, the permuted groups, and any groups that were not permuted.

63. A method according to claim 60, wherein applying a permutation function to at least one of the groups includes applying the permutation function to each group of the second segment if the unique corresponding bit in the first segment is set, and not applying the permutation function to each group of the second segment if the unique corresponding bit in the first segment is not set.

67. A method according to claim 29, wherein organizing the bits in the second segment into a number of groups includes organizing the bits in the second segment into a number of groups, each of the group including a plurality of bits.

71. A method according to claim 29, wherein 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 includes organizing the bits in the second segment into the number of groups, the number of groups greater than two.