One of the ways in which TLS breaks when run over an
unreliable data network is that there are dependencies between
the data records. In particular, decrypting record X+1
depends upon knowing information about record X. When you're
one of the communicating peers, this isn't generally a problem
because TCP guarantees the reliability of the transport, but
in passive sniffing applications, it's reasonably common
to lose packets. With some thought, however,
it turns out that with some thought you can actually
reconstruct most of the remaining data stream.
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.
