CSAW 2015 - wyvern (reversing 500) Writeup

Hint:

There's a dragon afoot, we need a hero. Give us the dragon's secret and we'll give you a flag.

Running this program, it looks like it's going to be a fairly standard crackme:

$ ./wyvern_c85f1be480808a9da350faaa6104a19b
+-----------------------+
|    Welcome Hero       |
+-----------------------+

[!] Quest: there is a dragon prowling the domain.
      brute strength and magic is our only hope. Test your skill.

Enter the dragon's secret: no

[-] You have failed. The dragon's power, speed and intelligence was greater.

Taking a look at it in Hex-Rays, we see that it's a C++ program that calls fgets to input the string, then creates a std::string out of it, before calling start_quest to see if you've input the right thing.

std::operator<<<std::char_traits<char>>(
  &std::cout,
  (unsigned int)"Enter the dragon's secret: ",
  "Enter the dragon's secret: ");
fgets(&s, 257, stdin);
std::allocator<char>::allocator(&v8, 257LL);
std::string::string(&v9, &s, &v8);
std::allocator<char>::~allocator(&v8);
std::string::string((std::string *)&v7, (const std::string *)&v9);
v3 = start_quest((std::string *)&v7);
std::string::~string((std::string *)&v7);
if ( v3 == 0x1337 )
{
  std::string::string((std::string *)&v6, (const std::string *)&v9);
  reward_strength((unsigned __int64)&v6);
  std::string::~string((std::string *)&v6);
}
else
{
  std::operator<<<std::char_traits<char>>(
    &std::cout,
    (unsigned int)"\n[-] You have failed. The dragon's power, speed and intelligence was greater.\n",
    v4);
}

The start_quest method does all kinds of stuff with std::vectors, the input string, and some static buffers. It also calls another method called sanitize_input that looks even less fun to try to make sense of.

I hate reversing compiled C++. Let's see if we can find any shortcuts to make this less painful... Running the program through ltrace, we can see that one of the last things it does (given this input) before cleaning up is to call std::string::length() const which returns the length of the input string:

$ echo no | ltrace -C ./wyvern_c85f1be480808a9da350faaa6104a19b 3>&1 >/dev/null 2>&3 | tail
memmove(0x8d1100, "d\0\0\0\326\0\0\0\n\001\0\0q\001\0\0\241\001\0\0\017\002\0\0n\002\0\0\335\002\0\0"..., 64) = 0x8d1100
operator delete(void*)(0x8d10b0, 0x6102f8, 0x7fff1b5eb0a0, 0x8d10b0) = 0
std::string::length() const(0x7fff1b5eb668, 1, 0xffffffff, 0) = 3
std::basic_string<char, std::char_traits<char>, std::allocator<char> >::~basic_string()(0x7fff1b5eb668, 0xffffffff, 0, 0) = 1
std::basic_ostream<char, std::char_traits<char> >& std::operator<< <std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*)(0x6101e0, 0x40e75c, 1, 0) = 0x6101e0
std::basic_string<char, std::char_traits<char>, std::allocator<char> >::~basic_string()(0x7fff1b5eb688, 0x40e700, 0x7fec595127d8, 0) = 0x8d1070
std::ios_base::Init::~Init()(0x610314, 0, 224, 0x7fec58d08d50) = 3
operator delete(void*)(0x8d1100, 0x6102f8, 0x7fff1b5eb510, 0x8d1100) = 1
std::ios_base::Init::~Init()(0x610310, 0, 160, 0x7fec58d08d10) = 0x7fec5952a100
+++ exited (status 0) +++

I'm gonna bet that the crackme is doing an initial length check and bailing since the input isn't the right length. To figure out the correct length, run the program under GDB, put a breakpoint on std::string::length() const and finish to get back to the calling scope.

   0x40469c <_Z11start_questSs+844>:  call   0x400f50 <_ZNKSs6lengthEv@plt>
=> 0x4046a1 <_Z11start_questSs+849>:  sub    rax,0x1
   0x4046a7 <_Z11start_questSs+855>:  mov    r9d,DWORD PTR ds:0x610138
   0x4046af <_Z11start_questSs+863>:  sar    r9d,0x2
   0x4046b3 <_Z11start_questSs+867>:  movsxd rcx,r9d
   0x4046b6 <_Z11start_questSs+870>:  cmp    rax,rcx

The call to the length method is at 0x4046a1. Then it subtracts one, presumably to remove the newline from the count, readies another value in rcx before comparing the string length to the value in rcx at 0x4046b6. Stepping down to the cmp and looking at the registers, we find the desired input length:

RAX: 0x2  # input length
RCX: 0x1c # desired input length

So the input to pass the crackme is 28 (0x1c) characters long.

At this point, I had a hunch that the program was checking the input character-by-character and I may be able to use a sidechannel to derive the password incrementally. I had never really done much with instruction counting, but a quick Google search showed that the callgrind tool in Valgrind would do the trick. A quick test confirmed my hunch and showed that the password began with "d":

$ for a in {a..z} {A..Z} ; do echo $a $(echo ${a}Aa0Aa1Aa2Aa3Aa4Aa5Aa6Aa7Aa8 | valgrind --tool=callgrind ./wyvern_c85f1be480808a9da350faaa6104a19b 2>&1 | grep Collected) ; done
a ==13480== Collected : 1511690
b ==13484== Collected : 1511690
c ==13488== Collected : 1511690
d ==13492== Collected : 1522020
e ==13499== Collected : 1511690
f ==13503== Collected : 1511690
g ==13507== Collected : 1511690
h ==13511== Collected : 1511690
i ==13518== Collected : 1511690
j ==13522== Collected : 1511690
k ==13526== Collected : 1511690
l ==13530== Collected : 1511690
m ==13534== Collected : 1511690
n ==13538== Collected : 1511690
o ==13542== Collected : 1511690
p ==13548== Collected : 1511690
q ==13552== Collected : 1511690
r ==13556== Collected : 1511690
s ==13560== Collected : 1511690
t ==13564== Collected : 1511690
u ==13568== Collected : 1511690
v ==13572== Collected : 1511690
w ==13576== Collected : 1511690
x ==13580== Collected : 1511690
y ==13584== Collected : 1511690
z ==13588== Collected : 1511690
A ==13592== Collected : 1511690
B ==13596== Collected : 1511690
C ==13600== Collected : 1511690
D ==13604== Collected : 1511690
E ==13608== Collected : 1511690
F ==13614== Collected : 1511690
G ==13618== Collected : 1511690
H ==13622== Collected : 1511690
I ==13626== Collected : 1511690
J ==13630== Collected : 1511690
K ==13634== Collected : 1511690
L ==13638== Collected : 1511690
M ==13642== Collected : 1511690
N ==13646== Collected : 1511690
O ==13650== Collected : 1511690
P ==13654== Collected : 1511690
Q ==13658== Collected : 1511690
R ==13662== Collected : 1511690
S ==13666== Collected : 1511690
T ==13670== Collected : 1511690
U ==13674== Collected : 1511690
V ==13680== Collected : 1511690
W ==13684== Collected : 1511690
X ==13688== Collected : 1511690
Y ==13692== Collected : 1511690
Z ==13696== Collected : 1511690

So I threw together the following solver script. For some unknown reason, callgrind occasionally gives a different value than expected. If the solver sees more than one outlier for a given character of the password, it throws away that loop's values and tries again.

solve.pl

 1 #!/usr/bin/perl
 2 
 3 use strict;
 4 use warnings;
 5 use diagnostics;
 6 use feature 'say';
 7 use Data::Dumper;
 8 
 9 my $len = 28;
10 my $prefix = '';
11 
12 while(length($prefix) < $len)
13 {
14       my %values = ();
15       for my $char_val ( 0 .. 255 )
16       {
17               my $char = chr($char_val);
18               next unless($char =~ /[[:print:]]/);
19               my $pw = $prefix . $char;
20               $pw .= '-' x ($len - length($pw));
21               $pw =~ s/'/'"'"'/g;
22               my $result = `echo '$pw' | valgrind --tool=callgrind ./wyvern_c85f1be480808a9da350faaa6104a19b 2>&1 | grep Collected`;
23               say $pw;
24               if($result =~ /Collected : (\d+)/)
25               {
26                       push @{$values{$1}}, $char;
27               }
28       }
29       my @possibilities = map { $_->[0] } grep { scalar(@$_) == 1 } values %values;
30       if(scalar(@possibilities) != 1)
31       {
32               print Dumper(\@possibilities);
33               say "not a single outlier";
34       }
35       else
36       {
37               $prefix .= $possibilities[0];
38       }
39 }
40 say "Password: $prefix";

The script runs for a while, printing out all the passwords it attempts. As an aside, I absolutely love TV-style hacking scripts that find the answer character-by-character. The script eventually settles on the flag:

Password: dr4g0n_or_p4tric1an_it5_LLVM

Posted on Oct. 14, 2015, 11:48 a.m. by tecknicaltom