0. Abstract
1. Introduction
1.1 TCP Sequence generation and PRNGs
1.2 Spoofing Sets
2. Phase Space Analysis, Attractors and ISN Guessing
2.1 Introduction to Phase Space Analysis
2.2 Using Attractors for Spoofing Set Construction
2.3 Real-Life Attack Algorithms
3. Review of Operating Systems
3.1 Linux
3.2 Windows
3.3 Cisco IOS
3.4 AIX
3.5 FreeBSD and NetBSD
3.6 OpenBSD
3.7 HP/UX
3.8 Solaris
3.9 BSDI
3.10 IRIX
3.11 MacOS
3.12 Multiple Network Devices
3.13 Other PRNG issues
4. Risk Analysis
5. Conclusions
6. References
7. Credits
Appendix A: Phase Space Images of Known Generating Functions
0. Abstract
We consider the problem of inserting a malicious packet into a TCP
connection, as well as establishing a TCP connection using an address that
is legitimately used by another machine. We introduce the notion of a
Spoofing Set as a way of describing a generalized attack methodology. We
also discuss a method of constructing Spoofing Sets that is based on Phase
Space Analysis and the presence of function attractors. We review the major
network operating systems relative to this attack. The goal of this document
is to suggest a way of measuring relative network-based sequence number
generators quality, which can be used to estimate attack feasibility and
analyze underlying PRNG function behavior. This approach can be applied
to TCP/IP protocol sequence numbers, DNS query identifiers, session-id
generation algorithms in cookie-based authentication schemes, etc.
Please note that presented results are preliminary and should not be
considered as a reliable metric for comparing the relative strength of
the operating systems ISN generators at this time.
1. Introduction
1.1 TCP Sequence generation and PRNGs
Upon connection via TCP/IP to a host, the host generates an Initial
Sequence Number (ISN). This sequence number is used in the conversation
between itself and the host to help keep track of each packet and to
ensure that the conversation continues properly. Both the host and the client
generate and use these sequence numbers in TCP connections.
As early as 1985 there was speculation that by being able to guess the
next ISN, an attacker could forge a one-way connection to a host by spoofing
the source IP address of a trusted host, as well as the ISN which would
normally be sent back to the trusted host via an acknowledgement packet.
It was determined that to help ensure the integrity of TCP/IP connections,
every stream should be assigned a unique, random sequence number. The
TCP sequence number field is able to hold a 32-bit value, and 31-bit is
recommended for use by RFC specifications. An attacker wanting to
establish connection originating from a fake address, or to
compromise existing TCP connection integrity by inserting malicious
data into the stream [1] would have to know the ISN.
Because of the open nature of the Internet, and because of large number of
protocols that are not using cryptographic mechanisms to protect data
integrity, it is important to design TCP/IP implementations in a way that
does not allow remote attackers to predict an ISN (this is called a
"blind spoofing" attack).
It is difficult to generate unpredictable numbers using a computer. This
is because computers are designed to execute strictly defined sets of
commands in repeatable and accurate ways. Thus, every fixed algorithm
can be used to produce exactly the same results on another computer,
which then can be used to effectively predict output values, assuming
attracker can reconstruct internal state of such a remote system.
Also, even if the target PNRG function is not known, sooner or later
the algorithm will start generating the same exact sequences over again,
because there is a limited number of possible internal states that can
be used by a specific algorithm (computers are using finite precision and
range arithmetics). Hopefully this happens later and the conditions to
start the repeating of sequential numbers will take many months or years.
But, there are known vulnerable implementations with a PRNG generator
period of just over 500 elements or less.
The common approach of dealing with this lack of true randomness is to
introduce additional randomness, or entropy, from an external,
unpredictable source. Usually, this randomness is calculated from
keystroke intervals, specific I/O interrupts and other parameters that are not
known to the attacker. This solution, combined with a reasonably good hashing
function that produces full 32 or 31-bit data with no correlation
between subsequent results without revealing useful information about the
internal state of PRNG function, can be used to make an excellent TCP sequence
generator. Unfortunately, TCP ISN generators are rarely written this
way, and when they are, there are numerous flaws or implementation errors
that can lead to predictable ISNs.
RFC1948 suggests the use of source IP address, destination IP address,
source port and destination port, plus an additional random secret key.
This data should be hashed using a shortcut function to generate random
and unique sequence numbers for every unique connection. Failing to account
for this can lead to improper conclusions when analyzing TCP generators with
respect to ISN predictability. Indeed, statements that are true for the
ISNs coming back to the attacker might not be true for other
connections, as the hash values would be different.
This research attempts to analyze the pseudo-random number generators
(PRNGs) used for TCP sequence number generation in different operating
systems and to expose potential flaws in the algorithms used. We
analyzed the generated sequence numbers, instead of trying to focus
on the actual implementations in the various operating systems. In essence,
we approached the analysis from the same standpoint as the remote attacker
would - from the network.
[1] - Data insertion attacks require additional knowledge about
established connections, which can be easily obtained in some cases. However,
no knowledge is required about the transferred data itself so, these
attacks qualify as "blind spoofing" attacks. Such attacks are performed
against open client-server connections based on the knowledge about
predictable ISNs used at one of the endpoints, and can be performed
against numerous protocols. One of the examples is inserting malicious
contents or malicious RCPT TO fields into SMTP transaction in order to
modify or intercept e-mails.
1.2 Spoofing Sets
TCP implementations must be reasonably robust against denial of service
(DoS) attacks. Among other things, this means that all TCP
implementations regularly discard packets with incorrect ISNs, since the
failure to do so presents an obvious DoS attack. TCP ISNs are 32-bit numbers.
So, if an attacker is able to generate 2^32 packets, each with a different
guess for the next sequence number, the attacker would be assured that
one of his malicious packets will contain the correct sequence number.
However, guessing the right ISN from the entire 32-bit space (4,294,967,296
possibilities) is not feasible due to the excessive amount of bandwidth
and time required. That is why a good TCP sequence number generator
implementation currently provides enough security to protect against
spoofing attacks, at least for the present time and in typical conditions.
But increasing bandwidth and processor speed will eventually make brute
force guessing of 32-bit ISNs feasible for the average attacker.
Based on these observations, we introduce the idea of a Spoofing Set. A
Spoofing Set is a set of guessed values for ISNs that are used to
construct a packet flood that is intended to corrupt some established TCP
connections. Our goal is to add enough reasonable guesses to the
Spoofing Set to ensure that the next ISN value is included, while at the same
time, keeping the Spoofing Set size small enough for an attack to be feasible.
A Spoofing Set can be as small as a single value or it as large as a
several million posibilities.
Attacks with less than 5,000 combinations are usually feasible
regardless of network uplink parameters and available resources.
Attacks with 5,000 to 60,000 possibilities are more resource-consuming,
but still possible. Attacks using more than 60,000 packets are possible only
rarely and would consume amounts of bandwidth and resources that are not
available to all attackers.
2 Introduction to Phase Space Analysis
In this section we provide a short introduction to phase space analysis
and the behavior of strange attractors. We then discuss how to apply these
tools to the problem of ISN value guessing.
2.1 Introduction to Phase Space Analysis
Phase space is an n-dimensional space that fully describes the state of
an n-variable system. An attractor is a shape that is specific to the given
PRNG function, and reveals the complex nature of dependencies between
subsequent results generated by the implementation.
We wanted to generate clean, three-dimensional representations of
one-dimensional input data. The method used is known as "delayed
coordinates", and is well-known and widely used in the analysis of
dynamic systems, especially nonlinear systems and deterministic chaos
[2].
This method assumes that we can reconstruct missing dimensions using
previous, delayed function values as additional coordinates. Instead of using
function values, we decided to calculate the first-order difference for
the input data to generate more suggestive and useful results to show the
function dynamics. So if s stands for the input set, and x, y and z are
the point coordinates we are looking for, the equations are:
The following is an example of input data from a sequence of ISNs.
Looking at the example doesn't allow us to determine what kind of underlying
function was used to generate the data. It appears that these numbers
are random with no dependencies between subsequent results:
...4293832719, 3994503850, 4294386178, 134819, 4294768138 191541,
4294445483, 4294608504, 4288751770, 88040492...
Here is what we would see when using the attractor reconstruction
technique:
What we see is an order and a correlation between subsequent results,
creating a subtle three-dimensional path.
2.2 Using Attractors for Spoofing Set Construction
We can now describe how to use 3-dimensional PRNG function attractors to
construct a Spoofing Set. Since the behavior of attractors is not fully
understood, we note that the algorithm presented here is a heuristic
approach. We can not prove, in a strict mathematical sense, that our
algorithm will accurately guess ISN values. Nor have we done the
statistical analysis that would be required to verify that our results are
statistically significant and predictive of future results. Such analysis
would require the collection of more data and is beyond the scope of this
paper. We hope this sort of independent verification will be an area of
future work.
Our approach is built upon this widely accepted observation about attractors:
If a sequence exhibits strong attractor behavior, then future values in
the sequence will be close to the values used to construct previous points
in the attractor.
Our goal is to construct a spoofing set, and, later, to calculate its
relative quality by empirically calculating the probability of making
the correct ISN prediction against our test data. For the purpose of ISN
generatorscomparison , we established a limit of guess set size at the
level of 5,000 elements, which is considered a limit for trivial attacks
that does not require excessive network bandwidth or processing power
and can be conducted within few seconds.
We assume the targeted system's operating system is known and that we
have already collected a sample sequence of approximately 50,000 ISN values.
We will call this sequence seq[n], and will call the corresponding set
of 3-dimensional phase-points calculated based on the deltas between
sequence values, A. Remember, the coordinates for points in the attractor,
A, are calculated using the equations:
Here is an example of the 3-dimensional attractor for some sequence,
seq[n]:
If we know the value of seq[t-1], the problem of determining a "good"
guess for the value of seq[t] is equivalant to choosing a "good" point in
discrete 3-space. Indeed, given a point (x, y, z), we can add x +
seq[t-1] to our Spoofing Set as a guess for seq[t].
Now, we turn our attention towards choosing points in discrete 3-space
that will produce effective Spoofing Sets. We refer to adding a point (x, y,
z), adding a delta value x and adding a sequence value to the Spoofing Set
interchangeably.
We begin this analysis by noting that seq[t-1], seq[t-2] and seq[t-3]
can be easily gathered by probing the remote host. Thus, the point (x[t],
y[t], z[t]), which corresponds to the next sequence value, seq[t], will be
somewhere on the line, L, given by:
If the effect of the 3-D attractor is strong, then it is reasonable to
assume that the actual value of seq[t] will correspond to a point that
is in, or is close to, the intersection of L and A.
So, we now consider how to build up our Spoofing Set. It is useful to
think of this as a three phase process. First, we want to include any points
in the intersection between our line, L, and the attractor, A. However, we
note that this intersection may be empty; a situation that occurs if the
subsequence seq[t-3], seq[t-2], seq[t-1] never appears in our original
input data stream. In this case, we want to add points in A that are
"close" to our line, L.
To explain this approach, we will describe how to construct a Spoofing
Set using a hypothetical example. Let's assume that the three previous
sequence values were equal to 5, 10 and 7816. Further suppose we do not
have any point in the attractor matching the y and z coordinates calculated
using these deltas ( y = 10-5 = 5, z = 7816-10 = 7806), but there is another
attractor point, for y = 6 and z = 7805. If the PRNG is not working
properly and there is some kind of correlation between the previous and
the next results, we can expect that points with almost the same y
and z coordinates would have almost the same x coordinates. Of course,
this may not be true, but if it is, then it is a clear sign of a weak PRNG.
Assuming it's true, we want to include this point in our Spoofing Set,
and hope that the next ISN will be relatively similar.
So, the second phase of our process is to select all points in A that
are within some radius, R1, of the line, L, and use their corresponding x
values to create candidates for the Spoofing Set.
Finally, the observed behavior of strong attractors is that their shape
tends to fill up and become more dense as more points are plotted. This
implies that the value of x(t) should be relatively close to the x-value
of one of the points already in our Spoofing Set.
Geometrically speaking, we can think of taking the projection of all
points currently in our Spoofing Set onto line L or in near proximity of it
(radius R1). Then for each point in the projection we create an interval
with radius R2, and add each of the integer values within these
intervals to the Spoofing Set. More precisely, for each value x in the initial
Spoofing Set, we add the following values:
x + 1, x - 1, x + 2, x - 2, ... x + R2, x - R2
Because we want to implement a fixed limit of 5,000 elements per guess
set, we have to select R1 in the way that would generate non-empty guess sets
(usually of the size 1-500) in the phase 2, and choose R2 to produce
exactly 5,000 elements (excluding possible overlaps in generated ranges
for every ISN guess obtained in phase 2).
We have produced a program that implements this algorithm, and performs
an attractor space search to predict the next ISN values.
The program accepts four parameters. These parameters are the three
previous sequence numbers and the search radius R1, which affects search
speed and does not have significant meaning for the generated results as
long as any points can be found. The program tries to guess the next
ISN. The ISN guesses generated correspond to the values that are used to
generate attractor points. For more precise results, the Spoofing Set
can be sorted first by the "attraction strength" (point saturation) of
every point and then, for points of similar attraction strength, by
distance from the given y and z line.
Separate program was used to calculate the value of R2
that has to be used for the initial Spoofing Set returned previously
in order to achieve Spoofing Set of size exactly 5000.
For PRNG function analysis, we collected streams of 100,000 sequence
numbers for many popular operating systems. For each operating system,
we divided our input data set into two parts. The first 50,000 were used by
our algorithm to reconstruct the phase-space attractor. Then,
trials were conducted to analyze relative Spoofing Set quality. This was
done by inspecting all possible quadruples of ISNs from the second
50,000 and calculating the number of values that could be predicted using the
Spoofing Set generation algorithm described above. The percentage of
successful guesses is referred to as the "attack feasibility ratio".
Additional spoofing set characteristics are calculated at the time of
initial tests:
- Average R2 radius, which reflects attractor strength; a larger R2
radius indicates a stronger attractor structure while a smaller R2 indicates a
more dispersed structure
- Average error, which reflects average distance from the numbers
generated in stage 2; it is always smaller than R2, and a large disproportion
means that usually less than 5,000 guesses has to be made for successful ISN
prediction,
- Average number of elements generated in stage 2, and average number of
elements to be processed before getting the right guess; this, for given
R1, reflects attractor density,
Note that average error value can be calculated only if there is enough
correct guesses.
These values, along with the attack feasibility and specific attractor
3D representation, are unique for every operating system or ISN
implementation.
To minimize or avoid the risk caused by the RFC1948 suggestions
mentioned earlier, our test data was generated using a constantly
changing source port number. For properly working hashing functions
built according to the RFC specifications, changes of used source port
would cause effects that are not distinguishable from changes caused by
different source addresses. Other behaviors would mean that the hashing
function could be easily reversed and is not secure for PRNG or RFC1948
purposes. Whenever RFC1948-specific behavior was observed, additional
tests with constantly changing source address IPs were performed to confirm
this assumption.
Note: Our test set of approximately 50,000 quadruples is not a true
random sampling of real-life data. The quadruples are subsequent to each other
and are subsequent to the data set used to reconstruct the attractor. For
this reason, we must point out that our coverage rate can not be interpreted
as being predictive of future success. It should be relatively straight
forward to perform the requisite statistical analysis to be able to make
statements about the accuracy of our initial trials, but this is beyond
the scope of this paper.
2.3 Real-Life Attack Algorithm
The results presented in this document were produced using relatively
good network parameters on LAN networks or fast Internet uplinks. For some
algorithms, mainly time-dependent algorithms, the generated attractors
are specific for given packet latency ranges. For example, an attractor
built for a network where SYN packets (and SYN+ACK responses) are delivered in
the intervals of 10 to 20 milliseconds would be unsuitable or would
produce significantly lower quality guesses against a host with packet
delivery intervals of 500-800 ms.
Because of this, it may be a good idea to generate attractors for few
common timing ranges for each operating system, and use the best for a
specific attack. Nevertheless, unstable or overloaded links, where
average delivery delays vary heavily (e.g. 10-5000ms), might decrease the
relative quality of Spoofing Sets generated against time-dependent algorithms.
This observation does not apply to other algorithms that show no
time-dependency patterns. Additionally, excessive packet drop ratios and
other network conditions can affect attack feasibility.
For the purpose of estimating attack feasibility and choosing the best
attractor for a given operating system, applied patches and network
latency, we recommend the following algorithm:
A) The attacker has a set of attractors built for specific systems (and
in specific network conditions). Every attractor should be described with
additional parameters, that include estimated attack feasibility,
average R2, average error, average elements count, etc.
B) The attacker should get n data samples, each containing four
subsequent sequence numbers from the host to be attacked. The operating
system of the target does not need to be known at this point. In most cases,
n=20 should be sufficient. This it requires sending 80 packets.
C) For each attractor in the archive, the attacker should use the first
three sequence numbers in each data sample to predict the fourth, by
using the algorithm discussed above and the R1 that belongs to this
attractor. The attacker should choose the attractor with the best results.
D) Then, the attacker has to wait until the attack condition happens.
The attacker can then collect the three sequence numbers, create a
Spoofing Set with the selected attractor and perform the attack.
E) If no suitable attractor has been found, the specific operating
system or specific network parameters cannot be exploited in a feasible way
using the known data, then here are two ways to solve this problem. First, the
attacker can use target itself to build an attractor. This method would be very
accurate, but it involves sending thousands of packets, which might be
noticed. Or, they can perform operating system fingerprinting, and
reproduce the targeted system configuration in a lab or locate it
somewhere else, where attack would not be noticed. Then, the attacker
needs to measure the average network latency and the fluctuations, and
reproduce the conditions during the attractor construction process.
Finally, standard attractor test procedures (probability estimations,
choosing R1, etc.) need to be performed.
3. Review of Operating Systems
In this section, we discuss the specific TCP/IP ISN
generators used by a variety of operating systems.
3.1 Linux
Linux 2.2 TCP/IP sequence numbers are not as good as they might be, but
are certainly adequate, and attack feasibility is very low. There is no
strong attractor structure; it makes a 24-bit wide cloud, which means that the
deltas are in the range C to C + 2^b - 1, where C is a constant shift and b is
a bit width of the cloud. A wider 32- or 31-bit cloud would be better, but
24 bits gives over 16 million combinations, making spoofing practically
impossible in most real-life scenarios.
Our attractor analysis method gives results comparable to a brute-force
search of whole 24-bit space. Linux can be qualified as low-risk OS in the
scope of this document.
Linux is taking advantage of RFC1948. The hashing function
implementation seems to be flawless, and additional randomness is introduced.
Thus, the observed ISN generator characteristics are not related to any
specific TCP connection parameters. ISNs are more easily predictable when
using exactly the same source port, source address, destination port and
destination address, but hashing function "secret" value is modified
in relatively short time intervals (and thus frequently changing observed
characteristics), do not exposing system security.
3.2 Windows
Windows 2000 and Windows NT4 SP6a are presenting almost the same level
of TCP sequence number predictability, which can be qualified as medium to
high, allowing attacker to get reasonably high success rates without
using excessive amounts of network resources. Both systems are mildly
vulnerable to attacks. There is no strong attractor structure visible
(3D "cube").
Windows NT4 with no recent service patches and hotfixes is vulnerable to
ISN guessing attacks using just a few packets, and can be easily
attacked using 5,000 guesses with an almost 100% success rate. This version of
Windows NT 4.0 can be qualified as high risk. Our attractor analysis method
gives very good results here. NOTE: Problems in pre-SP6a Windows NT were
already addressed in several advisories.
Windows 95 sequence numbers are very weak. But it is really difficult to
understand is why this algorithm was further "weakened" in Windows 98
(SE), decreasing estimated error and number of elements required to get the
right guess, in average:
3.3 Cisco IOS
Recently, some security advisories addressing serious TCP/IP sequence
number flaws in the Cisco IOS operating system were released. Short
tests against Cisco IOS implementation show the nature of this vulnerability:
What we see above is a trivial, probably microsecond clock-based time
dependency at its finest (see Appendix A), with most
of the points attracted to one point with "echos" around. In order to
exploit this vulnerability, the attacker would simply have to synchronize
his own clock with the IOS clock, taking care of packet rtt times, and
performing the attack at any time by sending packets for, e.g., 100
microseconds +/-. Thus, Cisco IOS can be qualified as a high-risk OS.
Besides that, our attractor analysis method provides reasonably high
success ratio using 5,000 guesses against this OS.
Here, for comparsion, are the results for patched IOS. The main
attractor is still there, but some additional noise was introduced to make the
prediction more difficult:
3.4 AIX
This is a trivial cyclic increments example. The output doesn't look too
impressive because there are just a few values used:
3.5 FreeBSD and NetBSD
FreeBSD 4.2 implementation is not impressive, and can be qualified as a
medium to low risk system. An attack with minimal resources has a small,
but non-zero success ratio:
3.6 OpenBSD
The problem here is pretty similar to the FreeBSD case - not alarming,
but not impressive. Tested against OpenBSD 2.8:
The OpenBSD TCP/IP sequence number generator has recently been rewritten
by Niels Provos. New code is available, but had not been included in any
official release as of this writing. According to Theo de Raadt, the
code was finished in December, and is supposed to be shipped with OpenBSD 2.9
in late May. The current version of OpenBSD generates a 31-bit wide cloud
which does not produce any useful spoofing sets:
3.7 HP/UX
HPUX10 seems to have, practically speaking NO random sequence numbers.
It has constant increases of 64,000 (0 bits of randomness, 1 guess, R1=0,
R2=0). This is the default configuration, which fortunately can be
modified, but once modified becomes a well-known cube pattern. HPUX11
seems to have a significantly improved random number generator. The function
used seems to be really weird, reminding us of the shape of the Mir orbital
station. Unfortunately, this is certainly not enough. It is possible to
find a 12-element spoofing set, and HPUX can be described as a high risk
system:
3.8 Solaris
Solaris has three different settings for the tcp_strong_iss kernel
parameter. When it is set to 0, completely predictable numbers are
generated (a 9-element SpoofingSet). With the default setting of 1,
Solaris 7 and 8 generates relatively good, but certainly not perfect, ISNs:
In Solaris 8 with tcp_strong_iss=1, the "randomness" source seems to
behave slightly differently, but this does not affect its quality. The data
makes oval, Linux-like cloud:
Setting tcp_strong_iss to 2, according to the vendor, is supposed to
generate very reliable and unpredictable ISNs. The attractor generated
for this operating system is filling 32-bit space rather uniformly. On the
other hand, using the attractor analysis method, it is possible to guess
the right value in less than 200 attempts, which can be explained by
heavy saturation of attractor points:
It is important to note that, Solaris with tcp_strong_iss set to 2 seems
to use the RFC1948 approach, which can be deduced by observing very low ISN
deltas changes when using exactly the same source port and other TCP parameters
in subsequent probes. To eliminate the risk described above when we
discussed the issue of RFC1948 compliance, we repeated this tests for two
different IP addresses, using the first data set to predict results
found in the second. We found that the attractors generated in both cases are
different. This does mean that you cannot use the data gathered using one IP
address to perform attacks against another, because there is no consistency in
ISN values when changing IP address.
At the same time, this problem does not exist, for example, on Linux,
which is implementing RFC1948 as well. This is because Linux is introducing
additional randomness to ISNs, while Solaris does not, and generates
constant, predictable patterns for the same IP address. The Solaris
implementation is insufficient, because ISNs are almost completely
dependent on shortcut function results, and for a few thousand of
commonly used source port values, there could be no more than few
thousand hashes (assuming other TCP connection parameters are not changing).
Solaris does not compensate this problem, and does not seem to introduce
additional randomness or re-generate a hashing function secret value.
Consequences are potentially dangerous in cases when clients connecting
to Solaris server are using reusable IP addresses (e.g. dial-ups, networks
implementing dynamic addresses or address translation / sharing),
because attacker can build an attractor based on the characteristics of the
target server and use it to perform attacks against server-client
communication in the future. Additionally, this information can be used to
perform blind spoofing attacks to establish a fake identity of the
network object that the attacker had access to some time ago (but does
not have it anymore).
At the same time, in cases when IP addresses in TCP connections
established to Solaris server are not used by other people at any time,
there is no risk caused by that.
Below is the attractor pattern for Solaris with tcp_strong_iss set to 2
generated for constantly changing source IP addresses:
3.9 BSDI
Both BSDI's 3.0 and 4.releases are similar to FreeBSD and give
practically the same results,
with a little bit more visible shadows. This makes the attack more
difficult. The risk factor is medium to high.
3.10 IRIX
The IRIX operating system, even in versions that are meant to have
relatively good ISN subsystem (recent 6.5 releases), seems to be flawed:
This graph shows a 15-bit "flower" containing over 98% of all observed
ISN deltas. Risk is medium to high.
3.11 MacOS
The older MacOS9 operating system has a predictable ISN generator. The
output pattern is similar to an X-wing fighter:
The MacOS X operating system is another candidate for possible TCP
sequence number guessing attacks, but is more secure than previous releases:
3.12 Multiple Network Devices
Most of the network devices like HP printers, many routers (Motorola,
Netopia, US Robotics and Intel), Siemens IP phones, numerous 3Com switches
and so on have completely predictable sequence numbers that use constant
increments (or no increments at all). These devices would have a one-point
or few-point representation of their PRNG engines. These problems are, in
most cases, widely known and have been discussed on numerous forums (such
as BugTraq), thus we do not think they are worth a separate discussion in
this paper, but, as there is constantly increasing number of services
provided by such a "smart" network equipment (for remote management,
configuration or document delivery), this becomes more and more appealing
problem.
3.13 Other PRNG issues
PRNGs are providing data source authentication not only in TCP protocol.
Other uses are generating session-id "cookies" for secure web browsing
and DNS protocol sequence numbers. DNS runs over UDP most of the time and
the UDP protocol itself does not support sequence numbers. This paper is not
going to discuss other PRNG applications in detail, but we would like to note
the problem and demonstrate how easily our approach can be extended to,
practically speaking, any [P]RNG implementation. First of all, three
examples:
The following picture shows the weak glibc 2.1.9x resolver DNS sequence
numbers implementation on Linux in client queries (over 50% attack feasibility,
applying our previous algorithm to this case):
Below is the pattern generated for the Microsoft DNS server
implementation (queries originating from the server), which shows very strong
predictability pattern and is certainly not sufficient to protect
against DNS spoofing (100% feasibility, average error of 2):
The last example is the Solaris 7 libc resolver pattern. It looks much
more random than two examples mentioned above, but still have significant
attractor patterns:
DNS sequence numbers are, generally speaking, weak, because only 16-bit
space is used for this purpose. Weakening these numbers even more - as
in MS DNS or Linux resolver case - allows attacker to perform almost
instant DNS poisoning / DNS spoofing attacks. These attacks are even more
dangerous, and certainly less complicated than TCP sequence number
attacks. To intercept traffic originating from vulnerable client to,
for example, www.microsoft.com server, attacker has to convince the DNS
resolver implementation that this address should resolve to the attacker's IP
address instead of the legitimate one. In case of caching servers or
client-side daemons (like *nsd), this condition is even worse, because
attack does not require human interaction and can be automated.
Recent bind releases and the FreeBSD resolver do not show attractor
patterns. We have not tested another DNS daemon implementations (djbdns, etc)
or resolvers (IRIX, HPUX, AIX), session-id generators in numerous other
protocols, etc.
4. Risk Analysis
Below is the graph representing relative ranking of the operating
systems tested in this survey:
OpenBSD-current (future 2.9 release) wins the competition. Linux 2.2.1x gets
a relatively good score, but it is far
from being perfect. Other systems generally received mediocre or very bad
scores. Solaris with tcp_strong_iss set to 2 is interesting because it gets
both one of the best and
the one of the worst ranks at the same time, depending on whether
or not the same Source IP is used to generate the attractor and to
launch the attack.
We would like to note that using
a strictly RFC1948 compliant implementation may not be a
definitive answer to ISN guessing attacks. We make two observations.
First, RFC1948 permits systems to create their ISN generation secret
at boot time and to reuse this secret until shutdown. Second,
IPv4 addresses are very often re-used (e.g. ISP dynamically assigned
addresses, network address translations). Taken together
these means that if an attacker were able to construct
a scenario in which he could build an attractor (approx. 50k ISN numbers)
with a set Source IP, then he could later launch an attack from that same
Source IP with a reasonable chance of success, so long as the
ISN generation secret on the target has not been recreated.
This explains the large disparity between our Attack Feasibility
estimates for Solaris with tcp_strong_iss=2 based on using the
same Source IP (66%) and using different Source IPs (0%).
5. Conclusions
The general conclusions can seem a little scary. What comes to our
attention is that most every implementation described above, except
maybe current OpenBSD and Linux, has more or less serious flaws that
make short-time TCP sequence number prediction attacks possible. Solaris
7 and 8 with tcp_strong_iss set to 2 results are a clear sign there are
a lot of things to do for system vendors. We applied relatively loose
measures, classifying attacks as "feasible" if they can be accomplished using
relatively low bandwidth and a reasonable amount of time. But, as
network speeds are constantly growing, it would be not a problem for an
attacker having access to powerful enough uplink to search the entire 32-bit
ISN space in several hours, assuming a local LAN connection to the victim
host and assuming the network doesn't crash, although an attack could be
throttled to compensate. While it seems obvious that OS vendors should
do their very best to make such attacks as difficult as possible, it
obviously isn't so. In most cases, we are observing ISN generators that are
vulnerable to immediate guess, or can be attacked using average modem /
DSL connection. This is even in server systems that are supposed to have
strong ISNs.
It is worth reminding that risks caused by predictable ISNs were known for
at least 15 years, giving more than enough time to build strong and
unpredictable implementations. In all PRNG applications where risks were
not that emphasized - DNS resolver implementations, authentication
cookies and session-id generators, situation is even worse.
Of course, when it comes to TCP/IP ISNs, the good news is that a lot
of this is dependent upon certain conditions. For an attack to work,
you need the following:
- An open TCP port to get an initial ISN, or a sniffed ISN. If there are
no open ports reachable by the attacker, then the ISN would have to be
guessed. Knowing a current ISN would certainly help tailor an attack to
increase the odds of its success. This is still very possible, but the
level of intelligence required to make the attack in the first place
(such as sniffing and probing) would probably point to an alternate attack
method that would be far more likely to succeed.
- Routing that will allow forged packets to reach the target. Proper
firewall and router rules can prevent forged packets from reaching the
target (network interface subnet filtering, expected TTL measuring, ISN
storm detection). This does not necessarily mean spoofing is impossible,
and, in some cases, might lead to serious DoS conditions, but would
make TCP/IP blind spoofing attacks harder to perform.
- A service listening on the target that can be properly exploited via a
blind spoof (or, alternatively, existing and known client-server stream
that would be vulnerable to spoofing). Except denial of service and
potentially exploiting trust relationships, many attacks against
listening services often require more than just guessing the ISN. They
require the knowledge of several potentially unpredictable factors.
If the target doesn't really have an exploitable service or client
software running, or some factors required to perform the attack are
unknown to the attacker, then his options (ISN spoofing or otherwise) can be
extremely limited.
It is worth mentioning that TCP/IP sequence numbers analysis has some
other interesting aspects besides finding vulnerable implementations. Every
operating system generates a different attractor shape. While metrics
used in traditional OS fingerprinting can be easily fooled (usually by
altering publicly available kernel parameters via sysctl), a TCP sequence
number generator cannot be modified that easily. At the same time, every system
seems to have a separate generating function. So, this technique may be
modified for reliable remote OS detection, as well.
6. References
TCP/IP networking:
http://msdn.microsoft.com/library/backgrnd/html/tcpipintro.htm
TCP/IP spoofing, ISN weakness:
http://www.sans.org/infosecFAQ/threats/intro_spoofing.htm
Phase-space reconstruction:
http://www.mpipks-dresden.mpg.de/~tisean/TISEAN_2.1/docs/chaospaper/node6.html
Chaos Theory and Fractal Phenomena: http://www.duke.edu/~mjd/chaos/chaos.html
Tool sources: vseq.tgz
Used data samples: data.tgz (approx. 15 MB)
7. Credits
Some of data sets (Solaris, AIX, HPUX) contributed by skyper
<skyper@segfault.net>
Windows 95/98 data contributed by noah williamsson
<noah@hd.se
Cisco and BSDI data contributed by (anonymous).
Solaris tcp_strong_iss and other data contributed by Elias Levy
<aleph1@securityfocus.com>
Router data sets contributed by Piotr Zurawski
<szur@ix.renet.pl>
Some of HPUX samples contributed by Solar Designer
<solar@openwall.com>
Thanks to Theo de Raadt and all other people who reviewed this
publication and came up with suggestions, corrections or comments.
Special thanks to Matt Power, Dave Mann, Mark Loveless, Scott Blake
and other RAZOR Team members for their extensive work on this document.
x[n] = s[n-2] - s[n-3]
y[n] = s[n-1] - s[n-2]
z[n] = s[n] - s [n-1]
![[ curly function ]](funct.jpg)
x[t] = seq[t] - seq[t-1]
y[t] = seq[t-1] - seq[t-2]
z[t] = seq[t-2] - seq[t-3]
![[ random planes ]](mix.jpg)
y = seq[t-1] - seq[t-2]
z = seq[t-2] - seq[t-3]
![[ yellow line ]](mix2.jpg)
![[ Linux ]](linux.jpg)
Operating system:
Linux 2.2
R1 radius:
1000
Attack feasibility:
below 0.05%
Avg. number of elements:
27 / n/a
Average R2:
1415
Average error:
n/a
![[ Windows 2000 ]](win2k.jpg)
Operating system:
Windows 2000
R1 radius:
10
Attack feasibility:
12.08%
Avg. number of elements:
81 / 5
Average R2:
413
Average error:
151
Operating system:
Windows NT4 SP6a + hotfixes
R1 radius:
10
Attack feasibility:
15%
Avg. number of elements:
106 / 5
Average R2:
426
Average error:
177
![[ Windows NT ]](winnt.jpg)
Operating system:
Windows NT4 SP3
R1 radius:
0
Attack feasibility:
97.00%
Avg. number of elements:
570 / 2
Average R2:
670
Average error:
8
![[ Windows 95 ]](win95.jpg)
Operating system:
Windows 95
R1 radius:
0
Attack feasibility:
100.00%
Avg. number of elements:
1048 / 1
Average R2:
2294
Average error:
118
![[ Windows 98 ]](win98.jpg)
Operating system:
Windows 98 SE
R1 radius:
0
Attack feasibility:
100.00%
Avg. number of elements:
785 / 1
Average R2:
1091
Average error:
7
![[ Cisco IOS t-dep ]](cisco2.jpg)
Operating system:
Cisco IOS 12.0 (unpatched)
R1 radius:
10
Attack feasibility:
20.00%
Avg. number of elements:
88 / 3
Average R2:
557
Average error:
431
![[ Cisco IOS patched ]](cisco.jpg)
Operating system:
Cisco IOS 12.0 (patched)
R1 radius:
1000
Attack feasibility:
2.06%
Avg. number of elements:
143 / 3
Average R2:
296
Average error:
182
![[ AIX ]](aix.jpg)
Operating system:
AIX 4.3
R1 radius:
0
Attack feasibility:
100.00%
Avg. number of elements:
99 / 1
Average R2:
278
Average error:
0
![[ FreeBSD ]](freebsd.jpg)
Operating system:
FreeBSD 4.2
R1 radius:
10
Attack feasibility:
1.00%
Avg. number of elements:
59 / 2
Average R2:
129
Average error:
64
![[ OpenBSD ]](openbsd.jpg)
Operating system:
OpenBSD 2.8
R1 radius:
20
Attack feasibility:
3.05%
Avg. number of elements:
63 / 4
Average R2:
660
Average error:
372
![[ OpenBSD-current ]](obsdnew.jpg)
Operating system:
OpenBSD-current
R1 radius:
1000000
Attack feasibility:
0.00%
Avg. number of elements:
20 / n/a
Average R2:
1707
Average error:
n/a
![[ HP/UX 11 ]](hpux11.jpg)
Operating system:
HPUX11
R1 radius:
0
Attack feasibility:
100.00%
Avg. number of elements:
10 / 1
Average R2:
2499
Average error:
0
![[ Solaris 7 ]](sol7.jpg)
Operating system:
Solaris 7 (tcp_strong_iss=1)
R1 radius:
10
Attack feasibility:
2.08%
Avg. number of elements:
27 / 2
Average R2:
1292
Average error:
732
![[ Solaris 8 ]](sol8.jpg)
![[ tcp_strong_iss 2 ]](sol2.jpg)
Operating system:
Solaris 7 (tcp_strong_iss=2)
R1 radius:
100
Attack feasibility:
66.00%
Avg. number of elements:
19 / 1
Average R2:
2448
Average error:
108
![[ tcp_strong_iss 2 ]](sol2ip.jpg)
Operating system:
Solaris 7 (tcp_strong_iss=2)
R1 radius:
1000000
Attack feasibility:
0.00%
Avg. number of elements:
762 / n/a
Average R2:
208
Average error:
n/a
![[ BSDI ]](bsdi.jpg)
Operating system:
BSDI 3.0
R1 radius:
10
Attack feasibility:
18.00%
Avg. number of elements:
70 / 3
Average R2:
779
Average error:
379
![[ IRIX ]](irix.jpg)
Operating system:
IRIX 6.5
R1 radius:
100
Attack feasibility:
20.00%
Avg. number of elements:
87 / 4
Average R2:
700
Average error:
200
![[ MacOS 9 ]](macos1.jpg)
Operating system:
MacOS 9
R1 radius:
100
Attack feasibility:
89.00%
Avg. number of elements:
1064 / 46
Average R2:
184
Average error:
30
![[ MacOS X ]](macos.jpg)
Operating system:
MacOS X
R1 radius:
10
Attack feasibility:
17.00%
Avg. number of elements:
121 / 6
Average R2:
384
Average error:
249
![[ libc resolver ]](dnslibc.jpg)
![[ MS DNS ]](dnswin.jpg)
![[ Solaris resolver ]](dnssol.jpg)
![[comparsion]](comp.jpg)
Harris, B. and Hunt, R., "TCP/IP security threats and attack methods",
Computer Communications, vol. 22, no. 10, 25 June 1999, pp.
885-897.
Guha, B. and Mukherjee, B., "Network Security via Reverse Engineering
of TCP Code: Vulnerability Analysis and Proposed Solutions",
IEEE Network, vol. 11, no. 4, July/August 1997, pp. 40-48.
Hegger, R., Kantz, H., and Schreiber, T., "Practical implementation of
nonlinear time series methods: The TISEAN package", Chaos, vol.
9, no. 2, June 1999, pp. 413-435.
Schreiber, T. and Schmitz, A., "Surrogate time series", Physica D,
vol. 142, no. 3-4, 15 August 2000, pp. 346-382.
Benoit B. Mandelbrot, "The Fractal Geometry of Nature",
W. H. Freeman and Company, NY, 1977-2000
![[ random noise ]](random.jpg)
![[ stat correlation ]](data.jpg)
![[ small increases ]](linc.jpg)
![[ t-dep ]](ttime.jpg)