Score 3
Link http://assets.shallweplayaga.me/linked.txt

This challenge was very simple in itself and didn’t involve reversing a binary or finding a vulnerability :

 typedef struct _llist {
   struct _llist *next;
   uint32_t tag;
   char data[100];
 llist;

and:

register char *answer;
char *(*func)();
llist *head;
...
func = (char *(*)(llist *))userBuf;
answer = (char *)(*func)(head);
send_string(answer);
exit(0);

Write me shellcode that traverses the randomly generated linked list, looking
for a node with a tag 0x41414100, and returns a pointer to the data associated
with that tag, such that the call to send_string will output the answer.

We began connecting to the server and experimenting a few things in order to determine the architecture, maximum length and other information required to write this shellcode.

The service clearly advised that the maximum length was 16 bytes when one sent a longer packet. We quickly narrowed the architecture to bare x86, and, if we thought the shellcode had to be NULL-free at first, we quickly discovered that it needn’t.

So we gave it a first shot, using a few tricks in order to use the lowest number of bytes, but could not squeeze it to less than this shellcode which is 20 bytes-long :

pop edx ; return address
pop ebx ; linked-list head

push 0x41414100
pop edi

myloop:
mov ebx, [ebx]
cmp [ebx + 4], edi
jnz myloop

lea eax, [ebx + 8] ; mov eax, ebx + 8
jmp edx

So we began experimenting with shellcodes that did not fully respect the subject but could get us a close-enough result to retrieve the flag. We first tried to test that the second lowest byte was 0x41, but this was not restrictive enough to get the flag, so we tried matching 0x4100.

To do that in less than 16 bytes, we had to replace our two first pops by a popa which is only 1 byte-long but may totally destroy the stack frame. But since the function that calls our shellcode never returns, as shown in the subject, we don’t really care.

The final result is:

popa ; edi = return addr, esi = linked-list head

myloop:
mov esi, [esi]
cmp word [esi + 4], 0x4100
jnz myloop

lea eax, [esi + 8]
jmp edi

And we were quite surprised that it worked on the first try. One funny thing to note is that the key it gave us was:

The key is: Who says ESP isn't general purpose!?!?

Hmm, I guess our solution was not the intended one…

For reference, the intended solution, given by an organizer (gynophage) at the end of the CTF was:

mov eax,0x41414100
pop ebx
pop ebp

leave
mov edi,esp
scasd
jnz 0x7

xchg eax,edi
call ebx