[Vuln-Dev Challenge] - VulnDev1.c Summary

[Aaron Adams <aadams () securityfocus com>]

For each challenge program that we release we will do our best to post a
summary that includes our intentions for releasing the particular program.
We will also explain and summarize some of the findings by people who took
part in the discussion.

VulnDev2.c is currently in the works and will hopefully be released May
21st.

VulnDev1.c Summary
------------------

-- Summary --

The VulnDev1.c challenge program was written to encourage people to look
into the internal workings of heap allocation on various systems. It was
designed in hopes that readers would research into why an off-by-one in
the heap is exploitable under some circumstances.

It was specifically written to be exploited on a system implementing the
Doug Lea Malloc implementation [1]. This includes the Linux and GNU/HURD
operating systems, and possibly others. As a result, this issue had
varying results depending on the type of system under which it was
invoked. Some participants noted a segmentation fault would not occur on
AIX and Windows systems. This is due to differing allocation algorithms
and memory management features. *BSD systems are also unaffected by this
issue as the algorithm used (PHK) does not implement inline memory
management. Meaning that information used for keeping track and managing
the status of the heap is not corruptable by overrunning a buffer in the
heap.

I assume that the reader of this summary is familiar with the internals of
the Doug Lea algorithm as well has heap-based exploitation methods [2, 3].
I will not be delving into the internals of these as they have all been
well documented.

-- Details --

VulnDev1.c contained a simple flaw within the for() loop.

for (i = 0; i <= SIZE && i != '\0'; i++)
        buf1[i] = p[i];

This flaw allowed a user invoking the program to overwrite 1 byte of heap
memory adjacent to memory allocated for buf1. Due to the Doug Lea
implementation, this 1 byte of memory corruption can be leveraged to
execute our own instructions. Two contributors to the discussion
demonstrated this successfully.

The one key attribute of VulnDev1.c which made exploitation possible was
the following declaration:

#define SIZE 252

As some posts indicated, simple modifications of this value would prevent
a segmentation fault from occurring when SIZE is overrun. This is due to
the behavior of the malloc() function when allocating buffers of various
sizes.

As described in Once Upon A free(), each chunk size passed to
malloc() has a minimum of 4 bytes additional overhead. This is to
accommodate for the [SIZE] field of the adjacent chunk header. Also, due
to the 3 least significant bits of each [SIZE] value being used as flags,
the [SIZE] value of each chunk is padded to the next 8 byte boundary.

The following examples depict this behavior:

malloc(256)     [SIZE = 264]
malloc(15)      [SIZE = 24 ]
malloc(0)       [SIZE = 8  ]

And most importantly:

malloc(252)     [SIZE = 256]

As shown above, depending on the [SIZE] padding and the subsequent layout
of the chunk within memory, the last byte of a user-controllable buffer
may be directly adjacent to the first byte of the next headers [SIZE]
value. This condition will only occur when the size of an allocated buffer
+ 4 falls on an 8 byte boundary, such as 252, 12, 1020, etc. In
situations where this does not occur, overwriting 1 byte of memory will
result in the corruption of a padding byte. However, in situations similar
to the memory layout caused by VulnDev1.c, overwriting 1 byte of memory
will allow for the corruption of the LSB of the adjacent [SIZE] field on
little endian machines. A variety of posts touched on this issue when
slightly modifying the SIZE variable used by malloc().

Now that we know that this bug can be used to overwrite a sensitive value
in memory, the question is whether or not this can be leveraged to execute
our own instructions. As was shown, this is indeed possible and I will
explain why. Just as a note, due to the layout of the program, at first
glance it may appear that exploitation could occur during free(buf2). In
actuality, exploitation could occur during free(buf1). There are also some
anomalies with exploitation which I will do my best to address later on.

When buf2 is allocated (buf2 = malloc(SIZE) ) the additonal 4 bytes are
added to SIZE, resulting in a [SIZE] value of 0x0100 (256). Because buf1
has also been allocated, and thus is in use, the PREV_INUSE flag will also
be set, causing the [SIZE] to be 0x0101.

When the 1 byte of memory corruption occurs the LSB of buf2's [SIZE] will
be overwritten. For example's sake we will use the value 0xC. This will
result in buf2's [SIZE] value being 0x010C. This corrupted value is first
referenced during the call to free(buf1) and this is where exploitation
takes place.

At some point during execution the free(buf1) call checks whether the
adjacent forward or backward chunks are free. If so, the chunks will be
coalesced to avoid contiguous free chunks. The [SIZE] value of buf1's
header is first checked for the PREV_INUSE flag to see if buf1 and the
previous chunk should be coalesced. This is followed by a check to see if
the forward chunk, in our case buf2, is free. To make the check the
PREV_INUSE flag AFTER buf2 must be tested. This is accomplished by
referencing the address at *buf1 + ([SIZE] field of buf1) + ([SIZE] field
of buf2). This third chunk's [SIZE] value is then referenced via this
location. Under normal circumstances this would place the test at the
first bytes of data in the chunk following buf2. In the context of
exploitation of VulnDev1.c however the buf2[SIZE] value has been
corrupted. This will result in the check for PREV_INUSE flag occuring
further in the heap, beyond the chunk following buf2. In our case, if
buf2[SIZE] is 0x010C, then the check will occur at the offset *buf1 + 524.
In our situation this offset will place us in unused heap memory which has
been initialized to zero.

This will result in the PREV_INUSE flag appearing unset, making free()
believe that buf2 is in fact free. Forward consolidation will then occur
and the unlink() function will be called on buf2. This inturn can be used
to our advantage by populating the first 8 bytes of buf2 with fake [FD]
and [BK] pointers, which when referenced by unlink() will be corrupted.

As shown by the two exploits released, this can lead to exploitation by
overwriting the free GOT entry. Other values which could be overwritten
include .dtors or a function pointer within free() itself. It should be
noted that if the second free() is allowed to be called and the corrupted
[SIZE] is again referenced, varying functionality may occur.

That's all. Overwriting the free GOT entry to point to our own
instructions somewhere in memory will allow us to execute our own code,
theoretically with elevated privileges of course. Off-by-one bugs in the
heap have been found in the wild and I hope the list's discussion and
summary will help people understand how exploitation works.

-- Additional Discussion --

When I first wrote the program I considered a scenario, dependent on bytes
chosen for the 1 byte overwrite, that would result in the program
exiting cleanly. I also believed that in some situations exploitation
could occur during the second free(), however I was unable to reproduce
the situation and have since determined that exploitation during the
second free() is likely not possible.

Although I was unable to reproduce my hypothesis, Matrix and Marco Ivaldi
described a situation that was similar to the scenario I had anticipated.
No discussion really followed their findings so I will do my best to shed
a little light on the issues. It should be noted that there is some
behavior that I have not been able to figure out. Any corrections or
additional information regarding these observations is much appreciated
and anticipated.

Matrix:

> It's true that the exploit will work on the first free() for any value
> of the overflow char > 0x9, however I noticed some different things
> happen for values < 0x9. If the overflow char is 0x1, 0x2, 0x6, 0x7, or
> 0x9 the program will exit cleanly without a segfault. If the overflow
> char is 0x4 or 0x5, the first free() will execute find, and the program
> will segfault on the second free(). I don't know if these cases are
> exploitable or not. And finally, if the overflow char is 0x8 the program
> segfaults in the first free() (like when the char is > 0x9)

If the corrupted size value is small enough (0x1, 0x2, 0x6, 0x7) the
value will be ignored during forward consolidation. This is again due to
the first 3 bits of the value being used as flags. All 4 of these values
will consume only the 3 least significant bits of the [SIZE] field. As a
result, the correct [SIZE] (256) will be used for the forward
consolidation check. As buf2 will correctly be shown as INUSE, unlink()
will not be called. When the call to free(buf1) is completed, the
PREV_INUSE flag of buf2 will appropriately be removed and the [PREV_SIZE]
will be updated accordingly. As a result, exploitation during these cases
is not possible.

I have not been able to figure out why 0x4 and 0x5 will trigger a segfault
during the second free() as I would expect their behavior to mimic those
values above. Especially since they also only consume the 3 least
significant bits of buf2 [SIZE]. Any takers?

The first free() segfaults with a value of 0x8 because it affects the 4th
bit of buf2 [SIZE] thus affecting the forward consolidation check. This
should put it ahead in heap memory and result in an unset PREV_INUSE flag.

As for 0x9, again I would expect the behavior to mimic that of 0x8. I'm
not sure why 0x9 does not behave the same way.

Any questions or corrections to the summary, please feel free to post to
the list as it will benefit everyone. If necessary, I will participate in
the list discussion.

-- References --

[1] Doug Lea Malloc Implementation
http://gee.cs.oswego.edu/dl/html/malloc.html

[2] Once Upon A free()
http://www.phrack.org/phrack/57/p57-0x09

[3] Vudo - An object superstitiously believed to embody magical powers
http://www.phrack.org/phrack/57/p57-0x08

EOF

Aaron Adams