The timing signal – Attacks on the TLS Record Protocol
21.1.2 The timing signal
You may be wondering where the timing signal originates from in the encryption process illustrated in Figure 21.1. That source, it turns out, is the HMAC algorithm. Recall from Chapter 11, Hash Functions and Message Authentication Codes, that the HMAC construction applies the underlying hash function h to the message m twice, in an iterated manner:
This, in turn, leads to the following data-dependent timing behavior of the HMAC algorithm when it is implemented in a straightforward manner:
- Messages of up to 55 bytes can be encoded into a single 64-byte block. As a result, such messages require four hash function invocations, two for the inner and two for the outer hash.
- In contrast, messages of 56 to 115 bytes are encoded in two 64-byte blocks and, therefore, require five hash function invocations, three for the inner and two for the outer hash.
This means it is possible by measuring computation times for the HMAC to distinguish between messages that are shorter than 56 bytes and those that are 56 bytes or longer.
21.1.3 The attack
How can Eve exploit the HMAC timing signal to recover a plaintext from an encrypted TLS record? To see this, let c∗ be a ciphertext block whose corresponding plaintext p∗ Eve wants to recover. Let c′ be the ciphertext block preceding the block c∗.
Now, let Δ be a 16-byte block and cΔ a ciphertext of the form:
where the ciphertext block c′⊕ Δ is an XOR-masked version of c′ – that is, it’s the result of Eve XORing the original ciphertext block c′ with a 16-byte value Δ of her choice – and c∗ is the last ciphertext block.
The corresponding 64-byte plaintext is:
and – because we are using the CBC mode of operation – the plaintext block p4 is related to the unknown, targeted plaintext p∗ in this specific manner:
For illustration purposes, assume that SHA-1 is the hash function used in the HMAC algorithm (the attack works also for MD5 and SHA-256). In that case, the MAC tag is 20 bytes long.
As you can see in Figure 21.1, after decrypting ciphertext cΔ into plaintext p, Alice must do the following:
- Retrieve the payload from p by discarding padding and the received MAC tag.
- Compute a MAC tag for the message SQN∥HDR∥Payload.
- Compare the computed MAC tag to the received one.
Because of the length of the SQN∥HDR header – namely, 13 bytes, which also gives the attack its name – there are three possible outcomes when Alice calculates the MAC tag:
- Outcome 1: p4 ends with byte 0x00. In this case, 1 padding byte is removed from p and the next 20 bytes are interpreted as the MAC tag. As a result, the remaining 64 − 21 = 43 bytes are interpreted as the payload, and Alice computes the MAC for a 13 + 43 = 56-byte message SQN∥HDR∥Payload.
- Outcome 2: p4 ends with a valid padding pattern of at least 2 bytes. In this case, at least 2 padding bytes are removed from p, and the next 20 bytes are interpreted as the MAC tag. Consequently, at most 64−22 = 42 remaining bytes are interpreted as the payload, and Alice computes the MAC for the message SQN∥HDR∥Payload of at most 55 bytes.
- Outcome 3: p4 ends with any other byte pattern. In that case, the padding is invalid and – following the TLS 1.1 RFC recommendation – Alice treats plaintext p as if it had no padding at all. As a result, the last 20 bytes of p are interpreted as the MAC tag and the remaining 64 − 20 = 44 bytes are interpreted as the payload. Alice, therefore, computes the MAC for a 13 + 44 = 57-byte message SQN∥HDR∥Payload.
In all three cases, the MAC verification will fail. However, whereas in cases 1 and 3 the hash function will be executed 5 times, it will be only executed 4 times in case 2. So, Eve can distinguish case 2 from cases 1 and 3 by measuring how fast Alice replies with a TLS error message.
When Eve detects case 2, she knows that (given the plaintext has no specific structure) the likeliest padding pattern is 0x01∥0x01. This is because any longer padding pattern, such as 0x02∥0x02∥0x02, is about 256 times less likely. Thus, Eve can infer that p4 ends with 0x01∥0x01 and, based on the relation p4 = p∗⊕ Δ, recover the last two bytes of p∗.
Because Eve must correctly guess only the last two bytes of Δ to provoke case 2, she will succeed after 216 trials in the worst case. This is just a little more than 16 thousand trials and is, therefore, feasible in practice.
Once Eve has determined the last two bytes of p∗, she repeats the attack with a new mask Δ′, which is a modification of Δ in the third-to-last byte. This is even simpler than the initial hypothesis because now Eve only needs to guess one byte. Hence, Eve needs at most 14 × 28 trials to reveal all remaining 14 bytes of p∗.
Figure 21.2: TLS median network timings measured by Alfardan and Paterson using the OpenSSL library [4]
AlFardan and Paterson discovered that then-actual versions of popular cryptographic libraries such as OpenSSL, GnuTLS, NSS, PolarSSL, CyaSSL, and Java’s BouncyCastle and OpenJDK were vulnerable to the attack. Figure 21.2 shows the median of Alice’s decryption time for the different values of byte 15, where value 0xFE leads to a padding corresponding to case 2.
As expected, the correct guess leads to a shorter processing time, even when the times are measured over the network.