Method and system for high throughput blockwise independent encryption/decryption

• US 8,379,841 B2
• Filed: 03/22/2007
• Issued: 02/19/2013
• Est. Priority Date: 03/23/2006
• Status: Active Grant

• Current Assignee: Ip Reservoir, LLC
• Original Assignee: Exegy Incorporated
• Inventors: Taylor, David E., Indeck, Ronald S., White, Jason R., Chamberlain, Roger D.
• Primary Examiner(s): Flynn, Nathan
• Assistant Examiner(s): Vaughan, Michael R
• Application Number:
  US11/690,034
• Publication Number:
  US 20070237327A1
• Time in Patent Office: 2,161 Days
• Field of Search: None
• US Class Current: 380/28
• CPC Class Codes: H04L 2209/125 Parallelization or pipelining, e.g. for accelerating processing of cryptographic operations
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 9/0637 Modes of operation, e.g. cipher block chaining [CBC], electronic codebook [ECB] or Galois/counter mode [GCM]
• CPC Class Codes: H04L 9/0662 with particular pseudorandom sequence generator
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

An encryption technique is disclosed for encrypting a data segment comprising a plurality of data blocks, wherein the security and throughput of the encryption is enhanced by using blockwise independent bit vectors for reversible combination with the data blocks prior to key encryption. Preferably, the blockwise independent bit vectors are derived from a data tag associated with the data segment. Several embodiments are disclosed for generating these blockwise independent bit vectors. In a preferred embodiment, the data tag comprises a logical block address (LBA) for the data segment. Also disclosed herein is a corresponding decryption technique as well as a corresponding symmetrical encryption/decryption technique.

Claims

1. A method of encrypting a data segment, the data segment comprising a plurality of data blocks, each data block comprising a plurality of data bits, the method comprising:

encrypting a first plurality of data blocks of the data segment by (1) generating a first plurality of bit vectors, (2) reversibly combining each of the first plurality of data blocks with a corresponding one of the first plurality of bit vectors to thereby generate a first plurality of data block-bit vector combinations, and (3) performing an encryption operation on the first plurality of data block-bit vector combinations, wherein the first plurality of bit vectors have values that are independent of the encryption operations performed on the first plurality of data blocks; and

encrypting a second plurality of data blocks of the data segment by (1) generating a second plurality of bit vectors based at least in part upon a value of one of the first plurality of encrypted data block-bit vector combinations, (2) reversibly combining each of the second plurality of data blocks with a corresponding one of the second plurality of bit vectors to thereby generate a second plurality of data block-bit vector combinations, and (3) performing an encryption operation on the second plurality of data block-bit vector combinations; and

wherein the method steps are performed by a circuit, wherein the circuit comprises a block cipher circuit and a sequence generator circuit, the block cipher circuit comprising a plurality m of pipelined stages, the block cipher circuit pipelined stages simultaneously performing, in a pipelined fashion, a portion of the encrypting steps on a plurality m of different data block-bit vector combinations corresponding to m data blocks of the data segment, the sequence generator circuit performing the steps of generating the first and second plurality of bit vectors, the sequence generator circuit comprising counter control logic, the method further comprising the counter control logic (1) generating a count value indicative of how many data blocks of the same data segment have been processed by the block cipher circuit, (2) determining whether a condition corresponding to a feedback stride has been met such that the counter control logic determines that the feedback stride condition has been met in response to at least m data blocks of the same data segment having been processed by the block cipher circuit, (3) in response to a determination that the condition corresponding to the feedback stride has not been met, selectively controlling the generating step to generate the first plurality of bit vectors, and (4) in response to a determination that the condition corresponding to the feedback stride has been met, selectively controlling the generating step to generate the second plurality of bit vectors.

2. The method of claim 1 wherein the step of generating the first plurality of bit vectors comprises generating the first plurality of bit vectors based at least in part upon a data tag associated with the data segment.

3. The method of claim 2 wherein the step of generating the first plurality of bit vectors further comprises randomizing the values of the first plurality of bit vectors.

4. The method of claim 1 wherein the steps of generating the first and second plurality of bit vectors comprise:

the sequence generator circuit (1) receiving a data tag associated with the data segment, (2) generating a randomized bit vector based on the received data tag, (3) receiving feedback data corresponding to the value of one of the first plurality of encrypted data block-bit vector combinations, (4) selecting as between null data and the feedback data based on the determining step such that the null data is selected in response to a determination that the condition corresponding to the feedback stride has not been met and the feedback data is selected in response to a determination that the condition corresponding to the feedback stride has been met, and (5) combining the generated randomized bit vector with the selected data to thereby generate an output bit vector for subsequent reversible combination with a data block during the encryption operation.

5. The method of claim 4 wherein the combining step comprises the sequence generator circuit reversibly combining the generated randomized bit vector with the selected data to thereby generate the output bit vector for subsequent reversible combination with a data block during the encryption operation.

6. The method of claim 1 wherein the steps of generating the first and second plurality of bit vectors comprise:

the sequence generator circuit (1) receiving a data tag associated with the data segment, (2) receiving feedback data corresponding to the value of one of the first plurality of encrypted data block-bit vector combinations, (3) selecting as between the data tag and the feedback data based on the determining step such that the data tag is selected in response to a determination that the condition corresponding to the feedback stride has not been met and the feedback data is selected in response to a determination that the condition corresponding to the feedback stride has been met, and (4) generating a randomized bit vector based on the selected data as an output bit vector for subsequent reversible combination with a data block during the encryption operation.

7. The method of claim 1 further comprising performing the method steps in parallel via a plurality of parallel block cipher circuits and sequence generator circuits.

8. The method of claim 1 wherein the encrypting steps comprise symmetrically encrypting the first and second plurality of data blocks by reversibly combining each of the first and second plurality of encrypted data block bit-vector combinations with the corresponding bit vectors reversibly combined with the data blocks corresponding thereto.

9. The method of claim 1 wherein the circuit comprises a programmable processor for performing the method steps in response to executing software.

10. The method of claim 9 wherein the programmable processor comprises a plurality of general purpose processors for performing the method steps in response to executing software.

11. The method of claim 1 wherein the circuit comprises a reconfigurable logic device for performing the method steps.

12. The method of claim 11 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA) for performing the method steps.

13. The method of claim 1 wherein the circuit comprises a chip multi-processor (CMP) for performing the method steps.

14. The method of claim 1 wherein the circuit comprises an application-specific integrated circuit (ASIC) for performing the method steps.

15. A method of encrypting a data segment, said data segment comprising a plurality of data block groups, each of said data block groups comprising a plurality of data blocks, the method comprising:

a sequence generator circuit creating a first plurality of bit vectors, wherein the bit vectors of the first plurality of bit vectors comprise blockwise independent bit vectors, the sequence generator circuit comprising counter control logic;

a block cipher circuit encrypting the data blocks of a first data block group based at least in part upon the first plurality of bit vectors that are combined with the data blocks of the first data block group, the block cipher circuit comprising a plurality m of pipelined stages, the block cipher circuit pipelined stages simultaneously performing, in a pipelined fashion, a portion of the first data block group encrypting step on a plurality m of different data blocks corresponding to the data blocks of the first data group;

the sequence generator circuit creating a second plurality of bit vectors based at least at part on one of the previously encrypted data blocks;

the block cipher circuit encrypting the data blocks of a data block group after the first data block group based at least in part upon the second plurality of bit vectors that are combined with the data blocks of the data block group after the first data block group, the data block groups belonging to the same data segment, and the block cipher circuit pipelined stages simultaneously performing, in a pipelined fashion, a portion of the second data block group encrypting step on a plurality m of different data blocks corresponding to m data blocks of the second data block group; and

the counter control logic (1) generating a count value indicative of how many data blocks of the same data block group have been processed by the block cipher circuit, (2) determining whether a condition corresponding to a feedback stride has been met such that the counter control logic determines that the feedback stride condition has been met in response to at least m data blocks of the first data block group having been processed by the block cipher circuit, (3) in response to a determination that the condition corresponding to the feedback stride has not been met, selectively controlling the sequence generator to create the first plurality of bit vectors, and (4) in response to a determination that the condition corresponding to the feedback stride has been met, selectively controlling the sequence generator to create the second plurality of bit vectors.

16. The method of claim 15 wherein the steps of creating the first and second plurality of bit vectors comprise:

the sequence generator circuit (1) receiving a data tag associated with the data segment, (2) generating a randomized bit vector based on the received data tag, (3) receiving feedback data corresponding to a previously encrypted data block, (4) selecting as between null data and the feedback data based on the determining step such that the null data is selected in response to a determination that the condition corresponding to the feedback stride has not been met and the feedback data is selected in response to a determination that the condition corresponding to the feedback stride has been met, and (5) combining the generated randomized bit vector with the selected data to thereby generate an output bit vector for subsequent reversible combination with a data block during the encrypting steps.

17. The method of claim 16 wherein the combining step comprises the sequence generator circuit reversibly combining the generated independent bit vector with the selected data to thereby generate the output bit vector for subsequent reversible combination with a data block during the encrypting steps.

18. The method of claim 15 wherein the steps of creating the first and second plurality of bit vectors comprise:

the sequence generator circuit (1) receiving a data tag associated with the data segment, (2) receiving feedback data corresponding to a previously encrypted data block, (3) selecting as between the data tag and the feedback data based on the determining step such that the data tag is selected in response to a determination that the condition corresponding to the feedback stride has not been met and the feedback data is selected in response to a determination that the condition corresponding to the feedback stride has been met, and (4) generating a randomized bit vector based on the selected data as an output bit vector for subsequent reversible combination with a data block during the encrypting steps.

19. The method of claim 15 further comprising performing the method steps in parallel via a plurality of parallel block cipher circuits and sequence generator circuits.

20. The method of claim 15 wherein the encrypting steps comprise symmetrically encrypting the data blocks of the first data block group and the data blocks of the data block group after the first data block group by reversibly combining each of the encrypted data blocks with the corresponding bit vectors combined with the data blocks corresponding thereto.

21. The method of claim 15 wherein the circuit comprises a programmable processor for performing the method steps in response to executing software.

22. The method of claim 21 wherein the programmable processor comprises a plurality of general purpose processors for performing the method steps in response to executing software.

23. The method of claim 15 wherein the circuit comprises a reconfigurable logic device for performing the method steps.

24. The method of claim 23 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA) for performing the method steps.

25. The method of claim 15 wherein the circuit comprises a chip multi-processor (CMP) for performing the method steps.

26. The method of claim 15 wherein the circuit comprises an application-specific integrated circuit (ASIC) for performing the method steps.

27. A system for encrypting a plurality of data block groups, at least some of said data block groups comprising a plurality of data blocks, said system comprising:

an encryptor circuit; and

a sequence generator circuit configured to generate at least two types of bit vectors for use by the encryptor circuit, a first type of bit vector being blockwise independent and a second type of bit vector being dependent on at least one encrypted data block of a prior data block group;

wherein the encryptor circuit is configured to reversibly combine the data blocks of at least two of the data block groups with a plurality of bit vectors generated by the sequence generator to thereby generate a plurality of data block-bit vector combinations;

wherein the encryptor circuit comprises a block cipher circuit for encrypting the data block-bit vector combinations, the block cipher circuit comprising a plurality m of pipelined stages for simultaneously processing, in a pipelined fashion, a plurality m of different data block-bit vector combinations corresponding to m data blocks of the data block groups;

wherein the sequence generator circuit comprises counter control logic, the counter control logic configured to (1) generate a count value indicative of how many data block-bit vector combinations corresponding to data blocks belonging to the same data block group have been processed by the block cipher circuit, (2) determine whether a condition corresponding to a feedback stride has been met in response to the count value indicating that at least m data block-bit vector combinations corresponding to m data blocks belonging to the same data block group have been processed by the block cipher circuit, (3) in response to a determination that the feedback stride condition has not been met, selectively control the sequence generator circuit to output a bit vector of the first type, and (4) in response to a determination that the feedback stride condition has been met, selectively control the sequence generator circuit to output a bit vector of the second type.

28. The system of claim 27 wherein the sequence generator circuit further comprises a multiplexer, a bit vector sequence generator circuit, and a combiner circuit;

wherein the multiplexer is configured to receive as inputs null data and the at least one encrypted data block of a prior data block group;

wherein the counter control logic is configured to control the multiplexer to select which of the inputs is passed as an output based on the determination operation such that the null data is selected in response to a determination that the condition corresponding to the feedback stride has not been met and the at least one encrypted data block of a prior data block group is selected in response to a determination that the condition corresponding to the feedback stride has been met;

wherein the bit vector sequence generator circuit is configured to (1) receive a data tag associated with the data segment, and (2) generate a randomized bit vector based on the received data tag; and

wherein the combiner circuit is configured to combine the output from the multiplexer with the randomized bit vector generated by the bit vector sequence generator circuit to thereby generate an output bit vector for delivery to the encryptor circuit for subsequent reversible combination with a data block by the encryptor circuit.

29. The system of claim 28 wherein the combiner circuit is configured to reversibly combine the output from the multiplexer with the randomized bit vector generated by the bit vector sequence generator circuit to thereby generate the output bit vector for delivery to the encryptor circuit for subsequent reversible combination with a data block by the encryptor circuit.

30. The system of claim 27 wherein the data block groups are members of a data segment, and wherein the sequence generator circuit further comprises a multiplexer and a bit vector sequence generator circuit;

wherein the multiplexer is configured to receive as inputs a data tag associated with the data segment and the at least one encrypted data block of a prior data block group;

wherein the counter control logic is configured to control the multiplexer to select which of the inputs is passed as an output based on the determination operation such that the data tag is selected in response to a determination that the condition corresponding to the feedback stride has not been met and the at least one encrypted data block of a prior data block group is selected in response to a determination that the condition corresponding to the feedback stride has been met;

wherein the bit vector sequence generator circuit is configured to generate a randomized bit vector based on the output from the multiplexer to thereby generate an output bit vector for delivery to the encryptor circuit for subsequent reversible combination with a data block by the encryptor circuit.

31. The system of claim 27 further comprising a plurality of the encryptor circuits in parallel and a circuit upstream from the parallel encryptor circuits, the upstream circuit configured to receive a stream comprising a plurality of the data block groups and distribute the data block groups to the parallel encryptor circuits for parallel processing thereby.

32. The system of claim 27 wherein the encryptor circuit comprises a symmetric encryptor circuit.

33. The system of claim 27 wherein the encryptor circuit and the sequence generator circuit are implemented on a programmable processor.

34. The system of claim 33 wherein the programmable processor comprises a plurality of general purpose processors.

35. The system of claim 27 wherein the encryptor circuit and the sequence generator circuit are implemented on a reconfigurable logic device.

36. The system of claim 35 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).

37. The system of claim 27 wherein the encryptor circuit and the sequence generator circuit are implemented on a chip multi-processor (CMP).

38. The system of claim 27 wherein the encryptor circuit and the sequence generator circuit are implemented on an application-specific integrated circuit (ASIC).

39. An apparatus comprising:

an encryption circuit for encrypting a plurality of data blocks of a data segment, the encryption circuit comprising a combiner circuit, a block cipher circuit, and a sequence generator circuit;

wherein, for each of the data blocks of the data segment,

the sequence generator circuit is configured to generate a bit vector for delivery to the combiner circuit;

the combiner circuit is configured to (1) receive the bit vector generated by the sequence generator circuit for delivery thereto, and (2) reversibly combine the received bit vector with a data block of the data segment to thereby generate a bit vector-data block combination;

the block cipher circuit comprising a plurality m of pipelined stages for simultaneously processing, in a pipelined fashion, a plurality m of different bit vector-data block combinations corresponding to m data blocks of the data segment that are generated by the combiner circuit to thereby generate a plurality of encrypted data blocks; and

the sequence generator circuit is further configured to (1) receive a feedback input of an encrypted data block from the block cipher circuit, (2) track a configurable feedback stride condition as the plurality of data blocks are processed by the encryption circuit by generating a count value such that the sequence generator circuit determines that the feedback stride condition has been met in response to at least m data blocks of the same data segment having been processed by the block cipher circuit, (3) selectively control the generation of the bit vector in response to the feedback stride condition being met such that the generated bit vector for delivery to the combiner circuit comprises a blockwise dependent bit vector based on the feedback input, and (4) selectively control the generation of the bit vector in response to the feedback stride condition not being met such that the generated bit vector for delivery to the combiner circuit comprises a blockwise independent bit vector, the sequence generator circuit thereby being configured to generate a plurality of the blockwise dependent bit vectors and a plurality of the blockwise independent bit vectors for combination with a plurality of the data blocks of the same data segment prior to encryption by the block cipher circuit.

40. The apparatus of claim 39 wherein the combiner circuit comprises a first combiner circuit, wherein the sequence generator circuit comprises a multiplexer, counter control logic, a bit vector sequence generator circuit, and a second combiner circuit;

the multiplexer configured to receive as inputs null data and the feedback input;

the counter control logic configured to (1) determine whether the feedback stride condition has been met based at least in part on the count value, (2) in response to a determination that the feedback stride condition has not been met, control the multiplexer to pass the null data as an output, and (3) in response to a determination that the feedback stride condition has been met, control the multiplexer to pass the feedback input as an output;

the bit vector sequence generator circuit configured to (1) receive a data tag associated with the data segment, and (2) generate a randomized bit vector based on the received data tag; and

the second combiner circuit is configured to combine the output from the multiplexer with the randomized bit vector generated by the bit vector sequence generator circuit to thereby generate the bit vector for delivery to the first combiner circuit.

41. The apparatus of claim 40 wherein the second combiner circuit is configured to reversibly combine the output from the multiplexer with the randomized bit vector generated by the bit vector sequence generator circuit to thereby generate the bit vector for delivery to the first combiner circuit.

42. The apparatus of claim 39 wherein the sequence generator circuit comprises a multiplexer, counter control logic, and a bit vector sequence generator circuit;

the multiplexer configured to receive as inputs a data tag associated with the data segment and the feedback input;

the counter control logic configured to (1) determine whether the feedback stride condition has been met based at least in part on the count value, (2) in response to a determination that the feedback stride condition has not been met, control the multiplexer to pass the data tag as an output, and (3) in response to a determination that the feedback stride condition has been met, control the multiplexer to pass the feedback input as an output;

the bit vector sequence generator circuit configured to (1) receive the output from the multiplexer, and (2) generate a randomized bit vector based on the received output from the multiplexer to thereby generate the bit vector for delivery to the combiner circuit.

43. The apparatus of claim 39 further comprising a plurality of the encryption circuits in parallel and a circuit upstream from the parallel encryption circuits, the upstream circuit configured to receive a stream comprising a plurality of data blocks and distribute the data blocks to the parallel encryptor circuits for parallel processing thereby such that each parallel encryption circuit receives a plurality of data blocks of the same data segment.

44. The apparatus of claim 39 wherein the combiner circuit comprises a first combiner circuit, the encryption circuit further comprising a second combiner circuit for reversibly combining the encrypted data block generated by the block cipher circuit with the generated bit vector to thereby render the encryption circuit a symmetric encryption circuit.

45. The apparatus of claim 39 wherein the combiner circuit, the block cipher circuit, and the sequence generator circuit are implemented on a programmable processor.

46. The apparatus of claim 45 wherein the programmable processor comprises a plurality of general purpose processors.

47. The apparatus of claim 39 wherein the combiner circuit, the block cipher circuit, and the sequence generator circuit are implemented on a reconfigurable logic device.

48. The apparatus of claim 47 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).

49. The apparatus of claim 39 wherein the combiner circuit, the block cipher circuit, and the sequence generator circuit are implemented on a chip multi-processor (CMP).

50. The apparatus of claim 39 wherein the combiner circuit, the block cipher circuit, and the sequence generator circuit are implemented on an application-specific integrated circuit (ASIC).

51. An apparatus comprising:

an encryption circuit for encrypting a plurality of data blocks of a data segment, the encryption circuit comprising a combiner circuit, a block cipher circuit, and a sequence generator circuit;

the block cipher circuit comprising a plurality m of pipelined stages for simultaneously processing, in a pipelined fashion, a plurality m of different bit vector-data block combinations corresponding to m data blocks of the data segment that are generated by the combiner circuit to thereby generate a plurality of encrypted data blocks; and

the sequence generator configured to selectively switch between a blockwise independent randomized (BIR) mode and a cipher block chaining (CBC) mode based on a configurable feedback stride condition, the configurable feedback stride condition corresponding to the block cipher circuit completing encryption of at least the bit vector-data block combination corresponding to the first of the m data blocks, wherein the sequence generator circuit comprises counter control logic configured to track when the feedback stride condition is met, and wherein the sequence generator is further configured to (1) generate and output a plurality of randomized blockwise independent bit vectors while in the BIR mode, and (2) generate and output a plurality of blockwise dependent bit vectors while in the CBC mode, the blockwise dependent bit vectors being based on a previously encrypted bit vector-data block combination fed back from the block cipher circuit;

the combiner circuit being configured to (1) receive a streaming input of the data blocks, (2) receive an input of the bit vectors output by the sequence generator circuit, and (3) reversibly combine the received bit vectors with the received streaming data blocks to generate a plurality of bit vector-data block combinations for delivery to the block cipher circuit; and

wherein the sequence generator is further configured to (1) operate in the BIR mode while the block cipher circuit is processing the bit vector-data block combinations corresponding to the first m data blocks of the same data segment, and (2) switch to the CBC mode in response to the feedback stride condition being met, the block cipher circuit thereby being configured to generate the plurality of encrypted data blocks wherein at least the first m encrypted data blocks of the same data segment are encrypted in combination with blockwise independent bit vectors and wherein a plurality of the other encrypted data blocks of the same data segment are encrypted in combination with blockwise dependent bit vectors.

52. The apparatus of claim 51 wherein the encryption circuit is implemented on a programmable processor.

53. The apparatus of claim 52 wherein the programmable processor comprises a plurality of general purpose processors.

54. The apparatus of claim 51 wherein the encryption circuit is implemented on a reconfigurable logic device.

55. The apparatus of claim 54 wherein the reconfigurable logic device comprises a field programmable gate array (FPGA).

56. The apparatus of claim 51 wherein the encryption circuit is implemented on a chip multi-processor (CMP).

57. The apparatus of claim 51 wherein the encryption circuit is implemented on an application-specific integrated circuit (ASIC).