From Wikipedia, the free encyclopedia

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 significantly increased complexity.

Contents 1 General characteristics 2 Ciphertext stealing mode description 2.1 ECB ciphertext stealing 2.1.1 ECB encryption steps 2.1.2 ECB decryption steps 2.1.3 ECB ciphertext stealing error propagation 2.2 CBC ciphertext stealing 2.2.1 CBC encryption steps 2.2.2 CBC decryption steps 2.2.3 CBC Implementation Notes 2.2.3.1 CBC ciphertext stealing encryption using a standard CBC interface 2.2.3.2 CBC ciphertext stealing decryption using a standard CBC interface 2.2.4 CBC ciphertext stealing error propagation 3 References

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 (i.e., the resulting ciphertext is the same length as the plaintext, as compared to the longer ciphertext that would result from most padding schemes used with ECB and CBC modes). This is accomplished by padding the last block (which is possibly incomplete) with the low 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 (thus 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 block-oriented block cipher mode of operation can be used (stream-cipher-like modes can already be applied to messages of arbitrary length without padding, so they do not benefit from this technique). The common block cipher mode of operation that are coupled with ciphertext stealing are the ECB and CBC modes.

Ciphertext stealing requires the plaintext to be longer than one block. A possible workaround is to use a stream cipher like block cipher mode of operation when the plaintext length is one block or less, such as the CTR, CFB or OFB modes.

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.

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 Exclusive-OR. 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.

Ciphertext stealing in ECB mode introduces an intra-block dependency within the last two blocks, resulting in altered error propagation behavior for the last two blocks.

1. 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.
2. 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 second-to-last ciphertext block. In all cases, the last two blocks are sent in a different order than the corresponding plaintext blocks.
3. D_n = P_n || Tail (E_n−1, B−M). Pad P_n with the low order bits from E_n−1.
4. 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 this data has been encrypted under this key (It was already encrypted in the production of E_n−1 in step 2).

1. D_n = Decrypt (K, C_n−1). Decrypt C_n−1 to create D_n. This undoes step 4 of the encryption process.
2. 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).
3. 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.
4. P_n−1 = Decrypt (K, E_n−1). Decrypt E_n−1 to create P_n−1. This reverses encryption step 1.

A bit error in the transmission of C_n−1 would result in the block-wide corruption of both P_n−1 and P_n. A bit error in the transmission of C_n would result in the block-wide corruption of P_n−1. This is a significant change from ECB's error propagation behavior.

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.

1. X_n−1 = P_n−1 XOR C_n−2. Exclusive-OR 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.
2. 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.
3. 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 second-to-last ciphertext block. In all cases, the last two blocks are sent in a different order than the corresponding plaintext blocks.
4. 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.
5. D_n = E_n−1 XOR P. Exclusive-OR 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.
6. 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 this data has been encrypted under this key (It was already encrypted in the production of E_n−1 in step 2).

1. D_n = Decrypt (K, C_n−1). Decrypt C_n−1 to create D_n. This undoes step 6 of the encryption process.
2. 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.
3. X_n = D_n XOR C. Exclusive-OR 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 4-5 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.
4. 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.
5. 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.
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.
7. P_n−1 = X_n−1 XOR C_n−2. Exclusive-OR 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.

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.

1. Encrypt the plaintext through the last full block using the standard CBC mode.
2. Pad the last partial block with the trailing ciphertext of the last full block
3. Encrypt the last block (plaintext plus ciphertext)
4. Swap the last two ciphertext blocks.
5. Truncate the ciphertext to the length of the original plaintext.

1. D_n = Decrypt (K, C_n−1). Decrypt the second to the last ciphertext block.
2. 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 second-to-last ciphertext block.
3. Swap the last two ciphertext blocks.
4. Decrypt the ciphertext (except the now last block) using the standard CBC mode.
5. Truncate the plaintext to the length of the original ciphertext.

A bit error in the transmission of C_n−1 would result in the block-wide 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 block-wide corruption of P_n−1.

• 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 0-471-12845-7. pp 191, 195
• Meyer, Carl H.; Matyas, Stephen M.,(1982). Cryptography: A New Dimension in Computer Data Security, John Wiley & Sons, Inc. ISBN 0-471-04892-5, pp 77–85
• R. Baldwin, R. Rivest, RFC 2040: "The RC5, RC5-CBC, RC5-CBC-Pad, and RC5-CTS Algorithms"

Block ciphers v • d • e
Algorithms: 3-Way | AES | Akelarre | Anubis | ARIA | BaseKing | Blowfish | C2 | Camellia | CAST-128 | CAST-256 | CIKS-1 | CIPHERUNICORN-A | CIPHERUNICORN-E | CMEA | Cobra | COCONUT98 | Crab | CRYPTON | CS-Cipher | DEAL | DES | DES-X | DFC | E2 | FEAL | FROG | G-DES | GOST | Grand Cru | Hasty Pudding Cipher | Hierocrypt | ICE | IDEA | IDEA NXT | Iraqi | Intel Cascade Cipher | KASUMI | KHAZAD | Khufu and Khafre | KN-Cipher | Libelle | LOKI89/91 | LOKI97 | Lucifer | M6 | MacGuffin | Madryga | MAGENTA | MARS | Mercy | MESH | MISTY1 | MMB | MULTI2 | NewDES | NOEKEON | NUSH | Q | RC2 | RC5 | RC6 | REDOC | Red Pike | S-1 | SAFER | SC2000 | SEED | Serpent | SHACAL | SHARK | Skipjack | SMS4 | Square | TEA | Triple DES | Twofish | UES | Xenon | xmx | XTEA | Zodiac
Design: Feistel network | Key schedule | Product cipher | S-box | SPN Attacks: Brute force | Linear / Differential / Integral cryptanalysis | Mod n | Related-key | Slide | XSL
Standardization: AES process | CRYPTREC | NESSIE Misc: Avalanche effect | Block size | IV | Key size | Modes of operation | Piling-up lemma | Weak key
Cryptography v • d • e
History of cryptography | Cryptanalysis | Cryptography portal | Topics in cryptography
Symmetric-key algorithm | Block cipher | Stream cipher | Public-key cryptography | Cryptographic hash function | Message authentication code | Random numbers