Block cipher mode of operation for secure, length-preserving encryption

Abstract

A method for encrypting a plaintext string into ciphertext begins by cipher block chaining (CBC) the plaintext using a first key and a null initialization vector to generate a CBC message authentication code (MAC) whose length is equal to the block length. The plaintext string is then cipher block chained again, now using a second key and the CBC-MAC as the initialization vector, to generate an enciphered string. The CBC-MAC and a prefix of the enciphered string comprising all of the enciphered string except the last block are then combined to create the ciphertext. The described mode of operation is length-preserving, yet has the property that related plaintexts give rise to unrelated ciphertexts.

What is claimed is: 
     
       1. A computer-implemented method, using first and second keys, to encrypt a plaintext string x to a ciphertext string F, comprising the steps of: using the string x and the first key a 0  to compute a message authentication code t;   using the string x, the second key a 1 , and the message authentication code t to produce an enciphered string y' that depends substantively on the message authentication code; and   taking the ciphertext y to comprise the message authentication code t together with a predetermined piece of the enciphered string y'.   
     
     
       2. The computer-implemented method as described in claim 1 wherein said predetermined piece is shorter than y' yet the plaintext string is still uniquely recoverable given the ciphertext. 
     
     
       3. The computer-implemented method as described in claim 1 wherein the message authentication code is computed by cipher block chaining a block cipher. 
     
     
       4. The computer-implemented method as described in claim 2 wherein the block cipher is DES. 
     
     
       5. The computer-implemented method as described in claim 2 wherein the predetermined piece of the enciphered string includes all but a last block of the enciphered string. 
     
     
       6. The computer-implemented method as described in claim 2 wherein the message authentication code has a length equal to a block length. 
     
     
       7. A method, using first and second keys, to encrypt a plaintext string to a ciphertext string, comprising the steps of: (a) cipher block chaining (CBC) the plaintext string using the first key and a first initialization vector (IV) to generate a CBC message authentication code whose length is equal to a block length;   (b) cipher block chaining the plaintext string using the second key and the CBC message authentication code as a second initialization vector to generate an enciphered string; and   (c) combining the CBC message authentication code and a predetermined portion of the enciphered string to form the ciphertext string.   
     
     
       8. The method as described in claim 7 wherein the predetermined portion of the enciphered string includes all but a last block of the enciphered string. 
     
     
       9. The method as described in claim 7 wherein the first initialization vector is the null vector. 
     
     
       10. The method as described in claim 7 wherein the plaintext string has a length that is a multiple of a length of a block. 
     
     
       11. The method as described in claim 7 wherein the plaintext string has a length that is not equal to a multiple of a length of a block. 
     
     
       12. The method as described in claim 7 wherein step (c) concatenates the CBC message authentication code and the predetermined portion of the enciphered string to form the ciphertext string. 
     
     
       13. The method as described in claim 7 wherein the ciphertext string has a length equal to the plaintext string. 
     
     
       14. The method as described in claim 7 wherein the first and second keys are derived from an underlying secret key. 
     
     
       15. A method, using first and second keys and a block cipher, to decrypt a ciphertext string into a plaintext string, the ciphertext string comprising a CBC message authentication code and an enciphered string, comprising the steps of: (a) decrypting by cipher block chaining the enciphered string using the second key and the CBC message authentication code as an initialization vector to generate a deciphered string;   (b) cipher block chaining the deciphered string using the first key and a null initialization vector to generate a string having a last block;   (c) calculating a predetermined function of the last block and an inverse of the block cipher under the first key at the CBC message authentication code; and   (d) combining the deciphered string and a result of the predetermined function to generate the plaintext string.   
     
     
       16. The method as described in claim 15 wherein the block cipher is DES. 
     
     
       17. The method as described in claim 15 wherein the predetermined function in step (c) is an exclusive OR. 
     
     
       18. A computer apparatus, comprising: a storage device;   program means supported in the storage device for encrypting a plaintext string x to a ciphertext string y, the program means comprising: means for using the string x and a first key a 0  to compute a message authentication code t;   means for using the string x, a second key a l , and the message authentication code t to produce an enciphered string y'; and   means for taking the ciphertext y to comprise the message authentication code t together with a predetermined piece of the enciphered string y', where said predetermined piece is shorter than y'.     
     
     
       19. A computer, comprising: a storage device;   program means supported in the storage device for decrypting a ciphertext string into a plaintext string, the ciphertext string comprising a CBC message authentication code and an enciphered string, the program means comprising: means for decrypting the enciphered string by cipher block chaining the enciphered string using a secret key and the CBC message authentication code as an initialization vector to generate a deciphered string;   means for cipher block chaining the deciphered string using a second secret key and a null initialization vector to generate a string having a last block;   means for calculating a predetermined function of the last block and an inverse of a block cipher evaluated using the second secret key; and   means for combining the deciphered string and the predetermined function to generate the plaintext string.     
     
     
       20. A program storage device readable by a processor and tangibly embodying a program of instructions executable by the processor to perform encryption and decryption methods, using first and second keys and a block cipher, wherein the encryption method comprises the steps of: (a) cipher block chaining (CBC) a plaintext string using the first key and an initialization vector (IV) to generate a CBC message authentication code;   (b) cipher block chaining the plaintext string using the second key and the CBC message authentication code as the initialization vector to generate an enciphered string; and   (c) combining the CBC message authentication code and a portion of the enciphered string to form a ciphertext string;   and wherein the decryption method comprises the steps of:   (a) cipher block chaining the enciphered string using the second key and the CBC message authentication code as the initialization vector to generate a deciphered string;   (b) cipher block chaining the deciphered string using the first key and a null initialization vector to generate a string having a last block;   (c) calculating a predetermined function of the last block and an inverse of the block cipher under the first key at the CBC message authentication code; and   (d) combining the deciphered string and the predetermined function to generate the plaintext string.