Strange Attractors and TCP/IP Sequence Number Analysis - One Year Later
Author: Michal Zalewski <lcamtuf@coredump.cx>
...thanks to the RAZOR team.


Table of Contents:

1. Introduction
1.1 Current risks of TCP/IP spoofing
2. New evidence
    3.1 Windows
    3.2 IRIX
    3.3 Netware
    3.4 Cisco IOS
    3.5 Solaris
    3.6 *BSD family
    3.7 MacOS X
    3.8 UNICOS
    3.9 Tru64
    3.10 HPUX
    3.11 OS/400
    3.12 NextSTEP
    3.13 AIX
    3.14 OpenVMS
    3.15 OS9
4. Conclusions
5. Credits


1. Introduction

Over a year ago, I published a whitepaper titled "Strange Attractors and TCP/IP Sequence Number Analysis" - an attempt to evaluate TCP/IP sequence number generators in several mainstream operating systems by mapping the dynamics of the generated sequence numbers into a three-dimensional phase space. We demonstrated how this approach can be used to find many non-trivial correlations, and discussed why the results can be directly used to perform actual ISN prediction. This research, along with the research from Guardent, resulted in the release of CERT Advisory CA-2001-09 and several vendor bulletins.

The goal of this follow-up is to evaluate any subsequent security measures implemented by the vendors in this field since the release of the original publication, and to evalute several systems that were not covered earlier. For the purpose of this document, we assume that the reader has read the original publication, and has an understanding of the methodology and terminology used.

Please note that the 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.

IMPORTANT UPDATE: Please read this notice about the bundled sequence analysis tool.

2. Current risks of TCP/IP spoofing

While the situation has greatly improved since the days when Kevin Mitnick used a TCP/IP spoofing attack to break into Tsutomu Shimomura's machine, and while the r* protocols or telnet logins over public networks are almost completely extinct, the importance of providing good, unpredictable TCP ISN numbers is downplayed by many. The majority of the Internet traffic is still unencrypted, and much of this data can be considered high-profile, even if it does not directly contain sensitive information as such. Here are several most obvious attack vectors:

3. New evidence

In this section, we review a number of operating systems that were either identified as not satisfactory in the original publication, or were not covered by our research at the time. Several systems, such as Linux, use the same, satisfactory ISN generator as the one used a year ago, and because of that, are not covered here in any more detail.

3.1 Windows

In the original publication, we reviewed the ISN generator in Windows 2000 and NT4 SP6a, and found it hardly sufficient for the current needs, considering the bandwith available to a typical attacker and other important factors. Quoting the original document:

"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."

One year later, we find that both Windows 2000 SP2 and Windows XP still use essentially the same ISN generator:

[ Windows XP ]

OS Name: Windows XP
R1 radius: 10
Average R2: 251
Average N: 179
Average error: 279
Attack feasibility: 12.00%

This ISN generator does not provide a sufficient protection against targeted high-profile attacks. The code does not seem to use RFC1948 to minimize the potential impact. RFC1948, proposed by Steve M. Bellovin, is an attempt to differentiate ISNs used for each host. This is done using one-way MD5 shortcuts in a way that reduces the impact of non-random sequence numbers to only one source-destination IP pair.

3.2 IRIX

IRIX 6.5.15 provides two settings, tcpiss_md5 set to zero - insecure mode - and tcpiss_md5, a secure mode that is supposed to implement strong randomness. With this setting set to zero, results are extremely trivial to crack:

[ IRIX tcpiss_md5=0 ]

OS Name: IRIX 6.5.15 tcpiss_md5=0
R1 radius: 0
Average R2: 93
Average N: 297
Average error: 0
Attack feasibility: 100.00%

Unfortunately, tcpiss_md5 setting does not seem to provide much security either. It does not properly implement RFC1948, and sequence numbers for different hosts are roughly the same. Data collected by one host can be used to attack another. The attack feasibility is reasonable, with 25% success ratio in our 5,000 element test.

[ IRIX tcpiss_md5=1 ]

OS Name: IRIX 6.5.15 tcpiss_md5=1
R1 radius: 0
Average R2: 869
Average N: 43
Average error: 556
Attack feasibility: 25.00%

The attractor above is essentially a different view of the one we published in the original paper. This is interesting in the light of a premilinary statement from SGI that this feature does prevent the attack described by CERT. The name of this setting seems to suggest that MD5 is used in the implementation, but the output does not indicate that any significant portion of MD5-hashed data is used.

We contacted SGI about this problem. SGI users should expect a patch and an official advisory coming soon.

3.3 Netware

[ Netware 6 ]

OS Name: Netware 6
R1 radius: 10
Average R2: 2484
Average N: 11
Average error: 0
Attack feasibility: 90.00%

At first sight, Netware 5 and 6 appeared reasonably robust, providing approximately 24 bits of randomness. This result was confirmed by a trivial nmap test:

TCP Sequence Prediction: Class=random positive increments
                         Difficulty=4636703 (Good luck!)

But when we took a closer look at the picture, we noticed that almost all points are excessively saturated, and that the coverage of the 24 bit space is, in fact, very poor. Further tests confirmed that, while Netware uses "random" deltas to generate subsequent ISNs, it appears that the random number generator is badly broken in that it constantly returns a small subset of randomly looking increments / decrements in a short cycle. Our tool was able to make correct guesses in 90% of the cases. Further analysis showed that Netware does not implement RFC1948 to minimize the impact of this issue.

After being contacted in the course of writing this paper, the Netware developers contacted us promptly, providing us with a sample of the new ISN generator that is supposed to solve the issue:

[ new Netware ]

OS Name: Netware 6 (SP3)
R1 radius: 100000
Average R2: 999
Average N: 34
Average error: n/a
Attack feasibility: 0.00%

The attractor does look very interesting, suggesting that some randomness was added to less random output, perhaps the old generator, still leaving some gaps in the space, but the amount of this randomness is sufficient to make the attack not feasible, with approximately 30 bits of randomness present. UPDATE (10/20/2002): This fix is now available from Novell here.

Please note that use of the "packet signature" feature in Netware can minimize the exposure with previous versions. For more details, please refer to this or this URL at novell.com.

3.4 Cisco IOS

We tested the Cisco IOS 3640 running IOS 12.2.10a. It appears that the fix implemented by Cisco performs well, delivering a 32-bit randomness. Our approach did not deliver meaningful results, and the implementation scored very well:

[ IOS 12.2.10a ]

OS Name: IOS 12.2.10a
R1 radius: 100000
Average R2: 1487
Average N: 25
Average error: n/a
Attack feasibility: 0.00%

3.5 Solaris

Our initial analysis seems to indicate that Solaris 9 is using essentially the same level of TCP ISN protection as Solaris 8 - with the first setting, tcp_strong_iss set to 0, providing no randomness at all (feasibility: 100%), the default setting of 2 providing some medium protection (feasibility: 3%), and tcp_strong_iss set to 2 implementing RFC1948. Further investigation is necessary for tcp_strong_iss=2, a setting that had a slight but possibly fatal flaw caused by having a static secret used in its RFC1948 implementation to determine whether this issue is still present. Please refer to the original publication for more details about the issue.

We were unable to obtain Solaris 9 samples gathered from a Linux box that was used to generate the original evaluation. The importance of using the same test system is that different systems use a different range and ordering of source ports for outgoing connections, and that will affect the particular flaw discussed originally. We were able to get results obtain results gathered from another Solaris system that may indicate the issue was at least partly addressed by Sun:

[ Solaris ISS=2 ]

OS Name: Solaris 9 (tcp_strong_iss=2)
R1 radius: 1000000
Average R2: 118
Average N: 260
Average error: 120
Attack feasibility: 0.02%

3.6 *BSD family

[ FreeBSD 4.6 ]

OS Name: FreeBSD 4.6
R1 radius: 1000000
Average R2: 101
Average N: 279
Average error: n/a
Attack feasibility: 0.00%

The code that is now being used in FreeBSD and other *BSD systems (except for BSDI, which we hadn't have a chance to test here) seems to be very good, providing a clean, 32-bit randomness. As Mike Silbersack pointed out, the code is not exactly the same, but all implementations generate comparable results.

3.7 MacOS X

MacOS X scored rather poorly in the original test, but its PRNG has been significantly improved since then. Current results show an uniform, random 31-bit cloud:

[ MacOS ]

OS Name: MacOS X
R1 radius: 1000000
Average R2: 118
Average N: 239
Average error: n/a
Attack feasibility: 0.00%

3.8 UNICOS

The following results are from UNICOS 10.0.0.8 running on Cray SV1:

[ UNICOS 10.0.0.8 ]

OS Name: UNICOS 10.0.0.8
R1 radius: 10
Average R2: 948
Average N: 47
Average error: 390
Attack feasibility: 9.00%

This is a very interesting case that gives attack feasibility around 10% in our test. The UNICOS PRNG implementation is rather poor, but the attractor shows a complex nature in this algorithm. It is probably a very good candidate for further investigation, and perhaps some analysis in more than three dimensions, which we leave as an exercise to more curious readers.

3.9 Tru64

The following results are from Tru64 5.1A:

[ Tru64 5.1 A ]

OS Name: Tru64 5.1A
R1 radius: 0
Average R2: 742
Average N: 694
Average error: 405
Attack feasibility: 100.00%

This is a very trivial attractor. A close-up of the attractor reveals that every single point on this picture is actually a very small cloud:

[ Tru64 5.1 A (zoom) ]

OS Name: Tru64 5.1A
R1 radius: 0
Average R2: 742
Average N: 694
Average error: 405
Attack feasibility: 100.00%

This indicates there is some randomness - but the amount is so insignificant, the results are 100% predictable in 5,000 attempts.

3.10 HPUX

HPUX11 scored poorly in our original test. A patch was released (PHNE_26771) that is supposed to fix weak ISN problems and implement RFC1948. The functionality is not enabled by default, and the resulting sequence numbers are of mediocre quality:

[ HPUX11 ]

OS Name: HPUX 11
R1 radius: 10
Average R2: 382
Average N: 113
Average error: 121
Attack feasibility: 2.00%

Once turned on, the generator implemented in PHNE_26771 yields the following results:

[ HPUX11 pass ]

OS Name: HPUX 11 (passphrase set)
R1 radius: 100000
Average R2: 388
Average N: 145
Average error: 416
Attack feasibility: 3.00%

This seems to suffer from the same problem that was present in the Sun's implementation of RFC1948 in Solaris 8. It appears that results for a given IP are highly predictable over a longer period of time, making many IP reuse attack scenarios feasible. On the other hand, such attacks are much more difficult to perform and limited to some specific environments, so this is not a critical issue.

3.11 OS/400

OS/400 yielded very surprising results. For several minutes, it returned a numbers that while were not completely random, seemed to display a non-trivial dependency. The "randomness" wasn't really unpredictable, in that the PRNG seemed to generate same values over and over again, generating a highly saturated attractor points and resulting in 100% attack feasibility:

[ OS/400 ]

OS Name: OS/400
R1 radius: 0
Average R2: 2499
Average N: 14
Average error: 0
Attack feasibility: 100.00%

What was more surprising is that, after a while, apparently as a result of receiving many subsequent connection attempts (approximately 20000), the numbers have completely changed. OS/400 started to return a very long sequences of exactly the same, low ISN number (113464), that, after some time, eventually increased by one to start another long sequence of exactly the same nature. This was still an issue long hours after finishing the test, and wasn't specific to a single source IP address. It appears that OS/400 stack is broken, and can be rendered more vulnerable to trivial attacks by a short SYN flood.

3.12 NextSTEP

NextSTEP uses trivially predictable sequence numbers:

[ NextSTEP ]

OS Name: NextSTEP
R1 radius: 0
Average R2: 833
Average N: 33
Average error: 0
Attack feasibility: 100.00%

3.13 AIX

AIX 5.1 does not seem to deliver satisfactory results:

[ AIX ]

OS Name: AIX 5.1
R1 radius: 0
Average R2: 1999
Average N: 15
Average error: 0
Attack feasibility: 100.00%

3.14 OpenVMS

The following results come from OpenVMS V7.2 running on VAXstation 4000-60, with Compaq TCP/IP Services for OpenVMS VAX Version V5.1 (the default TCP/IP stack). A clear and strong attractor is visible, and overall ISN quality is low:

[ OpenVMS ]

OS Name: OpenVMS V7.2
R1 radius: 10000
Average R2: 503
Average N: 2231
Average error: 0
Attack feasibility: 15.00%

3.13 OS9

The following data comes from OS9 v2.3 - the results are trivially predictable:

[ OS9 ]

OS Name: OS 9
R1 radius: 0
Average R2: 791
Average N: 37
Average error: 0
Attack feasibility: 100.00%

4. Conclusions

The general conclusion is that while some vendors like Cisco reacted promptly and tested their solutions properly, many still either ignored the issue and never evaluated their implementations, or implemented a flawed solution that apparently was not tested using a known approach.

Please keep in mind that our results are preliminary, and that you should exercise caution when interpreting them. Always consult with your vendor to confirm any findings.

5. Credits

This publication was made possible by the good will and generous data contributions from the following people:

Mariusz Woloszyn
Jogchem de Groot
Antoni Sawicki
OUAH

In addition, several people have reviewed this document and helped resolve, verify or correct the findings discussed above. Special thanks go to Mark Loveless and Dave Mann for looking over this document.


- by lcamtuf@bos.bindview.com, best viewed with html browser -
, you are a visitior number , webpage hit counter: .