[OCLUG-devel] Re: GNU code with security holes?!! [was: Trouble with strings and files]

[Christopher Smith]

On Thu, 2004-07-08 at 19:10, Jack Denman wrote:
> On Thu, 2004-07-08 at 14:41, Christopher Smith wrote:
> 
> > This readline() function is quite different in behavior from fgets(),
> > and as such, depending on how you look at the original program it would
> > be unwise to use readline() (in particular, unless you start using
> > unlimited precision integers, there's no point in reading in more than
> > 50 characters on most platforms). The code also drops carriage returns
> > and line feeds from the file it reads in, and makes a carriage return
> > and an EOF indistinguishable, which is not necessarily desireable.
> 
> Old news.
> There is a  major difference between EOF and  carriage returns. EOF =
> -1 as a 32 bit integer.

Please try to read more carefully. I didn't claim their wasn't. I said
that your sample code treats them equivalently (as indicated by the (c
== EOF || (c == '\n')). You'd have to add an additional EOF test after
doing this in order to know whether you needed to append the "\n" or
just let the file end. It is, as I said, a minor point.

> > The code is also not entirely portable, as different platforms treat
> > carriage return and line feed characters differently. That may be an
> > issue, but this code should be portable to POSIX systems as well as
> > Windows, so no big concern here either.
> 
> '\n' covers both the <CRLF> on Windows and the <LF> on *nix systems.
> The only reason for testing for an '\r would be if no <CR> was
> present. Has anyone ever seen this in a text file?

Well, '\n' doesn't cover <CRLF> on Windows if you open in binary mode,
but yes, as I said, it works on POSIX systems and Windows. It's kind of
frightening that you think that's the whole world. Notice a major
platform I didn't mention? Yup, MacOS. While OS X is a POSIX-ish system,
so I imagine '\n' works fine on it, all prior versions of the MacOS used
'\r'. If you ever used a teletype, this actually might seem to make more
sense than '\n', as '\r' corresponds to the "Line Feed" and '\n'
corresponds to 'carriage return'. Here's a quick link I found searching
online which explains it in more detail:

http://www.websiterepairguy.com/articles/os/crlf.html

So, with old MacOS text files, having \r's without \n's would be pretty
common.

> > The handling of the (c == EOF) || (c == '\n') case, while perfectly good
> > code, could be improved. For starters, I'd test this before I'd test
> > against '\r', because one would hope that the '\r' case would occur less
> > often. More importantly this snippet:
> > 
> > >            c = '\0';
> > >             *p++ = (char) c;
> > >             break;
> 
> > The problem is in this line of code:
> > 
> > line->size *= 2;
> > 
> > This can can cause line->size to overflow, which in turn would result in
> > the buffer being reallocated to a *smaller* size, but p would be updated
> > to point to a location as if memory had grown. All subsequent writes to
> > p would constitute a buffer overflow.
> 
> If the buffer is doubled how does it get smaller?
> (character) p is updated to the position of the first position in
> second half of the doubled buffer. Where is the beef (overflow)?

Jack, given all the claims you have made about security expertise, and
the work that you did working on AIX, making it so secure, I'm frankly
quite shocked by this. I explained to you exactly what is wrong with
this code, and you still don't get it. This is a classic integer
overflow problem. It's one thing to make the mistake in the first place
(even the best security experts acknowledge they need code reviews in
order to avoid mistakes slipping through), but it should be obvious once
someone points it out to you. This is the kind of thing you are taught
in the first few hours of training on writing secure software. Don't
worry though, I'll break it down so those without security training can
understand it.

> > The simple fix to this would be to change the line to:
> > 
> > line->size = (line->size < (SIZE_MAX/2)) ? line->size*2 : SIZE_MAX;
> 
> I don't see this as necessary over the GNU code.

Well, I guess GNU does.

I tracked down your function in the GNU code base. The function is
called readlinebuffer. It is like your code sample, with a few changes.
There is no ungetc(), no checking against '\r', and a few other changes,
some of which we've talked about. readlinebuffer no longer does the *=2
itself, nor does it call xrealloc(). It now calls a GNU function called
x2realloc() which grows the buffer to 2x whatever size
you pass in.

Now, why would GNU make a special realloc function for this? Well,
x2realloc() eventually traces down to this little bit of code:

      if (SIZE_MAX / 2 / s < n)
        xalloc_die ();
      n *= 2;

Looks a bit like my code doesn't it?

They decide to die right then and there, rather than wait for xrealloc
to do it for them. After thinking about it some more, it seems like the
smarter thing to do would be to try reallocate to ((n/2) +
(SIZE_MAX/2))/s. I might ping the GNU maintainer about this. Anyway, the
"s" there is an extra parameter that lets you set an allocation ceiling
that is SIZE_MAX/s, for whatever reason (s == 1 in the case where you
invoke x2realloc()).

Anyway, what does this tell us? It tells us GNU seems to think I'm on to
something here.

Now, this takes us back to what is the risk here. Jack wants to know why
the number could get smaller when you do:

line->size *= 2

Where's the beef? Well, think of the test case in my code:

(line->size < (SIZE_MAX/2))

Okay, that's a pretty strong hint. I seem to think the problem is
happening somewhere around SIZE_MAX/2. Now, technically, there isn't a
problem if line->size == (SIZE_MAX/2), but since "*= 2" on that would
work out to SIZE_MAX anyway, I thought why not save ourselves doing a
multiply? So, what happens once line->size > (SIZE_MAX/2). Well, lets do
this algebraically.

let line->size = SIZE_MAX/2 + i, where i is defined as being a positive
integer.

Now, let's see what we end up with:

line->size = (SIZE_MAX/2 + i) * 2
line->size = SIZE_MAX + 2i

So, based on this, it'd be safe to say line->size is going to be greater
than SIZE_MAX. But wait... they must call it SIZE_MAX for a reason
right? SIZE_MAX represents the highest possible value that a value of
size_t can possibly be; size_t simply isn't big enough to fit a larger
value. So, what happens when you go above SIZE_MAX? You get an integer
overflow. In some programming languages, this produces an exception, but
in C the result "wraps around". Your end result is essentially "what
you'd expect" mod (SIZE_MAX + 1). So it turns out:

line->size = (SIZE_MAX + 2i) % (SIZE_MAX + 1)

which is the same as:

line->size = 2(i - 1)

I know, I'm sure Jack thinks I'm a liar, who's making all this stuff up.
I'm sure he checked out what happens when you go over SIZE_MAX/2
himself. Let's see what happens:

#include <stdio.h>
#include <stdint.h>

int main() {
  size_t i;
  for (i = 1; i < (SIZE_MAX/2); ++i) {
    size_t foo = SIZE_MAX/2 + i;
    printf("i = %u\n", i);
    printf("2(i - 1) = %u\n", 2*(i - 1));
    printf("foo: %u\n", foo);
    foo *= 2;
    printf("foo*2: %u\n", foo);
  }
}

You probably will want to stop this before it runs too long.

Jack seemed to be suggestion that this line might some how correct for
this problem:

p += buffer - line->buffer

But that line compensates for changes in the starting address of the
buffer. It doesn't in any way compensate for changes in the size of the
buffer. Indeed, for p to be pointing at allocated memory after this
line, you have to assume that the size of the new buffer is greater than
the size of the old buffer. If not.... ta-da! Buffer overflow.

I'm sure Jack's code sample is based on an older version of the GNU code
base. I know the GNU core utilities guy did a presentation at SCALE
where he talked about an audit of the core code base he did the previous
summer, where he uncovered and corrected hundreds of bugs like this. So,
maybe this was corrected during that audit, and your code snapshot is
older than that.

Now, I've explained the problem in this code in quite painful detail,
but I haven't seen an explanation of a security hole in my code. I'll
conclude that Jack couldn't find one.

-- 
Christopher Smith <x at xman.org>