Monday, June 16, 2008

Underhanded C Programming

A couple days ago, Slashdot posted a link to The Underhanded C Contest. The idea is to write a program that redacts part of an image while making it possible to recover the lost information. The trick: it has to look innocent to another programmer reviewing your code.

My first version has the following output:


Here's the pertinent part of the code:

Redact to black (the "right" way):

p.rgb[R] = 0;
p.rgb[G] = 0;
p.rgb[B] = 0;

Redact to random noise (an acceptable way, see image on right):

p.rgb[R] = rand();
p.rgb[G] = rand();
p.rgb[B] = rand();

Nefarious redaction to random noise (see image on right):

p.rgb[R] ^= rand();
p.rgb[G] ^= rand();
p.rgb[B] ^= rand();

The key is using "^=" rather than just "=". The "^" will perform a bitwise XOR, and XOR has an interesting property. If you XOR A with B, and XOR the result by B a second time, you get back A.

So all we have to do to get the proper image back again is use the same sequence of random numbers, and that's easier than it sounds. It's customary to seed the random number generator using the following code:

srand((unsigned int)time(0));

But the file we're spitting out has the timestamp it was created--the exact time we're using as the seed in our RNG!

(If you're worried about the timestamp changing as the file is copied and passed around, then simply embed the time as a comment in the file--not nefarious at all.)


Xirax said...

Pretty good :)
I'm not sure that random's seed will exactly match your file timestamp creation, did you test it?

The Writer said...

Unless your program takes longer than a second to run (very slow computer, or very large file) it should match exactly.

If it doesn't, then simply run the program for nearby timestamps, give or take a few seconds.

However, an experiment showed it worked perfectly. "stat output.ppm" showed a modification date of "2008-06-16 17:02:08". That's a UNIX timestamp of 1213657328. Using that as the seed of my RNG and running the program over the redacted version resulted in the original version returning.