Challenge: Brute and Smart (SOLUTION)


(pico) #1

Continuing the discussion from Challenge: Brute and Smart:

Did you solved the Brute and Smart challenge (Challenge: Brute and Smart)? In case you did and you wonder if your solution was right or you didn’t solve it and you wonder how to do it… here is my write up.

The program asked for a 6 digit long PIN. Therefore, there are 1 million possible keys. Furthermore, the program implements a 10 seconds delay to prevent a Brute Force attack. If you try a direct brute force attack, it may take something like 1000000 * 10 = 10000000 secs … roughly 115 days. So we have to do better than that to get the secret message.

Reverse engineering

Let’s take a look to the program to see what can we do. The program does not have the symbols stripped so we get a quite clean disassembling. Let’s go with radare2 and take a look to the beginning of the main function

$ r2 sample
[0x00400270]> aaaa
[x] Analyze all flags starting with sym. and entry0 (aa)
[x] Analyze len bytes of instructions for references (aar)
[x] Analyze function calls (aac)
[0x004001a3 ESIL infinite loop detectedences (aae)

0x004001ac ESIL infinite loop detected

[x] Emulate code to find computed references (aae)
[>] Scanning -r-x 0x40017c - 0x4003d9 skip
[>] Scanning mr-x 0x400000 - 0x400518 done
Analyzed 0 functions based on preludes
[x] Finding function by preludes (aap)
[x] Analyze consecutive function (aat)
[x] Analyze value pointers (aav)
[x] Constructing a function name for fcn.* and sym.func.* functions (aan)
[0x00400270]> pdf @main
            ;-- main:
            ;-- section_end..note.gnu.build_id:
            ;-- section..text:
            ;-- section_end.NOTE:
/ (fcn) sym.main 244
|           ; CALL XREF from 0x00400281 (sym.main)
|           0x0040017c      55             push rbp                    ; [2] va=0x0040017c pa=0x0000017c sz=605 vsz=605 rwx=--r-x .text
|           0x0040017d      31c0           xor eax, eax
|           0x0040017f      b900010000     mov ecx, 0x100
|           0x00400184      ba17000000     mov edx, 0x17
|           0x00400189      53             push rbx
|           0x0040018a      4881ec080800.  sub rsp, 0x808
|           0x00400191      488b35580e20.  mov rsi, qword [rip + 0x200e58] ; [0x600ff0:8]=0x40040e "k\W.]CLI...CP\Q^QRT\ABVX\\.RZZ.Z]_ARVMA;" LEA obj.msg1 ;
|           0x00400198      4889e7         mov rdi, rsp
|           0x0040019b      488d9c240004.  lea rbx, [rsp + 0x400]      ; 0x400 ; "co" @ 0x400
|           0x004001a3      f3ab           rep stosd dword [rdi], eax
|           0x004001a5      4889df         mov rdi, rbx
|           0x004001a8      66b90001       mov cx, 0x100
|           0x004001ac      f3ab           rep stosd dword [rdi], eax
|           0x004001ae      4889df         mov rdi, rbx
|           0x004001b1      b10a           mov cl, 0xa
|           0x004001b3      f3a5           rep movsd dword [rdi], dword ptr [rsi]
|           0x004001b5      bed9034000     mov esi, str.Enter_PIN__6_digits__: ; "Enter PIN (6 digits) : " @ 0x4003d9
|           0x004001ba      bf01000000     mov edi, 1
|           0x004001bf      e840010000     call sym.write
|           0x004001c4      31ff           xor edi, edi
|           0x004001c6      ba00040000     mov edx, 0x400              ; "co" @ 0x400
|           0x004001cb      31c0           xor eax, eax
|           0x004001cd      4889e6         mov rsi, rsp
|           0x004001d0      e827010000     call sym.__libc_read


We can see how the program uses write and read instead of printf or fgets in order to show the message asking for the password and to read the PIN from the user. If you cannot see it directly, try to strace the program and that should become pretty obvious. Nothing special so far… those rep stosd are actually inlined memset and memcpy calls. You will see them in the source code later.

I’m not going to explain in details what all the code do. The relevant part is that, the encoded string is copied in the stack. at the beginning of the function (0x004001ac to 0x004001b3). Then there is an in-lined strlen and a check of the string length. If the length is OK, the message Decoding... is shown.

This is the inlined strlen check and Decoding... message.

|           0x004001d5      4883caff       or rdx, 0xffffffffffffffff
|           0x004001d9      31c0           xor eax, eax
|           0x004001db      4889e7         mov rdi, rsp
|           0x004001de      4889d1         mov rcx, rdx
|           0x004001e1      f2ae           repne scasb al, byte [rdi]
|           0x004001e3      4889e7         mov rdi, rsp
|           0x004001e6      48f7d1         not rcx
|           0x004001e9      c6440cfe00     mov byte [rsp + rcx - 2], 0
|           0x004001ee      4889d1         mov rcx, rdx
|           0x004001f1      f2ae           repne scasb al, byte [rdi]
|           0x004001f3      4883f9f8       cmp rcx, -8
|       ,=< 0x004001f7      7556           jne 0x40024f
|       |   0x004001f9      ba0c000000     mov edx, 0xc
|       |   0x004001fe      bef1034000     mov esi, str.Decoding..._n  ; "Decoding...." @ 0x4003f1
|       |   0x00400203      bf01000000     mov edi, 1
|       |   0x00400208      e8f7000000     call sym.write

Otherwise, if the length is not OK, the program exists using the following code (see the jne 0x4002af):

|    |```-> 0x0040024f      bf01000000     mov edi, 1
|    |      0x00400254      ba0a000000     mov edx, 0xa
|    |      0x00400259      be03044000     mov esi, str.Wrong_PIN_n    ; "Wrong PIN." @ 0x400403
|    |      0x0040025e      31c0           xor eax, eax
|    |      0x00400260      e89f000000     call sym.write
|    |      0x00400265      bf01000000     mov edi, 1
|    |      ; JMP XREF from 0x0040024d (sym.main)
|    `----> 0x0040026a      e869000000     call fcn.004002d8
\           0x0040026f      90             nop

The code shows the message Wrong PIN and exits with exit code 1… Yes, take a look to fcn.004002d8) and you will find the exit system call.

So far so good. The program returns 1 if the length of the key is not right (6 chars in this case). Still nothing useful to attack the program. Let’s keep analysing the main function.

|       |   0x0040020d      ba28000000     mov edx, 0x28               ; '('
|       |   0x00400212      4889e6         mov rsi, rsp
|       |   0x00400215      4889df         mov rdi, rbx
|       |   0x00400218      e873000000     call sym.mp1
|       |   0x0040021d      3b05c50d2000   cmp eax, dword [rip + 0x200dc5] ; [0x600fe8:4]=0x31b20 LEA ; " .." @ 0x600fe8
|      ,==< 0x00400223      752a           jne 0x40024f
|      ||   0x00400225      befe034000     mov esi, str.heco           ; "heco" @ 0x4003fe
|      ||   0x0040022a      4889df         mov rdi, rbx
|      ||   0x0040022d      e80e010000     call sym.strstr
|      ||   0x00400232      4885c0         test rax, rax
|     ,===< 0x00400235      7418           je 0x40024f
|     |||   0x00400237      bf02000000     mov edi, 2
|     |||   0x0040023c      ba28000000     mov edx, 0x28               ; '('
|     |||   0x00400241      4889de         mov rsi, rbx
|     |||   0x00400244      31c0           xor eax, eax
|     |||   0x00400246      e8b9000000     call sym.write
|     |||   0x0040024b      31ff           xor edi, edi
|    ,====< 0x0040024d      eb1b           jmp 0x40026a


Now, things become more interesting. The program calls a function named mp1 and checks the value returned by that function with the content of 0x600fe98 (a local variable with value 0x31b20)… If the function returns the wrong value the program jumps to the exit code, showing the message Wrong PIN and exiting, again, with code 1. Then it calls the strstr function. This function looks for a substring within a given string. In this case, it is looking for the sub-string at address 0x400340 (heco) within the string passed as first parameter to the mp1 function.

Again, if the string is not found, the program will end, exiting with exit code 1. Otherwise it will print the current buffer (the one passed to mp1 but in this case using stderr (file descriptor 2) instead of stdout). Then it will set EAX to 0 and jump to the call to exit (just check the previous assembler fragment).

So far we have found something useful. The program will return 0 when the key is correct and 1 otherwise. This is a clean condition to know when we have found the right password. A lot easier that parsing the output of the program and trying to figure out if there is some meaningful content on it.

The mp1 function

Other than a clean condition to stop our brute force attack, we haven’t found much yet. It is time to check the mp1 function.

[0x00400270]> pdf @sym.mp1
/ (fcn) sym.mp1 71
|           ; CALL XREF from 0x00400218 (sym.mp1)
|           0x00400290      53             push rbx
|           0x00400291      4189d1         mov r9d, edx
|           0x00400294      31c9           xor ecx, ecx
|           0x00400296      31db           xor ebx, ebx
|           0x00400298      41b806000000   mov r8d, 6
|       ,=< 0x0040029e      eb20           jmp 0x4002c0
|      .--> 0x004002a0      99             cdq
|      ||   0x004002a1      41f7f8         idiv r8d
|      ||   0x004002a4      4863d2         movsxd rdx, edx
|      ||   0x004002a7      4801f2         add rdx, rsi
|      ||   0x004002aa      8a02           mov al, byte [rdx]
|      ||   0x004002ac      32040f         xor al, byte [rdi + rcx]
|      ||   0x004002af      88040f         mov byte [rdi + rcx], al
|      ||   0x004002b2      0fb612         movzx edx, byte [rdx]
|      ||   0x004002b5      0fb6c0         movzx eax, al
|      ||   0x004002b8      48ffc1         inc rcx
|      ||   0x004002bb      0fafc2         imul eax, edx
|      ||   0x004002be      01c3           add ebx, eax
|      ||   ; JMP XREF from 0x0040029e (sym.mp1)
|      |`-> 0x004002c0      4439c9         cmp ecx, r9d
|      |    0x004002c3      89c8           mov eax, ecx
|      `==< 0x004002c5      7cd9           jl 0x4002a0
|           0x004002c7      bf0a000000     mov edi, 0xa
|           0x004002cc      31c0           xor eax, eax
|           0x004002ce      e841000000     call sym.sleep
|           0x004002d3      89d8           mov eax, ebx
|           0x004002d5      5b             pop rbx
\           0x004002d6      c3             ret

I will not explain this line by line, but this is a XOR encoding function using a key of 6 characters. The result is stored in the original buffer. The key itself is a parameter to the function. It is actually the string entered by the user so… the program does not store the key anywhere in the code. It uses the user provided key to decode the encrypted message. Furthermore, this code calculates a checksum of the decoded strings as it is decoded. That is actually the value the function returns and that is compared in the main function with the constant 0x31b20. This is not really relevant and I’ll tell you later why it is there.

However, the end of the function is interesting. Let’s take a look again:

|           0x004002c7      bf0a000000     mov edi, 0xa
|           0x004002cc      31c0           xor eax, eax
|           0x004002ce      e841000000     call sym.sleep

This is a call to Sleep passing as parameter the value 0x0a (10 secs). So, these are the 10 seconds we have to wait to be able to try another key… Sometimes, this timing can be checked somewhere else in the code and cannot be easily removed. In this case, we can see that there is nothing in the program taking into account these 10 secs delay, therefore, it looks like a way to prevent a brute force attack. The first thing to do is to remove that delay, because we will have to brute force attack the program anyway… In this case, there is no other way around.

After removing the delay, we can try the brute force attack and see how it well it will work

Note: Just look for the hex values above in your preferred Hex editor and change the sleep call (e841000000) to NOPs (code 0x90)

A Brute Force attack

So, we have to write a program (actually a script will be easier in this case) to try all the possible PIN codes. We know that the program will return 1 whenever we input the wrong code, so we can easily stop our attack when we are done.

I wrote my script in Perl (of course), and it looks like this:

$start = 0;
$end = 999999;
$start = $ARGV[0] if $#ARGV >= 0;
$end = $start + $ARGV[1] if $#ARGV == 1;

for ($i = $start; $i < $end; $i++)
    $key = sprintf "%06d", $i;
    $cmd = "echo $key | ./sample-no-sleep > /dev/null";
    system ($cmd);
    print "$key " . int(($i *100)/ 999999) . "%\n" if ($i && $i % 5000 == 0);
    if ($? == 0)
	printf "Key is $key\n";
print "Last Key was: $key\n";

When executed without parameters, it will try all possible PIN codes. If we provide one parameter, it will try PIN codes starting with that value. This way we can stop the program and restart it later if needed. Finally, if we provide a second parameter then, the program will just check that number of keys. This allows us to launch the script multiple times and even run it in several computers to get the key broken faster.

I think the code is pretty straight forward. The only thing you need to know is that the variable $? conveniently contains the exit code of the last executed program.

Running this script without parameters (checking all the keys in one go), took around 30 minutes for my computer to find the key. That is pretty reasonable, but… we can do a lot better.

This solution does not require you to completely reverse the encryption algorithm. We are using the program itself to do the decoding. If you manage to completely reverse the algorithm the brute force script will run a lot faster as we do not need to run a complete process. Kudos to @dtm for following that approach.

Alternatively, you can get the assembly for the mp1 function and use it in your program (we already know how to add asm function to our C code) without reversing it.

That strstr function should be handy

Sure it is. Do you remember the hint provided for this challenge? No worries, here it is again:

By now, you should have figure out that the program has encrypted the target string using XOR encryption and that the key is not stored in the code at all. You need to find the key by brute forcing the password. Here it goes the hint:

If P is the plain text, C is the crypted text and K is the key, then:

P xor K = C
P xor C = K

Therefore, if you have the plain text (or part of it) then you can know the key (or part of it).

So, that strstr function tries to find some characters in the decoded message. In other words, it tries to find some specific sequence of characters in the plain text message. Radare2 already show us the string heco that is, a part of the plain text message.

Yes, I know. This strstr thingy requires some explanation. I will provide it later when I show you the source code at the end of this write up.

Anyway, so we have the crypted message, we have a 6 characters long key and we have 4 plain characters. This means that, if we xor together the crypted message with the string we are looking for, we will get 4 digits of our key. Unfortunately, we do not know where those characters are within the whole string, and we do not know either which index of the key will affect each one.

This sounds a bit confusing, so, let’s do a diagram.

CCCCCCCCCCCCCC     This is our crypted strings
KKKKKKKKKKKKKK     This is our key repeated module 6

The substring can be in any of those positions. Note that, as the key is 6 digits, the string is actually being rotated (because the index 6 becomes 0 and index 7 becomes 1 and so on). With this information, we can write a simple program to try to decode the crypted string, using keys including the heco. So I wrote this small program.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define KEY_LEN 6
#define MSG_LEN 40

unsigned char *msg1 = "\x6b\x5c\x57\x59\x41\x43\x48\x03\x1d\x1e\x41\x5f\x5d\x5a\x5d\x55\x50\x5b\x5d\x4a\x41\x52\x5a\x53\x5d\x17\x51\x5e\x58\x18\x5b\x56\x5c\x45\x50\x59\x4c\x4a\x32\x31";

int find_num (unsigned char *s, int l)
  int i;
  for (i = 0; i < l; i++)
      if (isdigit(s[i])) printf ("%c", s[i]);
      else printf (" ");
  printf ("\n");

int mp (unsigned char *s, unsigned char *k, int l)
  char c;
  int  i;

  for (i = 0; i < l; i++)
      s[i] ^= k[(i % KEY_LEN)];
  return 0;


main ()
  unsigned char buffer[1024];
  unsigned char msg[1024];
  int c;

  memset (buffer, 0, 1024);
  memset (msg, 0, 1024);
  memcpy (msg, msg1, MSG_LEN);

  memcpy (buffer, "heco\0\0", 6);
  mp (msg, buffer, MSG_LEN);
  printf ("%s\n", msg);
  find_num (msg, MSG_LEN);
  mp (msg, buffer, MSG_LEN);

  memcpy (buffer, "\0heco\0", 6);
  mp (msg, buffer, MSG_LEN);
  printf ("%s\n", msg);
  find_num (msg, MSG_LEN);
  mp (msg, buffer, MSG_LEN);

  memcpy (buffer, "\0\0heco", 6);
  mp (msg, buffer, MSG_LEN);
  printf ("%s\n", msg);
  find_num (msg, MSG_LEN);
  mp (msg, buffer, MSG_LEN);

  memcpy (buffer, "o\0\0hec", 6);
  mp (msg, buffer, MSG_LEN);
  printf ("%s\n", msg);
  find_num (msg, MSG_LEN);
  mp (msg, buffer, MSG_LEN);

  memcpy (buffer, "co\0\0he", 6);
  mp (msg, buffer, MSG_LEN);
  printf ("%s\n", msg);
  find_num (msg, MSG_LEN);
  mp (msg, buffer, MSG_LEN);

  memcpy (buffer, "eco\0\0h", 6);
  mp (msg, buffer, MSG_LEN);
  printf ("%s\n", msg);
  find_num (msg, MSG_LEN);
  mp (msg, buffer, MSG_LEN);


Yes, it is just 6 possibilities before they repeat so copy&paste worked faster that a loop :stuck_out_tongue: . The program takes the crypted string (extracted from the binary using any tool you like) and encodes it with the heco string that is shifted 1 character to the right 6 times to cover all possible positions of the substring. Then the function find_num is called. This function just prints the numbers in the decrypted string. Finally we call again the crypt function to restore the crypt message for the next round.

The hint we have is that if we XOR together the crypted and plain text we get the key. In this case, the PIN is a numeric code, so we are interested only in numbers. Actually we are only interested in sequences of 4 consecutive numbers. Those are the ones that produces the heco strings we are looking for. So, let’s see what does this program tell us.

$ make test
$ ./test
946AC f~qA_5?>:P[5/"=ZS5r21X33?*PY$/Q^
 946        5     5     5 21  33
 42          286     15   4 7   9
k\?<",Hu{"0]Z5034]J)79<]9;;w[V4 36LJZT
           0  5034   79   9     4 36
\W1$ 'v$<2Z]=582JA:?02Q6={4V\-5:#J2Y
   1        2   582    02  6  4   5   2
 3           5  8     26    0 89  8   21
  8        7892  38     8      53  1   1

Nice, we see two 4 digits sequences: 5034 and 7892. We know that the key will have those 4 digits plus 2 additional ones that we do not know. We do not know either the position within the 6 digit pin of these 4 digits, but we know that the are consecutive… Let’s brute force again:

Smarter Brute Forcing

With the information we had got, I wrote a new script to brute force the program. Here it is:

$val = $ARGV[0] if $#ARGV >= 0;

for ($i = 0; $i < 100; $i++)
    $key = $val . sprintf "%02d", $i;
    for ($j =0; $j < 6; $j++)
	$key1 = substr ($key, $j) . substr ($key, 0, $j);
	$cmd = "echo $key1 | ./c01 > /dev/null";
	system ($cmd);

	if ($? == 0)
	    printf "Key is $key\n";
print "Last Key was: $key\n";

The script receives as parameter a 4 digit number. Then, it completes the number with the two missing digits (from 00 to 99) and try the 6 PIN codes that result of shifting the just generated 6 digits code. This requires in total: 100 * 6 = 600 PIN checks.

Let’s try the script with the 4 digit candidates we found before:

$ ./ 5034
Last Key was: 503499

Bad luck with the first one. Let’s try the next one:

$ ./ 7892



Again, you can implement the encryption algorithm in the script and make it run a lot faster. However, for this solution it just takes a few seconds to find the key.

The source Code

To finish with this paper, this is the source code of the challenge:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define KEY_LEN 6
#define MSG_LEN 40

unsigned char *msg1 = "\x6b\x5c\x57\x11\x5d\x43\x4c\x49\x08\x1e\x1a\x43\x50\x5c\x51\x5e\x51\x52\x54\x5c\x41\x42\x56\x58\x5c\x5c\x1c\x52\x5a\x5a\x17\x5a\x5d\x5f\x41\x52\x56\x4d\x41\x3b";

int cm =  203552;

int mp1 (unsigned char *s, unsigned char *k, int l)
  char c;
  int  i, sum = 0;

  for (i = 0; i < l; i++)
      s[i] ^= k[(i % KEY_LEN)];
      sum += s[i] * k[(i % KEY_LEN)];
  sleep (10);

  return sum;

main ()
  unsigned char buffer[1024];
  unsigned char msg[1024];
  int c;

  memset (buffer, 0, 1024);
  memset (msg, 0, 1024);
  memcpy (msg, msg1, MSG_LEN);

  write (1, "Enter PIN (6 digits) : ", 23);
  read (0, buffer, 1024);
  buffer[strlen(buffer) - 1] = 0;
  if (strlen (buffer) != 6) 
    goto wrong;

  write (1, "Decoding...\n", 12);
  c = mp1 (msg, buffer, MSG_LEN);
  if (c == cm && strstr (msg, "heco"))
      write (2, msg, MSG_LEN);
      exit (0);

  write (1, "Wrong PIN\n", 10);
  exit (1);

After all your reverse engineering efforts, there are not many surprises I guess. There is only one thing to explain. I wanted the program to do not store the password at all so you will have to brute force it. The problem is that I needed the program to be able to detect if the password was right or not. In a normal case I will probably use a hash of the plain text (MD5, SHA1), but that will bring a lot of complexity to the code and make the challenge even more difficult.

So I just calculated a very basic checksum, but it didn’t worked very well, and that is why I added the strstr check. So, when the user enters a PIN, the message is decoded with that PIN and a checksum generated. There are many PINs that produces that checksum but do not decode the message right so I added a second check to ensure that a specific sequence of characters shall appear in the plain message. Probably the checksum can be removed now… consider it noise :slight_smile:

I just used 4 characters so you could only extract a partial password (as we have seen above) but you get a chance to heavily improve a brute force attack.

Well, I’m not sure if doing the analysis described here takes longer that a direct Brute force attack but I believe it is a lot more interesting. In this challenge I try to point out the following ideas:

  • Sometimes, reverse engineering is not enough… Or, in other words. Sometimes brute force is the only solution.
  • Blindly brute forcing is not very effective. With a little bit of extra work you can do it a lot better
  • Perl is cool :stuck_out_tongue_winking_eye:

(system) #2

This topic was automatically closed after 30 days. New replies are no longer allowed.