CTF Service Overview: GrimCreeper

Before it gets too far past Defcon, I've decided to post about a service that SophSec submitted to our homies in Kenshoto to use as a vulnerable service for Defcon's CTF. (For those unaware, Kenshoto is the group of 1337 hax0rs who manage the Capture-The-Flag competition - a pretty cool contest requiring real-world application exploitation skills)

[This is a long winded post, I recommend getting your coffee now.]

I was lucky enough to be involved in writing a vulnerable network service to be used during CTF for the teams to try and compromise. What I submitted was GrimCreeper, a piece of code with a pretty neat bug. Provided below is a basic run down on the service and an overview of the subtle yet devastating bug it contained.

[Warning: Plot Sploiler] If you want to find the bug on your own, leave now [/Warning]

This write-up assumes a scenario using 32bit x86 architecture.

GrimCreeper is a simple network service, providing extremely basic (read: dumb) functionality to its users. Functionality includes a network echo service, time service, as well as a fortune like service returning a lie or a fact.

GrimCreeper had several psuedo-bugs; that is, lines of code which are intentionally designed to look buggy but are not exploitable. The service also contained one real exploitable bug caused by a signedness issue during a size check, involving bit shifting. This ultimately results in a memory copy for a user-specified length into a stack buffer.

This scenario is introduced by accepting a user-specified length variable for the copying of user-specified data. This isn't a typical signedness bug though. An example of a typical signedness bug could look like:

/* 
 * return true if size is reasonable,
 *  return false if it is too big
*/
int some_check_function(size_t net_size)
{
 int checksize = net_size;

 if (checksize <= MAXBUFFERSIZE)
 {
   return 1;
 }

 return 0;
}

With checksize being a signed integer, when it is assigned the value of the (presumably, user-supplied) net_size it will be negative if the value in net_size is greater than 2^31 - 1. If checksize is negative, of course the 'if' statement will evaluate as less than the MAXBUFSIZE macro definition, which is also signed. This type of bug isn't as common anymore, as developers have gotten better about using uniform unsigned size types as well as performing signedness checks before/after assignment.

A step up from this, GrimCreeper performs a size signedness check before handling the user-sizes for anything else. Consider the following code:

/*
 * returns true if net_size is "safe",
 * and can be assigned to a signed int
 * without causing it to be negative
*/
int check_signed_int(size_t net_size)
{
 unsigned int x;
 x = ~0;
 x = (x << 1)>>1;

 if (net_size <= x)
 {
   return 1;
 }

 return 0;
}

This check function can be used prior to the previous function to ensure that the size is not too big for a signed check. (I understand this is getting contrived, but it makes for a great bug setup :P). It is also not entirely unreasonable to consider that this type of code might be implemented in a real world program where mixing of type signedness occurs for size variables, such as in legacy applications/network protocols.

The interesting thing here is that the same function fails when applied to datatypes smaller than int. Consider the following code:

/*
 * function is intended to return true
 * if net_size is "safe",
 * and can be assigned to a signed short
 * without causing it to be negative
*/
int check_signed_short(unsigned short net_size)
{
 unsigned short x;
 x = ~0;
 x = (x << 1)>>1;

 if (net_size <= x)
 {
   return 1;
 }

 return 0;
}

This function will always return true ("safe") for any value passed into it, and thus does not work to check if a large unsigned short will cause a signed short to be negative. Strangely, if the bit shifting in the above function is spaced over two lines, the function does work properly and as expected. Observe the following:

/*
 * returns true if net_size is "safe",
 * and can be assigned to a signed short
 * without causing it to be negative
*/
int check_signed_short(unsigned short net_size)
{
 unsigned short x;
 x = ~0;
 x = x << 1;
 x = x >> 1;

 if (net_size <= x)
 {
   return 1;
 }

 return 0;
}

Voila! The basis for the bug in GrimCreeper. The seemingly subtle visual difference between these two functions has a huge impact on their functionality. Now for the breakdown of how, why, and where this bug happens..

By observing the binary generated by the compiler for each of these functions, the difference becomes apparent. The proper, working implementation of the function (using the shifts across two lines), results in the following binary output:
...

movw   $0xffff,0xfffffffe(%ebp)
movzwl 0xfffffffe(%ebp),%eax
add    %eax,%eax
mov    %ax,0xfffffffe(%ebp)
movzwl 0xfffffffe(%ebp),%eax
shr    %eax
mov    %ax,0xfffffffe(%ebp)

... Seen above, the

add   %eax,%eax

replaces (and acts the same as) the single shift left, and the

shr    %eax

represents the single shift right. The value resulting from these operations is 0x7fff, and is exactly as intended and expected. Now observe the binary generated by the single-line (and broken) version of the function:
...

movw   $0xffff,0xfffffffe(%ebp)
movzwl 0xfffffffe(%ebp),%eax
add    %eax,%eax
sar    %eax
mov    %ax,0xfffffffe(%ebp)
mov    0xffffffec(%ebp),%eax

...
Similar to the previous function, the code uses an

add  %eax, %eax

in place of the shift left. However, directly after this is a HUGE difference: a SAR. A SAR? WTF IS A SAR? SAR is a Shift-Arithmetic-Right, and its action differs from a SHR in that SAR is intended to be used with signed values and retains the state of the signed-bit. This shows that the value is being treated as signed, even though it was specifically declared as unsigned.

It should be noted, that when I first discovered this difference I paid no further attention to the assembly I had in front of me, and jumped directly to an incorrect conclusion. The use of the SAR (and thus treatment of an unsigned short as a signed value) in the single-line shifting had me convinced that this was the result of a compiler bug, and that GCC was generating faulty code. I discussed this difference and showed the C code to several sharp people who all drew the same conclusion as I did. Big thanks and props to Mark Dowd for pointing out what was actually happening.

The cause for this difference is an integral promotion of the unsigned short to a signed integer. This happens because in C every operation on a primitive type that is smaller than an integer results in that type being promoted a signed-integer for that operation, regardless of that original type's signedness. In the case of the shifting happening in two lines, the separation between lines allows for the type be demoted back to a 16 bit value. In the single line instance, the value is maintained in its promoted state, and thus results in a different value. Here is a breakdown of what is actually happening in the single-line example:

1. The value for all 16 bits being set (0xffff) is being stored in 32 bit register %eax.
2. %eax is then doubled via:

add    %eax,%eax

This represents the shift-left. The resulting value in %eax is 0x01fffe.
3. A Shift-Arithmetic-Right is then performed on %eax, returning the value back to 0xffff. The value of the lower 16 bits of %eax, stored in %ax, is then placed on the stack. Ultimately for the size-check routine, the value resulting from this is always going to be 0xffff.

Conclusions and Notes:

I. It is interesting to note that although SAR works differently than SHR, in this case it doesn't matter. The only real significance to SAR %eax being present is that it illustrates that the value is being treated as a signed integer - but since the signed-bit is not set, a SHR in place of that SAR would act the same.

II. During CTF the code for GrimCreeper was provided to the teams as a trick. This was intended to foster a code audit instead of the traditional reverse engineering or fuzzing. The idea was that without an in depth understanding of C and its integral promotion, this vulnerability is very difficult to spot. It truly stands in support of the belief that some vulnerabilities are easier to spot in assembly rather than source.

III. There are hints provided within the source code and the network responses by GrimCreeper which are meant to help teams find the vulnerability; these hints are flawed (accidentally) as they were written while I still believed this to be a compiler bug.

A friend pointed out a much sneakier way of introducing this vulnerability through obfuscation. In the original source code for GrimCreeper there are multiple functions for checking different typed size variables: one for unsigned integers, and one for unsigned shorts. This separation might warrant extra attention, as it appears quite suspect. By making a single #define macro to perform the shifting, the code is a lot cleaner and it becomes even less intuitive that the behavior of the shifting will change with different types:

#define STRIP_HIGH_BIT(var) \
  var = ((var<<1)>>1)

void func(unsigned short s, unsigned int i){
 STRIP_HIGH_BIT(i);
 STRIP_HIGH_BIT(s);
 ...
}

This would likely warrant less attention, and make the bug yet even harder to find, even to a seasoned auditor.

IV. Finally, as I am sure an astute programmer would have noticed, the use of two shifts to achieve this task is redundant. The check is easily performed using only one shift without introducing the bug. I initially discovered this bug during a real code review, and investigated it after wondering if there was any significance to the use of two shifts that wouldn't have been achieved with just one. I am under the belief that two shifts were used in the original code as a safety mechanism, in order to maintain the value of the highest bit, possibly as an old school assembly best-practice. Of course, it may have just been a mistake. Either way, without two shifts there'd be no bug, and no GrimCreeper.