Permutation data transform to enhance security

• US 20060034455A1
• 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 8,077,861 B2
• Time in Patent Office: Days
• 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.

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.

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

receiving data;

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.

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

transforming the data, including;

receiving the data;

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.