Patent Publication Number: US-8983063-B1

Title: Method and system for high throughput blockwise independent encryption/decryption

Description:
CROSS-REFERENCE AND PRIORITY CLAIM TO RELATED PATENT APPLICATIONS 
     This application is a continuation of U.S. patent application Ser. No. 13/759,227, filed Feb. 5, 2013, and entitled “Method and System for High Throughout Blockwise Independent Encryption/Decryption”, now U.S. Pat. No. 8,737,606, which is a continuation of U.S. patent application Ser. No. 11/690,034, filed Mar. 22, 2007, and entitled “Method and System for High Throughout Blockwise Independent Encryption/Decryption”, now U.S. Pat. No. 8,379,841, which claims priority to provisional patent application 60/785,821, filed Mar. 23, 2006, and entitled “Method and System for High Throughput Blockwise Independent Encryption/Decryption”, the entire disclosures of each of which are incorporated herein by reference. 
    
    
     FIELD OF THE INVENTION 
     The present invention relates to improved techniques for encrypting and decrypting data. 
     BACKGROUND AND SUMMARY OF THE INVENTION 
     The need for effective and efficient data encryption/decryption is widespread throughout today&#39;s world. Whether it be data maintained by a governmental agency that pertains to national security or data maintained by a private company that pertains to the company&#39;s trade secrets and/or confidential information, the importance of effective and efficient encryption/decryption cannot be understated. 
     Effective encryption/decryption is needed to preserve the integrity of the subject data. Efficient encryption/decryption is needed to prevent the act of encrypting/decrypting the subject data from becoming an overwhelming burden on the party that maintains the subject data. These needs exist in connection with both “data at rest” (e.g., data stored in nonvolatile memory) and “data in flight” (e.g., data in transit from one point to another such as packet data transmitted over the Internet). 
     A number of data encryption/decryption techniques are known in the art. Many of these encryption techniques utilize a block cipher (see, e.g., block cipher  100  in  FIG. 1 ). A block cipher is a cryptographic mechanism that operates on fixed length blocks of plaintext and produces fixed length blocks of ciphertext (see, e.g., blocks  108 ,  110  and  112  in  FIG. 1 ). Plaintext refers to data needing encryption and ciphertext refers to data that has been encrypted. A block cipher encrypts each plaintext block using a key as per well-known key-based encryption algorithms (see, e.g., key  114  in  FIG. 1 ). The key is typically (but need not be) the same size as the plaintext block. Using different keys to encrypt the same block of plaintext typically (but need not) produces different blocks of ciphertext. Block ciphers  100  can operate on data blocks of varying sizes, with typical data block sizes ranging between 64 bits and 512 bits. For example, the Advanced Encryption Standard (AES) block cipher operates on blocks of 128 bits (16 bytes). Encrypting large segments of plaintext requires a mode of encryption operation that defines the flow of a sequence of plaintext data blocks through one or more block ciphers. Likewise, decrypting large segments of ciphertext requires a mode of decryption operation that defines the flow of a sequence of ciphertext data blocks through one or more block ciphers. 
     As an example of one such known mode of encryption/decryption, the electronic codebook (ECB) mode of encryption/decryption is commonly used due to its simplicity and high data throughput. Examples of the ECB mode of encryption/decryption are shown in  FIG. 1 . With the ECB mode, a data segment needing encryption is divided into a plurality of data blocks, each data block comprising a plurality of data bits (see data blocks  102 ,  104  and  106  in  FIG. 1 ). Each block cipher  100  then encrypts each data block independently using key  114 . At time t=t 0 , plaintext data block  102  is encrypted by the block cipher  100  using key  114  to produce ciphertext data block  108 . Subsequently, at time t=t 1 , plaintext data block  104  is encrypted by the block cipher  100  using key  114  to produce ciphertext data block  110 . Then, at time t=t 2 , plaintext data block  106  is encrypted by the block cipher  100  using key  114  to produce ciphertext data block  112 . To later decrypt the ciphertext data blocks  108 ,  110  and  112 , these steps can then be repeated to reconstruct the original plaintext data blocks  102 ,  104 , and  106 . It is worth noting that the same block cipher  100  can be used to both encrypt and decrypt data using a key. 
     With ECB, the lack of sequential blockwise dependency in the encryption/decryption (i.e., feedback loops where the encryption of a given plaintext block depends on the result of encryption of a previous plaintext data block) allows implementations of the ECB mode to achieve high data throughput via pipelining and parallel processing techniques. While ECB exhibits these favorable performance characteristics, the security of ECB&#39;s encryption is susceptible to penetration because of the propagation of inter-segment and intra-segment uniformity in the plaintext to the ciphertext blocks. 
     For example, a 256 bit segment of plaintext containing all zeros that is to be encrypted with a 64 bit block cipher using ECB will be broken down into 4 64-bit blocks of plaintext, each 64-bit plaintext block containing all zeros. When operating on these plaintext blocks, ECB will produce a segment of ciphertext containing four identical blocks. This is an example of intra-segment uniformity. Furthermore, if another such 256-bit all zero segment is encrypted by ECB using the same key, then both of the resulting ciphertext segments will be identical. This is an example of inter-segment uniformity. In instances where intra-segment and/or inter-segment uniformity is propagated through to ciphertext, the security of the ciphertext can be compromised because the ciphertext will still preserve some aspects of the plaintext&#39;s structure. This can be a particularly acute problem for applications such as image encryption. 
     To address intra-segment and inter-segment uniformity issues, there are two commonly-used approaches. One approach is known as cipher block chaining (CBC). An example of the CBC mode of encryption/decryption is shown in  FIG. 2 . The CBC mode combines the most recent ciphertext output from the block cipher with the next input block of plaintext. The first plaintext block to be encrypted is combined with an initialization vector that is a bit string whose bits have random values, thereby providing the CBC mode with inter-segment randomness. 
     As shown in  FIG. 2 , At time t=t 0 , the first plaintext data block  102  is combined with a random initialization vector (IV)  200  using a reversible combinatorial operation  210 , to thereby create a block-vector combination. This block-vector combination is then encrypted by block cipher  100  using key  114  to thereby generate ciphertext block  202 . Next, at time t=t 1 , the ciphertext block  202  is fed back to be combined with the second plaintext block  104  via XOR operation  210 . The resultant block-vector combination is key encrypted by block cipher  100  to produce ciphertext block  204 , which is in turn fed back for combination with the next plaintext block at time t=t 2  to eventually produce ciphertext block  206 . Thus, as can be seen, when the CBC mode is used to encrypt a data segment comprising a plurality of data blocks, the bit vectors that are used for the reversible combinatorial operations with the plaintext data blocks that follow the first plaintext data block are bit vectors that are dependent upon the encryption operation(s) performed on each previously encrypted plaintext data block. 
     Preferably, the reversible combinatorial operation  210  is an XOR operation performed between the bits of the vector  200  and the block  102 . The truth table for an XOR operation between bits X and Y to produce output Z is as follows: 
                                                 X   Y   Z                          0   0   0           0   1   1           1   0   1           1   1   0                        
As is well known, the XOR operation is reversible in that either of the inputs X or Y can be reconstructed by performing an XOR operation between Z and the other of the inputs X or Y. That is, if one XORs X with Y, the result will be Z. If one thereafter XORs Z with Y, then X will be reconstructed. Similarly, if one thereafter XORs Z with X, then Y will be reconstructed.
 
     Thus, on the decryption side, the CBC mode operates to decrypt ciphertext block  202  with the cipher block  100  using key  114  to thereby reconstruct the XOR combination of plaintext data block  102  and the initialization vector  200 . Thereafter, this reconstructed combination can be XORed with the initialization vector  200  to reconstruct plaintext block  102 . Next, at time t=t 1 , the process is repeated for the next ciphertext block  204 , although this time the XOR operation will be performed using ciphertext block  202  (rather than initialization vector  200 ) to reconstruct plaintext data block  104 . Ciphertext block  202  is used in this XOR operation because it was ciphertext block  202  that was used in the XOR operation when plaintext block  104  was encrypted. Then, once again this process is repeated at time t=t 2 , albeit with ciphertext block  204  being used for the XOR combination operation with the output from cipher block  100 . 
     While the use of feedback by the CBC mode addresses the issue of inter-segment and intra-segment uniformity, such feedback imposes a sequential processing flow on the encryption that significantly limits the achievable throughput of the encryption engine. As such, the CBC mode cannot make ready use of pipelining because one of the inputs for the reversible combinatorial operation stage  210  of the encryption for a given data block depends upon the output of the cipher block stage  100  of the encryption performed on the previous data block. That is, because of the feedback, the reversible combinatorial operation stage in a CBC encryption engine must wait for the block cipher to complete its encryption of a given data block-bit vector combination before it can begin to process the next data block. 
     Furthermore, on the decryption side, the CBC mode&#39;s dependence on the sequential order of data block encryption can raise problems when one wants to retrieve only a portion of the encrypted data segment. For example, for a data segment that comprises data blocks DB 1  through DB 20 , when that data segment is encrypted and stored for subsequent retrieval in its encrypted form, an instance may arise where there is a need to retrieve data blocks DB 6  through DB 10 , wherein the other data blocks of the data segment are not needed. However, to be able to successfully decrypt data blocks DB 6  through DB 10 , the retrieval operation and decryption operation will nevertheless need to operate on data blocks DB 1  through DB 5  so that decryption can be performed for data blocks DB 6  through DB 10 . 
     Furthermore, when used for disk encryption, the CBC mode may be vulnerable to a “watermark attack” if the initialization vector  200  is not kept secret (such as may be the case when the initialization vector is derived from a quantity such as a disk volume number). With such an attack, an adversary can determine from the output ciphertext whether or not a specially crafted file is stored. While there are solutions to such an attack (such as using hashing to derive the initialization vector from the data blocks in the sector), these solutions add to the computational complexity of the encryption operation and thus further degrade the throughput and/or increase the computational resources required for the encryption. 
     A second approach is known as the Segmented Integer Counter (SIC) mode, or more succinctly the counter (CTR) mode.  FIG. 3  depicts an example of the SIC/CTR mode of encryption/decryption. The SIC/CTR mode key encrypts a block comprising a combination of a random value (or nonce) and a counter value. This random value-counter combination can be achieved in any of a variety of ways (e.g., concatenation, XOR, etc.) The counter values may be any sequence of values that do not repeat over a long duration, but a simple incremental counter is believed to be the most commonly-used approach. The output of the block cipher  100  is then combined with the plaintext block using a reversible combinatorial operation  210  (e.g., XOR), with the output of the operation  210  being the ciphertext block. The SIC/CTR mode belongs to the general class of encryption modes known as a stream cipher. 
     As shown in  FIG. 3 , at time t=t 0 , the random value  300  is combined with a counter value  308  in some manner to create a random value-counter combination block  302 . This block  302  is then encrypted by block cipher  100  using key  114 , and the output therefrom is then XORed with plaintext block  102  to generate ciphertext block  322 . Next, at time t=t 1 , the random value  300  is combined with a next counter value  310  in some manner to create the random value-counter combination block  304 . This block  304  is then encrypted by block cipher  100  using key  114 , and the output therefrom is then XORed with plaintext block  104  to generate ciphertext block  324 . Finally, at time t=t 2 , the random value  300  is combined with a next counter value  312  in some manner to create the random value-counter combination block  306 . This block  306  is then encrypted by block cipher  100  using key  114 , and the output therefrom is then XORed with plaintext block  106  to generate ciphertext block  326 . 
     On the decryption side, this process can then be reversed where the combination blocks  302 ,  304  and  306  are decrypted by block cipher  100  using key  114 , with the respective outputs therefrom being XORed with the ciphertext blocks  322 ,  324  and  326  respectively to reconstruct plaintext blocks  102 ,  104  and  106 . 
     The SIC/CTR mode of encryption/decryption also suffers from a security issue if data segments are always encrypted with the same random value  300 . If an adversary is able to gather several versions of the encrypted data segment, it would be possible to derive information about the plaintext because the cipher text (C) is simply the XOR of the variable (V) based on the random number and the plaintext (P), e.g., C=P⊕V, thus C⊕C′=P⊕P′. 
     Therefore, the inventors herein believe that a need exists in the art for a robust encryption/decryption technique that is capable of reducing both inter-segment and intra-segment uniformity while still retaining high throughput and exhibiting blockwise independence. As used herein, an encryption operation for a data segment is said to be “blockwise independent” when the encryption operations for each data block of that data segment do not rely on the encryption operation for any of the other data blocks in that data segment. Likewise, a decryption operation for a data segment is said to be “blockwise independent” when the decryption operations for each encrypted data block of that data segment do not rely on the decryption operation for any of the other data blocks in that data segment. 
     Toward this end, in one embodiment, the inventors herein disclose a technique for encryption wherein prior to key encryption, the plaintext data block is combined with a blockwise independent bit vector using a reversible combinatorial operation to thereby create a plaintext block-vector combination. This plaintext block-vector combination is then key encrypted to generate a ciphertext block. This process is repeated for all data blocks of a data segment needing encryption. For decryption of the cipher text blocks produced by such encryption, the inventors herein further disclose an embodiment wherein each ciphertext data block is key decrypted to reconstruct each plaintext block-vector combination. These reconstructed plaintext block-vector combinations can then be combined (using the reversible combinatorial operation) with the corresponding randomized bit vectors that were used for encryption to thereby reconstruct the plaintext blocks. 
     As an improvement relative to the CBC mode of encryption/decryption, each bit vector is blockwise independent. A bit vector is said to be blockwise independent when the value of that bit vector does not depend on any results of an encryption/decryption operation that was performed on a different data block of the data segment. Because of this blockwise independence, this embodiment is amenable to implementations that take advantage of the power of pipelined processing and/or parallel processing. 
     Moreover, because of the blockwise independent nature of the encryption performed by the present invention, a subset of the encrypted data segment can be decrypted without requiring decryption of the entire data segment (or at least without requiring decryption of the encrypted data blocks of the data segment that were encrypted prior to the encrypted data blocks within the subset). Thus, for a data segment that comprises data blocks DB 1  through DB 20 , when that data segment is encrypted and stored for subsequent retrieval in its encrypted form using the present invention, a need may arise to retrieve plaintext versions of encrypted data blocks DB 6  through DB 10  and DB 15 , wherein the other data blocks of the data segment are not needed in their plaintext forms. A preferred embodiment of the present invention supports successful decryption of a subset of data blocks within the encrypted data segment (e.g., data blocks DB 6  through DB 10  and DB 15 ) without requiring the decryption of the data segment&#39;s data blocks that are not members of the subset (e.g., data blocks DB 1  through DB 5 , data blocks DB 11  through DB 14  and data blocks DB 16  through DB 20 ). Accordingly, the present invention supports the decryption of any arbitrary subset of the encrypted data blocks of a data segment without requiring decryption of any data blocks that are non-members of the arbitrary subset even if those non-member data blocks were encrypted prior to the encryption of the data blocks within the arbitrary subset. 
     Similarly, even if an entire encrypted data segment is to be decrypted, the present invention supports the decryption of the encrypted data blocks in a block order independent manner. Further still, the present invention supports the encryption of data blocks in a block order independent manner as well as supports limiting the encryption to only a defined subset of a data segment&#39;s data blocks (wherein such a subset can be any arbitrary subset of the data segment&#39;s data blocks). 
     Furthermore, as an improvement relative to the SIC/CTR mode of encryption/decryption, a greater degree of security is provided by this embodiment because the data that is subjected to key encryption includes the plaintext data (whereas the SIC/CTR mode does not subject the plaintext data to key encryption and instead subjects only its randomized bit vector to key encryption). 
     Preferably, the blockwise independent bit vector is a blockwise independent randomized (BIR) bit vector. As is understood by those having ordinary skill in the art, randomization in this context refers to reproducible randomization in that the same randomized bit vectors can be reproduced by a bit vector sequence generator given the same inputs. Further still, the blockwise independent randomized bit vector is preferably generated from a data tag that is associated with the data segment needing encryption/decryption. Preferably, this data tag uniquely identifies the data segment. In a disk encryption/decryption embodiment, this data tag is preferably the logical block address (LBA) for the data segment. However, it should be noted that virtually any unique identifier that can be associated with a data segment can be used as the data tag for that data segment. It should also be noted that rather than using a single data tag associated with the data segment, it is also possible to use a plurality of data tags that are associated with the data segment, wherein each data tag uniquely identifies a different one of the data segment&#39;s constituent data blocks 
     A bit vector generation operation preferably operates on a data tag to generate a sequence of blockwise independent bit vectors, each blockwise independent bit vector for reversible combination with a corresponding data block. Disclosed herein are a plurality of embodiments for such a bit vector generation operation. As examples, bit vectors can be derived from the pseudo-random outputs of a pseudo-random number generator that has been seeded with the data tag; including derivations that employ some form of feedback to enhance the randomness of the bit vectors. Also, linear feedback shift registers and adders can be employed to derive the bit vectors from the data tag in a blockwise independent manner. 
     The inventors also disclose a symmetrical embodiment of the invention wherein the same sequence of operations are performed on data in both encryption and decryption modes. 
     One exemplary application for the present invention is to secure data at rest in non-volatile storage; including the storage of data placed on tape, magnetic and optical disks, and redundant array of independent disks (RAID) systems. However, it should be noted that the present invention can also be applied to data in flight such as network data traffic. 
     These and other features and advantages of the present invention will be apparent to those having ordinary skill in the art upon review of the following description and figures. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  depicts an example of a known ECB mode of encryption/decryption; 
         FIG. 2  depicts an example of a known CBC mode of encryption/decryption; 
         FIG. 3  depicts an example of a known SIC/CTR mode of encryption/decryption; 
         FIG. 4  depicts an exemplary data segment; 
         FIGS. 5(   a ) and ( b ) depict an embodiment of the present invention in both encryption and decryption modes; 
         FIG. 6  depicts an exemplary bit vector sequence generator; 
         FIGS. 7(   a ) and ( b ) depict exemplary encryption and decryption embodiments of the present invention; 
         FIGS. 8(   a ) and ( b ) depict exemplary encryption and decryption embodiments of the present invention showing their operations over time; 
         FIG. 9  depicts an exemplary embodiment of a bit vector sequence generator; 
         FIGS. 10(   a )-( c ) depict three additional exemplary embodiments of a bit vector sequence generator; 
         FIG. 11  depicts an exemplary embodiment of the present invention where multiple block ciphers are chained together; 
         FIGS. 12(   a ) and ( b ) depict exemplary encryption and decryption embodiments of the present invention that are hybrids of the embodiments of  FIGS. 8(   a ) and ( b ) and the CBC mode of encryption/decryption; 
         FIGS. 12(   c ) and ( d ) depict exemplary embodiments of the bit vector sequence generator for use with the hybrid embodiments of  FIGS. 12(   a ) and ( b ); 
         FIGS. 13(   a ) and ( b ) depict an exemplary embodiment for symmetrical encryption/decryption in accordance with the present invention; 
         FIGS. 14(   a ) and ( b ) depict an exemplary embodiment for symmetrical encryption/decryption in accordance with the present invention wherein the blockwise independent bit vectors are derived from the data segment&#39;s LBA; 
         FIGS. 15(   a ) and ( b ) depict the embodiment of  FIGS. 14(   a ) and ( b ) showing its operation over time; 
         FIGS. 15(   c ) and ( d ) depict a symmetrical encryption/decryption counterpart to the embodiments of  FIGS. 12(   a ) and ( b ); 
         FIG. 16  depicts a parallel architecture for encrypting or decrypting data blocks; 
         FIGS. 17(   a ) and ( b ) depict exemplary hardware environments for the present invention; and 
         FIGS. 18(   a )-( c ) depict exemplary printed circuit boards on which the encryption/decryption embodiments of the present invention can be deployed. 
     
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       FIG. 4  illustrates an exemplary data segment  400  on which the encryption/decryption technique of the present invention can be performed. The data segment  400  comprises a plurality of data blocks  102 ,  104 ,  106 , . . . . Each data block comprises a plurality of data bits and preferably has a fixed length (e.g., 64 bits, 256 bits, etc.). In an exemplary embodiment, wherein AES block ciphers are used, which as explained above operate on 16-byte data blocks, it is preferred that the data blocks  102 ,  104 ,  106  . . . possess a length of 16 bytes. It should also be noted that the size of the data segment  400  is typically much larger than the size of an individual data block. For example, a data storage system may operate on “logical blocks” of data having a size of 512 bytes. In such a case, the “logical block”, which can serve as the data segment  400 , will be a collection of 32 16-byte data blocks. 
       FIG. 5(   a ) illustrates an embodiment of the present invention wherein the encryption operation is segmented into a plurality of stages. At stage  504 , the blockwise independent bit vector  506  is generated, preferably from a data tag  502  that is associated with the data segment  400 . Preferably, the bit vector  506  has a length that is the same as the data blocks of the data segment, although this need not be the case. Further still, it is preferred that the blockwise independent bit vector  506  have a randomized value to thereby enhance the security of the encryption. Also, it is preferred that a different bit vector  506  be generated for each data block of a data segment that is encrypted, although this need not be the case. The bit vectors that are used in the encryption of a data segment&#39;s data blocks should be either stored for subsequent use when it is time to decrypt one or more of the data segment&#39;s data blocks or should be reproducible from a known quantity (such as the data tag) when it is time to decrypt one or more of the data segment&#39;s data blocks. 
     At stage  210 , a reversible combinatorial operation such as a bitwise XOR operation is performed on the blockwise independent bit vector  506  and plaintext data block. This reversible combinatorial operation preferably produces a data block-bit vector combination  508 . 
     At stage  100 , a block cipher performs an encryption operation on the data block-bit vector combination  508  using key  114  as per well-known key encryption techniques (e.g., AES, the Data Encryption Standard (DES), the triple DES (3DES), etc.). The output of the block cipher stage  100  is thus a ciphertext data block that serves as the encrypted counterpart to the plaintext data block that was fed into stage  210 . It should be noted that any of several well-known key management techniques can be used in connection with managing the key(s)  114  used by the block cipher(s)  100 . As such, the inventors do not consider the key management for the block cipher(s)  100  to be any limitation on the present invention. It should also be noted that “keyless” encryption techniques may also be used in the practice of the present invention (e.g., substitution ciphers that do not require a key). 
       FIG. 5(   b ) depicts the decryption counterpart to  FIG. 5(   a ). In  FIG. 5(   a ), the flow of data blocks and stages is reversed such that the ciphertext data block is first key decrypted by stage  100  to reconstruct combination  508 . Combination  508  is in turn combined with the same bit vector  506  that was used when creating that ciphertext data block and using the same reversible combinatorial operation  210  that was used when creating that ciphertext data block, to thereby reconstruct the plaintext data block. 
     As can be seen in  FIGS. 5(   a ) and ( b ), no feedback is required between stages, thus allowing this encryption/decryption technique to be implemented in a pipelined architecture and/or a parallel processing architecture for the achievement of a high throughput when performing encryption/decryption. Thus, as a stream of data blocks are sequentially processed through the encryption/decryption stages, a high throughput can be maintained because the reversible combinatorial stage  210  can operate on a given data block while the block cipher stage  100  simultaneously operates on a different data block because the reversible combinatorial operation stage  210  does not require feedback from the block cipher stage  100  to operate. 
     The data tag  502  may be any data value(s) that can be associated with the data segment  400 . Preferably, the data tag  502  serves as a unique identifier for the data segment  400 , although this need not be the case. A preferred data tag  502  is the logical block address (LBA) for the data segment to be encrypted. An LBA for a data segment is the logical memory address for the data segment that is typically assigned by an Operating System (OS) or memory management system. However, other data tags may be used in the practice of the present invention; examples of which include file identifiers, physical memory addresses, and packet sequence numbers. The source of the data tag can be any of a variety of sources, including but not limited to communication protocol, storage subsystem, and file management systems. 
       FIG. 6  illustrates how a sequence of bit vectors  506  can be generated from a data tag  502 . As an exemplary embodiment of bit vector generation stage  504 , bit vector sequence generator  600  preferably operates to produce a plurality of blockwise independent randomized bit vectors  506   i  from an input comprising data tag  502 .  FIGS. 9 and 10 , to be described hereinafter, illustrate various exemplary embodiments for the bit vector sequence generator  600 . 
       FIGS. 7(   a ) and ( b ) illustrate embodiments of the invention where the data segment&#39;s LBA is used as the data tag  502  for the encryption/decryption operations. Sequence generator  600  processes the LBA to produce a different blockwise independent randomized bit vector  506  for XOR combination ( 210 ) with each plaintext data block. On decryption (shown in  FIG. 7(   b )), the sequence generator  600  operates to produce the same plurality of different bit vectors  506  from the data segment&#39;s LBA as were produced by the sequence generator  600  for encryption (see  FIG. 7(   a )) given the same LBA input. Thus, as shown in  FIG. 7(   b ), each bit vector  506  is then used for XOR combination ( 210 ) with each decrypted ciphertext block. 
       FIG. 8(   a ) illustrates the embodiment of  FIG. 7(   a ) (wherein the LBA is labeled as an initialization vector), but depicting how the encryption operation can proceed over time. Thus, at time t=t 0 , plaintext data block  102  is reversibly combined with bit vector  506   1  produced by sequence generator  600  to generate a data block-bit vector combination that is key encrypted by a block cipher  100  to thereby produce an encrypted data block-bit vector combination  802  which serves as the ciphertext block. Subsequently, at time t=t 1 , the sequence generator produces another bit vector  506   2  for reversible combination with plaintext data block  104 . The resultant data block-bit vector combination is then key encrypted by the block cipher  100  to thereby produce an encrypted data block-bit vector combination  804  which serves as the next ciphertext block. This process then continues for subsequent clock cycles as additional data blocks of the data segment  400  are encrypted. 
       FIG. 8(   b ) depicts the decryption counterpart to  FIG. 8(   a ), wherein ciphertext blocks  802 ,  804  and  806  are decrypted in accordance with the embodiment of  FIG. 7(   b ) to reproduce plaintext data blocks  102 ,  104  and  106 . 
       FIG. 9  depicts an embodiment of the sequence generator  600  wherein a data tag  502  such as the LBA is used to seed a pseudo-random number generator (PRNG)  900 . When encrypting a first data block, the bit vector  506  is initialized to be the LBA itself. Then, when encrypting subsequent data blocks, the bit vector  506  is incremented through adder  902  by the pseudo-random output from the PRNG  900 . Preferably, a new pseudo-random number is generated by the PRNG  900  for each new data block of the data segment needing encryption. By using a PRNG  900  to generate counter increments for the bit vector  506 , the sequence of bit vectors  506  used for encrypting different data segments (identified by their LBA) will be difficult to predict and provide more security than a simple counter. For decryption, it should be noted that the PRNG  900  should operate to produce the same sequence of pseudo-random outputs given the same data tag input, to thereby enable the generation of the same set of bit vectors  506  when decrypting the encrypted data segment (or a subset of the encrypted data segment). 
     As can be seen, the sequence of bit vectors  506   1 ,  506   2 , . . .  506   n  produced by the sequence generator  600  of  FIG. 9  will be sequentially dependent in that each successive bit vector  506   i  will be a function of the previous bit vector  506   i-1  (via feedback to adder  902 ). This sequential nature of the bit vectors does not preclude their use in a blockwise independent encryption/decryption scheme. For example, consider a case where a data tag (such as an LBA) for a data segment comprising twenty data blocks is used as the basis for the blockwise independent bit vectors, but it is only desired to encrypt/decrypt data blocks DB 6  through DB 10 . In such a case, the sequence generator  600  is preferably initialized with the data tag and the bit vectors for data blocks DB 1  through DB 5  are generated but discarded by the sequence generator  600 . Such a configuration will require the reversible combinatorial stage  210  and the downstream encryption stage  100  to pause until the bit vector  506   6  for data block DB 6  is generated. While this pause produces a delay and degradation in throughput for the encryption/decryption technique, relative to the multiple iterations through a block cipher as required in the conventional CBC mode of encryption, the inventors herein believe that this delay and throughput degradation is relatively minor. For example, this pause will not need to wait for data blocks DB 1  through DB 5  to be encrypted/decrypted via block cipher  100  before being able to process data block DB 6 . 
     It should also be noted that if the encryption/decryption technique involves using a data tag that is unique to each data block to generate each data block&#39;s corresponding blockwise independent bit vector  506 , the need to pause operations while cycling through unneeded bit vectors can be eliminated. 
       FIGS. 10(   a )-( c ) depict other examples of sequence generator embodiments.  FIG. 10(   a ) discloses a sequence generator  600  that uses the LBA  502  to seed a PRNG  900  whose pseudo-random outputs then serve as the bit vectors  506  for combination with the data segment&#39;s data blocks. As with the embodiment of  FIG. 9 , preferably the LBA itself is used as the bit vector  506  for reversible combination with a first data block to be encrypted/decrypted. 
       FIG. 10(   b ) discloses a sequence generator  600  that uses the LBA  502  to seed a linear feedback shift register (LFSR)  1000  whose outputs then serve as the bit vectors  506  for combination with the data segment&#39;s data blocks. 
       FIG. 10(   c ) discloses a sequence generator  600  that uses the LBA  502  to seed a feedback counter  1002 , wherein the feedback counter  1002  has a constant increment  1004 , and wherein the counter&#39;s outputs then serve as the bit vectors  506  for combination with the data segment&#39;s data blocks. As with the embodiments of  FIG. 9  and  FIG. 10(   a ), preferably the LBA itself is used as the bit vector  506  for reversible combination with a first data block to be encrypted/decrypted. It should be noted that the sequence generator embodiment of  FIG. 10(   c ) can be configured to accommodate encryption/decryption of arbitrary subsets of data blocks within a data segment without requiring a pause while the sequence generator cycles through unneeded bit vectors. If an encryption/decryption is to begin at a data block within a data segment that is not the first data block of the data segment (e.g., data block DB k  of a data segment, wherein k&gt;1), the data tag  502  (such as an LBA) that is passed to the sequence generator  600  can be computed as:
 
Data Tag′=Data Tag+ k *Constant
 
wherein Data Tag′ represents the value of the data tag  502  that is fed into the sequence generator  600 , wherein Data Tag represents the value of the data tag that is associated with the data segment, wherein k represents the block number within the data segment of the data block to be encrypted/decrypted, and wherein Constant represents the value of the incremental constant  1004  for adder  1002 . This computation can be performed either within the sequence generator (in which case it will be the value Data Tag that is fed into the sequence generator  600 ) or in a module upstream from the sequence generator. Appropriate control logic is preferably used to control whether the multiplexer passes the data tag value  502  or the output of adder  1002  on to the reversible combinatorial stage  210 .
 
     It should also be noted that the present invention need not be limited to a single combination of a blockwise independent bit vector randomizer and a block cipher. Pairs of sequence generators  600 , reversible combinatorial operations  210 , and block ciphers  100  can be sequentially chained as shown in  FIG. 11 . Thus, a first sequence generator  600   1 , a first reversible combinatorial operator  210   1  and a first block cipher  100   1  can operate to produce an encrypted data block-bit vector combination that is fed into a second reversible combinatorial operator  210   2  for reversible combination with a bit vector produced by a second sequence generator  600   2 . The resultant encrypted data block-bit vector-bit vector combination produced by reversible combinatorial operator  210   2  can then be key encrypted by block cipher  100   2 . The inventors herein believe that such chaining can enhance the security of an encryption system. Moreover, the inventors note that still greater numbers of sequence generators  600 , reversible combinatorial operations  210 , and block ciphers  100  can be sequentially chained to enhance security if desired by a practitioner of this embodiment of the invention. It should also readily be understood that corresponding sequential decryption chains can be used. Preferably, in such a sequential chaining embodiment, each different sequence generator  600   i  will operate to produce different set of bit vectors given the same input. 
     Further still, the inventors herein disclose an embodiment that hybridizes the present invention and the CBC mode of encryption/decryption.  FIG. 12(   a ) illustrates an example of such an embodiment to perform encryption. This configuration provides the flexibility to include some feedback for higher security. Note that the first output of ciphertext  1200  is not used as feedback to the second encryption operation  1202 , rather it is used as feedback for encryption performed by subsequent block i where i is a feedback stride. The feedback stride can then be chosen to provide a favorable balance among security and throughput. If the feedback stride i is greater than or equal to the number of pipeline stages in the block cipher, then there is no performance penalty because there will need not be a delay in the insertion of a block into a block cipher. Furthermore, if one does choose a lower feedback stride value that would require a delay, one can introduce stall cycles in the processing. The added security provided by the technique of  FIG. 12(   a ) is that the encryption technique of  FIG. 12(   a ) does not exclusively rely on the sequence generator  600  (or the PRNG  900  in the sequence generator  600 ) to generate long, difficult to predict initialization sequences. Once the system begins feeding back ciphertext from previous blocks via feedback link  1206 , the system gains the strength of the block cipher in producing more random initialization bit vectors. This technique essentially narrows the visibility of an observer into the “window” of the random increments produced by the PRNG  900 . Thus, it is more difficult for observers to reconstruct the entire random sequence generated by the PRNG  900  (thereby making it more difficult for one to crack the encryption scheme).  FIG. 12(   b ) depicts a decryption counterpart to  FIG. 12(   a ). 
       FIGS. 12(   c ) and ( d ) depict exemplary embodiments of a sequence generator  600 ′ that could be used to generate bit vectors for the embodiments of  FIGS. 12(   a ) and ( b ). In the example of  FIG. 12(   c ), the sequence generator  600 ′ comprises any of the embodiments for sequence generator  600  as described in connection with  FIGS. 9 and 10(   a )-( c ). The bit vector  506  that is output by the sequence generator  600  is preferably reversibly combined with the feedback ciphertext i from link  1206  via reversible combinatorial operator  1250  to produce bit vector  506 ′ (which is in turn provided to the reversible combinatorial operator  210 ) when the conditions for the feedback stride i are met. Sequence generator  600 ′ also preferably includes appropriate control logic to ensure that the feedback stride defined for the hybrid embodiment is obeyed. As an example, such control can be achieved with a multiplexer  1262  whose inputs are either null value or the feedback ciphertext i. A counter-based control circuit  1260  can define which of the inputs to multiplexer  1262  are passed to the reversible combinatorial operator  1250  such that the feedback ciphertext i is only passed on when it is time to use the ciphertext to further randomize the bit vectors. 
       FIG. 12(   d ) depicts another exemplary embodiment for the sequence generator  600 ′. In the example of  FIG. 12(   d ), the sequence generator  600 ′ comprises any of the embodiments for sequence generator  600  as described in connection with  FIGS. 9 and 10(   a )-( c ). The sequence generator  600  will receive as an input either the data tag  502  or the feedback ciphertext i, as defined by control logic. The control logic is preferably configured to pass on the feedback ciphertext to seed the sequence generator  600  only when the conditions for the feedback stride i are met. As an example, such control can be achieved with a multiplexer  1262  whose inputs are either the data tag  502  or the feedback ciphertext i. A counter-based control circuit  1260  can define which of the inputs to multiplexer  1262  are passed to the sequence generator  600  such that the feedback ciphertext i is only passed on when it is time to use the ciphertext to further randomize the bit vectors. 
     As another embodiment of the present invention, the inventors disclose a symmetrical embodiment for encryption/decryption. With “symmetrical” encryption/decryption, the same order of operations can be performed on data blocks to both encrypt and decrypt those data blocks. Thus, with a symmetrical embodiment, the same module that is used to encrypt data can be used to decrypt encrypted data.  FIGS. 13(   a ) and ( b ) illustrate a symmetrical embodiment of the present invention. As can be seen, the same order of operations is used by  FIG. 13(   a ) to encrypt a data block as is used by  FIG. 13(   b ) to decrypt a ciphertext data block. The symmetrical encryption/decryption engine  1300  comprises a first reversible combinatorial stage  210 , a block cipher operation stage  100 , and a second reversible combinatorial stage  1302 . A bit vector generation stage  504  (such as the sequence generators  600  shown in  FIG. 9  and  FIGS. 10(   a )-( c )) operates to produce blockwise independent bit vectors  506  that are fed to both the first reversible combinatorial stage  210  and the second reversible combinatorial stage  1302 . 
     As shown in  FIG. 13(   a ), for encryption, a plaintext data block is reversibly combined with a blockwise independent bit vector  506  by first reversible combinatorial operation stage  210  (preferably XOR logic), to thereby generate a data block-bit vector combination  508 . Block cipher  100  then performs a block cipher operation on this data block-bit vector combination  508  using a key. The resultant block ciphered data block-bit vector combination  1304  is then reversibly combined with a blockwise independent bit vector  506  by second reversible combinatorial operation stage  1302  (preferably XOR logic), to thereby generate a block ciphered data block-bit vector-bit vector combination  1306 , which can serve as the ciphertext for the plaintext data block. 
     For decryption, as shown in  FIG. 13(   b ), the same order of operations is used, albeit starting from a ciphertext data block rather than a plaintext data block. The ciphertext data block used for decryption will be a block ciphered data block-bit vector-bit vector combination  1306  that was produced during the encryption operation. First reversible combinatorial operation stage  210  operates to reversibly combine such a ciphertext data block with the same bit vector  506  that was used by the second reversible combinatorial operation stage  1302  when encrypting that ciphertext data block. The result of this reversible combination will be a reconstruction of the block ciphered data block-bit vector combination  1304 . Block cipher  100  then performs a block cipher operation (decryption in this example) using the key to reconstruct the data block-bit vector combination  508 . Second reversible combinatorial operation stage  210  then operates to reversibly combine the reconstructed data block-bit vector combination  508  with the same bit vector  506  that was used by the first reversible combinatorial operation stage  210  when encrypting that ciphertext data block. The output of the second reversible combinatorial operation stage  1302  then serves as a reconstruction of the plaintext data block. 
     Timing logic (not shown) can be employed to synchronize the outputs of bit vectors  506  from the bit vector generation stage  504  such that the appropriate bit vector  506  is fed to the second reversible combinatorial stage  1302  for each block ciphered data block-bit vector combination  1304  (or reconstructed data block-bit vector combination  508  for the decryption mode) that is processed thereby. Such synchronization could be designed to accommodate the latency within the block cipher  100  to thereby allow the same bit vector  506  to be used for reversible combination with a given data block by first reversible combinatorial operation stage  210  as is used for later reversible combination with the block ciphered data block-bit vector combination  1304  derived from that given data block by the second reversible combinatorial operation stage  1302 . 
       FIG. 14(   a ) (for encryption mode) and  FIG. 14(   b ) (for decryption mode) depict an example of the symmetrical embodiment of  FIGS. 13(   a ) and ( b ), wherein the bit vectors  506  are derived from the LBA for the data segment  400 . 
       FIG. 15(   a ) (for encryption mode) and  FIG. 15(   b ) (for decryption mode) depict the operation of the embodiment of  FIGS. 14(   a ) and ( b ) over time. 
     It should also be noted that the symmetrical encryption/decryption embodiments described herein can also be used in a hybrid CBC embodiment like the ones shown in  FIGS. 12(   a ) and ( b ). An example of such a symmetrical hybrid embodiment is shown in  FIGS. 15(   c ) and ( d ), wherein the feedback link  1502  carries the block ciphered data block-bit vector-bit vector output  1306  of the second reversible combinatorial operation stage  1302  performed for the first data block. The sequence generators  600 ′ as shown in  FIGS. 12(   c ) and ( d ) can be employed, although the feedback ciphertext will preferably emanate from the output of the second reversible combinatorial operator  1302  rather than the output of the block cipher  100 . 
     As a further embodiment of the present invention, the inventors note that a parallel architecture  1600  such as the one shown in  FIG. 16  can be employed. With this parallel architecture, a stream of incoming data blocks  1604  (which can be either plaintext data blocks or ciphertext data blocks) are separated into a plurality of parallel streams for processing by parallel encryption/decryption engines  1602 . Such encryption/decryption engines can take the form of any of the embodiments of the invention described herein such as those shown in connection with  FIGS. 5(   a ) and ( b ),  7 ( a ) and ( b ),  11 ,  12 ( a ) and ( b ),  13 ( a ) and ( b ), and  14 ( a ) and ( b ). The resultant data streams produced by each parallel encryption/decryption engine  1602  can then be brought together to form the outgoing data stream  1606  (which may be either plaintext data blocks or ciphertext data blocks depending on whether the encryption/decryption engines  1602  performed encryption or decryption). It is also worth noting that each parallel engine  1602  can employ its own bit vector generation stage  504 , or the same bit vector generation stage  504  can be shared by multiple (or all) of the parallel encryption engines  1602 . 
     The encryption/decryption techniques of the present invention can be implemented in a variety of ways including but not limited to a software implementation on any programmable processor (such as general purpose processors, embedded processors, network processors, etc.), a hardware implementation on devices such as programmable logic devices (e.g., field programmable gate arrays (FPGAs)), ASICs, and a hardware and/or software implementation on devices such as chip multi-processors (CMPs), etc. For example, some CMPs include built-in hardware for encryption ciphers, in which case software on parallel processors systems for the CMPs could perform the bit vector generation and reversible combinatorial tasks while offloading the block cipher operations to the dedicated hardware. 
     However, the inventors herein particularly note that the present invention is highly amenable to implementation in reconfigurable logic such as an FPGA. Examples of suitable FPGA platforms for the present invention are those described in the following: U.S. patent application Ser. No. 11/339,892 (filed Jan. 26, 2006, entitled “Firmware Socket Module for FPGA-Based Pipeline Processing” and published as 2007/0174841), published PCT applications WO 05/048134 and WO 05/026925 (both filed May 21, 2004 and entitled “Intelligent Data Storage and Processing Using FPGA Devices”), U.S. patent application Ser. No. 10/153,151 (filed May 21, 2002 entitled “Associative Database Scanning and Information Retrieval using FPGA Devices”, published as 2003/0018630, now U.S. Pat. No. 7,139,743), and U.S. Pat. No. 6,711,558 (entitled “Associative Database Scanning and Information Retrieval”), the entire disclosures of each of which are incorporated by reference herein. 
       FIG. 17(   a ) depicts an example of an implementation environment for the present invention.  FIG. 17(   a ) depicts a system  1700  comprising a host processor  1708  and host RAM  1710  in communication with a disk controller  1706  via bus  1712 . Disk controller  1706  governs access to data store  1704  which may be any device capable of storing data. In an exemplary embodiment, data store  1704  is a mass storage medium such as a RAID system or subsystem. In such an instance, disk controller  1706  is a RAID controller. 
     Data flowing to or from data store  1704  can be routed through reconfigurable logic device  1702  (which may be embodied by an FPGA). One or more firmware application modules (FAMs)  1730  are deployed on the reconfigurable logic using the techniques described in the above-incorporated references. The different stages of the encryption/decryption engine of the present invention can be implemented on the reconfigurable logic device  1702  as a processing pipeline deployed on one or more of these FAMs  1730 . Firmware socket module  1720  can be implemented as described in the incorporated Ser. No. 11/339,892 patent application to control the flow of data to and from the encryption/decryption engine(s) deployed on the reconfigurable logic device  1702  via communication paths  1732  and  1734 . Data to be encrypted and stored in the data store can be routed through the reconfigurable logic device  1702  along with appropriate control instructions for the encryption. Such control information can include the data tag used to generate the blockwise independent bit vectors. Moreover, these control instructions can emanate from any source with access to system bus  1712  including sources that connect to the system bus  1712  over a network. For example, in an embodiment wherein the data segment&#39;s LBA is used as the data tag from which the bit vectors are generated, the LBA can be passed to the FAM pipeline  1730  with the data from the data store  1704  or it can be passed to the FAM pipeline  1730  from processor  1708 . Moreover, the data segments to be encrypted can emanate from any source with access to the reconfigurable logic device  1702 . Encrypted data to be decrypted can also be routed through the reconfigurable logic device  1702  along with appropriate control instructions for the decryption. 
     Thus, when encrypting a data segment to be stored at an LBA of the data store  1704 , the data blocks of the data segment can be streamed through a FAM  1730  on reconfigurable logic device  1702  that is configured to perform encryption in accordance with the teachings of the present invention (with the encryption FAM  1730  preferably deriving the blockwise independent bit vectors  506  from the LBA). The resultant ciphertext produced by the encryption FAM  1730  can then be stored in data store  1704  starting at the LBA. On decryption, the ciphertext data blocks of the encrypted data segment (or a subset thereof) can be streamed through a decryption FAM  1730  (or a symmetrical encryption/decryption FAM  1730 ) to reconstruct the plaintext data segment (or subset thereof). Once again, in an embodiment wherein the blockwise independent bit vectors are derived form the data segment&#39;s LBA, the LBA can also be used as the source of the bit vectors used during the decryption process. 
     It should also be noted that for disk or file encryption operations, it may be desirable to include the platform (e.g., FPGA or ASIC) on which the encryption/decryption engine of the present invention is deployed (or the encryption/decryption engine itself) on-board the disk controller  1706 . It may also be desirable for the encryption/decryption engine to receive all data streaming to/from the disk(s), in which case control information could be added to the data streams to inform the encryption/decryption engine of which data is to be encrypted/decrypted and which data is to be passed through without modification. For example, such control information can take the form of a flag within a data set&#39;s SCSI control block (SCB). 
     The embodiment of  FIG. 17(   b ) depicts the system  1700  wherein bus  1712  is also connected to a network  1742  through network interface  1740 . Such a network  1742  can also serve as a source or destination for data to be encrypted or decrypted (e.g., network data traffic such as network data packets that may need encryption/decryption). It should also be noted that system  1700  can be configured such that bus  1712  connects to a network  1742  (through network interface  1742 ) but not to a data store  1704  (through disk controller  1706 ) if desired by a practitioner of the present invention in view of the use(s) to which the practitioner intends to put the invention. 
       FIG. 18(   a ) depicts a printed circuit board or card  1800  that can be connected to the PCI-X bus  1712  of a computer system (e.g., a commodity computer system or other) for use in encrypting/decrypting data. In the example of  FIG. 18(   a ), the printed circuit board includes an FPGA chip  1802  (such as a Xilinx Virtex 4 FPGA) that is in communication with a memory device  1804  and a PCI-X bus connector  1806 . A preferred memory device  1804  comprises SRAM and DRAM memory. A preferred PCI-X bus connector  1806  is a standard card edge connector. 
       FIG. 18(   b ) depicts an alternate configuration for a printed circuit board/card  1800 . In the example of  FIG. 18(   b ), a private bus  1808  (such as a PCI-X bus), a disk controller  1810 , and a disk connector  1812  are also installed on the printed circuit board  1800 . Any commodity disk interface technology can be supported, as is understood in the art. In this configuration, the firmware socket  1720  also serves as a PCI-X to PCI-X bridge to provide the processor  1708  with normal access to the disk(s) connected via the private PCI-X bus  1808 . 
       FIG. 18(   c ) depicts another alternate configuration for a printed circuit board/card  1800 . In the example of  FIG. 18(   b ), a private bus  1808  (such as a PCI-X bus), a network interface controller  1820 , and a network connector  1822  are also installed on the printed circuit board  1800 . Any commodity network interface technology can be supported, as is understood in the art. In this configuration, the firmware socket  1720  also serves as a PCI-X to PCI-X bridge to provide the processor  1708  with normal access to the network(s) connected via the private PCI-X bus  1808 . 
     It should be further noted that the printed circuit board/card  1800  may also be configured to support both a disk controller/connector  1810 / 1812  and a network interface controller/connector  1820 / 1822  to connect the board  1800  to disk(s) and network(s) via private PCI-X bus  1808 , if desired by a practitioner of the invention. 
     It is worth noting that in either of the configurations of  FIGS. 18(   a )-( c ), the firmware socket  1720  can make memory  1804  accessible to the PCI-X bus, which thereby makes memory  1804  available for use by an OS kernel for the computer system as the buffers for transfers from the disk controller and/or network interface controller to the FAMs. It is also worth noting that while a single FPGA chip  1802  is shown on the printed circuit boards of  FIGS. 18(   a )-( c ), it should be understood that multiple FPGAs can be supported by either including more than one FPGA on the printed circuit board  1800  or by installing more than one printed circuit board  1800  in the computer system. Further still, it should be noted that the printed circuit boards  1800  of the embodiments of  FIGS. 18(   a )-( c ) can use an ASIC chip on which the encryption/decryption engines are deployed rather than an FPGA chip  1802 . if desired by a practitioner of the invention. 
     Exemplary applications for the present invention include but are not limited to general purpose data encryption (e.g., files, images, documents, etc.), disk encryption, streaming message (e.g., packets, cells, etc.) encryption, and streaming image encryption (e.g., streaming reconnaissance imagery, etc.). 
     While the present invention has been described above in relation to its preferred embodiment, various modifications may be made thereto that still fall within the invention&#39;s scope. Such modifications to the invention will be recognizable upon review of the teachings herein. As such, the full scope of the present invention is to be defined solely by the appended claims and their legal equivalents.