VSzA techblog

DEF CON 20 CTF urandom 300 writeup


As a proud member of the Hungarian team called “senkihaziak”, I managed to solve the following challenge for 300 points in the /urandom category on the 20th DEF CON Capture The Flag contest. The description consisted of an IP address, a port number, a password, and a hint.

Description of the challenge

Connecting with netcat to the specified IP address and port using TCP resulted in a password prompt being printed. After sending the password followed by a newline triggered the server to send back what seemed to be an awful lot of garbage, screwing up the terminal settings. A closer inspection using Wireshark revealed the actual challenge.

Network traffic after connecting and sending the password

Brief analysis of the network traffic dump confirmed that after about 500 bytes of text, exactly 200000 bytes of binary data was sent by the service, which equals to 100000 unsigned 16-bit numbers (uint16_t). As the text said, both the time and the number of moves to sort the array in-place was limited, and while I knew that quicksort is unbeatable in the former (it took 35 ms to sort the list on my 2.30GHz Core i3), I knew little to nothing about which algorithms support in-place sorting, and of those, which one requires the least number of exchanges.

KT came up with the idea of building a 64k long array to store the number of occurences of each index, filling it during reading, and iterating over it to achieve the sorted array. While this was a working concept in itself, it didn't give me what the challenge wanted – pairs of indices to exchange in order to reach the sorted state. To overcome this, I improved his idea by storing the position(s) on which the index occurs in a linked list insted of just the number of occurences. For easier understanding, here's an example of what this array of linked lists would look like on an array of 7 numbers.

Example of an array of linked lists

Since performance mattered, I chose C and began with establishing the TCP connection and handling the login.

#define PW "d0d2ac189db36e15\n"
#define BUFLEN 4096
#define PWPROMPTLEN 10

int main() {
  int i, sockfd;
  struct sockaddr_in serv_addr;
  char buf[BUFLEN];

  sockfd = socket(AF_INET, SOCK_STREAM, 0);
  memset(&serv_addr, '0', sizeof(serv_addr));

  serv_addr.sin_family = AF_INET;
  serv_addr.sin_port = htons(5601);
  inet_pton(AF_INET, "", &serv_addr.sin_addr);

  connect(sockfd, (struct sockaddr *)&serv_addr, sizeof(serv_addr));
  for (i = 0; i < PWPROMPTLEN; i += read(sockfd, buf, BUFLEN));
  write(sockfd, PW, strlen(PW));

After login, there was 504 bytes of text to ignore, and then the numbers were read into an array.

#define MSGLEN 504
#define NUMBERS 100000

uint16_t nums[NUMBERS];

for (i = 0; i < MSGLEN; i += read(sockfd, buf, MSGLEN - i));
for (i = 0; i < NUMBERS * sizeof(uint16_t);
  i += read(sockfd, ((char*)nums) + i, NUMBERS * sizeof(uint16_t) - i));

After the numbers were available in a local array, the array of linked lists was built. The end of a linked list was marked with a NULL pointer, so the array was initialized with 0 bytes;

typedef struct numpos {
  int pos;
  struct numpos *next;
} numpos_t;

numpos_t *positions[MAXNUM];

memset(positions, 0, MAXNUM * sizeof(void*));
for (i = 0; i < NUMBERS; i++) {
  numpos_t *newpos = malloc(sizeof(numpos_t));
  newpos->next = positions[nums[i]];
  newpos->pos = i;
  positions[nums[i]] = newpos;

The heart of the program is the iteration over this array of lists. The outer loop goes over each number in ascending order, while the inner loop iterates over the linked lists. An auxiliary counter named j tracks the current index on the output array. Inside the loops the current number is exchanged with the one at the current index in the original array, and the positions array of linked lists is also changed to reflect the layout of the output array.

int n, j = 0;
numpos_t *cur, *cur2;

for (n = 0; n < MAXNUM; n++) {
  for (cur = positions[n]; cur != NULL; cur = cur->next) {
    if (cur->pos != j) {
      sprintf(buf, "%d:%d\n", cur->pos, j);
      write(sockfd, buf, strlen(buf));
      tmp = nums[j];
      nums[j] = n;
      for (cur2 = positions[tmp]; cur2 != NULL; cur2 = cur2->next) {
        if (cur2->pos == j) {
          cur2->pos = cur->pos;
      nums[cur->pos] = tmp;

Finally, there's only one thing left to do: send an empty line and wait for the key to arrive.

write(sockfd, "\n", 1);
while (1) {
  if ((i = read(sockfd, buf, BUFLEN))) {
    buf[i] = '\0';
    printf("Got %d bytes of response: %s\n", i, buf);

After an awful lot of local testing, the final version of the program worked perfectly for the first time it was ran on the actual server, and printed the following precious key.

Result of the successful run, displaying the key


next posts >
< prev post

Proudly powered by Utterson