Spot the Vulnerability: Loops and Terminating Conditions

ByPaul Hendry

Published Sat Oct 30 2021

In memory-unsafe languages like C, special care must be taken when copying untrusted data, particularly when copying it to another buffer. In this post, we'll spot and mitigate a past vulnerability in Linux's NTP daemon.

Background: Buffer Overflows and Loop Termination

A buffer overflow occurs when code which intends to write data to a buffer inadvertently writes beyond that buffer into an adjacent memory location. At best this might just invalidate the program's state and cause a crash or other unintended behaviour, but a malicious exploitation of a buffer overflow can often lead to protected data being overwritten by an attacker, leading to denial-of-service or arbitrary code execution.

A common cause for buffer overflows is a looping construct whose terminating conditions are either invalid or missing. The simplest example of this is a strcpy()-style function like the following, intended to copy a string between source and destination buffers:

char * copy(char *dst, char *src) {    char *dst_start = dst;    while((*dst++ = *src++) != '\0');    return dst_start;}

The above loop copies from src to dst until it sees a NULL character, with no bearing on the size of the dst buffer. If src is larger than dst, this will overrun the buffer.

While the buffer overflow potential of the above is easy to recognize, it can be much more difficult when complex application logic is mixed in.

Processing a Packet in NTPD

What follows is more-or-less exactly the vulnerable NTPD code, presented in its entirety to help demonstrate how tricky it can be to assess complex loops for correctness.

In the code below,

  • ctl_getitem() is a function which gets the next data item from an incoming NTP packet,
  • buf is the 128-character buffer into which packet data is written,
  • cp is a pointer into the input data (used during the copy), and
  • tp is a pointer into buf (also used during the copy).
static struct ctl_var *ctl_getitem(    struct ctl_var *var_list,    char **data){    register struct ctl_var *v;    register char *cp;    register char *tp;    static struct ctl_var eol = { 0, EOV, };    static char buf[128];    /*     * Delete leading commas and white space     */    while (reqpt < reqend && (*reqpt == ',' || isspace((int)*reqpt))) {        reqpt++;    }    if (reqpt >= reqend)        return 0;    if (var_list == (struct c tl_var *)0)        return &eol;    /*     * Look for a first character match on the tag. If we find one, see if it is a full match.     */    v = var_list;    cp = reqpt;    while (!(v->flags & EOV)) {        if (!(v->flags & PADDING) && *cp == *(v->text)) {            tp = v->text;            while (*tp != '\0' && *tp != '=' && cp < reqend && *cp == *tp) {                cp++;                tp++;            }            if ((*tp == '\0') || (*tp == '=')) {                while (cp < reqend && isspace((int)*cp))                    cp++;                if (cp == reqend || *cp == ',') {                    buf[0] = '\0';                    *data = buf;                    if (cp < reqend)                        cp++;                    reqpt = cp;                    return v;                }                if (*cp == '=') {                    cp++;                    tp = buf;                    while (cp < reqend && isspace((int)*cp))                        cp++;                    while (cp < reqend && *cp != ',')                        *tp++ = *cp++;                    if (cp < reqend)                        cp++;                    *tp = '\0';                    while (isspace((int)(*(tp - 1))))                        *(--tp) = '\0';                    reqpt = cp;                    *data = buf;                    return v;                }            }            cp = reqpt;        }        v++;    }    return v;}

Feel free to pause here and try to identify a problem in this function unassisted, otherwise continue on and we'll break it down in detail.

Spotting the Vulnerability

Taking the perspective of an attacker is an effective way of switching from the typical development mindset of "should this work correctly?" to the mindset of "can this work incorrectly?" As an attacker who is trying to overrun buf, your goals would be to

  1. reach the code where buf gets written to via the tp pointer, and
  2. find a means to increment tp 128 or more times.

Starting with this first goal, we first have

tp = v->text;while (*tp != '\0' && *tp != '=' && cp < reqend && *cp == *tp) {    cp++;    tp++;}if ((*tp == '\0') || (*tp == '=')) {    while (cp < reqend && isspace((int)*cp))        cp++;

While looping through variables definitions in order to look for one which matches the input data, we're initially using tp as a pointer into the variable's text field. If the input matches that text up until a NULL or = character, this block gets executed. Next,

    if (cp == reqend || *cp == ',') {        buf[0] = '\0';        *data = buf;        if (cp < reqend)            cp++;        reqpt = cp;        return v;    }

If the input data contains a comma, this block will execute and return from the function. So to continue on, the input must not contain a comma.

    if (*cp == '=') {        cp++;        tp = buf;        while (cp < reqend && isspace((int)*cp))            cp++;

So long as the input data contains an equals sign, this block will execute. Finally,

        while (cp < reqend && *cp != ',')            *tp++ = *cp++;        if (cp < reqend)            cp++;        *tp = '\0';        while (isspace((int)(*(tp - 1))))            *(--tp) = '\0';

We've reached the code which copies into buf (via tp). So long as cp is not a comma and is less than the end of the input data (reqend), the copy continues. Notably, no checks prevent this loop from executing 128+ times and blowing the stack of buf, since the input data can exceed that size. Reviewing the preconditions we've built up for reaching this point in the code, we only have

  1. input does not contain a comma, and
  2. input contains an equals sign.

This sounds loose enough to be practically exploitable, and it turns out it was, by writing and executing malicious code on the stack beyond buf. The lack of bounds checking is obvious once it's singled out, but buried among the other checks and validations, it's much harder to find.

Mitigation in NTPD

The mitigation applied for this vulnerability was as simple as you might expect: adding another condition to the while loop performing the copy:

        while (cp < reqend && *cp != ',') {            *tp++ = *cp++;            if (tp >= buf + sizeof(buf) - 1) {#if 0  /* don't syslog for now - DoS potential on filling syslog */                msyslog(LOG_WARNING,                    "Attempted \"ntpdx\" exploit from IP %d.%d.%d.%d:%d (possibly spoofed)\n",                    (ntohl(rmt_addr->sin_addr.s_addr) >> 24) & 0xff,                    (ntohl(rmt_addr->sin_addr.s_addr) >> 16) & 0xff,                    (ntohl(rmt_addr->sin_addr.s_addr) >> 8) & 0xff,                    (ntohl(rmt_addr->sin_addr.s_addr) >> 0) & 0xff,                    ntohs(rmt_addr->sin_port));#endif                return (0);            }        }

It worth appreciating how the potential exploitability of the fix was itself taken into consideration, by choosing not to write logs when the size check is triggered. NTP is a UDP-based protocol which means that source IP addresses can be spoofed by the sender, so it was decided that there wasn't enough value in logging potentially-spoofed IPs given that it potentially introduces a resource exhaustion denial-of-service attack (by deliberately filling up the server's logs).

Takeaways

  • Copying untrusted data in memory-unsafe languages is a risky process which must be done with the utmost care.
  • When code which performs a copy is being a reviewed, a useful technique is to step through each code path leading up to the loop and assess whether any of them could cause the copy to overflow the buffer.
  • Whenever possible, "safe" size-aware copying routines should be used (e.g. strncpy) in place of "unsafe" routines (e.g. strcpy) or ad-hoc code.

Previous

Exploring Dependent Types in Idris
When I'm not coding the "impossible" at Art+Logic, I take a lot of interest in new programming technologies and paradigms; even if they're not yet viable for use in production, there can often be takeaways for improving your everyday code.