CTF 2006 Prequal Walkthrough: Binary Leetness
This category was like Pwnage-lite. You had to do a good bit of digging around in assembly, but with an eye towards intended function instead of UN-intended function. This gave it a nice flavor very different from the Pwnage challenges.
100: Demangling
Having experience with what compiled C++ looks like, and restating the challenge question into a more clear goal helped a lot. Another way to put it would be "demangle the function declarations in this executable and find the name of the Class that implements 'operator='".
The executable was PPC, and unstripped. If we'd had our PPC binutils at the time, we could have just asked "nm" to demangle the function names for us, using the "-C" option. Another tool, "c++filt", will also do C++ demangling. We just had to feed it the function names. So without our native binutils (or cross-compilers), we just cheated and used "strings" and "c++filt":
$ strings rtti | grep ^__Z | cut -c2- | c++filt -n | grep 'operator=('
Bazlicious::operator=(Bazlicious)
200: Unstripped labels
Besides determining the executable architecture, it can be good just to see how the program behaves. Finding what external library functions it will use is a good clue to estimate its capabilities. Running "objdump -R calvin" showed only simple utility calls and text I/O routines (exit, puts, printf, atoi).
Running "calvin" showed it was doing some kind of array look-up and printing a quote. (It would segfault if you gave it a too large, or negative, index.)
Before really diving into a disassembly, it can be a good idea to look at global variables ("objdump -t"), especially when the executable isn't stripped. In calvin's case, there was a rather enticing global named "keyoffset":
$ objdump -t calvin | grep '\.data' | grep -v 00000000
0804cba0 g     O .data  000001f4              calvin
0804cd94 g     O .data  00000004              keyoffset
Loading up gdb and displaying this value gave us the answer:
$ gdb ./calvin
...
(gdb) print keyoffset
$1 = 114
(gdb) quit
$ ./calvin 114
Dictator For Life, Calvin wants you to know:
This game lends itself to certain abuses.--- Calvin
300: Scrambled validation
The clues from "objdump -R" showed this executable to be using expected calls for a daemonizing network server. Some interesting stuff slightly outside the scope of a plain network daemon were the calls to "getenv", and "rand".
Using the disassembler of our choice, we followed the flow of execution through watching it setting up signal handlers, daemonizing, reading stuff out of the environment variable "KKEY", seeding the random number generator, binding to port 7756, listening, and finally sitting in an "accept" call waiting for incoming connections.
We identified the "client handler" function that got called after an "accept" returned, noting it was the only place "read" and "write" are called from. Tracing the output, and what it did with input, we constructed the following chain of expected events for a connection lifetime:
Studying "permuteC", we found it just wanted to see the string "GIMME".
Studying "permuteB", we found it was testing that every 3 bytes in the string of 0x17 bytes each had odd values. (Though, it seemed that leaving higher bytes at 0 was a good idea.) So, 8 triplets of value "1".
Studying "random_permute" gave us a headache, so we just ripped it out of the disassembly, made an assembler "random_permute.s" file out of it, and tacked it on to our C network client:
/* Run as "./client300 kenshoto.allyourboxarebelongto.us 7756" */
#include <stdio.h>
#include <sys/types.h>
#include <sys/socket.h>
#include <netinet/in.h>
#include <netdb.h> 
#include <unistd.h>
#include <errno.h>

int sockfd;

extern random_permute( uint32_t current, uint32_t cycle );

unsigned char * gank(int count) {
    static unsigned char buffer[1025];
    int i, n;

    bzero(buffer,1025);
    n = read(sockfd,buffer,count);
    if (n < count) {
         if (errno == EINTR) return NULL;
    }

    printf("read %d/%d: ",n,count);
    for (i=0;i<n;i++) {
           printf("%02x ",buffer[i]);
    }
    printf("\n");
    return buffer;
}

int shove(int len, unsigned char * data)
{
    int i;

    printf("write: %d: ",len);
    for (i=0;i<len;i++) {
        printf("%02x ",data[i]);
    }
    printf("\n");
    return write(sockfd,data,len);
}

int main(int argc, char *argv[])
{
    int portno, n;
    struct sockaddr_in serv_addr;
    struct hostent *server;

    unsigned char buffer[256];
    if (argc < 3) {
       fprintf(stderr,"usage %s hostname port\n", argv[0]);
       exit(0);
    }
    portno = atoi(argv[2]);
    sockfd = socket(AF_INET, SOCK_STREAM, 0);
    if (sockfd < 0) {
        perror("socket");
        exit(1);
    }
    server = gethostbyname(argv[1]);
    if (server == NULL) {
        fprintf(stderr,"ERROR, no such host\n");
        exit(0);
    }
    bzero((char *) &serv_addr, sizeof(serv_addr));
    serv_addr.sin_family = AF_INET;
    bcopy((char *)server->h_addr, 
         (char *)&serv_addr.sin_addr.s_addr,
         server->h_length);
    serv_addr.sin_port = htons(portno);
    if (connect(sockfd,&serv_addr,sizeof(serv_addr)) < 0)  {
        perror("connect");
        exit(1);
    }

    unsigned char response[] =
        "\xe0\x7e\x68\x5b" /* rand_permute */
        "\x00\x00\x01"  /* 8 triples of odds */
        "\x00\x00\x01"
        "\x00\x00\x01"
        "\x00\x00\x01"
        "\x00\x00\x01"
        "\x00\x00\x01"
        "\x00\x00\x01"
        "\x00\x00\x01"
        "GIMME"; /* 5 magic bytes */

    unsigned char * buf = gank(4);

    // start commenting here
    printf("\\x%02x\\x%02x\\x%02x\\x%02x\n",buf[0],buf[1],buf[2],buf[3]);
    uint32_t crc = random_permute( *((uint32_t*)buf), 0 );
    printf("CRC: \\x%08x\n",crc);

    *((uint32_t*)response)=crc;
    printf("\\x%02x\\x%02x\\x%02x\\x%02x\n",
           response[0],response[1],response[2],response[3]);
    // end commenting here

    uint16_t togo = 4+(8*3)+5;
    shove(2,&togo);
    shove(togo,response);

    buf = gank(1024);
    printf("%s\n",buf);
    return 0;
}
After playing with the client, we actually discovered that the "random_permute" function wasn't actually a CRC-like permute at all. It always produced the same output, regardless of input: "\xe0\x7e\x68\x5b". (As a result, you can comment out the call to random_permute above, as noted, and the client will still run correctly.)
400: Brute force wins
For this challenge, it seemed we needed to disassemble the encoder and figure out how to reverse it. We got as far as seeing that the executable was pushing an address in the (normally not disassembled) .got table onto the stack, so that returning from "main" would actually start execution of the encryption code. At that point, we had stopped reading assembly so we could watch an alternate approach that was almost done running: a brute force attack.
While feeding various strings into the encoder, it was observed that when the last character was changed and the string contained an odd number of characters, the output was only changed in the final byte. However, if the total number of characters were even, then the final two bytes of output were modified. From this, it was theorized that the encoder operated on byte pairs.
The encoded key's first byte pair was "\xf9\xef":
$ hexdump key.enc
0000000 f9ef 0942 1aa3 f743 8b8c 22bb c22a 14a3
0000010 0003                                   
Since prior keys were alphanumeric, we tried all alpha pairs, looking for a match on "f9ef":
#!/bin/bash
for char1 in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z; do
    for char2 in A B C D E F G H I J K L M N O P Q R S T U V W X Y Z a b c d e f g h i j k l m n o p q r s t u v w x y z; do
        echo -e "$char1$char2\t"`./encoder "$char1$char2"|hexdump|head -1`
    done
done
Running this, we see:
$ ./brute.sh | grep f9ef
BE      0000000 f9ef 0002
Be      0000000 f9ef 0003
This gave us the next piece of evidence that the encoding is strangely case-insensitive. That radically reduces (our already small) key space, and we can eliminate half the characters used in each cycle. Adjusting the script to use only lower case, we got no hits for the next two characters past "BE". Trying upper case also failed. We moved to using "Be" instead of "BE", and this time lower-case yielded results:
#!/bin/bash
for char1 in a b c d e f g h i j k l m n o p q r s t u v w x y z; do
    for char2 in a b c d e f g h i j k l m n o p q r s t u v w x y z; do
        echo -e "$char1$char2\t"`./encoder "Be$char1$char2"|hexdump|head -1`
    done
done
Producing:
$ ./brute.sh | grep 'f9ef 0942'
wi      0000000 f9ef 0942 0003
We continued in this fashion, uncovering "Bewitching", at which point no more letters worked, so we added a space to the mix, and found " S" as the next pair. Two more iterations, and we had a full match against "Bewitching Sexto":
$ ./brute.sh | grep 'f9ef 0942 1aa3 f743 8b8c 22bb c22a 14a3'
to      0000000 f9ef 0942 1aa3 f743 8b8c 22bb c22a 14a3
$ ./encoder "Bewitching Sexto" > key.guess
$ diff key.guess key.enc && echo pwnd
pwnd
500: Compressed static threads
The "file" output for this executable reported it was statically linked, so there were going to be no dynamic relocation clues to follow. It also mentioned "corrupted section header size", which was weird. "strings", however, gave us some answers:
...
$Info: This file is packed with the UPX executable packer http://upx.sf.net $
...
We downloaded UPX, and decompressed the executable. The new executable was still statically linked, but we could use "strings" to see the insanity it was linked against. The most obvious chunk seemed to be a full copy of OpenSSL.
Running the client, it reports the following and quits:
Calling Key Builder
Key was built in memory successfully
This means we've got to get a break-point into the program before it clears its memory (or exits), and then we need to find the key in memory.
We first find where the "Key was built..." string is located, and where it is used:
$ objdump -s -j .rodata ./RevEng500Client.uncompressed | grep "Key was"
 8187960 65720000 4b657920 77617320 6275696c  er..Key was buil
$ objdump -d ./RevEng500Client.uncompressed | grep -A1 8187964
 804834a:       68 64 79 18 08          push   $0x8187964
 804834f:       e8 40 12 0e 00          call   0x8129594
Now we set a break point just before (what we assume is) the "printf" call at address 0x804834f. However, the code runs without triggering the break point.
While messing around more with break points in other locations, we see that gdb has reported that the program is threaded. Since we're unable to stop at a break point we know is being called, we shift gears and tell gdb to follow the child thread instead of staying on the parent with the "set follow-fork-mode child" gdb command.
Now following the correct thread, we try again, this time stopping at 0x804834f. From here, we scan through memory, looking for the now-classic two-word key pattern:
(gdb) gcore
^Z
$ strings core.5919 | egrep '^[A-Z][a-z]+ [A-Z][a-z]+$'
Exhibitory Overproduction
Besides identifying important functions by looking for where arguments are being used, another way to deal with static binaries is to find all the "int 0x80" calls. These are the system calls for accessing low-level kernel interfaces. Since these are only the most basic of operations, it is much more limiting than being able to search for shared library calls.

ctf 2006 prequals