---[ Phrack Magazine Volume 8, Issue 53 July 8, 1998, article 13 of 15 -------------------------[ Designing and Attacking Port Scan Detection Tools --------[ solar designer ----[ Introduction The purpose of this article is to show potential problems with intrusion detection systems (IDS), concentrating on one simple attack: port scans. This lets me cover all components of such a simplified IDS. Also, unlike the great SNI paper (http://www.secnet.com/papers/IDS.PS), this article is not limited to network-based tools. In fact, the simple and hopefully reliable example port scan detection tool ("scanlogd") that you'll find at the end is host-based. ----[ What Can We Detect? A port scan involves an attacker trying many destination ports, usually including some that turn out not to be listening. One "signature" that could be used for detecting port scans is "several packets to different destination ports from the same source address within a short period of time". Another such signature could be "SYN to a non-listening port". Obviously, there are many other ways to detect port scans, up to dumping all the packet headers to a file and analyzing them manually (ouch). All of these different methods have their own advantages and disadvantages, resulting in different numbers of "false positives" and "false negatives". Now, let me show that, for this particular attack type, it is always possible for an attacker to make her attack either very unlikely to be noticed, or very unlikely to be traced to its real origin, while still being able to obtain the port number information. To obscure the attack, an attacker could do the scan very slowly. Unless the target system is normally idle (in which case one packet to a non-listening port is enough for the admin to notice, not a likely real world situation), it is possible to make the delay between ports large enough for this to be likely not recognized as a scan. A way to hide the origin of a scan, while still receiving the information, is to send a large amount (say, 999) of spoofed "port scans", and only on scan from the real source address. Even if all the scans (1000 of them) are detected and logged, there's no way to tell which of the source addresses is real. All we can tell is that we've been port scanned. Note that, while these attacks are possible, they obviously require more resources from the attacker to perform. Some attackers will likely choose not to use such complicated and/or slow attacks, and others will have to pay with their time. This alone is enough reason to still detect at least some port scans (the ones that are detectable). The possibility of such attacks means that our goal is not to detect all port scans (which is impossible), but instead, in my opinion, to detect as many port scan kinds as possible while still being reliable enough. ----[ What Information Can We Trust? Obviously, the source address can be spoofed, so we can't trust it unless other evidence is available. However, port scanners sometimes leak extra information that can be used to tell something about the real origin of a spoofed port scan. For example, if the packets we receive have an IP TTL of 255 at our end, we know for sure that they're being sent from our local network regardless of what the source address field says. However, if TTL is 250, we can only tell that the attacker was no more than 5 hops away, we can't tell how far exactly she was for sure. Starting TTL and source port number(s) can also give us a hint of what port scanner type (for "stealth" scans) or operating system (for full TCP connection scans) is used by the attacker. We can never be sure though. For example, nmap sets TTL to 255 and source port to 49724, while Linux kernel sets TTL to 64. ----[ Information Source (E-box) Choice For detecting TCP port scans, including "stealth" ones, we need access to raw IP and TCP packet headers. In a network-based IDS, we would use promiscuous mode for obtaining the raw packets. This has all the problems described in the SNI paper: both false positives and false negatives are possible. However, sometimes this might be acceptable for this attack type since it is impossible to detect all port scans anyway. For a host-based IDS, there are two major ways of obtaining the packets: reading from a raw TCP or IP socket, or getting the data directly inside the kernel (via a loadable module or a kernel patch). When using a raw TCP socket, most of the problems pointed out by SNI do not apply: we are only getting the packets recognized by our own kernel. However, this is still passive analysis (we might miss packets) and a fail-open system. While probably acceptable for port scans only, this is not a good design if we later choose to detect other attacks. If we used a raw IP socket instead (some systems don't have raw TCP sockets), we would have more of the "SNI problems" again. Anyway, in my example code, I'm using a raw TCP socket. The most reliable IDS is one with some support from the target systems kernel. This has access to all the required information, and can even be fail-close. The obvious disadvantage is that kernel modules and patches aren't very portable. ----[ Attack Signature (A-box) Choice It has already been mentioned above that different signatures can be used to detect port scans; they differ by numbers of false positives and false negatives. The attack signature that we choose should keep false positives as low as possible while still keeping false negatives reasonably low. It is however not obvious what to consider reasonable. In my opinion, this should depend on the severity of the attack we're detecting (the cost of a false negative), and on the actions taken for a detected attack (the cost of a false positive). Both of these costs can differ from site to site, so an IDS should be user-tunable. For scanlogd, I'm using the following attack signature: "at least COUNT ports need to be scanned from the same source address, with no longer than DELAY ticks between ports". Both COUNT and DELAY are configurable. A TCP port is considered to be scanned when receiving a packet without the ACK bit set. ----[ Logging the Results (D-box) Regardless of where we write our logs (a disk file, a remote system, or maybe even a printer), our space is limited. When storage is full, results will get lost. Most likely, either the logging stops, or old entries get replaced with newer ones. An obvious attack is to fill up the logs with unimportant information, and then do the real attack with the IDS effectively disabled. For the port scans example, spoofed "port scans" could be used to fill up the logs, and the real attack could be a real port scan, possibly followed by a breakin. This example shows how a badly coded port scan detection tool could be used to avoid logging of the breakin attempt, which would get logged if the tool wasn't running. One solution for this problem would be to put rate limits (say, no more than 5 messages per 20 seconds) on every attack type separately, and, when the limit is reached, log this fact, and temporarily stop logging of attacks of this type. For attack types that can't be spoofed, such limits could be put per source address instead. Since port scans can be spoofed, this still lets an attacker not reveal her real address, but this doesn't let her hide another attack type this way, like she could do if we didn't implement the rate limits... that's life. This is what I implemented in scanlogd. Another solution, which has similar advantages and disadvantages, is to allocate space for messages from every attack type separately. Both of these solutions can be implemented simultaneously. ----[ What To Do About Port Scans? (R-box) Some IDS are capable of responding to attacks they detect. The actions are usually directed to prevent further attacks and/or to obtain extra information about the attacker. Unfortunately, these features can often be abused by a smart attacker. A typical action is to block the attacking host (re-configuring access lists of the firewall, or similar). This leads to an obvious Denial of Service (DoS) vulnerability if the attack we're detecting is spoofable (like a port scan is). It is probably less obvious that this leads to DoS vulnerabilities for non-spoofable attack types, too. That's because IP addresses are sometimes shared between many people; this is the case for ISP shell servers and dynamic dialup pools. There are also a few implementation problems with this approach: firewall access lists, routing tables, etc... are all of a limited size. Also, even before the limit is reached, there are CPU usage issues. If an IDS is not aware of these issues, this can lead to DoS of the entire network (say, if the firewall goes down). In my opinion, there're only very few cases in which such an action might be justified. Port scans are definitely not among those. Another common action is to connect back to the attacking host to obtain extra information. For spoofable attacks, we might end up being used in attacking a third-party. We'd better not do anything for such attacks, including port scans. However, for non-spoofable attacks, this might be worth implementing in some cases, with a lot of precautions. Mainly, we should be careful not to consume too many resources, including bandwidth (should limit request rate regardless of the attack rate, and limit the data size), CPU time, and memory (should have a timeout, and limit the number of requests that we do at a time). Obviously, this means that an attacker can still make some of the requests fail, but there's nothing we can do here. See ftp://ftp.win.tue.nl/pub/security/murphy.ps.gz for an example of the issues involved. This paper by Wietse Venema details similar vulnerabilities in older versions of his famous TCP wrapper package. For these reasons, scanlogd doesn't do anything but log port scans. You should probably take action yourself. What exactly you do is a matter of taste; I personally only check my larger logs (that I'm not checking normally) for activity near the port scan time. ----[ Data Structures and Algorithm Choice When choosing a sorting or data lookup algorithm to be used for a normal application, people are usually optimizing the typical case. However, for IDS the worst case scenario should always be considered: an attacker can supply our IDS with whatever data she likes. If the IDS is fail-open, she would then be able to bypass it, and if it's fail-close, she could cause a DoS for the entire protected system. Let me illustrate this by an example. In scanlogd, I'm using a hash table to lookup source addresses. This works very well for the typical case as long as the hash table is large enough (since the number of addresses we keep is limited anyway). The average lookup time is better than that of a binary search. However, an attacker can choose her addresses (most likely spoofed) to cause hash collisions, effectively replacing the hash table lookup with a linear search. Depending on how many entries we keep, this might make scanlogd not be able to pick new packets up in time. This will also always take more CPU time from other processes in a host-based IDS like scanlogd. I've solved this problem by limiting the number of hash collisions, and discarding the oldest entry with the same hash value when the limit is reached. This is acceptable for port scans (remember, we can't detect all scans anyway), but might not be acceptable for detecting other attacks. If we were going to support some other attack type also, we would have to switch to a different algorithm instead, like a binary search. If we're using a memory manager (such as malloc(3) and free(3) from our libc), an attacker might be able to exploit its weaknesses in a similar way. This might include CPU usage issues and memory leaks because of not being able to do garbage collection efficiently enough. A reliable IDS should have its very own memory manager (the one in libc can differ from system to system), and be extremely careful with its memory allocations. For a tool as simple as scanlogd is, I simply decided not to allocate any memory dynamically at all. It is probably worth mentioning that similar issues also apply to things like operating system kernels. For example, hash tables are widely used there for looking up active connections, listening ports, etc. There're usually other limits which make these not really dangerous though, but more research might be needed. ----[ IDS and Other Processes For network-based IDS that are installed on a general-purpose operating system, and for all host-based IDS, there's some interaction of the IDS with the rest of the system, including other processes and the kernel. Some DoS vulnerabilities in the operating system might allow an attacker to disable the IDS (of course, only if it is fail-open) without it ever noticing. This can be done via vulnerabilities in both the kernel (like "teardrop") and in other processes (like having a UDP service enabled in inetd without a connection count limit and any resource limits). Similarly, a poorly coded host-based IDS can be used for DoS attacks on other processes of the "protected" system. ----[ Example Code Finally, here you get scanlogd for Linux. It may compile on other systems too, but will likely not work because of the lack of raw TCP sockets. For future versions see http://www.false.com/security/scanlogd/. NOTE THAT SOURCE ADDRESSES REPORTED CAN BE SPOOFED, DON'T TAKE ANY ACTION AGAINST THE ATTACKER UNLESS OTHER EVIDENCE IS AVAILABLE. <++> Scanlogd/scanlogd.c /* * Linux scanlogd v1.0 by Solar Designer. You're allowed to do whatever you * like with this software (including re-distribution in any form, with or * without modification), provided that credit is given where it is due, and * any modified versions are marked as such. There's absolutely no warranty. */ #include #include #include #include #include #include #include #include #include #include #include #include #if (linux) #define __BSD_SOURCE #endif #include #include #include /* * Port scan detection thresholds: at least COUNT ports need to be scanned * from the same source, with no longer than DELAY ticks between ports. */ #define SCAN_COUNT_THRESHOLD 10 #define SCAN_DELAY_THRESHOLD (CLK_TCK * 5) /* * Log flood detection thresholds: temporarily stop logging if more than * COUNT port scans are detected with no longer than DELAY between them. */ #define LOG_COUNT_THRESHOLD 5 #define LOG_DELAY_THRESHOLD (CLK_TCK * 20) /* * You might want to adjust these for using your tiny append-only log file. */ #define SYSLOG_IDENT "scanlogd" #define SYSLOG_FACILITY LOG_DAEMON #define SYSLOG_LEVEL LOG_ALERT /* * Keep track of up to LIST_SIZE source addresses, using a hash table of * HASH_SIZE entries for faster lookups, but limiting hash collisions to * HASH_MAX source addresses per the same hash value. */ #define LIST_SIZE 0x400 #define HASH_LOG 11 #define HASH_SIZE (1 << HASH_LOG) #define HASH_MAX 0x10 /* * Packet header as read from a raw TCP socket. In reality, the TCP header * can be at a different offset; this is just to get the total size right. */ struct header { struct ip ip; struct tcphdr tcp; char space[60 - sizeof(struct ip)]; }; /* * Information we keep per each source address. */ struct host { struct host *next; /* Next entry with the same hash */ clock_t timestamp; /* Last update time */ time_t start; /* Entry creation time */ struct in_addr saddr, daddr; /* Source and destination addresses */ unsigned short sport; /* Source port, if fixed */ int count; /* Number of ports in the list */ unsigned short ports[SCAN_COUNT_THRESHOLD - 1]; /* List of ports */ unsigned char flags_or; /* TCP flags OR mask */ unsigned char flags_and; /* TCP flags AND mask */ unsigned char ttl; /* TTL, if fixed */ }; /* * State information. */ struct { struct host list[LIST_SIZE]; /* List of source addresses */ struct host *hash[HASH_SIZE]; /* Hash: pointers into the list */ int index; /* Oldest entry to be replaced */ } state; /* * Convert an IP address into a hash table index. */ int hashfunc(struct in_addr addr) { unsigned int value; int hash; value = addr.s_addr; hash = 0; do { hash ^= value; } while ((value >>= HASH_LOG)); return hash & (HASH_SIZE - 1); } /* * Log this port scan. */ void do_log(struct host *info) { char s_saddr[32]; char s_daddr[32 + 8 * SCAN_COUNT_THRESHOLD]; char s_flags[8]; char s_ttl[16]; char s_time[32]; int index, size; unsigned char mask; /* Source address and port number, if fixed */ snprintf(s_saddr, sizeof(s_saddr), info->sport ? "%s:%u" : "%s", inet_ntoa(info->saddr), (unsigned int)ntohs(info->sport)); /* Destination address, if fixed */ size = snprintf(s_daddr, sizeof(s_daddr), info->daddr.s_addr ? "%s ports " : "ports ", inet_ntoa(info->daddr)); /* Scanned port numbers */ for (index = 0; index < info->count; index++) size += snprintf(s_daddr + size, sizeof(s_daddr) - size, "%u, ", (unsigned int)ntohs(info->ports[index])); /* TCP flags: lowercase letters for "always clear", uppercase for "always * set", and question marks for "sometimes set". */ for (index = 0; index < 6; index++) { mask = 1 << index; if ((info->flags_or & mask) == (info->flags_and & mask)) { s_flags[index] = "fsrpau"[index]; if (info->flags_or & mask) s_flags[index] = toupper(s_flags[index]); } else s_flags[index] = '?'; } s_flags[index] = 0; /* TTL, if fixed */ snprintf(s_ttl, sizeof(s_ttl), info->ttl ? ", TTL %u" : "", (unsigned int)info->ttl); /* Scan start time */ strftime(s_time, sizeof(s_time), "%X", localtime(&info->start)); /* Log it all */ syslog(SYSLOG_LEVEL, "From %s to %s..., flags %s%s, started at %s", s_saddr, s_daddr, s_flags, s_ttl, s_time); } /* * Log this port scan unless we're being flooded. */ void safe_log(struct host *info) { static clock_t last = 0; static int count = 0; clock_t now; now = info->timestamp; if (now - last > LOG_DELAY_THRESHOLD || now < last) count = 0; if (++count <= LOG_COUNT_THRESHOLD + 1) last = now; if (count <= LOG_COUNT_THRESHOLD) { do_log(info); } else if (count == LOG_COUNT_THRESHOLD + 1) { syslog(SYSLOG_LEVEL, "More possible port scans follow.\n"); } } /* * Process a TCP packet. */ void process_packet(struct header *packet, int size) { struct ip *ip; struct tcphdr *tcp; struct in_addr addr; unsigned short port; unsigned char flags; struct tms buf; clock_t now; struct host *current, *last, **head; int hash, index, count; /* Get the IP and TCP headers */ ip = &packet->ip; tcp = (struct tcphdr *)((char *)packet + ((int)ip->ip_hl << 2)); /* Sanity check */ if ((char *)tcp + sizeof(struct tcphdr) > (char *)packet + size) return; /* Get the source address, destination port, and TCP flags */ addr = ip->ip_src; port = tcp->th_dport; flags = tcp->th_flags; /* We're using IP address 0.0.0.0 for a special purpose here, so don't let * them spoof us. */ if (!addr.s_addr) return; /* Use times(2) here not to depend on someone setting the time while we're * running; we need to be careful with possible return value overflows. */ now = times(&buf); /* Do we know this source address already? */ count = 0; last = NULL; if ((current = *(head = &state.hash[hash = hashfunc(addr)]))) do { if (current->saddr.s_addr == addr.s_addr) break; count++; if (current->next) last = current; } while ((current = current->next)); /* We know this address, and the entry isn't too old. Update it. */ if (current) if (now - current->timestamp <= SCAN_DELAY_THRESHOLD && now >= current->timestamp) { /* Just update the TCP flags if we've seen this port already */ for (index = 0; index < current->count; index++) if (current->ports[index] == port) { current->flags_or |= flags; current->flags_and &= flags; return; } /* ACK to a new port? This could be an outgoing connection. */ if (flags & TH_ACK) return; /* Packet to a new port, and not ACK: update the timestamp */ current->timestamp = now; /* Logged this scan already? Then leave. */ if (current->count == SCAN_COUNT_THRESHOLD) return; /* Update the TCP flags */ current->flags_or |= flags; current->flags_and &= flags; /* Zero out the destination address, source port and TTL if not fixed. */ if (current->daddr.s_addr != ip->ip_dst.s_addr) current->daddr.s_addr = 0; if (current->sport != tcp->th_sport) current->sport = 0; if (current->ttl != ip->ip_ttl) current->ttl = 0; /* Got enough destination ports to decide that this is a scan? Then log it. */ if (current->count == SCAN_COUNT_THRESHOLD - 1) { safe_log(current); current->count++; return; } /* Remember the new port */ current->ports[current->count++] = port; return; } /* We know this address, but the entry is outdated. Mark it unused, and * remove from the hash table. We'll allocate a new entry instead since * this one might get re-used too soon. */ if (current) { current->saddr.s_addr = 0; if (last) last->next = last->next->next; else if (*head) *head = (*head)->next; last = NULL; } /* We don't need an ACK from a new source address */ if (flags & TH_ACK) return; /* Got too many source addresses with the same hash value? Then remove the * oldest one from the hash table, so that they can't take too much of our * CPU time even with carefully chosen spoofed IP addresses. */ if (count >= HASH_MAX && last) last->next = NULL; /* We're going to re-use the oldest list entry, so remove it from the hash * table first (if it is really already in use, and isn't removed from the * hash table already because of the HASH_MAX check above). */ /* First, find it */ if (state.list[state.index].saddr.s_addr) head = &state.hash[hashfunc(state.list[state.index].saddr)]; else head = &last; last = NULL; if ((current = *head)) do { if (current == &state.list[state.index]) break; last = current; } while ((current = current->next)); /* Then, remove it */ if (current) { if (last) last->next = last->next->next; else if (*head) *head = (*head)->next; } /* Get our list entry */ current = &state.list[state.index++]; if (state.index >= LIST_SIZE) state.index = 0; /* Link it into the hash table */ head = &state.hash[hash]; current->next = *head; *head = current; /* And fill in the fields */ current->timestamp = now; current->start = time(NULL); current->saddr = addr; current->daddr = ip->ip_dst; current->sport = tcp->th_sport; current->count = 1; current->ports[0] = port; current->flags_or = current->flags_and = flags; current->ttl = ip->ip_ttl; } /* * Hmm, what could this be? */ int main() { int raw, size; struct header packet; /* Get a raw socket. We could drop root right after that. */ if ((raw = socket(AF_INET, SOCK_RAW, IPPROTO_TCP)) < 0) { perror("socket"); return 1; } /* Become a daemon */ switch (fork()) { case -1: perror("fork"); return 1; case 0: break; default: return 0; } signal(SIGHUP, SIG_IGN); /* Initialize the state. All source IP addresses are set to 0.0.0.0, which * means the list entries aren't in use yet. */ memset(&state, 0, sizeof(state)); /* Huh? */ openlog(SYSLOG_IDENT, 0, SYSLOG_FACILITY); /* Let's start */ while (1) if ((size = read(raw, &packet, sizeof(packet))) >= sizeof(packet.ip)) process_packet(&packet, size); } <-->