TUCoPS :: Unix :: General
:: unix4359.htm
Update on M.Zalewski's paper "Strange Attractors and TCP/IP Sequence Number Analysis"
2nd May 2001 [SBWID-4359]
COMMAND
kernel
SYSTEMS AFFECTED
unices
PROBLEM
Michal Zalewski has released a papers named "Strange Attractors
and TCP/IP Sequence Number Analysis". It can be found at
http://razor.bindview.com/publish/papers/tcpseq.html
Update (11 September 2002), Michal Zalewski posted an updated paper :
======
http://lcamtuf.coredump.cx/newtcp/
In the paper Michal describes the use of dynamical system methods
to analyze and predict TCP initial sequence numbers.
Guardent has finally seen fit to release Tim Newsham's paper on
the weaknesses of TCP initial sequence number algorithms that use
random increments. You can download it from
http://www.guardent.com/cgi-bin/pdfdownload.pl
Following is based on a CERT's advisory CA-2001-09.
Attacks against TCP initial sequence number (ISN) generation have
been discussed for some time now. The reality of such attacks
led to the widespread use of pseudo-random number generators
(PRNGs) to introduce some randomness when producing ISNs used in
TCP connections. Previous implementation defects in PRNGs led to
predictable ISNs despite some efforts to obscure them. The
defects were fixed and thought sufficient to limit a remote
attacker's ability to attempt ISN guessing. It has long been
recognized that the ability to know or predict ISNs can lead to
manipulation or spoofing of TCP connections. What was not
previously illustrated was just how predictable one commonly used
method of partially randomizing new connection ISNs is in some
modern TCP/IP implementations.
A new vulnerability has been identified (CERT VU#498440, CVE
CAN-2001-0328) which is present when using random increments to
constantly increase TCP ISN values over time. Because of the
implications of the Central Limit Theorem, adding a series of
numbers together provides insufficient variance in the range of
likely ISN values allowing an attacker to disrupt or hijack
existing TCP connections or spoof future connections against
vulnerable TCP/IP stack implementations. Systems relying on
random increments to make ISN numbers harder to guess are still
vulnerable to statistical attack.
In 1985, Bob Morris first identified potential security concerns
with the TCP protocol. One of his observations was that if a TCP
sequence number could be predicted, an attacker could "complete"
a TCP handshake with a victim server without ever receiving any
responses from the server. One result of the creation of such a
"phantom" connection would be to spoof a trusted host on a local
network.
In 1989, Steve Bellovin observed that the "Morris" attack could
be adapted to attack client connections by simulating unavailable
servers and proposed solutions for strengthening TCP ISN
generators. In 1995, the CERT Coordination Center issued
CA-1995-01, which first reported the widespread use of such
attacks on the Internet at large.
Later in 1995, as part of RFC1948, Bellovin noted:
The initial sequence numbers are intended to be more or less
random. More precisely, RFC 793 specifies that the 32-bit
counter be incremented by 1 in the low-order position about
every 4 microseconds. Instead, Berkeley-derived kernels
increment it by a constant every second, and by another
constant for each new connection. Thus, if you open a
connection to a machine, you know to a very high degree of
confidence what sequence number it will use for its next
connection. And therein lies the attack.
Also in 1995, work by Laurent Joncheray further describes how an
attacker could actively hijack a TCP connection. If the current
sequence number is known exactly and an attacker's TCP packet
sniffer and generator is located on the network path followed by
the connection, victim TCP connections could be redirected.
In his recently published paper on this issue, Tim Newsham of
Guardent, Inc. summarizes the more generalized attack as follows:
As a result, if a sequence number within the receive window is
known, an attacker can inject data into the session stream or
terminate the connection. If the ISN value is known and the
number of bytes sent already sent is known, an attacker can
send a simple packet to inject data or kill the session. If
these values are not known exactly, but an attacker can guess
a suitable range of values, he can send out a number of
packets with different sequence numbers in the range until one
is accepted. The attacker need not send a packet for every
sequence number, but can send packets with sequence numbers a
window-size apart. If the appropriate range of sequence
numbers is covered, one of these packets will be accepted.
The total number of packets that needs to be sent is then
given by the range to be covered divided by the fraction of
the window size that is used as an increment.
Many TCP/IP implementers turned to incrementing the global tcp_iss
Initial Send Sequence number, a.k.a., an ISN] variable using
pseudo-random variables instead of constants. Unfortunately, the
randomness of the pseudo-random-number generators (PRNGs) used to
generate the "random" increments was sometimes lacking. As noted
in RFC1750:
It is important to keep in mind that the requirement is for
data that an adversary has a very low probability of guessing
or determining. This will fail if pseudo-random data is used
which only meets traditional statistical tests for randomness
or which is based on limited range sources, such as clocks.
Frequently such random quantities are determinable by an
adversary searching through an embarrassingly small space of
possibilities.
Eastlake, Crocker, and Schiller were focused on randomness in
cryptographic systems, but their observation was equally
applicable in any system which relies on random number generation
for security. It has been noted in the past that using such poor
PRNGs can lead to smaller search spaces and make TCP ISN
generators susceptible to practical brute-force attacks.
However, new research demonstrates that the algorithm implemented
to generate ISN values in many TCP/IP stacks is statistically weak
and susceptible to attack even when the PRNG is adequately
randomizing its increments. The problem lies in the use of
increments themselves, random or otherwise, to advance an ISN
counter, making statistical guessing practical.
Tim Newsham of Guardent, Inc. has written a paper titled "The
Problem with Random Increments" concerning an observed statistical
weakness in initial sequence number generation for TCP
connections. Newsham explains how incrementing the ISN by a
series of pseudo-random amounts is insufficient to protect some
TCP implementations from a practical ISN guessing attack in some
real-world situations. Such attacks would not rely on data
sniffed from a victim site but only on one or two ISN samples
collected by previous connections made to a victim site.
Newsham's statistical analyses provide a theoretical backdrop for
practical attacks, drawing attention once again to the protocol
analysis documented by Steve Bellovin (building on work pioneered
by Robert Morris) in RFC1948.
Newsham points out that the current popular use of random
increments to obscure an ISN series still contains enough
statistical information to be useful to an attacker, making ISN
guessing practical enough to lead to TCP connection disruption or
manipulation. This attack is possible because an attacker can
still predict within "a suitable range of values" what the next
(or a previous) ISN for a given TCP connection may be. This
range can be derived when looking at the normal distribution that
naturally arises when adding a large number of values together
(random or otherwise) due to expected values governed by the
Central Limit Theorem:
Roughly, the central limit theorem states that the
distribution of the sum of a large number of independent,
identically distributed variables will be approximately
normal, regardless of the underlying distribution.
In addition to statistical analysis of this weakness, Newsham's
paper demonstrates the weakness inherent in one specific TCP/IP
implementation. In other recently-published research, Michal
Zalewski of BindView surveys over 20 different ISN generators
included in many of the most widely available operating systems
on the Internet today. Their work shows in graphic detail how
observable this statistical weakness is.
Analysts at BindView have produced interesting research that
analyzes the patterns many of the most popular TCP/IP stacks
produce when producing ISNs. In a paper titled "Strange
Attractors and TCP/IP Sequence Number Analysis," author Michal
Zalewski uses phase analysis to show patterns of correlation
within sets of 32-bit numbers generated by many popular operating
systems' TCP ISN generators. As Zalewski explains:
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 generators comparison , 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.
(A "spoofing set" is defined as "a set of guessed values for ISNs
that are used to construct a packet flood that is intended to
corrupt some established TCP connections." Please see the paper
for more information about phase space analysis and attractor
reconstruction).
In effect, using this technique for data visualization, they are
able to highlight emergent patterns of correlation. Such
correlation, when present in TCP ISN generators, can dramatically
shrink the set of numbers that need to be guessed in order to
attack a TCP session.
Since the sequence number for TCP sessions is stored in packet
headers using 32-bits of data, it was generally assumed that an
attacker would have a very small chance of correctly guessing a
sequence number to attack established (or to-be established)
connections. BindView's research shows attackers actually have
much smaller bit-spaces to guess within due to dependencies on
system clocks and other implementation defects.
Zalewski further notes in his paper:
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.
The work done by Guardent and BindView illustrates that not all
current TCP/IP ISN generators have implemented the suggestions
made by Steve Bellovin in RFC1948 to address prediction-based ISN
attacks, or provided a equivalent fixes. In particular, TCP/IP
stacks based on operating system software which has not previously
incorporated RFC1948 or equivalent fixes will be susceptible to
classic TCP hijacking in the absence of other cryptographically
secure hardening (i.e., when not using IPSec or an equivalent
secure networking technology). Much work remains to be done to
ensure the systems deployed using TCP today and tomorrow have
strengthened their ISN generators using RFC1948 recommendations
or equivalent fixes.
If the ISN of an existing or future TCP connection can be
determined within some practical range, a malicious agent may be
able to close or hijack the TCP connections. If the ISNs of
future connections of a system are guessed exactly, an agent may
be able to "complete" a TCP three-way handshake, establish a
phantom connection, and spoof TCP packets delivered to a victim.
SOLUTION
The design of TCP specified by Jon Postel in RFC793 specifically
addressed the possibility of old packets from prior instantiations
of a connection being accepted as valid during new instantiations
of the same connection, i.e., with the same 4-tuple of
<local host, local port, remote host, remote port>:
To avoid confusion we must prevent segments from one
incarnation of a connection from being used while the same
sequence numbers may still be present in the network from an
earlier incarnation. We want to assure this, even if a TCP
crashes and loses all knowledge of the sequence numbers it has
been using. When new connections are created, an initial
sequence number (ISN) generator is employed which selects a
new 32-bit ISN. The generator is bound to a (possibly
fictitious) 32-bit clock whose low order bit is incremented
roughly every 4 microseconds. Thus, the ISN cycles
approximately every 4.55 hours. Since we assume that segments
will stay in the network no more than the Maximum Segment
Lifetime (MSL) and that the MSL is less than 4.55 hours we can
reasonably assume that ISN's will be unique.
In the discussions following the initial report of this
statistical weakness, several approaches to solving this issue
were identified. All have various strengths and weaknesses
themselves. Many have been implemented independently by various
vendors in response to other reported weaknesses in specific ISN
generators.
TCP initial sequence numbers were not designed to provide proof
against TCP connection attacks. The lack of
cryptographically-strong security options for the TCP header
itself is a deficiency that technologies like IPSec try to
address. It must be noted that in the final analysis, if an
attacker has the ability to see unencrypted TCP traffic generated
from a site, that site is vulnerable to various TCP attacks - not
just those mentioned here. The only definitive proof against all
forms of TCP attack is end-to-end cryptographic solutions like
those outlined in various IPSec documents.
The key idea with an end-to-end cryptographic solution is that
there is some secure verification that a given packet belongs in
a particular stream. However, the communications layer at which
this cryptography is implemented will determine its effectiveness
in repelling ISN based attacks. Solutions that operate above the
Transport Layer (OSI Layer 4), such as SSL/TLS and SSH1/SSH2, only
prevent arbitrary packets from being inserted into a session.
They are unable to prevent a connection reset (denial of service)
since the connection handling will be done by a lower level
protocol (i.e., TCP). On the other hand, Network Layer (OSI
Layer 3) cryptographic solutions such as IPSec prevent both
arbitrary packets entering a transport-layer stream and connection
resets because connection management is directly integrated into
the secure Network Layer security model.
The solutions presented above have the desirable attribute of not
requiring any changes to the TCP protocol or implementations to be
made. Some sites may want to investigate hardening the TCP
transport layer itself though. RFC2385 ("Protection of BGP
Sessions via the TCP MD5 Signature Option") and other technologies
provide options for adding cryptographic protection within the TCP
header at the cost of some potential denial of service,
interoperability, and performance issues.
The use of cryptographically secure protocols has several
advantages over other possible solutions to this problem.
Protection against hijacking and disruption are provided by the
cryptography, while the TCP layer is free to return to a simple
increasing sequence number mechanism, providing the greatest
level of reliability. The performance, durability, and
practicality of implementation will vary according to the
protocol selected, but IPSec in particular appears to have a
number of positive attributes in this regard.
In RFC1948, Bellovin observed that if the 32-bit ISN space could
be segmented across all the ports available to a system,
collecting sample ISNs from one connection could yield little or
no information about the ISNs being generated in other
connections. Breaking the reliance on a global ISN pool by using
cryptographically hashed secrets and [IP, port] 4-tuples
effectivly eliminates TCP ISN attacks by remote users (unless, of
course, attackers able to sniff traffic on a local network
segment).
Newsham notes in his paper:
RFC 1948 proposes a method of TCP ISN generation that is not
vulnerable to ISN guessing attacks. The solution proposed
partitions the sequence space by connection identifiers. Each
connection identifier, which is composed of the local address
and port and the remote address and port of a connection, is
assigned its own unique sequence space starting at an offset
that is a function of the connection identifier. The function
is chosen in such a way that it cannot be computed by an
attacker. The ISN is then [...] generated by increments to
this offset. ISN values generated in this way are not
vulnerable to ISN range prediction methods outlined in this
paper since an attacker cannot gain knowledge of the ISN space
for any connection identifiers he cannot directly observe.
Once the global ISN space becomes segmented among all the TCP
ports available on a system, attacking TCP ISNs remotely becomes
impractical. However, it should be noted that even when using
RFC1948 implementations, some forms of ISN attack remain viable
under very specific conditions, as discussed in further detail
below.
In addition, using a cryptographically strong hash function to
perform this segmentation may lead to longer TCP connection
establishment time. Some implementors (like those of the Linux
kernel) have chosen to use a reduced-round MD4 hash function to
provide a "good enough" solution from a security standpoint to
keep performance degradation to a minimum. One cost of weakening
the hash algorithm is the need to re-key the generator every few
minutes. Each time a re-keying occurs, security is strengthened,
but other reliability issues identified in RFC793 become a
concern.
It had been understood (but not widely noted) that ISNs generated
by a "strictly-compliant" RFC1948 generator would still allow ISN
guessing attacks to be made against previously-owned IP addresses.
If an attacker could "own" an IP address used by a potential
victim at some point afterward, given enough sample ISNs collected
within the shared [IP, port] 4-tuple ISN space, an attacker could
make reasonable guesses about the ISNs of subsequent connections.
This is because strict RFC1948 suggests the following algorithm:
ISN = M + F(sip, sport, dip, dport, <some secret>)
where
ISN = 32-bit initial sequence number
M = monotonically increasing clock/counter
F = crypto hash (typically MD4 or MD5)
sip = source IP
sport = source port
dip = destination IP
dport = destination port
<some secret> = an optional fifth input into the hash function
to make remote IP attacks unfeasible.
For the ISN itself to monotonically (constantly) increase, F()
needs to remain fairly static. So the <some secret> envisioned
by Bellovin was a system-specific value (such as boot time, a
passphrase, initial random value, etc) which would infrequently
change. Each time it changes, the value of F() (a hash) changes
and there is no guarantee that subsequent ISNs will be
sufficiently distanced from the previous value assigned, raising
the potential RFC793 reliability concern again.
When viewed from the perspective of a particular [IP, port]
4-tuple, the ISN sequence is predictable and therefore subject to
practical attacks. When looking at the Solaris tcp_strong_iss
generator (RFC1948) from the perspective of a remote IP attacker,
for example, the ISNs generated appear random. However, the
Zalewski paper analyzes data which looks at both the remote and
same-IP address attack vectors. Their data confirms the same-IP
attack vector against Solaris tcp_strong_iss=2 (RFC1948) is a
practical attack.
The Linux TCP implementors avoided this issue by rekeying <some
secret> every five minutes. Unfortunately, this breaks the
monotonicity of the algorithm, weakening the iron-clad reliability
guarantee that Bellovin was hoping to preserve by segmenting the
ISN space among ports in the first place.
Some have proposed that the following algorithm may be a better
answer to this issue:
M = M + R(t)
ISN = M + F(sip, sport, dip, dport, <some secret> )
where
R(t) = some random value changing over time
This is essentially adding a random increment to the RFC1948
result. This makes most attacks impractical, but still
theoretically possible. (It would still be "RFC1948-compliant" as
well ... RFC1948 makes as few assumptions about the F()
incrementing function as possible, requiring only that the
connection [IP, port] 4-tuple be inputs to the function and that
it be practically irreversible.) However, the "problem" of random
increments was what brought this issue back into the spotlight to
begin with.
A more direct solution chosen by some TCP implementors is to
simply feed random numbers directly into the ISN generator itself.
That is, given a 32-bit space to choose from, assign:
ISN = R(t)
Solutions which essentially randomize the ISN seem to mitigate
against the practical guessing attack once and for all (assuming
strong pseudo-random number generation). However, a purely-random
approach allows for overlapping sequence numbers among
subsequently-generated TCP connnections sharing [IP, port]
4-tuples. For example, a random generator can produce the same
ISN value three times in a row. This runs contrary to multiple
RFC assumptions about monotonically increasing ISNs (RFC 793, RFC
1185, RFC 1323, RFC1948, possibly others as well). It is unclear
what practical effect this will have on the long-term reliability
guarantees the TCP protocol makes or is assumed to make.
Another novel approach introduced by Niels Provos of the OpenBSD
group tries to strike a balance between the fully-random and
segmented (RFC1948) approaches:
ISN = ((PRNG(t)) << 16) + R(t)
where
PRNG(t) = a pseudo-randomly ordered list of sequentially-generated 16-bit numbers
R(t) = a 16-bit random number generator with its msb always set to zero
This formula is an approximation of the results the OpenBSD
implementation actually generates. Please see their actual code
at:
http://www.openbsd.org/cgi-bin/cvsweb/src/sys/netinet/tcp_subr.c
What the Provos implementation effectively does is generate a
psuedo-random sequence that will not generate duplicate ISN values
within a given time period. Additionally, each ISN value
generated is guaranteed to be at least 32K away from other ISN
values. This avoids the purely-random ISN collision problem, as
well as makes a stronger attempt to keep sequence number spaces
of subsequent [IP, port] 4-tuple connections from overlapping. It
also avoids the use of a cryptographic hash which could degrade
performance. However, monotonicity is lost, potentially causing
reliability problems, and the generator may leak information about
the system's global ISN state.
Further discussion and analysis on the importance of such
attributes needs to occur in order to ascertain the
characteristics present in each ISN generator implemented.
Empirical evidence provided by BindView may indicate that from a
predictability standpoint, the solutions are roughly equivalent
when viewed from a remote attackers perspective. It is unclear
at the time of this writing what the security, performance, and
reliability tradeoffs truly are.
Cisco Systems
=============
Cisco systems now use a completely random ISN generator. Please
see the following for more details:
http://www.cisco.com/warp/public/707/ios-tcp-isn-random-pub.shtml
Compaq Computer Corporation
===========================
At the time this document was written, Compaq is investigating the
potential impact to Compaq's Tru64 UNIX and OPENVMS operating
systems. Compaq views the problem to be a concern of moderate
severity. Compaq implementations of TCP/IP sequence randomization
for Tru64 UNIX for Alpha and OpenVMS for Alpha follow current
practices for implementation of TCP/IP initial sequence numbers.
FreeBSD
=======
FreeBSD has adopted the code and algorithm used by OpenBSD
2.8-current in FreeBSD 4.3-RELEASE and later, and this release is
therefore believed not to be vulnerable to the problems described
in this advisory (for patches and information relating to older
releases see FreeBSD Security Advisory 01:39). They intend to
develop code in the near future implementing RFC 1948 to provide
a more complete solution.
Fujitsu
=======
Fujitsu is currently working on the patches for the UXP/V OS to
address the vulnerabilities reported in VU#498440. The patches
will be made available with the following ID numbers:
OS Version,PTF level patch ID
-------------------- --------
UXP/V V20L10 X01021 UX28164
UXP/V V20L10 X00091 UX28163
UXP/V V10L20 X01041 UX15529
Hewlett-Packard Company
=======================
HP has been tracking tcp randomization issues over the years, and
has to date implemented the following.
For 11.00 and 11.11 (11i):
--------------------------
For 11.00, if you want HP's solution for randomized ISN numbers
then apply TRANSPORT patch PHNE_22397. Once you apply
PHNE_22397, there's nothing more to do --- default is randomized
ISNs. (Note: PHNE_22397 has patch dependencies unrelated to ISN
randomized ISN number modification listed in the dependency
section, but they should still be also applied. One is a PHKL
kernel patch dependency and the other STREAMS/UX minimum level
patch dependency.) The LR release of 11.11 (11i) has the same
random ISN implementation as the patched 11.00.
For releases up to, but not including 10.30:
--------------------------------------------
HP has key parameters that were made tunable to be able to
select two levels of levels of randomization with patch
PHNE_5361, a TRANSPORT Megapatch, which applies to releases up
to (but not including) 10.30. Check patch text for details. It
is done with nettune, and requires a reboot:
tcp_random_seq set to 0 (Standard TCP sequencing)
tcp_random_seq set to 1 (Random TCP sequencing)
tcp_random_seq set to 2 (Increased Random TCP sequencing)
IBM
===
IBM's AIX operating system should not be vulnerable as they have
implemented RFC 1948 in our source coding. According to Guardent,
IBM do not expect an exploit described in the document to affect
their AIX OS because we employ RFC 1948.
Linux
=====
The Linux kernel has used a variant of RFC1948 by default since
1996. Please see:
http://lxr.linux.no/source/drivers/char/ChangeLog#L258
http://lxr.linux.no/source/drivers/char/random.c#L1855
OpenBSD
=======
post-2.8 we no longer use random increments, but a much more
sophisticated way.
SGI
===
SGI implemented RFC 1948 with MD5 on IRIX 6.5.3 and above using
the tcpiss_md5 tunable kernel parameter, but the default is
disabled. To enablee tcpiss_md5 kernel parameter, use the
following command as root:
# /usr/sbin/systune -b tcpiss_md5 1
To verify RFC 1948 has been enabled in IRIX, use the following
command as root:
# /usr/sbin/systune tcpiss_md5
This should return:
tcpiss_md5 = 1 (0x1)
Sun Microsystems
================
Sun implemented RFC 1948 beginning with Solaris 2.6, but it isn't
turned on by default. On Solaris 2.6, 7 and 8, edit
/etc/default/inetinit to set TCP_STRONG_ISS to 2.
On a running system, use:
ndd -set /dev/tcp tcp_strong_iss 2