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.
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.
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.
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, "140.197.217.155", &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;
break;
}
}
nums[cur->pos] = tmp;
}
j++;
}
}
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.
