Finger 79/tcp # John McDonald: Answers To Challenge #1

Dave G. | November 10th, 2006 | Filed Under: Guests

Login: jm                   Name: John McDonald
Directory: /guests/jm      Shell: /bin/zsh
On since Fri Nov 10 08:55:00 CDT from shaolin
No Mail.
Plan:
----------------------------------
Views expressed by guest bloggers not necessarily those held by 
Matasano Chargen.

Ok, so let’s go over the first challenge:

int print_msb(int number)
{
  ...
  char buf[sizeof("255")];
  sprintf(buf, "%u", number >> 24);
  ...
}

This code is attempting to isolate the most significant byte of the integer argument number. It does this with a right shift, but because the number is a signed int, an arithmetic right shift is performed instead of a logical right shift. (google Intel’s “sar”) This means that the sign bit will be propagated as the number is shifted. So, if the number was -1, it would have a bit pattern of 11111111 11111111 11111111 11111111. After the right shift, it would still have this same bit pattern. Thus, the buffer buf won’t be big enough to hold the unsigned decimal ascii representation of the number, and a buffer overflow will be possible.

Now for the second one:

int bank1[1000], bank2[1000];
...
void hashbank(int index, int value)
{
  int *bank = bank1;
  if (index<0) {
    bank = bank2;
    index = -index;
  }
  bank[index % 1000] = value;
}

This is a demonstration of something we’ve dubbed the Leblancian Paradox, as the formidable David Leblanc showed it to us. So, in two’s complement arithmetic, to negate a number, you invert all the bits and add one. So what happens when you negate the number 0x80000000? Here’s the bit pattern:

10000000 00000000 00000000 00000000

Invert the bits, and you get:

01111111 11111111 11111111 11111111

Add one, and you get:

10000000 00000000 00000000 00000000

Neat, huh? So, in the above code, if you provide an index of 0x80000000, the unary negation doesn’t change the value of index. Thus, the code places value into offset 0x80000000 % 1000. Now, index is a signed integer type, so the result of this modulus operation will actually be -648. Thus, the memory behind the bank2 array will be modified! Now, we probably should have switched the order of bank1 and bank2 or added a fake void *gEXTRASUPERCRITICALFUNCTIONPOINTERSPLEASEFORTHELOVEOFGODDONOTOVERWRITE[1024] somewhere, but hopefully you can see how this could be a ruxer.

Congrats to the following Chargen superstars:

Liudvikas Bukys

Ian

James Lee

Mangoboy

cneckar

Kasperle

Matt

Next challenge will be post on Monday, November 13th at 12PM/EST.