User-supplied Array Index Exploitation Simplified.. sort of.

Thu, 04 Feb 2010 20:38:25 -0600

Have you ever ran into a case where you controlled an index into an array, but then were tasked with the annoying prospect of massaging the overwrite to suit your needs?

For example, from http://labs.idefense.com/intelligence/vulnerabilities/display.php?id=5 :

#define RFC2231_MAX 64
...
char *pieces[RFC2231_MAX];
and indexed by the signed integer variable 'n':
if(n < RFC2231_MAX){
    pieces[n] = parms->value;

^^ Note: parms->value is a pointer to user data.

Say you do some reversing and find out that 'pieces' is 300 bytes away from the stored return address. From the array write, we can tell that overwriting the return address would totally be exploitable (assuming no N^X) since it's overwritten with a pointer to data supplied by you.

We need the following: a negative integer that when multiplied by 4 (assuming a 32 bit architecture here), will yield 300.

Well, I'm not the most k-awesome bithax0r in the world, so I find the prospect of finding a negative integer to exploit this bug to be quite annoying. I know what I want, I just don't want to waste time telling some stupid imperative language how to give it to me! What could possibly solve my quandary? Hmmm, STP.. a constraint solver.. that sounds like just the thing!

Throw this into a file:

dummy: BITVECTOR(32);
overflow : BITVECTOR(64);
multiplyOverflow : BITVECTOR(64);
notDummy : BITVECTOR(32);
evilIndex : BITVECTOR(32);

% Make sure the number is negative via two's compliment ninjutsu
ASSERT(notDummy = ~dummy);
ASSERT(evilIndex = BVPLUS(32, notDummy, 0hex00000001));

% Make sure it's signed too
ASSERT(evilIndex & 0hex80000000 = 0hex80000000);

% Need a bigger bit width to express the overflow
ASSERT(overflow[31:0] = evilIndex);
ASSERT(multiplyOverflow = BVMULT(64, overflow, 0hex0000000000000004));

% We want evilIndex*4 == 300
ASSERT(multiplyOverflow[31:0] = 0hex0000012C);
QUERY(FALSE);

Now feed it to the solver...

$ stp -p array.access.stp
ASSERT( v_solver_0  = 0x00000000  );
ASSERT( overflow  = 0x00000000C000004B  );
ASSERT( multiplyOverflow  = 0x000000030000012C  );
ASSERT( evilIndex  = 0xC000004B  );
ASSERT( notDummy  = 0xC000004A  );
ASSERT( dummy  = 0x3FFFFFB5  );
Invalid.

Well, there you have it: 0xC000004B. Compare this to the alternative (from: http://milw0rm.org/exploits/99 ) :

unsigned int num(int dist) {
        int tmp = -1-dist;
        unsigned int border = tmp;
        int neg = (border/4)*(-1);
        unsigned int res;

        res = 0xffffffff+neg;

        return res;
}

I checked the output of my formula against the return value for num() here - they matched.

Well, I know which method looks more intuitive to me.

Hope someone finds this useful!

OpenRCE: Blog

User-supplied Array Index Exploitation Simplified.. sort of.