Lucky Thirteen attack
The Lucky Thirteen attack (CVE-2013-0169) is a cryptographic timing side-channel attack against implementations of the Transport Layer Security (TLS) and Datagram Transport Layer Security (DTLS) protocols that use Cipher Block Chaining (CBC) mode of operation for symmetric encryption.[1] Discovered in 2013 by researchers Nadhem J. AlFardan and Kenneth G. Paterson, it exploits subtle variations in the computational time required for message authentication code (MAC) verification during the decryption of records with invalid padding, enabling attackers to infer information about the underlying plaintext through statistical analysis of timing measurements across multiple network sessions.[1] The attack builds on prior vulnerabilities like the BEAST attack but targets the record layer processing in TLS 1.0, 1.1, and certain configurations of TLS 1.2, as well as DTLS, by amplifying timing differences caused by the number of hash function invocations (e.g., SHA-1 compression operations) needed to verify padding.[1] In practice, it allows for distinguishing between ciphertexts with valid and invalid padding, and with sufficient queries—on the order of 2^23 sessions for full plaintext recovery in TLS—it facilitates partial or complete recovery of sensitive data such as HTTP cookies or session tokens, particularly when combined with techniques like those in the BEAST attack to inject chosen plaintexts.[1] For DTLS, the attack is more severe due to non-fatal error handling, making plaintext recovery feasible within a single session through timing amplification.[1] Upon disclosure, the Lucky Thirteen attack prompted widespread patches in major TLS libraries, including a 500-line modification to OpenSSL to equalize processing times and mitigate the side channel.[2] Affected implementations include those in OpenSSL prior to version 1.0.1d,[3] with mitigations involving constant-time padding checks, removal of CBC mode from TLS 1.0/1.1 in modern protocols, and a shift toward authenticated encryption modes like AEAD (e.g., GCM) in TLS 1.3.[2] Despite these fixes, the vulnerability underscored the risks of timing-based attacks in cryptographic protocols and influenced standards updates by bodies like the IETF to prioritize side-channel resistance.[4]Background
TLS Protocol Overview
The Transport Layer Security (TLS) protocol is a cryptographic protocol designed to provide communications privacy and data integrity between two applications over the Internet. It serves as the successor to the Secure Sockets Layer (SSL) version 3.0, with TLS 1.0 introduced to address limitations in earlier SSL designs while maintaining compatibility. TLS operates through two primary layers: the TLS Handshake Protocol and the TLS Record Protocol. The Handshake Protocol enables the client and server to authenticate each other and negotiate cryptographic parameters, including the key exchange method, to establish a shared secret. The Record Protocol then uses this shared secret to fragment outgoing data into manageable records, compress them if negotiated, apply a message authentication code (MAC) for integrity, and encrypt the result for confidentiality before transmission. TLS versions 1.0, specified in RFC 2246, and 1.1, specified in RFC 4346, are particularly relevant due to their reliance on block ciphers for encryption, such as in cipher suites like TLS_RSA_WITH_3DES_EDE_CBC_SHA. These versions support symmetric block ciphers operating in modes like CBC to secure application data. In the TLS Record Protocol of these versions, the MAC-then-encrypt construction is employed: a MAC is first computed over the plaintext data (including a sequence number, content type, version, and length), appended to the plaintext, and the entire block is then encrypted. The resulting TLS record consists of a 5-byte header—comprising a 1-byte content type, 2-byte protocol version, and 2-byte length field—followed by the encrypted fragment data.CBC Mode and Padding in TLS
Cipher Block Chaining (CBC) mode is a block cipher mode of operation used in TLS to provide confidentiality for encrypted records. In CBC mode, the encryption of each plaintext block P_i (for i > 1) involves XORing it with the previous ciphertext block C_{i-1} before applying the block cipher encryption function E_K with key K, yielding C_i = E_K (P_i \oplus C_{i-1}). The first block uses an initialization vector (IV) in place of C_0, ensuring that identical plaintexts produce different ciphertexts.[5] In the TLS record protocol, CBC mode is employed with symmetric block ciphers such as AES to encrypt the compressed content and message authentication code (MAC), protecting data in transit. The IV for each record is derived from the security parameters or the prior record's final ciphertext block in earlier TLS versions, though later specifications mandate unpredictable IVs to mitigate certain attacks.[5][6] TLS records require the total length of the plaintext (including content, MAC, and padding) to be a multiple of the block cipher's block size, typically 16 bytes for AES. To achieve this, PKCS#7 padding is appended to the data: if n bytes are needed (where $1 \leq n \leq block size), n bytes each with value n are added, and the final padding byte explicitly indicates the length n. Padding is added such that the total length is a multiple of the block size; if the unpadded length (content + MAC) is already a multiple, a full block of padding bytes, each with value equal to the block size, is added.[5][7] Upon decryption in TLS, the receiver first decrypts the record to obtain the padded plaintext, then checks the padding: the length n is read from the last byte, and all preceding n-1 bytes must equal n; any mismatch results in a fatal error alert, such as decryption_failed. If the padding is valid, it is removed, and the MAC is then verified on the remaining decrypted content (data) to ensure integrity.[5][6] In TLS 1.0 and 1.1, this sequence—padding validation followed by MAC verification—can introduce implementation-dependent behaviors, where flaws in error handling may distinguish between MAC and padding failures despite specifications aiming for uniform alerts like bad_record_mac.[5][6]Attack Description
Core Mechanism
The Lucky Thirteen attack exploits a padding oracle vulnerability in implementations of the Transport Layer Security (TLS) protocol using Cipher Block Chaining (CBC) mode, where the server implicitly reveals the validity of padding through differences in processing that allow an attacker to infer plaintext bytes one at a time. In CBC mode, messages are padded to align with the block size before encryption, and during decryption, the server must validate this padding; if invalid, it typically triggers an error, but the manner of error handling can leak information about the decrypted bytes. This padding oracle enables byte-by-byte recovery of plaintext by systematically modifying ciphertexts and observing server responses, as originally conceptualized in Vaudenay's analysis of CBC padding flaws.[8][9] Lucky Thirteen builds on Vaudenay's 2002 padding oracle attack but adapts it specifically to TLS's MAC-then-Encrypt (MEE) construction in CBC mode (MEE-TLS-CBC), where a message authentication code (MAC) is appended to the plaintext before padding and encryption. In MEE-TLS-CBC, decryption yields a putative MAC concatenated with the data, followed by padding removal and MAC verification; the attack leverages the requirement to perform MAC verification even on invalid padding to maintain security against earlier oracles, creating an exploitable information leak. This adaptation accounts for TLS's structure, including the fixed-size explicit MAC (typically 16-32 bytes depending on the hash function) and the positioning of padding at the record's end.[8][9] The key flaw targeted by Lucky Thirteen lies in the residual timing variations during MAC computation, even in implementations designed with constant-time countermeasures against prior attacks like BEAST, particularly when processing data after padding validation. Post-BEAST mitigations, such as random explicit IVs in TLS 1.1 and later, aimed to prevent chosen-plaintext attacks but left server-side decryption vulnerable to timing side-channels in MAC operations on the unpadded (valid padding) versus full (invalid padding) data lengths. These leaks arise because MAC algorithms like HMAC-MD5 or HMAC-SHA-1 process variable-length inputs, and stripping valid padding shortens the input compared to cases with malformed padding, where the full decrypted block is used.[8] The attack requires the adversary to control or influence the plaintext, such as by crafting HTTP requests in a TLS session to position known data adjacent to target bytes, and to observe server response times over multiple connections, typically as a man-in-the-middle. By modifying the last byte of the previous CBC block (which affects decryption of the target block via CBC chaining), the attacker induces controlled padding errors, probing the validity of guessed plaintext bytes through the resulting timing differences. This relation to CBC mode is central, as the malleability of CBC ciphertexts allows precise manipulation of decrypted values without altering the overall record integrity until verification.[8]Timing Side-Channel Exploitation
The Lucky Thirteen attack exploits subtle timing differences in the server's processing of TLS records using CBC-mode encryption, particularly during decryption and MAC verification, where the length of the padding influences the amount of data processed. In implementations following TLS 1.0/1.1 specifications, valid padding (e.g., a single-byte pad) allows the server to compute the HMAC only up to the implicit length field, typically resulting in 55 bytes of data for AES-CBC with SHA-1, whereas invalid padding forces processing of an additional byte or more, up to 56 bytes or beyond, before early termination due to padding errors.[1] This variation arises because the HMAC-SHA-1 computation involves block-wise processing, with 55 bytes requiring four 512-bit blocks (four compression function calls), while 56 bytes or more trigger a fifth call.[1] These differences manifest as measurable timing discrepancies of approximately 1 microsecond (corresponding to 500–1000 CPU cycles on typical hardware), which, though small, can be amplified through repeated queries to distinguish between padding outcomes reliably.[1] For AES-CBC with SHA-1, the core timing leak stems from the MAC verification step, where valid short padding processes fewer bytes than invalid long padding, creating a side-channel that leaks information about the plaintext's final bytes even when the overall record authentication fails.[1] The attack's feasibility hinges on injecting errors via truncated ciphertexts, which remove the MAC and padding blocks to control the padding length observed by the server, requiring around $2^{32} operations to recover a full byte of plaintext through statistical analysis of timing signals.[1] It is named "Lucky Thirteen" because the 13 bytes of fixed header information (8-byte sequence number and 5-byte record header) included in the TLS MAC input contribute to a 13-byte "padding window," enabling the attacker to extract up to 13 bits of information per query by probing different padding hypotheses.[1] Practical execution depends on environmental factors such as low-latency networks (e.g., local area networks with jitter below 100 microseconds), which enhance timing precision and allow the attacker to control network conditions for accurate measurements.[1] Countermeasures like constant-time implementations reduce these leaks by ensuring uniform processing regardless of padding length, though incomplete adoption can still leave residual vulnerabilities exploitable in controlled settings.[1]Technical Details
Padding Oracle Variant
The Lucky Thirteen attack adapts the classic padding oracle attack to the TLS protocol's use of CBC-mode encryption with PKCS#7 padding. In a standard padding oracle attack, an adversary modifies the ciphertext by flipping bits and submits it to the target system, which acts as an oracle by providing feedback—such as error messages—indicating whether the padding is valid, thereby allowing the attacker to iteratively guess the plaintext bytes.[1] In the TLS context, the attack accounts for the HMAC prefix (using HMAC-SHA1) appended to the plaintext before padding, which affects the effective plaintext length processed during decryption. The padding length varies, influencing the timing of the decryption and MAC verification processes; for instance, longer padding reduces the number of plaintext bytes authenticated by the MAC. To recover a byte in the target block P_n, the attacker malleates the previous ciphertext block C_{n-1} by XORing it with a chosen \Delta, which flips the corresponding byte in P_n to \mathrm{original}\ P_n \oplus \Delta. The \Delta is chosen such that, assuming a guess for the original byte, the modified P_n ends with valid PKCS#7 padding. If the timing indicates valid padding, the guess is correct, revealing the original byte as \mathrm{guess} = \mathrm{assumed\ padding\ value} \oplus \Delta.[1] The attack targets the last block of a TLS record, leveraging the malleability of CBC mode to assume knowledge of prior blocks from previous oracle queries. Each timing response provides partial information about whether the padding is valid for the guess, requiring statistical analysis of multiple samples to reliably distinguish valid from invalid cases due to timing variations.[1] Distinguishing valid from invalid padding relies on measuring timing differences in the server's responses, with the probability of successful discrimination exceeding 99% after collecting $2^{20} samples, using a threshold on the observed timing distributions.[1]Attack Execution Steps
The Lucky Thirteen attack requires the attacker to position themselves as a man-in-the-middle (MITM) or on the same local network to intercept and modify TLS traffic while measuring response timings accurately, often using custom scripts to automate packet crafting and round-trip time (RTT) collection.[8]- Establish a TLS session with a vulnerable CBC cipher suite: The attacker initiates multiple TLS connections to the target server using a cipher suite such as TLS_RSA_WITH_AES_128_CBC_SHA, which employs CBC mode with PKCS#7 padding. In each session, the attacker sends an initial legitimate TLS record containing the target data, such as an HTTP request embedding a secret like a session cookie in the plaintext. This record is intercepted and stored for subsequent modification.[8]
- Craft modified records with malleable ciphertext and truncation: For a target plaintext block of 16 bytes, the attacker begins recovery from the last byte backward. They malleate the ciphertext of the previous block by XORing it with a value combining the guessed plaintext byte and the expected padding, such that the modified target block ends with valid padding if the guess is correct (e.g., for the final byte, 16 possible padding lengths 1 to 16). The record's ciphertext is truncated immediately after the modified block to exclude the MAC, forcing a padding validation error unless the guess aligns correctly with the padding structure. Multiple variants are prepared for each guess (256 possibilities per byte), incorporating a known prefix in prior blocks to control decryption behavior.[8]
- Send batches of modified records and measure RTTs: The attacker transmits batches of these crafted records across numerous sessions (a multi-session attack for TLS, as single-session reuse is limited by session state). For each guess, approximately $2^{16} queries are sent in groups of L = 128 to $2^8 trials per variant, measuring the RTT to the server's error response. Responses are classified as "fast" (padding invalid, minimal processing) or "slow" (padding valid but MAC truncated and invalid, incurring full decryption and partial MAC timing overhead of ~2.5 μs). Network jitter is mitigated by proximity to the server and statistical aggregation of timings.[8]
- Apply statistical analysis to recover plaintext bytes iteratively: Timings from each batch are analyzed using medians or percentiles to detect the distribution shift indicating a valid padding guess (higher RTT variance). The correct byte is identified when the slow-case timing exceeds a threshold (e.g., via hypothesis testing on samples). Once the last byte is recovered, the process repeats for the penultimate byte (now with known padding), reducing queries to ~$2^8 per byte thereafter. This backward iteration continues until the full 16-byte block is decrypted.[8]