Template:No footnotes In cryptography, ciphertext stealing (CTS) is a general method of using a block cipher mode of operation that allows for processing of messages that are not evenly divisible into blocks without resulting in any expansion of the ciphertext, at the cost of slightly increased complexity.
General characteristicsEdit
Ciphertext stealing is the technique of altering processing of the last two blocks of plaintext, resulting in a reordered transmission of the last two blocks of ciphertext and no ciphertext expansion. This is accomplished by padding the last plaintext block (which is possibly incomplete) with the high order bits from the second to last ciphertext block (stealing the ciphertext from the second to last block). The (now full) last block is encrypted, and then exchanged with the second to last ciphertext block, which is then truncated to the length of the final plaintext block, removing the bits that were stolen, resulting in ciphertext of the same length as the original message size. In all cases, the processing of all but the last two blocks is unchanged. The scheme described is consistent with Daemen and Schneier; Meyer describes a related, but incompatible scheme (with respect to bit ordering and key use).
In principle any blockoriented block cipher mode of operation can be used, but streamcipherlike modes can already be applied to messages of arbitrary length without padding, so they do not benefit from this technique. The common modes of operation that are coupled with ciphertext stealing are ECB and CBC.
Ciphertext stealing for ECB mode requires the plaintext to be longer than one block. A possible workaround is to use a stream cipherlike block cipher mode of operation when the plaintext length is one block or less, such as the CTR, CFB or OFB modes.
Ciphertext stealing for CBC mode doesn't necessarily require the plaintext to be longer than one block. In the case where the plaintext is one block long or less the IV can act as the prior block of ciphertext. In this case a modified IV must be sent to the receiver. This may not be possible in situations where the IV can not be set by the sender when the ciphertext is sent (e.g., when the IV is a derived or preestablished value), and in this case ciphertext stealing for CBC mode can only occur in plaintexts longer than one block.
To implement CTS encryption or decryption for data of unknown length, the implementation must delay processing (and buffer) the two most recent blocks of data, so that they can be properly processed at the end of the data stream.
Ciphertext stealing mode descriptionEdit
In order to encrypt or decrypt data, use the standard block cipher mode of operation on all but the last two blocks of data.
The following steps describe how to handle the last two blocks of the plaintext, called P_{n−1} and P_{n}, where the length of P_{n−1} equals the block size of the cipher in bits, B, the length of the last block, P_{n}, is M bits, and K is the key that is in use. M can range from 1 to B, inclusive, so P_{n} could possibly be a complete block. The CBC mode description also makes use of the ciphertext block just previous to the blocks concerned, C_{n−2}, which may in fact be the IV if the plaintext fits within two blocks.
For this description, the following functions and operators are used:
 Head (data, a): returns the first a bits of the 'data' string.
 Tail (data, a): returns the last a bits of the 'data' string.
 Encrypt (K, data): use the underlying block cipher in encrypt mode on the 'data' string using the key K.
 Decrypt (K, data): use the underlying block cipher in decrypt mode on the 'data' string using the key K.
 XOR: Bitwise ExclusiveOR. Equivalent to bitwise addition without use of a carry bit.
 : Concatenation operator. Combine the strings on either side of the operator.
 0^{a}: a string of a 0 bits.
ECB ciphertext stealingEdit
Ciphertext stealing in ECB mode introduces an interblock dependency within the last two blocks, resulting in altered error propagation behavior for the last two blocks.
ECB encryption steps (see figure) Edit
 E_{n−1} = Encrypt (K, P_{n−1}). Encrypt P_{n−1} to create E_{n−1}. This is equivalent to the behavior of standard ECB mode.
 C_{n} = Head (E_{n−1}, M). Select the first M bits of E_{n−1} to create C_{n}. The final ciphertext block, C_{n}, is composed of the leading M bits of the secondtolast ciphertext block. In all cases, the last two blocks are sent in a different order than the corresponding plaintext blocks.
 D_{n} = P_{n}  Tail (E_{n−1}, B−M). Pad P_{n} with the low order bits from E_{n−1}.
 C_{n−1} = Encrypt (K, D_{n}). Encrypt D_{n} to create C_{n−1}. For the first M bits, this is equivalent to what would happen in ECB mode (other than the ciphertext ordering). For the last B−M bits, this is the second time that these data have been encrypted under this key (It was already encrypted in the production of E_{n−1} in step 2).
ECB decryption stepsEdit
 D_{n} = Decrypt (K, C_{n−1}). Decrypt C_{n−1} to create D_{n}. This undoes step 4 of the encryption process.
 E_{n−1} = C_{n}  Tail (D_{n}, B−M). Pad C_{n} with the extracted ciphertext in the tail end of D_{n} (placed there in step 3 of the ECB encryption process).
 P_{n} = Head (D_{n}, M). Select the first M bits of D_{n} to create P_{n}. As described in step 3 of the ECB encryption process, the first M bits of D_{n} contain P_{n}. We queue this last (possibly partial) block for eventual output.
 P_{n−1} = Decrypt (K, E_{n−1}). Decrypt E_{n−1} to create P_{n−1}. This reverses encryption step 1.
ECB ciphertext stealing error propagationEdit
A bit error in the transmission of C_{n−1} would result in the blockwide corruption of both P_{n−1} and P_{n}. A bit error in the transmission of C_{n} would result in the blockwide corruption of P_{n−1}. This is a significant change from ECB's error propagation behavior.
CBC ciphertext stealingEdit
In CBC, there is already interaction between processing of different adjacent blocks, so CTS has less conceptual impact in this mode. Error propagation is affected.
CBC encryption stepsEdit
 X_{n−1} = P_{n−1} XOR C_{n−2}. ExclusiveOR P_{n−1} with the previous ciphertext block, C_{n−2}, to create X_{n−1}. This is equivalent to the behavior of standard CBC mode.
 E_{n−1} = Encrypt (K, X_{n−1}). Encrypt X_{n−1} to create E_{n−1}. This is equivalent to the behavior of standard CBC mode.
 C_{n} = Head (E_{n−1}, M). Select the first M bits of E_{n−1} to create C_{n}. The final ciphertext block, C_{n}, is composed of the leading M bits of the secondtolast ciphertext block. In all cases, the last two blocks are sent in a different order than the corresponding plaintext blocks.
 P = P_{n}  0^{B−M}. Pad P_{n} with zeros at the end to create P of length B. The zero padding in this step is important for step 5.
 D_{n} = E_{n−1} XOR P. ExclusiveOR E_{n−1} with P to create D_{n}. For the first M bits of the block, this is equivalent to CBC mode; the first M bits of the previous block's ciphertext, E_{n−1},are XORed with the M bits of plaintext of the last plaintext block. The zero padding of P in step 4 was important, because it makes the XOR operation's effect on the last B−M bits equivalent to copying the last B−M bits of E_{n−1} to the end of D_{n}. These are the same bits that were stripped off of E_{n−1} in step 3 when C_{n} was created.
 C_{n−1} = Encrypt (K, D_{n}). Encrypt D_{n} to create C_{n−1}. For the first M bits, this is equivalent to what would happen in CBC mode (other than the ciphertext ordering). For the last B−M bits, this is the second time that these data have been encrypted under this key (It was already encrypted in the production of E_{n−1} in step 2).
CBC decryption stepsEdit
 D_{n} = Decrypt (K, C_{n−1}). Decrypt C_{n−1} to create D_{n}. This undoes step 6 of the encryption process.
 C = C_{n}  0^{B−M}. Pad C_{n} with zeros at the end to create a block C of length B. We are padding C_{n} with zeros to help in step 3.
 X_{n} = D_{n} XOR C. ExclusiveOR D_{n} with C to create X_{n}. Looking at the first M bits, this step has the result of XORing C_{n} (the first M bits of the encryption process' E_{n−1}) with the (now decrypted) P_{n} XOR Head (E_{n−1}, M) (see steps 45 of the encryption process). In other words, we have CBC decrypted the first M bits of P_{n}. Looking at the last B−M bits, this recovers the last B−M bits of E_{n−1}.
 P_{n} = Head (X_{n}, M). Select the first M bits of X_{n} to create P_{n}. As described in step 3, the first M bits of X_{n} contain P_{n}. We queue this last (possibly partial) block for eventual output.
 E_{n−1} = C_{n}  Tail (X_{n}, B−M). Append the tail (B−M) bits of X_{n} to C_{n} to create E_{n−1}. As described in step 3, E_{n−1} is composed of all of C_{n} (which is M bits long) appended with the last B−M bits of X_{n}. We reassemble E_{n−1} (which is the same E_{n−1} seen in the encryption process) for processing in step 6.
 X_{n−1} = Decrypt (K, E_{n−1}). Decrypt E_{n−1} to create X_{n−1}. This reverses encryption step 2. X_{n−1} is the same as in the encryption process.
 P_{n−1} = X_{n−1} XOR C_{n−2}. ExclusiveOR X_{n−1} with the previous ciphertext block, C_{n−2}, to create P_{n−1}. Finally, we reverse the XOR step from step 1 of the encryption process.
CBC Implementation NotesEdit
For CBC ciphertext stealing, there is a clever (but opaque) method of implementing the described ciphertext stealing process using a standard CBC interface. Using this method imposes a performance penalty in the decryption stage of one extra block decryption operation over what would be necessary using a dedicated implementation.
CBC ciphertext stealing encryption using a standard CBC interfaceEdit
 Pad the last partial plaintext block with 0.
 Encrypt the whole padded plaintext using the standard CBC mode.
 Swap the last two ciphertext blocks.
 Truncate the ciphertext to the length of the original plaintext.
CBC ciphertext stealing decryption using a standard CBC interfaceEdit
 D_{n} = Decrypt (K, C_{n−1}). Decrypt the second to the last ciphertext block, using zeros as IV.
 C_{n} = C_{n}  Tail (D_{n}, B−M). Pad the ciphertext to the nearest multiple of the block size using the last B−M bits of block cipher decryption of the secondtolast ciphertext block.
 Swap the last two ciphertext blocks.
 Decrypt the ciphertext using the standard CBC mode up to the last block.
 ExclusiveOR the last ciphertext (was already decrypted in step 1) with the second last plaintext.
 Truncate the plaintext to the length of the original ciphertext.
CBC ciphertext stealing error propagationEdit
A bit error in the transmission of C_{n−1} would result in the blockwide corruption of both P_{n−1} and P_{n}. A bit error in the transmission of C_{n} would result in a corresponding bit error in P_{n}, and in the blockwide corruption of P_{n−1}.
ReferencesEdit
 Daemen, Joan, Cipher and Hash Function Design, Strategies Based on Linear and Differential Cryptanalysis (1995), Ph. D. Thesis, Katholieke Universiteit Leuven. Sections 2.5.1 and 2.5.2
 Schneier, Bruce, Applied Cryptography (2nd, Ed.), John Wiley & Sons, Inc. ISBN 0471128457. pp 191, 195
 Meyer, Carl H.; Matyas, Stephen M.,(1982). Cryptography: A New Dimension in Computer Data Security, John Wiley & Sons, Inc. ISBN 0471048925, pp 77–85
 R. Baldwin, R. Rivest, RFC 2040: "The RC5, RC5CBC, RC5CBCPad, and RC5CTS Algorithms"
