Note: the following discussion assumes you have the traffic keys.
Block Ciphers
It's easiest to recover if a block cipher is being used. Imagine that
we see a run of records, then lose a packet, producing a gap of
Length bytes. Call the first record after the gap Rx, the
next one Rx+1, etc.
SSL uses the last cipher block of
record Rx-1 as the CBC IV for record Rx. Thus, if
record Rx-1 is lost, we are not able to decrypt the
first cipher block of record Rx. However, the rest
of the record can be easily decrypted. Thus
the records we didn't see are unavailable, but
we can mostly access the records we managed to capture.
Obviously, because we don't have the first plaintext block of Rx, we can't verify the MAC. However, we can verify record Rx+1, because we do have the IV (the CBC residue from Rx). Unfortunately, because we don't know how many records have been lost, we don't know what the sequence number for Rx+1 is, and it's required to verify the MAC.
We can brute-force resynchronize by iterating over all possible sequence numbers until we find one where the MAC matches, at which point we must be synchronized. The question now becomes whether resynchronization can be done efficiently. The SSL sequence number space is 64 bits. Clearly, then, searching the entire space is prohibitive. Intuitively, there cannot have been more records than the number of lost bytes, so the number of sequence numbers we need search cannot be greater than the length of the missing region.
In practice, we need search far fewer than that. The maximum sequence number can be found by asking what the maximum number of records could have been contained in the missing TCP segments. Assuming that records are non-empty, the minimum plaintext size is 1 + M where M is the size of the MAC. Because M is either 16 (for MD5 or 20 (for SHA-1) and we have to pad to a block boundary, the ciphertext will be 24 bytes for DES and 3DES and 32 bytes for AES. With the 5-byte record header, the minimum record size MRS is 29 bytes (37 bytes with AES).
If we assume that the gap is smaller than the maximum SSL record, then the minimum number of missing records is 1. Thus, if we have a gap of Length bytes, this could contain anywhere from 1 to Length/29 records. If the last record before the gap has sequence number N, then Rx+1 has a sequence number in the range [N + 3,N + 2 + (Length/MRS)]. (The first missing record has sequence number N+1 and Rx has sequence number N+2). If we've lost a single Ethernet frame, this means checking no more than 50 sequence numbers for DES/3DES and 40 for AES.
In practice it's rarely necessary to try more than a few sequence numbers. Most SSL implementations use relatively consistent large record sizes so the loss of a single frame probably only means losing a single record.
In many cases, the data being transmitted will be highly structured, in which case we will have a good chance of guessing a single cipher block. If we can guess the plaintext of the leading block of the first record after the gap, we can verify it by checking to see if the MACs match. Note that it's much more efficient to resynchronize on the next record and then go back and try to verify our incomplete record: if there are n possible sequence numbers and m possible first blocks, this strategy requires m+n operations rather than the m*n operations required to resynchronize and guess plaintext blocks at the same time.1
Stream Ciphers
If the traffic is encrypted using a stream cipher, the problem becomes
figuring out exactly what section of keystream to use. We know from
the TCP sequence numbers how much data we have lost but because SSL
record sizes are variable, we don't know exactly how many bytes of
keystream have been used (recall that the record headers are not
encrypted). However, we can use a technique similar to the one we used
for block ciphers to recover the appropriate keystream offset.
Naively, we could simply try each potential stream cipher offset/sequence number combination until Rx verifies correctly, but this could be very expensive. Instead, we can take advantage of the fact that the keystream offset can be predicted if you know how many records you've missed. The logic is as follows: We know that Length bytes of TCP data are missing. Some of that data is un-encrypted headers. The rest was encrypted. The amount of keystream used is the size of the data which was encrypted, which is equal to Length minus the un-encrypted headers. Because SSL record headers are 5 bytes long, we get:
Offset = Length - (Records * 5)
Thus, we simply iterate over the possible values for Records until a MAC matches. Because each value of Records corresponds to one sequence number for our target record, we don't need to iterate over sequence numbers as well.
As before, we can determine the upper and lower bounds for the number of records lost. Because the records are unpadded, the minimum SSL record size when a stream cipher is used (again, assuming 1-byte long plaintext) is given by MRS = 5 + 1 + M Thus, there may have been anywhere from 1 to Length / MRS records lost. For example, if we've lost 1460 bytes, there could be anywhere from 1 to 66 records (if the MAC is MD5) and 1 to 56 records (if the MAC is SHA).
Partial Record Loss
Obviously, it's possible to lose only part of a record.
With a block cipher, we can recover exactly as described
above, except that we cannot verify the MAC at all on the
partial record.
With a stream cipher, we perform the recovery
procedure described above on the next whole packet and
then work backwards to figure out what the keystream
for the partial packet must be.
Handshake Message Loss
In general, losing handshake messages is bad, but it's
possible to recover from the loss of the Finished
messages, simply by treating them as data messages and
proceeding as described above. If the hello messages
or the ClientKeyExchange
are lost, however, we will be unable to generate the keying
material required to decrypt the connection.
1. Note that TLS 1.1 will have an explicit IV so as long as you have a complete record you will be able to decrypt it without the previous record.
This material was adapted from Secure Auditing for SSL Transactions by myself and Kevin Dick.
