Ciphertext stealing
Ciphertext stealing (CTS) is a cryptographic technique used in block cipher modes of operation to encrypt plaintext messages of arbitrary length without padding, ensuring the resulting ciphertext has exactly the same length as the plaintext.[1] It achieves this by modifying the encryption process for the final blocks, effectively "stealing" bits from the penultimate ciphertext block to complete the last partial block, thereby avoiding the need for additional padding bytes that would expand the ciphertext.[2] This method is particularly associated with the Cipher Block Chaining (CBC) mode and addresses a limitation of standard CBC, which requires input lengths to be multiples of the block size.[1]
The concept of ciphertext stealing originated in the early 1980s as a practical solution for handling non-block-aligned data in block ciphers.[2] It was first described in detail by Stephen M. Matyas and Carl H. Meyer in their 1982 book Cryptography: A New Dimension, where they proposed a variant for CBC mode, though later analysis revealed security flaws in their specific construction.[2] By 2010, the National Institute of Standards and Technology (NIST) formalized and recommended three secure variants—CBC-CS1, CBC-CS2, and CBC-CS3—in an addendum to Special Publication 800-38A, standardizing their use for CBC encryption.[1] These variants differ primarily in the ordering of bits within the final two ciphertext blocks: CBC-CS1 maintains the standard order with partial block adjustment, CBC-CS2 swaps the final blocks for partial inputs, and CBC-CS3 always performs the swap, as implemented in protocols like Kerberos 5.[1]
In terms of operation, CTS processes the plaintext in CBC mode up to the last two blocks. For a message shorter than two full blocks, special handling applies, but generally, the encryption computes the penultimate block normally and then derives the final block by XORing the partial plaintext with the encryption of a modified penultimate block, effectively borrowing bits to fill the output.[1] Decryption reverses this process symmetrically. Security analyses, including a 2011 proof by Phillip Rogaway and colleagues, demonstrate that the NIST variants provide indistinguishability under chosen-plaintext attacks (IND-CPA) equivalent to standard CBC mode, assuming a pseudorandom permutation block cipher and random initialization vector, with security degradation bounded by the number of blocks processed.[2] This makes CTS suitable for applications requiring exact-length preservation, such as disk encryption in modes like XTS, though it is not recommended for all scenarios due to potential malleability in CBC.[2]
Background
Block Cipher Modes and Padding Needs
Block ciphers are symmetric-key cryptographic algorithms that operate on fixed-size blocks of plaintext to produce ciphertext blocks of the same size. For instance, the Data Encryption Standard (DES), standardized in 1977 through FIPS PUB 46, processes 64-bit blocks, while the Advanced Encryption Standard (AES), specified in FIPS PUB 197 in 2001, uses 128-bit blocks with key lengths of 128, 192, or 256 bits.[3][4] These fixed block sizes ensure efficient, parallelizable encryption but require the input data to align with the block length for proper processing.
To extend block ciphers beyond single-block messages, modes of operation were developed to handle arbitrary-length data securely. FIPS PUB 81, published in 1980, defined four primary modes for DES: Electronic Codebook (ECB), Cipher Block Chaining (CBC), Cipher Feedback (CFB), and Output Feedback (OFB). ECB encrypts each block independently, treating the plaintext as a sequence of non-overlapping blocks, while CBC chains blocks by XORing each plaintext block with the previous ciphertext block before encryption, using an initialization vector (IV) for the first block. CFB and OFB, in contrast, generate a keystream from the cipher output fed back into the encryption process, allowing operation on segments smaller than the full block size (1 to 64 bits for DES). ECB and CBC modes, however, mandate that the plaintext length be an exact multiple of the block size to avoid incomplete blocks.[5]
This block alignment requirement introduces the padding problem, where additional bytes must be appended to the plaintext if its length is not a multiple of the block size. Common padding schemes, such as PKCS#7, add bytes to reach the next block boundary, with the padding length encoded in the final byte (e.g., five 0x05 bytes for five padding bytes). This process increases the ciphertext length by up to one full block minus one byte, potentially exposing metadata about the original message size. Moreover, padding introduces side-channel vulnerabilities, notably padding oracle attacks, where an attacker exploits error messages or timing differences during decryption to infer plaintext information block by block. Such attacks were first formalized against CBC mode with padding in 2002, demonstrating how even subtle implementation leaks can compromise confidentiality.[6] Ciphertext stealing offers an alternative by rearranging the final blocks to eliminate padding altogether.[5]
Limitations of Traditional Padding
Traditional padding schemes for block ciphers, such as PKCS#7, ANSI X.9.23, and ISO 10126, are designed to extend plaintext messages to a multiple of the block size, typically 64 or 128 bits depending on the cipher. PKCS#7 padding, standardized in RFC 5652, appends a sequence of bytes where each byte's value equals the total number of padding bytes added (ranging from 1 to the block size), ensuring unambiguous removal during decryption.[7] ANSI X.9.23 padding, defined in the withdrawn ANSI standard but still used in some implementations, fills the padding area with zero bytes except for the final byte, which indicates the padding length.[8] ISO 10126 padding, also withdrawn in 2007 due to its association with insecure single-DES operations, uses random bytes for the padding followed by a byte specifying the padding length, aiming to add some variability but introducing implementation complexities.[8][9]
A primary limitation of these schemes is the expansion of the ciphertext length, which can increase by up to one full block (e.g., 16 bytes for AES) even for messages just one byte short of a multiple of the block size, leading to unnecessary bandwidth and storage overhead. This overhead is particularly inefficient for short messages, where the padding dominates the final block, potentially amplifying transmission costs in constrained environments. Additionally, deterministic padding like PKCS#7 and ANSI X.9.23 produces predictable patterns in the padded portions of short messages, which can leak information about message length or facilitate statistical analysis if combined with other side-channel leaks, as the padding values are fixed and non-random.[10]
Security vulnerabilities represent a critical drawback, most notably susceptibility to padding oracle attacks, where an attacker exploits error messages or timing differences during decryption to iteratively reveal plaintext bytes. Serge Vaudenay's seminal 2002 analysis demonstrated how CBC mode with PKCS#5/PKCS#7 padding enables such attacks, allowing full plaintext recovery with adaptive chosen-ciphertext queries by manipulating padding validity feedback. These attacks, requiring only an "oracle" that distinguishes valid from invalid padding (e.g., via server responses), have impacted protocols like SSL/TLS and IPsec, underscoring the malleability introduced by padding validation.[6] ISO 10126 mitigates some predictability but remains vulnerable if random number generation is weak, further complicating secure implementations.[9]
From a performance perspective, traditional padding incurs computational overhead by necessitating the encryption (and decryption) of at least one additional full block, even for messages nearly aligned to the block size, which can increase processing time by up to 100% for very short inputs in modes like CBC.[11] This extra block operation involves full cipher invocations, contributing to latency in high-throughput scenarios and exacerbating resource demands on embedded or resource-limited devices.[12]
Core Concepts
Definition and Purpose
Ciphertext stealing (CTS) is a technique employed in block cipher modes of operation, such as cipher block chaining (CBC), to encrypt plaintext messages of arbitrary length—specifically, lengths at least equal to the block size—without requiring traditional padding, thereby producing ciphertext of exactly the same length as the plaintext.[1] This method achieves its goal by "stealing" the necessary bits from the penultimate (next-to-last) ciphertext block to form and encrypt the final partial block, effectively modifying the last two ciphertext blocks during the encryption process to handle any remainder that is not a full block.[1] The key principle underlying CTS is this targeted modification of the final two blocks, which integrates seamlessly with existing modes while eliminating the need for appended padding data.[1]
The primary purpose of CTS is to avoid the ciphertext expansion inherent in conventional padding schemes, which add extra bytes to reach a multiple of the block size and can introduce overhead, particularly for short or variably sized messages.[1] By producing no-padding ciphertext, CTS maintains data confidentiality for arbitrary-length inputs and ensures compatibility with standard block cipher modes, making it suitable for applications like disk encryption where exact length preservation is beneficial.[1]
The basic idea of ciphertext stealing was first proposed by Carl H. Meyer and Stephen M. Matyas in their seminal 1982 book Cryptography: A New Dimension, where they described an early version for handling partial blocks in block cipher encryption. This concept was later formalized and standardized by the National Institute of Standards and Technology (NIST) in the 2010 addendum to Special Publication 800-38A, which specifies three secure variants of CTS for CBC mode to address limitations in traditional padding approaches.[1]
General Characteristics
Ciphertext stealing (CTS) is a method applied to block cipher modes of operation that enables the encryption of plaintext messages of arbitrary length without the need for padding, producing ciphertext that matches the exact length of the input plaintext. This property eliminates the overhead associated with traditional padding schemes, ensuring no expansion in data size during encryption. CTS is compatible with any underlying block cipher, as it relies on the cipher's standard block processing capabilities rather than specific algorithmic features.[1][13]
The technique supports three primary formats—CS1, CS2, and CS3—which primarily differ in their approach to handling the penultimate ciphertext block during the final encryption steps. These variants maintain the core goal of length-preserving encryption but vary in the ordering and partial block manipulations to ensure correct decryption. CTS integrates seamlessly with modes such as ECB and CBC, inheriting their operational requirements; notably, it imposes no additional initialization vector (IV) beyond what the base mode demands, such as none for ECB or a single IV for CBC.[2][1]
In terms of security properties, CTS exhibits malleability characteristics akin to the underlying mode—for instance, it remains malleable in the same manner as CBC, where modifications to ciphertext blocks can predictably alter corresponding plaintext blocks without detection. Efficiency-wise, CTS introduces minimal computational overhead, typically requiring just one extra block cipher operation for messages shorter than two full blocks, making it suitable for scenarios where padding avoidance is prioritized over complex processing.[2][13]
Ciphertext Formats
The CS1 format, denoted as CBC-CS1 in the NIST Special Publication 800-38A Addendum, is a variant of ciphertext stealing for the CBC mode of block ciphers that produces ciphertext of the same length as the plaintext without padding expansion. It handles the final partial plaintext block by padding it internally with zeros during encryption but adjusting the output to include a partial block.[1]
For a plaintext P of length not a multiple of the block size b, let n = \lceil |P| / b \rceil, r = |P| \mod b (0 \leq r < b). The plaintext is divided into n-1 full blocks P_1, \dots, P_{n-1} and a partial block P_n^* of length r (if r=0, P_n^* is full and r=b). Pad the partial as \tilde{P}n = P_n^* || 0^{b-r}. Apply standard CBC encryption to produce full ciphertext blocks C_i = E_K(P_i \oplus C{i-1}) for i=1 to n, with C_0 = IV. The output ciphertext is then C_1 || \dots || C_{n-2} || \text{MSB}r(C{n-1}) || C_n if r > 0 (or the full blocks if r=0). This places the partial block (stolen as the most significant r bits of C_{n-1}) as the penultimate block, followed by the full C_n.[1][2]
The structure ensures the ciphertext stream has full blocks up to n-2, a partial penultimate block of r bits, and a full final block of b bits, preserving the total length equal to the plaintext. The "stealing" refers to using only the first r bits of the intermediate C_{n-1} for output, effectively borrowing from this ciphertext block to accommodate the partial plaintext without expansion. For r = b, it reduces to standard CBC output. Decryption reverses this by reconstructing the full C_{n-1} from the partial output and the decrypted C_n (using the known padding zeros).[1][2]
This format is defined specifically for CBC mode; adaptations for ECB would differ, as covered in other sections. It prioritizes compatibility with standard CBC for full-block inputs while managing partial blocks through bit truncation in output.[2]
The CS2 format, formally defined as CBC-CS2 in the NIST Special Publication 800-38A Addendum, is a variant of ciphertext stealing designed for the CBC mode of block ciphers to handle plaintexts whose length is not a multiple of the block size without requiring explicit padding.[1] This format ensures the ciphertext has exactly the same length as the plaintext, avoiding expansion while maintaining compatibility with standard CBC processing for full-block messages.[1]
In CS2, the encryption process begins by treating the plaintext as if it were padded to a full number of blocks, but the output rearranges the final blocks to position any partial block at the end. Let b denote the block size, n = \lceil |\text{P}| / b \rceil, and r = |\text{P}| \mod b (with $0 \leq r < b), where the plaintext is split into full blocks P_1, \dots, P_{n-1} and a partial final block P_n^* of length r (if r = 0, then P_n^* = P_n is full). The padded final input block is formed as \tilde{P}_n = P_n^* || 0^{b-r}. Standard CBC encryption is then applied to produce intermediate blocks C_i = E_K(P_i \oplus C_{i-1}) for i = 1 to n, with C_0 = \text{IV}, yielding full blocks C_1, \dots, C_n. The partial block is derived as C_{n-1}' = \text{MSB}_r(C_{n-1}), the first r bits of C_{n-1}. If r = b, the output is simply C_1 || \dots || C_{n-1} || C_n; otherwise, it is C_1 || \dots || C_{n-2} || C_n || C_{n-1}'.[1]
This structure positions the full block C_n (derived from the encryption involving the padded final plaintext) as the penultimate output block and the partial C_{n-1}' (stolen from the first r bits of the penultimate intermediate ciphertext) as the final output block when r < b. Decryption reverses this by first checking the total length to determine r; if r < b, it swaps the last two input blocks before applying the inverse of the CS1 decryption process.[1]
Unlike the CS1 format, where the partial block C_{n-1}' precedes the full C_n in the output (resulting in a partial penultimate block), CS2 swaps their order only when necessary (r < b) to ensure the partial block is always last in the ciphertext stream, which can simplify streaming or concatenation in some protocols.[1] This conditional swapping preserves exact compatibility with unpadded CBC when the plaintext length is a multiple of b, distinguishing CS2 from the always-swapping CS3 variant.[1] The format processes the final plaintext block as partial internally via zero-padding but produces no padding in the output, relying on the stolen bits from the intermediate C_{n-1} to fill the effective length.[1]
The CS3 format, denoted as CBC-CS3 in standards documentation, is a variant of ciphertext stealing specifically tailored for the Cipher Block Chaining (CBC) mode of operation, enabling encryption of plaintexts whose length is not a multiple of the block cipher's block size without adding padding bytes to the ciphertext. This format ensures the ciphertext length equals the plaintext length while maintaining compatibility with CBC's chaining dependencies, particularly in protocols like Kerberos 5 that require predictable block ordering.[1]
In the CS3 format, the encryption uses the same process as CBC-CS1: for a block size b, divide the plaintext into full blocks P_1, \dots, P_{n-1} and partial P_n^* of r bits (1 \leq r < b or r=b if full). Pad \tilde{P}_n = P_n^* || 0^{b-r}. Compute full CBC blocks C_i = E_K(P_i \oplus C_{i-1}) for i=1 to n, with C_0=IV. Derive the partial as C_{n-1}' = \text{MSB}_r(C_{n-1}). The output is always C_1 || \dots || C_{n-2} || C_n || C_{n-1}', unconditionally placing the full C_n before the partial block, even if r=b (in which case C_{n-1}' = C_{n-1}).[1][2]
This structure always positions the partial (or full if no remainder) block last, with the full block derived from the padded partial plaintext as penultimate. The stealing extracts the r most significant bits from the intermediate C_{n-1}. As specified in NIST Special Publication 800-38A Addendum, CBC-CS3 was introduced to address limitations in traditional CBC padding schemes, such as unnecessary expansion and potential interoperability issues in CBC-based systems, by enforcing an unconditional swap of the last two blocks relative to CS1.[1]
For clarity, the key relations are:
C_{n-1} = E_K(P_{n-1} \oplus C_{n-2}), \quad C_n = E_K( (P_n^* || 0^{b-r}) \oplus C_{n-1} ), \quad C_{n-1}' = \text{MSB}_r (C_{n-1})
with output order \dots || C_{n-2} || C_n || C_{n-1}'. This ensures proper chaining and security equivalent to standard CBC.[1][2]
Mode-Specific Implementations
ECB with Ciphertext Stealing
The Electronic Codebook (ECB) mode operates by encrypting each plaintext block independently with the block cipher and the same key, resulting in no inter-block dependencies or use of an initialization vector (IV). This independence allows for straightforward parallelization but exposes patterns in the plaintext, as identical blocks yield identical ciphertext blocks.
When integrating ciphertext stealing (CTS) with ECB, the technique is applied solely to the final two blocks to accommodate plaintext lengths not divisible by the block size, thereby avoiding traditional padding schemes and producing ciphertext of equal length to the plaintext. Unlike chained modes, ECB-CTS largely maintains block independence for all but the final two blocks, where the stealing process introduces a dependency between them, with no IV required. This variant, sometimes denoted as ECB-CS1, ensures no expansion in message size for inputs longer than one block. Unlike the CBC-CTS variants, ECB-CTS has not been formally standardized by NIST.[14][15]
ECB-CTS inherits the core advantages of ECB, such as implementation simplicity and support for random access decryption, but amplifies its security weaknesses by failing to provide diffusion across blocks, making it susceptible to statistical attacks that reveal plaintext structure through repeated patterns in ciphertext. Due to these vulnerabilities, ECB-CTS is infrequently adopted in secure systems and is generally limited to non-confidential applications, such as encrypting random or pre-randomized data, or when embedded within protocols offering additional protections like higher-layer mixing.
CBC with Ciphertext Stealing
Cipher Block Chaining (CBC) mode is a widely used block cipher mode of operation where the plaintext is divided into fixed-size blocks of length b bits, and each block is encrypted by first XORing it with the previous ciphertext block (or the initialization vector (IV) for the first block) before applying the underlying block cipher under a secret key.[1] This chaining mechanism provides diffusion across blocks, ensuring that changes in one plaintext block affect subsequent ciphertext blocks.[1]
Ciphertext stealing (CTS) integrates with CBC to handle plaintexts whose length is not a multiple of the block size b, specifically when the final partial block has length r where $0 < r < b. In CBC-CTS, the stealing process modifies the chaining dependencies for the last two ciphertext blocks, incorporating bits from the penultimate block to form the final partial ciphertext without adding a padding block.[1] Three variants—CBC-CS1, CBC-CS2, and CBC-CS3—are tailored for CBC, differing primarily in the ordering of the final two ciphertext blocks to accommodate the partial block while preserving the chaining integrity.[1] In contrast to standard ECB, which provides full block independence, CBC-CTS leverages the mode's diffusion but requires careful adjustment of the chaining for the affected blocks.[1]
The National Institute of Standards and Technology (NIST) formalized these variants in the addendum to Special Publication 800-38A, titled "Recommendation for Block Cipher Modes of Operation: Three Variants of Ciphertext Stealing for CBC Mode," published in October 2010.[1] This specification ensures that CBC-CTS produces ciphertext of exactly the same length as the plaintext, avoiding the expansion inherent in traditional padding schemes like PKCS#7 used in plain CBC.[1] Plain CBC, by contrast, mandates padding the plaintext to a full block multiple, resulting in a ciphertext at least as long as the next block boundary.[1]
Encryption and Decryption Processes
ECB CTS Encryption
ECB ciphertext stealing (ECB CTS) is a non-standard extension of ECB mode to handle partial blocks without padding, though it is rarely used due to ECB's insecurity for most applications. The process for a plaintext of length (q-1)b + r, with q ≥ 2 and 0 < r < b, divides the plaintext into q-1 full blocks P_1 to P_{q-1} and partial P_q of r bits. The first q-2 blocks are encrypted independently: C_i = E_K(P_i) for i = 1 to q-2. The penultimate block is encrypted as C_{q-1} = E_K(P_{q-1}). To handle the partial block, a reversible stealing construction analogous to CBC-CS1 is used: pad P_q with b-r zeros to form P_q' = P_q || 0^{b-r}, then C_q = E_K(P_q'). The output ciphertext is C_1 || ... || C_{q-2} || MSB_r(C_{q-1}) || C_q, ensuring length matches the plaintext. For messages with length < b, ECB CTS is not supported and requires padding; for b ≤ length < 2b, apply the stealing directly without the q-2 loop.[16]
Note that unlike CBC, ECB CTS lacks chaining, so security is no better than plain ECB, and implementations must ensure reversibility by reconstructing missing bits during decryption (see below). The following pseudocode outlines a basic ECB CTS encryption (CS1-like variant):
function ECB_CTS_Encrypt(K, P):
b = block_size
if length(P) < b:
// Special case: pad with zeros or error
P_padded = P || 0^{b - length(P)}
return E_K(P_padded)[1 : length(P)] // Truncate output, but note this is not true CTS
n = ceil(length(P) / b)
r = length(P) mod b
if r == 0:
r = b
C = empty
for i = 1 to n-2:
P_i = extract_block(P, i)
append E_K(P_i) to C
if n == 1:
// Single block case handled above
pass
else:
P_{n-1} = extract_block(P, n-1)
C_{n-1_full} = E_K(P_{n-1})
if r < b:
P_n = extract_partial(P, n, r)
P_n_padded = P_n || 0^{b-r}
C_n = E_K(P_n_padded)
C_{n-1_partial} = C_{n-1_full}[1 : r]
append C_{n-1_partial} to C
append C_n to C
else:
append C_{n-1_full} to C
return truncate(C, length(P)) // Ensure exact length
function ECB_CTS_Encrypt(K, P):
b = block_size
if length(P) < b:
// Special case: pad with zeros or error
P_padded = P || 0^{b - length(P)}
return E_K(P_padded)[1 : length(P)] // Truncate output, but note this is not true CTS
n = ceil(length(P) / b)
r = length(P) mod b
if r == 0:
r = b
C = empty
for i = 1 to n-2:
P_i = extract_block(P, i)
append E_K(P_i) to C
if n == 1:
// Single block case handled above
pass
else:
P_{n-1} = extract_block(P, n-1)
C_{n-1_full} = E_K(P_{n-1})
if r < b:
P_n = extract_partial(P, n, r)
P_n_padded = P_n || 0^{b-r}
C_n = E_K(P_n_padded)
C_{n-1_partial} = C_{n-1_full}[1 : r]
append C_{n-1_partial} to C
append C_n to C
else:
append C_{n-1_full} to C
return truncate(C, length(P)) // Ensure exact length
This approach borrows bits from the penultimate ciphertext block, but note that full reversibility in ECB requires careful bit recovery during decryption.[16]
ECB CTS Decryption
ECB CTS decryption recovers the plaintext by independent block decryption for initial blocks and special reconstruction for the final two when r > 0. For ciphertext of length (q-1)b + r, parse into q-2 full blocks C_1 to C_{q-2}, partial C_{q-1} of r bits, and full C_q of b bits. Decrypt the first q-2 blocks as P_i = D_K(C_i). For the final blocks, compute temp = D_K(C_q) = P_q || 0^{b-r}. The partial plaintext is P_q = MSB_r(temp). To recover P_{q-1}, reconstruct full C_{q-1} = C_{q-1 partial} || LSB_{b-r}(E_K(P_{q-1} wait, but since ECB, this circular; actually, for this analog, the missing bits are not recoverable without the full C_{q-1}, highlighting why ECB CTS is non-standard. In practice, implementations may pad the partial C_{q-1} with zeros for decryption, but this alters the result. A correct recovery requires the encryption to use zero padding for the last and truncate the penultimate ciphertext, but security is compromised. For exact reversibility, use CBC CTS instead. If r = 0, standard ECB decryption applies. Special case for length < b: pad the ciphertext with zeros to b bits, decrypt, and take first length bits.[16]
CBC CTS Encryption
CBC CTS encryption extends CBC mode to arbitrary-length plaintexts using ciphertext stealing for the final partial block, as standardized by NIST in three variants (CBC-CS1, CS2, CS3). The plaintext is divided into n-1 full b-bit blocks P_1 to P_{n-1} and partial P_n* of d bits (1 ≤ d < b). Pad P_n* with b-d zeros to form P_n = P_n* || 0^{b-d}. Apply standard CBC encryption with IV = C_0: C_i = E_K(P_i ⊕ C_{i-1}) for i = 1 to n, yielding full C_1 to C_n. The variants differ in output formatting for the last two blocks:[1]
- CBC-CS1: Output C_1 || ... || C_{n-2} || MSB_d(C_{n-1}) || C_n (partial penultimate, full last).
- CBC-CS2: If d = b, same as CS1; else C_1 || ... || C_{n-2} || C_n || MSB_d(C_{n-1}) (swap if partial).
- CBC-CS3: Always C_1 || ... || C_{n-2} || C_n || MSB_d(C_{n-1}) (always swap).
For plaintext length < b, pad with zeros and treat as single block (d = length(P)); for b ≤ length < 2b, n=2, apply directly. This ensures ciphertext length equals plaintext length without explicit padding overhead. CBC CTS requires sequential processing of the last two blocks due to chaining dependency.[1][2]
CBC CTS Decryption
CBC CTS decryption reverses the process using standard CBC for initial blocks and reconstructs the final blocks based on the variant. For ciphertext C of length m, let n = ceil(m / b), d = m mod b (if d=0, d=b). Parse according to the variant; for CS1, C_1 to C_{n-2} full, C_{n-1}^* = next d bits (partial), C_n = last b bits (full). Decrypt initial blocks: P_i = D_K(C_i) ⊕ C_{i-1} for i=1 to n-2, with C_0 = IV. For the final blocks in CS1: compute Z = D_K(C_n), Z* = MSB_d(Z), Z** = LSB_{b-d}(Z). Reconstruct full C_{n-1} = C_{n-1}^* || Z**. Then P_{n-1} = D_K(C_{n-1}) ⊕ C_{n-2}. The partial P_n* = Z* ⊕ MSB_d(C_{n-1}) (or equivalently Z* ⊕ C_{n-1}^* after reconstruction). Output P_1 || ... || P_{n-1} || P_n*. For CS2 and CS3, reorder the final two blocks to match CS1 format (swap if needed), then apply CS1 decryption. If d = b, reduces to standard CBC. For length < b, parse as partial C_1 of d bits, but modes typically require full IV and may pad implicitly. This self-recovers stolen bits via the block cipher inverse, requiring only the message length.[1][2]
Security Analysis
Ciphertext stealing (CTS) modes, when applied to block cipher modes like CBC, maintain the security properties of their underlying constructions provided the block cipher is a secure pseudorandom permutation (PRP). Specifically, CBC-CTS variants achieve indistinguishability under chosen-plaintext attack (IND-CPA) security, with the adversary's advantage bounded by σ²/2ᵇ, where σ is the total number of blocks queried and b is the block size. This ind$-security, a strong form of IND-CPA where ciphertexts are indistinguishable from random bits, holds for all NIST-recommended CBC-CTS1, CBC-CTS2, and CBC-CTS3 modes assuming the block cipher is secure.[2]
The security of CBC-CTS is equivalent to that of standard CBC mode with padding, as CTS operates by rearranging bits from the padded CBC output without introducing any quantitative degradation in security. This equivalence ensures that CTS does not weaken the confidentiality guarantees of CBC, preserving the same level of protection against chosen-plaintext attacks. Unlike padded CBC, however, CTS avoids the need for explicit padding, thereby eliminating vulnerabilities associated with padding schemes, such as padding oracle attacks, when implemented correctly. CBC-CTS inherits general weaknesses of CBC mode, including malleability that could enable attacks if authentication is not provided, but no unique vulnerabilities specific to the stealing mechanism have been identified in the approved variants.[2]
In the context of XTS mode, which incorporates a CTS mechanism for handling partial blocks in disk encryption, the construction provides confidentiality for storage devices without data expansion or authentication. NIST approves XTS-AES under SP 800-38E, confirming its security for sector-based encryption where data units are up to 2²⁰ blocks long, relying on the PRP security of AES and the tweakable design to prevent patterns across sectors. The CTS component in XTS ensures seamless handling of incomplete sectors while maintaining the overall mode's IND-CPA security.[17]
Error Propagation and Reliability
In Electronic Codebook (ECB) mode with ciphertext stealing (CTS), a bit error in a ciphertext block prior to the final two blocks affects only the decryption of that specific plaintext block, as each block is processed independently. For the final two blocks, where CTS modifies the penultimate ciphertext block by incorporating part of the last block's data before encryption, an error in the penultimate ciphertext block corrupts the corresponding penultimate plaintext block and may also garble the adjacent partial plaintext block due to the stolen ciphertext's role in recovery. Similarly, an error in the last ciphertext block impacts only the partial plaintext block, with no further propagation. This localized error effect mirrors standard ECB mode but introduces limited coupling between the final two blocks from the stealing process.[18]
In Cipher Block Chaining (CBC) mode with CTS, a bit error in a ciphertext block generally corrupts the entire corresponding plaintext block and propagates to the next plaintext block via the chaining XOR operation, garbling one bit in it, while subsequent blocks recover normally. For the last blocks under CTS, an error in the final ciphertext block affects only the partial plaintext block, as there is no subsequent block to propagate to. However, an error in the penultimate ciphertext block corrupts both the penultimate plaintext block and the final partial plaintext block, amplifying the damage due to the stealing mechanism's dependency on the penultimate block for recovering the stolen portion. This behavior aligns with standard CBC's self-synchronizing properties but heightens local impact on the message tail from the partial block handling.[19]
Compared to their base modes without CTS, ECB CTS and CBC CTS exhibit similar error propagation characteristics overall, with errors confined to one or two blocks, but the partial final block in CTS scenarios can increase localized corruption in the message end by coupling the last two blocks more tightly. These modes demonstrate limited error propagation, making them reliable for applications like disk storage where bit error rates are low (typically below 10^{-12} per bit), but less suitable for transmission over noisy channels, such as wireless media, where frequent errors could accumulate despite the self-recovery in CBC.[18][19]
Applications
Relation to XTS Mode
XTS mode, formally known as XEX-based tweaked-codebook mode with ciphertext stealing, is a block cipher mode of operation designed specifically for the protection of data on storage devices, as defined in the IEEE Std 1619-2007.[20] This standard integrates ciphertext stealing (CTS) as a core component to enable the encryption of data units that may not be exact multiples of the block size, such as disk sectors, without requiring additional padding. In XTS, the underlying structure employs a tweakable block cipher based on the XEX construction, where each block is encrypted in an ECB-like manner but with a position-dependent tweak derived from the sector address and block index, ensuring that the encryption is sensitive to the data's location within the storage medium.[17]
Ciphertext stealing fits into XTS by addressing the challenge of partial blocks at the end of a data unit, allowing the mode to "steal" bits from the preceding full block to complete the final partial ciphertext block, mirroring the plaintext structure exactly. This process occurs within the tweaked ECB framework: the data is first preprocessed with the tweak (via XOR with a tweaked initialization vector), encrypted block-by-block, and then CTS is applied only if the final block is partial, swapping and adjusting the last two ciphertext blocks as needed to maintain the original data length. The NIST Special Publication 800-38E approves XTS-AES under this construction, emphasizing that CTS enables the mode to handle sequences of complete blocks followed by a non-empty partial block without data expansion.[17]
One key advantage of incorporating CTS in XTS is the provision of position-dependent encryption, where the tweak ensures that identical plaintext blocks in different positions produce distinct ciphertexts, enhancing security against pattern analysis in storage contexts. Additionally, by avoiding padding, XTS with CTS supports fixed-size sector encryption typical in disk storage, preventing the overhead and potential vulnerabilities associated with padding schemes in other modes. This design choice makes XTS particularly suitable for full-disk encryption, where data integrity and minimal expansion are critical.[17][20]
The evolution of XTS reflects a targeted adaptation of CTS for modern storage encryption needs, building on earlier CTS variants to create a mode that operates efficiently within the constraints of block-oriented devices like hard drives and SSDs. Originally proposed to meet the requirements of the IEEE P1619 working group, XTS leverages CTS to ensure interoperability and flexibility in physical data ordering, such as allowing the optional swapping of the final two ciphertext blocks for storage efficiency, while preserving decryption correctness. This integration has positioned XTS as a widely recommended mode for sector-level confidentiality, as endorsed by NIST for protecting sensitive data at rest.[17]
Implementations in Standards and Software
Ciphertext stealing (CTS) has been standardized primarily as variants of CBC mode in cryptographic guidelines. The National Institute of Standards and Technology (NIST) published an addendum to Special Publication 800-38A in October 2010, specifying three variants of CBC mode incorporating CTS to handle plaintext lengths not divisible by the block size without padding.[21] These variants differ only in the ordering of the final two ciphertext blocks during encryption and decryption.[1] In 2023, NIST announced a revision to SP 800-38A to incorporate this addendum directly into the main document, reflecting ongoing maintenance of block cipher modes.[22]
However, adoption of CBC-based CTS has declined in network protocols due to vulnerabilities in CBC mode. The Transport Layer Security (TLS) Protocol Version 1.3, defined in RFC 8446 (August 2018), explicitly removes support for CBC modes, including CTS variants, in favor of authenticated encryption with associated data (AEAD) modes to mitigate risks like padding oracle attacks.[23] This deprecation extends to earlier TLS versions in modern implementations, where CBC-CTS is avoided for transport security.
In software libraries, CTS is implemented for compatibility and specific use cases. Microsoft's .NET Framework and .NET Core include CipherMode.CTS in the System.Security.Cryptography namespace, allowing developers to use it with supported block ciphers like Triple DES, though support for AES-CTS remains limited or provider-dependent in some versions.[24] The Bouncy Castle cryptographic library for Java provides CTSBlockCipher and NISTCTSBlockCipher classes, enabling CBC-CTS and other CTS variants with algorithms such as AES via the javax.crypto API.[25] OpenSSL supports CTS indirectly through its XTS mode implementation (EVP_aes_128_xts, etc.), which incorporates ciphertext stealing for handling non-block-aligned data in storage encryption.[26]
Prominent applications of XTS with CTS include full-disk encryption tools such as Microsoft's BitLocker, which uses XTS-AES 128-bit or 256-bit by default for operating system and fixed drives as of Windows 11, and VeraCrypt, an open-source successor to TrueCrypt that supports XTS-AES for container and whole-disk encryption.[27][28] In January 2025, a vulnerability (CVE-2025-21210) was disclosed in BitLocker's XTS implementation, enabling a randomization attack that allows attackers with physical access to manipulate ciphertext blocks and potentially recover information, though this is specific to the Windows implementation and does not affect the underlying XTS or CTS design.[29]
CTS finds application in legacy systems requiring exact-length ciphertext without padding, disk encryption leveraging XTS mode (as standardized in NIST SP 800-38E), and resource-constrained embedded devices where minimizing overhead is critical.[30] In XTS-AES, CTS ensures sectors not perfectly divisible by the block size (e.g., 512 bytes) are encrypted without truncation or extraneous padding.[17]
As of 2025, CTS remains in use for these niche scenarios but is generally superseded by AEAD modes like GCM or ChaCha20-Poly1305, which provide both confidentiality and integrity without the error propagation risks of CBC-based approaches.[31] NIST and other authorities recommend AEAD for new designs, limiting CTS to backward compatibility.[32]