Creating a keygen for the Twisted Road to Despair

#What’s this about?
Hello everyone, I’m Noswis. You might have already met me on IRC but this my first real post here! In this post I want to show you how I made a key-generator for a puzzle that @0x00pf created. I learned a lot from the puzzle that I’d like to share with you and I hope you will learn a lot in the process as well. The format of the puzzle is pretty simple, you’re asked for a name and a key and the program either responds with success or failure.

For those interested, the puzzle can be found here: [KEYGEN] The Twisted Road to Despair.

Author Assigned Level: Newbie/Wannabe

Community Assigned Level:

  • Newbie
  • Wannabe
  • Hacker
  • Wizard
  • Guru

0 voters

Required Skills

I will skip over a lot of details to keep this article readable so you might need some background knowledge of the following things to understand what I’m talking about:

  • x86-64 assembly
  • C Programming language
  • Bitwise operations

Some stuff:

  • If you want to solve this puzzle yourself I recommend you to stop reading now because this will contain a lot of spoilers.
  • I’m in no means an expert in this field so I will definitely make mistakes, please tell me if you spot one. This way we can both learn!

Getting to know the program

We start off with checking what kind of file it is.

$  file TRtD
TRtD: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), statically linked, stripped

Nothing crazy here, pretty much as expected. Note that the file is statically linked and stripped, this means that we will not have any symbols or external function calls. Every function that the program needs is already included in the executable.

The next step is to run the program.

$ ./TRtD
The Twisted Road to Despair
by p1co

Enter Username (min 10 char): noswisnoswis
Enter Key: ourkey123
Keep Trying

It seems the program needs a minimum of 10 characters, let’s keep this in mind. We can’t learn much more from this so it’s time to open up a decompiler. I used Radare2 for this in case you were curious.

The Title

We recognize the title of the puzzle in the assembly, this is a good place to start looking.

0x00400183    bf952d4000   mov edi, str.TheTwistedRoadtoDespair
0x00400188    e8610b0000   call fcn.00400cee
0x0040018d    bfba2d4000   mov edi, str.EnterUsernamemin10char
0x00400192    31c0         xor eax, eax
0x00400194    e8960a0000   call fcn.00400c2f

The username

Right after the previous snippet we see a function call:

0x004001a0    4889e7       mov rdi, rsp
0x004001a3    be00040000   mov esi, 0x400
0x004001a8    e897080000   call fcn.00400a44

The previous function prompted the user to type in his/her name, so this should be a scan function. Besides that, there are more clues to what this function does. We see the value of rsp is moved to rdi, this means that the user input will be stored at the current position of the stack pointer. The value passed into esi is the input buffer, this is the maximum amount of memory that the program reserves for the username.

      0x004001c2    4183fd09     cmp r13d, 0x9
      0x004001c6    c6040400     mov byte [rsp+rax], 0x0
  ,=< 0x004001ca    7f16         jg 0x4001e2
  |   0x004001cc    488b353d3e2. mov rsi, [rip+0x203e3d]
  |   0x004001d3    bfd92d4000   mov edi, str.Usernametoshort...tryagain...
  |   0x004001d8    e8da080000   call fcn.00400ab7
  |   0x004001dd    4489e0       mov eax, r12d
,===< 0x004001e0    eb71         jmp loc.00400253
| `=> 0x004001e2    4889e7       mov rdi, rsp
|     0x004001e5    e826010000   call fcn.00400310

I left out some code that calculated the length of the username, this length is stored in the r13 register and compared with 0x9. As you might have already guessed, this code snippet checks if the username is minimally 10 characters long. If this is not the case, the program prints out “try again” and jumps out of the function. Note that when the username is the correct length, it skips this whole part and goes traight to the function call at the bottom of the snippet. This function turns out to be very important, as you will see later on.

The key

Moving on to the next part, we see something that looks very familiar.

0x004001ea    bffc2d4000   mov edi, str.EnterKey
0x004001ef    31c0         xor eax, eax
0x004001f1    e8390a0000   call fcn.00400c2f
0x004001f6    488b15733e2. mov rdx, [rip+0x203e73]
0x004001fd    be00040000   mov esi, 0x400
0x00400202    4889ef       mov rdi, rbp
0x00400205    e83a080000   call fcn.00400a44

It basically looks like the part that asks for the username. The big difference is that the key will not be stored in the location pointed to rsp but by the rbp. Cool, now we know where both our username and our key is stored.

Validation

This is perhaps the most interesting part as a reverser; the decision point.

    0x00400231    e84c000000   call fcn.00400282
    0x00400236    85c0         test eax, eax
    0x00400238    bf082e4000   mov edi, str.WellDone
,=< 0x0040023d    7405         jz 0x400244
|   0x0040023f    bf142e4000   mov edi, str.KeepTrying
`-> 0x00400244    e8a50a0000   call fcn.00400cee

After the function call the returned value in eax is tested. If eax equals zero, the string “Well Done” is loaded in edi and it then skips over the instruction that overrides this string with “Keep Trying”. So, to get “Well Done” printed on the screen we need this function to return zero. We will analyze this function thoroughly in the next section.

The Validation Function

A few lines before the function call that validates the name/key pair, we see these two instuctions.

0x00400218    4889e7       mov rdi, rsp
0x0040021b    4889ee       mov rsi, rbp

These registers contain the pointer to the two strings that are passed on to the function. Recall from earlier that the username and key are both stored in a buffer pointed to by the rsp and rbp respectively. Let’s rerun the program with the same input as we did at the start of the article.

:> px 0x10 @ rdi
- offset -       0 1  2 3  4 5  6 7  8 9  A B  0123456789AB
0x7fffe309ada0  6a6b 7177 6777 6e6f 7f73 6573  jkqwgwno.ses
0x7fffe309adac  0000 0000                      ....

:> px 0x10 @ rsi
- offset -       0 1  2 3  4 5  6 7  8 9  A B  0123456789AB
0x7fffe309b1a0  7468 6973 6973 6d79 6b65 790a  thisismykey.
0x7fffe309b1ac  0000 0000                      ....

Interesting, we see that the key is still the same, but the username seems to be scrambled. It turns out that there is a function that scrambles the username to this form after the name is given by the user. We will take a closer look at how that function works later on. We will first figure out the validation function works.

Now that we now what parameters are passed on, we can jump into the function.

       0x00400282    4156         push r14
       0x00400284    31c0         xor eax, eax
       0x00400286    4883c9ff     or rcx, 0xffffffffffffffff
       0x0040028a    4155         push r13
       0x0040028c    4989fd       mov r13, rdi
       0x0040028f    4889f7       mov rdi, rsi
       0x00400292    4154         push r12
       0x00400294    4989f4       mov r12, rsi
       0x00400297    55           push rbp
       0x00400298    53           push rbx                      ; The part above basically boils down to:
       0x00400299    89d3         mov ebx, edx                  ; The name is moved to r13 and the key to r12
       0x0040029b    4883ec10     sub rsp, 0x10
       0x0040029f    f2ae         repne scasb
       0x004002a1    48f7d1       not rcx
       0x004002a4    8d41ff       lea eax, [rcx-0x1]
       0x004002a7    b902000000   mov ecx, 0x2
       0x004002ac    99           cdq
       0x004002ad    f7f9         idiv ecx
       0x004002af    8d7801       lea edi, [rax+0x1]
       0x004002b2    89c5         mov ebp, eax
       0x004002b4    4863ff       movsxd rdi, edi
       0x004002b7    e893010000   call fcn.0040044f             ; Only succeeds if the key is twice
       0x004002bc    39dd         cmp ebp, ebx                  ; the length of the name
   ,=< 0x004002be    7539         jnz 0x4002f9
   |   0x004002c0    4989c6       mov r14, rax
   |   0x004002c3    31db         xor ebx, ebx
 .---> 0x004002c5    488d3c1b     lea rdi, [rbx+rbx]
 | |   0x004002c9    4c01e7       add rdi, r12
 | |   0x004002cc    39dd         cmp ebp, ebx
 |,==< 0x004002ce    7e30         jle 0x400300
 |||   0x004002d0    488d54240c   lea rdx, [rsp+0xc]
 |||   0x004002d5    31c0         xor eax, eax
 |||   0x004002d7    be902d4000   mov esi, str.02x              ;  Passing on a format specifier
 |||   0x004002dc    e8c8030000   call fcn.004006a9
 |||   0x004002e1    8b54240c     mov edx, [rsp+0xc]            ; Output of the function moved in edx
 |||   0x004002e5    410fbe441d00 movsx eax, byte [r13+rbx]     ; Takes a character the name indexed by rbx
 |||   0x004002eb    4188141e     mov [r14+rbx], dl
 |||   0x004002ef    0fb6d2       movzx edx, dl
 |||   0x004002f2    48ffc3       inc rbx                       ; Increase the rbx counter                
 |||   0x004002f5    39c2         cmp edx, eax
 `===< 0x004002f7    74cc         jz 0x4002c5
  |`-> 0x004002f9    b801000000   mov eax, 0x1
,====< 0x004002fe    eb02         jmp 0x400302
| `--> 0x00400300    31c0         xor eax, eax
`----> 0x00400302    4883c410     add rsp, 0x10
       0x00400306    5b           pop rbx
       0x00400307    5d           pop rbp
       0x00400308    415c         pop r12
       0x0040030a    415d         pop r13
       0x0040030c    415e         pop r14
       0x0040030e    c3           ret

As you can see, the function is quite complex. Fortunately, we do not really need to understand every aspect of it. One of the first things that I noticed is that the string “02x” was passed on to a function in the esi register. This is a format specifier to use two digits. There is another function call here (call fcn.0040044f) that only succeeds if the key is twice the length of the name.

Okay, let’s throw in a key that has the same length as the name “noswisnoswis” (length 12), say “abcdabcdabcdabcdabcdabcd” (length 24) and focus on this part:

0x004002d7    be902d4000   mov esi, str.02x
0x004002dc    e8c8030000   call fcn.004006a9
0x004002e1    8b54240c     mov edx, [rsp+0xc]           ; Output of the function moved in edx
0x004002e5    410fbe441d00 movsx eax, byte [r13+rbx]    ; Takes a character the name indexed by rbx
0x004002eb    4188141e     mov [r14+rbx], dl
0x004002ef    0fb6d2       movzx edx, dl
0x004002f2    48ffc3       inc rbx                      ; Increase the rbx counter
0x004002f5    39c2         cmp edx, eax

Let’s take a look at the part after the function call. We see that a value is moved in the edx, what could this be?

171 0xab 0253 171 0000:00ab 171 "\xab" 10101011

Hmm, it looks like the first two characters of our key, but it is converted into hex. In fact, when we go to the next iteration of the loop, we encounter the value 0xcd in edx. The edx is subsequently compared the corresponding character in the mangled name. If both are the same, the function continues, if they are not the same, the function exits with a 1 in eax (recall that we need it to exit with 0).

So, what it comes down to is that two characters in the key are compared with one character in the mangled name. The function in the above snippet converts our ASCII key to the hex representation, for example, the string “ab” becomes 0xab. This value should be the same as the ASCII number of the character in the name.

This gives that the name “noswis” should have the corresponding key “6e 6f 73 77 69 73” (without the spaces). However, note that our original name was mangled, so we need the hexadecimal representation of the mangled name instead of our original name. Fortunately, we can easily get the hexadecimal representation from within radare since the mangled name is stored in r13:

:> px 0x10 @ r13
- offset -       0 1  2 3  4 5  6 7  8 9  A B  C D  E F  0123456789ABCDEF
0x7ffcae1c1de0  6a6b 7177 6777 6e6f 7f73 6573 0000 0000  jkqwgwno.ses....
:> 

Nice, we can just copy the hexadecimal representation from memory and give the program another shot

The Twisted Road to Despair
by p1co

Enter Username (min 10 char): noswisnoswis
Enter Key: 6a6b717767776e6f7f736573
Well Done!

Awesome! We still have a problem though. We need to be able to generate the mangled name from the normal name without having to run the debugger and copying it from memory. This is what we’ll do in the next section.

Creating the keygen

Let’s take a look at the function that mangles the name.

0x00400310      5a             pop rdx
0x00400311      53             push rbx
0x00400312      4831c0         xor rax, rax
0x00400315      4831db         xor rbx, rbx
0x00400318      8a07           mov al, byte [rdi]
0x0040031a      3c00           cmp al, 0
0x0040031c      742e           je 0x40034c
0x0040031e      88c3           mov bl, al
0x00400320      4088f9         mov cl, dil
0x00400323      30cb           xor bl, cl
0x00400325      80e303         and bl, 3
0x00400328      48d1e3         shl rbx, 1
0x0040032b      ff24dd500340.  jmp qword [rbx*8 + 0x400350]
0x00400332      6839034000     push 0x400339
0x00400337      c3             ret

There is something strange going on, there is a jump that depends on the value in rbx.

0x0040031e      88c3           mov bl, al   ; The last byte in rax is moved in bl
0x00400320      4088f9         mov cl, dil  ; Last byte of dil is moved in cl
0x00400323      30cb           xor bl, cl   ; We xor the two bytes cl and bl
0x00400325      80e303         and bl, 3    ; And we keep the last 3 bits, rest zeroes
0x00400328      48d1e3         shl rbx, 1   ; Then we do shift left

There are some bitwise operation which determine what value rbx takes. Look at the ‘and’-operation between bl and 3. This means that the only the last two bits of rbx matter. This gives that rbx has the values 0, 2, 4 or 6 (due to shl 1). When we calculate the address to where the jump will be taken for each value of rbx, we don’t see any real instructions. I suspect that radare does not recognize the instructions because they are not properly aligned or something (I would love to take a look at the sourcecode and see what caused this). Fortunately, when we run the program we can see where the flow of the program continues after the jump.

Since the values of rbx are so limited, we can quite easily make a table of what happens for every value of rbx

| Value of rbx | Operation            |
|--------------|----------------------|
| 0            | "nothing"            |
| 2            | sub al, bl           |
| 4            | xor al, bl           |
| 6            | shl bl, 1            |
|              | xor al, bl           |

After every operation, the byte pointed to by rdi is set to al. In this case, the rdi register points to current character, this means that only the current character gets altered. Finally, the value of rdi is increased by one, meaning that we move on to the next character. We do this until we have had every character in the name.

Now we know every operation, we can create a switch statement in c which handles the different values of rbx.

switch(rbx) {
  case 0:
      // Do nothing
      break;
  case 2:
      name[i] = name[i] - rbx;
      break;
  case 4:
      name[i] = name[i] ^ rbx;
      break;
  case 6:
      name[i]= (rbx << 1) ^ name[i];
      break;
  default:
      printf("Unexpected value encountered");
      return 1;
}

The only thing left is calculating the rbx in C. The code below loops over every character in the name and changes it according to the rbx value. It’s all fairly straightforward and clear from the disassembly. There was a tricky part though that I overlooked initially. See, the instruction ‘mov cl, dil’ moves the last byte of rdi in the cl register. I did not realise that the rdi value would increase by one in every iteration since the rdi points to the character that is currently being modified. This caused the value in cl to change as well and therefore changing the value of rbx in turn.

char *name = argv[1];

int j = 0xc0; // The last byte of rdi
for (int i = 0; i < strlen(name); i++) {
    char rbx = name[i];
    rbx = rbx ^ j;
    rbx = rbx & 3;
    rbx = rbx << 1;

    /* 
      The switch statement 
       ...
    */
    j += 1;
}

Now we have everything we need (I let some uninteresting stuff out though). Let’s compile the program and generate some keys!

./keygen letscreateakey
6c6570736f7e696574656d6b6379
./TRtD
The Twisted Road to Despair
by p1co

Enter Username (min 10 char): letscreateakey
Enter Key: 6c6570736f7e696574656d6b6379
Well Done!

And it works!!!

The complete keygen sourcecode can be found here in case you want to try it out yourself: https://pastebin.com/HBSKAGuz

Final Words

Thanks for reading the article, I hoped you learnt something new! I noticed that I got quite a lot better at using radare with this puzzle. Before I only really used IDA or similar graphical disassemblers. I still won’t call myself a master at it though, radare is pretty complicated and has a ton of functions that are still way beyond me. Please let me know if you have any questions or suggestions, I’d be happy to answer.

Noswis signing off.

7 Likes