10.13.09

2008 Winners

Posted in Uncategorized at 1:36 pm by XcottCraver

At long last, here are the winners of the 2008 underhanded C contest.

The 2008 contest had over 100 entries, a record for our contest. Sifting through them all and determining their underhanded behavior wasn’t easy, but many of them fell into several standard approaches. The most common:

  • XORing the redaction region with a pseudo-random mask, which can later be retrieved. The underhanded behavior usually consists of a purposefully mistaken approach to seeding the pseudo-random generator.
  • Accidentally appending the original data to the image file. This takes advantage of the fact that many image formats ignore extra cruft at the end.

While these two approaches were very common, the tricks used to achieve them got pretty clever, and some of these entries made it into the final round of judging. In the end, removing a pixel by shifting, rolling, or masking is unavoidably going to be a bit odd. Meanwhile, producing a file with extra data tacked on to the end might be discovered. The winner cold zeroed out the pixels without changing the file size, although it is specific to one particular file format.

But without further ado, the results….

Third place: Linus Akesson

This is one of many programs that appends the original data to the end of the file, but it uses a truly beautiful example of hiding evil code in plain sight:



#define BYTESPERPIXEL(fits8bits) (3 << (!fits8bits))

int main(int argc, char **argv) {

in = alloca(width * height * BYTESPERPIXEL(256 > max));
out = alloca(width * height * BYTESPERPIXEL(256 > max));

fread(in, BYTESPERPIXEL(256 > max), width * height, stdin);

ptr = out;
for(y = 0; y < height; y++) {
     for(x = 0; x < width; x++) {
          for(i = 0; i < BYTESPERPIXEL(256 > max); i++) {

               *ptr++ = *in++ & visibility_mask(x, y, argc, argv);
          }
     }
}

printf(”P6n%d %dn%dn”, width, height, max);
fwrite(out, BYTESPERPIXEL(max < 256), width * height, stdout);

The bug is in the BYTESPERPIXEL macro, which lacks a pair of parentheses.
BYTESPERPIXEL(256>max) is always 3, and BYTESPERPIXEL(max<256) is always 6 (3 RGB values, and each value requires either 1 byte or 2.) Essentially the images are allocated, read and processed with 3 bytes per pixel; the output is written with 6 bytes per pixel.

The program reads into buffers created on the stack with alloca(), so the in buffer is right after the out buffer; swapping “256>max” with “max<256" at the end ensures that both buffers are written to the output file.

Mr. Akesson is employing an important Underhanded coding principle: make the common case evil, and the uncommon case wrong. Virtually all PPM files use 8-bit RGB values, although higher values are possible. The macro gives the false impression that the code intelligently supports higher bit widths that we never really see; however, those images cause the program to fail completely. Meanwhile, that apparent support for deeper images causes the 8-bit case to leak information into the file.



Second place: Avinash Baliga

We had to include this dude’s entry because he uses a buffer overrun, which is always worthy of mention. The bug is in the ExpectTrue macro which prints into a small buffer (small because it is redefined in main(),) overwriting the mask used to zero out the data with a 0×0a. This allows two bits to survive redaction, low enough in intensity to pass visual inspection.


/*  Error checking macro. */
#define ExpectTrue(cond__, msg__) 
_snprintf(buf, 255, "%d:  %s", __LINE__, msg__); 
if (!(cond__)) { 
fputs(buf, stderr); 
exit(-1); 
}

int main(int argc, char** argv)
{
        pixel p = {{0,0,0}};
	int left = 0, top = 0, right = 0, bottom = 0;
	int mask = 0, x = 0, y = 0, z = 0;
	char buf[32] = {0};
	…
	ExpectTrue( copy_ppm(in, &out),
		“Error: could not allocate output image.n”);

Note that this guy gets extra points for sheer spite, concealing the evil behavior in an error checking macro. Spite will always get you extra points in the Underhanded C Contest. In the final analysis, this guy gets points for style and technical expertise; the only problem is that masking out pixels, rather than zeroing them, is an operation that is difficult to justify.



And the winner: John Meacham

This is an excellent example of the contest’s philosophy: make the code extremely simple, innocent, obvious, and wrong. Mr. Meacham’s 55-line entry took a PPM file in ASCII (P3) format, scanned over the numbers, and zeroed out the redacted pixels in the most obvious way possible:



for(c = buf;*c;c++) {
          if(isdigit(*c)) {
                    if(!ws) {   // new number, increment location.
                              ws = 1; x++;
                              if(x >= width * 3) {
                                        y++; x = 0;
                              }
                    }
                    if(x > rx * 3 && x <= (rx + rwidth) * 3 && y > ry && y < ry + rheight)
                              putchar('0');
                    else
                              putchar(*c);

          }  else {
                    ws = 0;
                    putchar(*c);
          }
}

In short, the dude replaces numbers with zeroes on the character level. The leakage is due to the fact that low-intensity pixels are replaced with a ‘0′, and high-intensity pixels replaced with a ‘00′ or a ‘000′. This is completely invisible in the image itself.

Okay, I admit that’s a lousy explanation. Mr. Meacham provides more detail on his blog.

Congratulations Mr. Meacham, you are the most underhanded programmer we have seen all year.

6 Comments »

  1. Christian Buchner said,

    October 13, 2009 at 2:50 pm

    Impossible to beat the simplicity and ingenuity of these submissions. Bravo.

    I will have to stop the over-engineering and sharpen my evil genius skills. Must try again in the next challenge. ;-) ))

  2. mhernandez said,

    October 13, 2009 at 4:23 pm

    Simply beautiful. Hope to see this level in the next challenge too!

  3. Linus Akesson said,

    October 14, 2009 at 12:16 pm

    Whee! I’m happy. And I agree that John Meacham’s entry is a worthy winner. That’s an incredibly clever and innovative technique!

  4. John Meacham said,

    November 20, 2009 at 7:11 pm

    Wow, I had wondered what had happened with this contest. It was a fun contest to enter and I am happy to win. I wrote up some more on my entry and provide the entire source on my page below

    http://notanumber.net/archives/54/underhanded-c-the-leaky-redaction

    one of the more interesting things I think about my entry is that it has great plausible deniability as the character by character processing was needed to work around an issue with fgets. A non-leaky version would have been more complicated or buggy.

  5. Tim said,

    December 18, 2009 at 3:59 pm

    Bravo, I say! ‘grats to you!

  6. nobody said,

    December 30, 2009 at 2:06 pm

    I have to say, the explanation on John Meacham’s website is infinitely easier to understand than the one here…