2008
This year’s challenge: leaky redaction
The object of this year’s contest: write a short, simple C program that redacts (blocks out) rectangles in an image. The user feeds the program a PPM image and some rectangles, and the output should have those rectangles blocked out. Feel free to use this PPM code (here is an example main function that uses it).
[Note: “blocked out” means “replaced with non-image.” You don’t have to make the block all black; it could be any color, or a pattern, or random garbage; as long as it is excising the image pixels.]
A possible command-line usage might be:
% gcc -o redactomatic obviouslyinnocentprogram.c
% redactomatic in.ppm > out.ppm
10 14 121 44
10 60 121 90
10 104 121 134
^D% redactomatic scan.ppm < redactions.txt > newscan.ppm
The challenge: write the code so that the redacted data is not really gone. Ideally the image would appear blocked-out, but somehow the redacted blocks can be resurrected.
The removed pixels don’t have to be perfectly reconstructable; if a very faint signal remains, that’s often good enough for redacted document scans. Indeed, an attacker may know that a redacted block might be one of two words, and any tiny bit of leakage that helps her determine which is more likely is technically a valid attack. However, more points are given for greater pixel leakage.
Extra points were handed out for the following reasons:
- Extra points if the error, once found, looks like an innocent bug rather than deliberate miscoding.
- Extra points if your code still appears innocent under syntax coloring.
- Extra points if the information leakage is dramatic.
2008 Winners
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.
Congratulations Mr. Meacham, you are the most underhanded programmer we have seen all year.