Firewall Discovery and Network Research with the Nmap Qscan by Doug Hoyte and HCSW Labs R&D partially funded by a Google Summer of Code 2006 grant Some test equipment and servers are property of Zerosum Holding Corporation Nmap [4] is already the standard tool in mapping firewall configurations. The ACK/Window scans, -f for IP fragmentation, FTP/Proxy scanning, Ed3f's --bad-checksum option, -g for custom source port values - all contribute in making Nmap the most comprehensive firewall discovery and mapping tool in existance. Last year at a conference I attended, CanSecWest [6], I rubbed shoulders with numerous security professionals and had several discussions involving mapping firewall configurations. I remember talk about two valuable types of firewall mapping tests that neither Nmap nor any other tool was completely able to perform. 1) Firewall Time To Live (TTL) discrepancies. The standard traceroute concept. Note that since TTL is an IP layer attribute this test can be applied to any Internet Protocol: TCP, UDP, ICMP, IGMP, what have you. In theory, firewalls that decrement the TTL field of the IP header when forwarding a packet are easy to detect. If, with a certain packet format, a target is tracerouted to be n hops away but n-1 hops away by a different one, then we can infer the n-1th hop is applying some sort of packet filter. Although this technique is well understood, the tools to perform and analyse these metrics are somewhat lacking. There's Mike Schiffman's venerable firewalk program [2], but it lacks query and rDNS parallelisation making it too slow to be practical in many cases. There's custom hping, (my as yet unreleased) nuff, scapy, etc scripts/commands but these often lack the standardisation, convenience, and reliable interpretation of results that Nmap is famous for. One of the items on the Summer Of Code (SoC) agenda is to design and code a traceroute mapping utility of exactly this sort. SoC participant Eddie Bell has been working hard to bring you this mapping functionality in the near future and, perhaps by the time you've read this, will already be available as a patch for Nmap. The biggest downside to this sort of measurement is that it is easy to set up packet filters that don't decrement the TTL value of packets. 2) Round-Trip Time (RTT) discrepancies. Transmitting packets over the network takes time. No matter how you structure your networks, network latency is a factor. Transmitting a packet over ethernet, ISDN, wifi, pigeon, etc, inevitably results in a statistically detectable packet transmission delay. In theory, if packets of a certain format are replied to after t, say, milliseconds, and packets of a different format are replied to in t+delta milliseconds, we can infer the existance of some sort of filtering or forwarding delay of delta milliseconds. On that note, we are pleased to introduce... The Nmap Qscan ~~~~~~~~~~~~~~ We have designed a new Nmap scan type, tentatively named Qscan, which tries to measure these differences within a consistent statistical context. Although Qscan makes use of Nmap's powerful port and host specification features, it isn't like other Nmap scans - It doesn't try to determine the states of ports. Instead, Qscan provides a method for carefuly measuring packet round-trip times and applying powerful statistics to the results. Qscan endeavours to provide a way of sending probes, measuring their responses, and interpreting the inevitable delay between network hops. To make this as useful as possible, we have decided to embed Qscan into Nmap in order to make use of Nmap's extensive packet creation/transmission/capture functionality and to allow the user to specify hosts/ports in the convenient, familiar Nmap command line style (and, perhaps eventually, through sophisticated Nmap GUIs like UMIT). So how, exactly, does Qscan work? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ Qscan depends on a very simple model of network behaviour: o Due to queuing delays and inherent network latency, packet round trip times are assumed to conform to a truncated normal distribution. See [2] for empirical evidence as well as an explanation involving the application of the Central Limit Theorum to packet arrival times. o A target TCP is assumed to respond to SYN packet requests as soon as it can and no sooner. In other words, nobody is trying to trick us by maliciously delaying packets or replying to packets they haven't yet received. Our algorithm is simple: We cycle through the list of specified port/host combinations sequentially. For instance, if a user specifies: nmap -sQ -p 22,80 192.168.0.1 192.168.0.2 We will alternate transmission between the following 4 packet host/port designations (we'll just call them "targets" from now on): 192.168.0.1:22 192.168.0.1:80 192.168.0.2:22 192.168.0.2:80 Qscan waits a random interval between each transmission in order to avoid the periodic, self-similar round-trip time delay biases described in [2]. The user of Qscan is able to customise the average delay. With an average delay set to N milliseconds, Qscan will select delays from the uniformly distributed range of 0.5N to 1.5N. Qscan listens for replies to queries it sent and measures, to the best of its ability, the exact round-trip time for each target. The first round of transmissions are not included in the statistics to avoid initial NAT and routing table lookup delays. Qscan works against ports that are open and ports that are closed. In the case of filtered ports, since we don't necessarily get a response back from the target TCP, Qscan does not work. If you scan filtered ports Qscan will display a packet loss of %100 and will be unable to classify the port. Once Qscan has collected a certain number of round-trip time measurements (another user customisable parameter) for each target, it finishes and attempts to statistically analyse the data. Qscan uses a dual-tailed, independent-group Student's t-test to estimate the probability that 2 sequences of packets with different measured means and standard deviations are, in fact, different. Wikipedia has a lengthy treatment of the subject [3]: "In probability and statistics, the t-distribution or Student's t-distribution is a probability distribution that arises in the problem of estimating the mean of a normally distributed population when the sample size is small. It is the basis of the popular Student's t-tests for the statistical significance of the difference between two sample means, and for confidence intervals for the difference between two population means." By comparing our samples (the measured RTTs for each packet host/port combination) using the t-test we can estimate the liklihood that there is an actual difference in packet traversal times rather than simple random fluctuations. Yet another Qscan parameter indicates the confidence level we require in order to state that, yes, there was a statistically signifigant difference between these 2 packet delivery times. This parameter is called the confidence level and, by default, is set to 0.95, representing a confidence level of 95%. When reporting the results, Qscan uses the t-test to try grouping targets together into "families". Each family is considered to, statistically, have the same round-trip response time. The Qscan Options ~~~~~~~~~~~~~~~~~ --qscan-delay Specifies the average delay between packets sent. Qscan waits between 0.5N and 1.5N between transmissions. Defaults to 200. --qscan-numtrips Specifies the minimum number of round trips for Qscan to record before terminating. Defaults to 10. --qscan-confidence Specifies the "confidence" parameter to the Qscan. Must be a value on the range 0.0 < N < 1.0. The higher the value the more obvious the differences in round trip times will have to be for Qscan to differentiate ports into different families. Currently the only confidence levels supported are 0.75, 0.9, 0.95, 0.975, 0.99, 0.995, and 0.9995 though we might support more values in the future through interpolation. Defaults to 0.95. OK, enough theory, how do I use it? ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (These examples have been partially edited for clarity and brevity) Example #1) Let's try measuring the round trip times to 2 ports on my wireless router. Port 80 is open and port 23 is closed. # ./nmap -sQ -p 23,80 192.168.0.1 Starting Nmap ( http://www.insecure.org/nmap/ ) Qscan parameters: round trips: 10, avg delay = 200ms, confidence = 0.95 Target:Port Fam uRTT +/- Stddev Loss% 192.168.0.1:23 A 3.1 +/- 0.2 0 192.168.0.1:80 A 3.2 +/- 0.1 0 Nmap finished: 1 IP address (1 host up) scanned in 9.905 seconds It isn't too suprising that these 2 ports seem to have the same round-trip times. After all, they're handled by the same piece of hardware on the same interface. Notice how they've both been grouped into the family 'A'. Example #2) In the event that you scan a port that is filtered, Qscan should handle it gracefuly. In this case, my DSL's outbound port 25 is filtered: # ./nmap -sQ -p 23,25,80 hcsw.org Starting Nmap ( http://www.insecure.org/nmap/ ) Qscan parameters: round trips: 10, avg delay = 200ms, confidence = 0.95 Target:Port Fam uRTT +/- Stddev Loss% 65.98.116.106:23 A 79.6 +/- 0.7 0 65.98.116.106:25 ? N/A +/- N/A 100 65.98.116.106:80 A 84.8 +/- 12.7 0 Nmap finished: 1 IP address (1 host up) scanned in 14.594 seconds Example #3) OK, that's all fun and interesting, but I thought we could use Qscan to detect firewalls?! We can! I've set up a router with the IP address 192.168.1.254 to forward packets on port 8080 to an internal machine, but the router handles packets on other ports itself. Here's the resulting Qscan: # ./nmap -sQ -p 23,25,80,8080,9876 192.168.1.254 Starting Nmap ( http://www.insecure.org/nmap/ ) Qscan parameters: round trips: 10, avg delay = 200ms, confidence = 0.95 Target:Port Fam uRTT +/- Stddev Loss% 192.168.1.254:23 A 3.1 +/- 0.1 0 192.168.1.254:25 A 3.1 +/- 0.2 0 192.168.1.254:80 A 3.2 +/- 0.1 0 192.168.1.254:8080 B 4.6 +/- 0.3 0 192.168.1.254:9876 A 3.1 +/- 0.2 0 Nmap finished: 1 IP address (1 host up) scanned in 22.886 seconds Qscan easily discovers this and, appropriatley, groups them into separate families - 'A' representing the ports handled by the router (firewalled) and 'B' the ports passed through to the internal machine. Of course this is on a low-latency, low-variance local network which makes it easy to measure these differences even with few packets over a short period of time. If you are trying to discover this information over a high variance network like the general internet, it is likely that the Qscan parameters will need to be tuned. With enough data, verified enough times from enough network locations, it should be possible to discover almost any round-trip time discrepancies. Example #4) Qscan has already helped me discover tidbits of network connectivity information that I previously wasn't aware of. You might know that, when searching for filtered/firewalled ports, 113 (auth/ident) is often a good target. Administrators are generally aware of the privacy and performance problems associated with this port and filter it heavily. # ./nmap -sQ -p 25,113 smtp1.google.com Starting Nmap ( http://www.insecure.org/nmap/ ) Qscan parameters: round trips: 10, avg delay = 200ms, confidence = 0.95 Target:Port Fam uRTT +/- Stddev Loss% 216.239.57.25:25 A 76.6 +/- 5.3 0 216.239.57.25:113 B 2.4 +/- 1.9 0 Nmap finished: 1 IP address (1 host up) scanned in 12.097 seconds Hold on there! Look at how low the port 113 round-trip times are! After investigating it we discovered that, on this server, our upstream provider responds to connection initiations with resets, presumably to speed up protocols that hang while waiting for responses on this port. (I personally think it's to annoy people running IRC daemons, but nevermind). Example #5) There really are many possible uses for Qscan! Consider search engine selection. # ./nmap -P0 -sQ -p 80 google.com yahoo.com live.com ask.com Starting Nmap ( http://www.insecure.org/nmap/ ) Warning: Hostname google.com resolves to 3 IPs. Using 64.233.187.99. Warning: Hostname yahoo.com resolves to 2 IPs. Using 66.94.234.13. Qscan parameters: round trips: 10, avg delay = 200ms, confidence = 0.95 Target:Port Fam uRTT +/- Stddev Loss% 64.233.187.99:80 A 23.2 +/- 6.3 0 66.94.234.13:80 B 77.3 +/- 10.2 0 207.68.172.235:80 C 94.8 +/- 14.2 0 65.214.39.56:80 D 7.4 +/- 0.2 0 Nmap finished: 4 IP addresses (4 hosts up) scanned in 17.574 seconds Looks like from this particular network location I get the best response time from ask.com! If I was writing a script that performed web searches (and ask.com's quality was sufficiently close to google's) I might consider using ask.com for the fastest possible results. Notes ~~~~~ o There are many different factors that can influence the results reported by Qscan. If the routes that packets follow are changed during the Qscan, or the targets are handled by IP-based load balancers, or the network connection is especially unreliable, the results will obviously be skewed. You are encouraged to experiment with and verify any results reported by Qscan. Keep in mind that, unlike other Nmap scans that determine the states of ports, Qscan is a statistical tool and a certain margin of error must be expected and accounted for. o Remember that the congestion caused by the packets sent by Qscan and the replies from the target and the subsequent RSTs sent by your operating system (in the case of open ports) can themselves cause a fair amount of network congestion and actually impact the results of your scan! If this is a concern, using a larger --qscan-delay can offset this. o Using an extremely low --qscan-delay can be dangerous! It is possible for Qscan to timeout a probe and send a new probe from the same source port. If the response to the original probe arrives subsequently, incorrect round trip times can be recorded. Qscan is usually smart enough to determine when this is a possibilty and will warn you. This should be almost impossible with reasonable --qscan-delay values. o As a side-effect of the underlying design, Qscan can also serve as a powerful SYN flood attack tool. By spoofing a fake (unresponsive) IP address with the Nmap -S option so your OS doesn't reply with RST packets to the victim's SYN|ACK packets and finding a --qscan-delay with a reasonably low packet loss, a very efficient SYN flood attack can be performed. This is, of course, not recommended except for experimentation and research purposes. See [5] for an overview of SYN flooding attacks. Future Work ~~~~~~~~~~~ o The algorithm could possibly be improved. Some sort of median filter would be helpful in throwing out packets that are obviously outliers and not representative of the packet delays. o A variable rate Qscan could potentially be helpful but invites a new set of problems that would have to be dealth with. o It could be useful to allow people to Qscan with different types of probe packets. ACK or SYN|ACK packets instead of SYN packets would be obviously useful. Also, UDP and ICMP probes are possible. o Testing and tuning! The default parameters are mostly just arbitrary values we picked (except for a confidence level of 0.95 which is the gold standard in statistics). Experimentation and real-world usage might discover better values to use. o Right now Qscan assumes all targets are reachable through the same network interface. This is an unnecessary restriction and should be eliminated. References: [1] Firewalk software distribution (1998-) Mike D. Schiffman, David Goldsmith http://www.packetfactory.net/projects/firewalk/ [2] On the Distribution of Round-trip Delays in TCP/IP Networks (1999) Tamas Elteto, Sandor Molnar http://citeseer.ist.psu.edu/elteto99distribution.html [3] Wikipedia's "Student's t-distribution" article http://en.wikipedia.org/wiki/Student's_t-distribution [4] Nmap software distribution (1997-) Fyodor, Insecure.Com LLC, et al [5] Wikipedia's "SYN Flood" article http://en.wikipedia.org/wiki/SYN_flood [6] CanSecWest Security Conference, Vancouver (2006) http://www.cansecwest.com