Scythe17 Optimize Me 350

optimize-me scythe17 350

Death is knocking on your door. He will take your soul away unless you are able to quickly tell him the flag. But of course, he had employed f0xtr0t to slow down the speed at which you can see the flag. Can you tell him the flag quick enough and save yourself? Here’s the binary.

Let’s get going

$ file optimize_me
optimize_me: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux.so.2,
for GNU/Linux 2.6.24, BuildID[sha1]=702db318aec446950b713581b5adb2995d2463d4, stripped
$ ./optimize_me
Welcome to f0xtr0t's extremely slow program
-------------------------------------------

In

The binary is taking long time to print characters waiting for it to finish is not an option , Let open it in radare2

0x0804868c      c7442404308b.  mov dword [local_4h], str.Welcome_to_f0xtr0t_s_extremely_slow_program_n_____________________________________
0x08048694      c70424010000.  mov dword [esp], 1                                                                                          
0x0804869b      e8e0fcffff     call sym.imp.__printf_chk   ;[1]                                                                            
0x080486a0      c74424180000.  mov dword [count], 0                                                                                    

sym.imp.__printf_chk is used to print the string , After there is a loop with 0x4e52 number of iteration we can see that the print function is called with argument eax , this might be the place were the characters are printing

|   0x0804879f      8b44242c       mov eax, dword [local_2ch]  ; [0x2c:4]=-1 ; ',' ; 44                                                        
|   0x080487a3      c74424048c8b.  mov dword [local_4h], 0x8048b8c ; [0x8048b8c:4]=0x6325                                                      
|   0x080487ab      c70424010000.  mov dword [esp], 1                                                                                          
|   0x080487b2      2b44241c       sub eax, dword [local_1ch]                                                                                  
|   0x080487b6      31c8           xor eax, ecx                                                                                                
|   0x080487b8      31f0           xor eax, esi                                                                                                
|   0x080487ba      0fbec0         movsx eax, al                                                                                               
|   0x080487bd      89442408       mov dword [local_8h], eax                                                                                   
|   0x080487c1      e8bafbffff     call sym.imp.__printf_chk   ;[2]                                                                            
|   0x080487c6      8344241801     add dword [count], 1                                                                                        
|   0x080487cb      817c2418524e.  cmp dword [count], 0x4e52   ; [0x4e52:4]=-1                                                                 
`=< 0x080487d3      0f85cffeffff   jne 0x80486a8               ;[3]    

So we need to find why this binary is taking so much time to print one character and from were does this comes from , from debugging the binary by we can see that this is the loop which makes it this much slow

[0x08048741]> pd 30 @ 0x8048741
!      ; JMP XREF from 0x0804872c (main)
|   0x08048741      8d1c09         lea ebx, [ecx + ecx]
|   0x08048744      89c8           mov eax, ecx
|   0x08048746      0fafc1         imul eax, ecx
|   0x08048749      29d0           sub eax, edx
|   0x0804874b      99             cdq
|   0x0804874c      f7fb           idiv ebx
|   0x0804874e      8b54242c       mov edx, dword [local_2ch]  ; [0x2c:4]=-1 ; ',' ; 44
|   0x08048752      8b5c242c       mov ebx, dword [local_2ch]  ; [0x2c:4]=-1 ; ',' ; 44
|   0x08048756      29c1           sub ecx, eax
|   0x08048758      89d0           mov eax, edx
|   0x0804875a      c1f81f         sar eax, 0x1f
|   0x0804875d      c1e81e         shr eax, 0x1e
|   0x08048760      01c2           add edx, eax
|   0x08048762      83e203         and edx, 3
|   0x08048765      29c2           sub edx, eax
|   0x08048767      89d8           mov eax, ebx
|   0x08048769      c1f81f         sar eax, 0x1f
|   0x0804876c      c1e81e         shr eax, 0x1e
|   0x0804876f      01c3           add ebx, eax
|   0x08048771      83e303         and ebx, 3
|   0x08048774      29c3           sub ebx, eax
|   0x08048776      8b0495008609.  mov eax, dword [edx*4 + 0x8098600] ; [0x8098600:4]=0
|   0x0804877d      2b049d40a004.  sub eax, dword [ebx*4 + 0x804a040]
|   0x08048784      31c1           xor ecx, eax
|   0x08048786      8b44242c       mov eax, dword [local_2ch]  ; [0x2c:4]=-1 ; ',' ; 44
|   0x0804878a      83c001         add eax, 1
|   0x0804878d      8944242c       mov dword [local_2ch], eax
|   0x08048791      8b44242c       mov eax, dword [local_2ch]  ; [0x2c:4]=-1 ; ',' ; 44
|   0x08048795      3944241c       cmp dword [local_1ch], eax  ; [0x13:4]=-1 ; 19
`=< 0x08048799      778d           ja 0x8048728

The loop is ran until local_1ch local_2ch are equal , and it turns out the local_1ch is huge number , now we have to know what is happening inside this loop , before that have i have to figure how the character is computer , it will give us some insight on the loop

 |   0x0804879b      8b742414       mov esi, dword [local_14h]  ; [0x14:4]=-1 ; 20                                                              
 !      ; JMP XREF from 0x0804870d (main)                                                                                                       
 |   0x0804879f      8b44242c       mov eax, dword [local_2ch]  ; [0x2c:4]=-1 ; ',' ; 44                                                        
 |   0x080487a3      c74424048c8b.  mov dword [local_4h], 0x8048b8c ; [0x8048b8c:4]=0x6325                                                      
 |   0x080487ab      c70424010000.  mov dword [esp], 1                                                                                          
 |   0x080487b2      2b44241c       sub eax, dword [local_1ch]                                                                                  
 |   0x080487b6      31c8           xor eax, ecx                                                                                                
 |   0x080487b8      31f0           xor eax, esi                                                                                                
 |   0x080487ba      0fbec0         movsx eax, al                                                                                               
 |   0x080487bd      89442408       mov dword [local_8h], eax                                                                                   
 |   0x080487c1      e8bafbffff     call sym.imp.__printf_chk   ;[2]                                                                            

We will work backwards here, value at EAX is printed , ESI contains value from the location local_14h and ECX contains some value we do not know were that value comes from , the difference from the local_1ch local_2ch is stored EAX it will be zero from last loop the value are xored , xor eax, ecx just copy the value from ecx to eax, then esi and eax is xored , and the last byte is printed

We have to figure out how ecx is set and the value of local_14h

We can see that the ECX is set on the above loop , but debugging that loop we can see that during first few iteration the ecx value is changing after that the ECX have the same value , We do not need to loop large number of time to figure out ecx’s final value thus reduce the time needed

0x080486a8 b    8b3504860908   mov esi, dword [0x8098604]  ; [0x8098604:4]=0                                                               
0x080486ae      c744242c0000.  mov dword [local_2ch], 0                                                                                    
0x080486b6      a100860908     mov eax, dword [0x8098600]  ; [0x8098600:4]=0                                                               
0x080486bb      8b7c2418       mov edi, dword [count]      ; [0x18:4]=-1 ; 24                                                              
0x080486bf      2b3544a00408   sub esi, dword [0x804a044]                                                                                  
0x080486c5      2b0540a00408   sub eax, dword [0x804a040]                                                                                  
0x080486cb      8b1cbd804c08.  mov ebx, dword [edi*4 + 0x8084c80] ; [0x8084c80:4]=0x175f9165                                               
0x080486d2      8b0cbd201307.  mov ecx, dword [edi*4 + 0x8071320] ; [0x8071320:4]=0x81af                                                   
0x080486d9      31c6           xor esi, eax                                                                                                
0x080486db      a108860908     mov eax, dword [0x8098608]  ; [0x8098608:4]=0                                                               
0x080486e0      895c241c       mov dword [local_1ch], ebx                                                                                  
0x080486e4      2b0548a00408   sub eax, dword [0x804a048]                                                                                  
0x080486ea      31c6           xor esi, eax                                                                                                
0x080486ec      a10c860908     mov eax, dword [0x809860c]  ; [0x809860c:4]=0                                                               
0x080486f1      2b054ca00408   sub eax, dword [0x804a04c]                                                                                  
0x080486f7      31c6           xor esi, eax                                                                                                
0x080486f9      8b44242c       mov eax, dword [local_2ch]  ; [0x2c:4]=-1 ; ',' ; 44                                                        
0x080486fd      3334bd60a004.  xor esi, dword [edi*4 + 0x804a060]                                                                          
0x08048704      39d8           cmp eax, ebx                                                                                                
0x08048706      8934bd60a004.  mov dword [edi*4 + 0x804a060], esi ; [0x804a060:4]=0x39e58d23                                               
0x0804870d      0f838c000000   jae 0x804879f               ;[2]                                                                            
0x08048713      8b04bdc0d905.  mov eax, dword [edi*4 + 0x805d9c0] ; [0x805d9c0:4]=0x308ade1d                                               
0x0804871a      89742414       mov dword [local_14h], esi                                                                                  

The value of local_1ch which is the number of time the loop should run is loaded from 0x8084c80 address and local_14h value is read from 0x804a060 the the value is not just read but xor value of previous esi and this location is read , for correct value to be loaded the value at esi should be zero ,

[0x0804869b]> px 40 @ 0x804a060
- offset -   0 1  2 3  4 5  6 7  8 9  A B  C D  E F  0123456789ABCDEF
0x0804a060  238d e539 2634 7107 911b c43b 0df0 245e  #..9&4q....;..$^
0x0804a070  8214 1435 bdda 4c28 00bc 501e 8dfc bc2b  ...5..L(..P....+
0x0804a080  9626 776e a28f d27c                      .&wn...|
[0x0804869b]> px 40 @ 0x8084c80
- offset -   0 1  2 3  4 5  6 7  8 9  A B  C D  E F  0123456789ABCDEF
0x08084c80  6591 5f17 c734 1e48 e76c a721 8aba 2456  e._..4.H.l.!..$V
0x08084c90  1fd4 2d37 5cd0 926f eb1e 327b b648 1a54  ..-7\..o..2{.H.T
0x08084ca0  58da 0767 1a51 9835                      X..g.Q.5

the first value at 0x8084c80 is

[0x0804869b]> x/d  @ 0x8084c80
0x08084c80  0x175f9165 0x481e34c7                        e._..4.H

So the loop will run 0x175f9165 times we can reduce this number to save and very low number , I patched the numbers to 100

[0x080487e3]> x/4d  @ 0x8084c80
0x08084c80  0x00000100 0x00000100 0x00000100 0x00000100  ................
0x08084c90  0x00000100 0x00000100 0x00000100 0x00000100  ................

Well running does not give the desirable output but first characters are printed faster

$ ./optimize_me
Welcome to f0xtr0t's extremely slow program
-------------------------------------------

oM@

What is happening over there , well it turns out that there is a check to find out if the binary is changed .

As i said before loading the value to local_14h it is xored with ESI and ESI’s value is zero when 0x8098600 and 0x804a040 are equal , 0x0804a040 is inside the binary and 0x08098600 is calculated on runtime,

[0x08048680]> axt 0x8098600
main 0x80486b6 (data) mov eax, dword [0x8098600]
main 0x8048776 (data) mov eax, dword [edx*4 + 0x8098600]
(nofunc) 0x804845f (data) mov dword [0x8098600], ecx
(nofunc) 0x8048a69 (data) mov eax, dword [edx*4 + 0x8098600]

0x08048390 contains the code which calculate checksum we can run the binary and read the content at this address and patch the same value to the binary so the check will be true , so we open radare in debug mode and

[0xf77d8a20]> db 0x080486a8
[0xf77d8a20]> dc
Welcome to f0xtr0t's extremely slow program
-------------------------------------------

hit breakpoint at: 80486a8
[0x080486a8]> px 20 @ 0x8098600
- offset -   0 1  2 3  4 5  6 7  8 9  A B  C D  E F  0123456789ABCDEF
0x08098600  f66b 2a23 3768 7b2a ae4c 9735 dee5 3341  .k*#7h{*.L.5..3A
0x08098610  0000 0000                                ....
[0x080486a8]> px 20 @ 0x804a040
- offset -   0 1  2 3  4 5  6 7  8 9  A B  C D  E F  0123456789ABCDEF
0x0804a040  652d 77b9 3768 7b2a ae4c 9735 dee5 3341  e-w.7h{*.L.5..3A
0x0804a050  0000 0000                                ....

Open radare in write mode

[0x080487e3]> wex 0xf66b2a23 @ 0x0804a040
[0x080487e3]> px 20 @ 0x804a040
- offset -   0 1  2 3  4 5  6 7  8 9  A B  C D  E F  0123456789ABCDEF
0x0804a040  f66b 2a23 3768 7b2a ae4c 9735 dee5 3341  .k*#7h{*.L.5..3A
0x0804a050  0000 0000                                ....
[0x080487e3]> q

But there is a problem there are around 0x4e52 values in location 0x08084c80 which we need to change to 100 , to reduce the runtime, doing it one by one is not an option we need to automate it , it turnout radare has the wright command to do this

[0x08084c80]> !rax2 0x4e52*4
80200
[0x08084c80]> wex 0x00010000 @@s:$$ $$+80200 4

$$ means current seek @@ is the iterator , it iterates command on specified locations ,

[0x08084c80]> @@?
|@@  # foreach iterator command:
| Repeat a command over a list of offsets  
| x @@ sym.*                               run 'x' over all flags matching 'sym.' in current flagspace
| x @@dbt[abs]                             run 'x' command on every backtrace address, bp or sp
| x @@.file                                run 'x' over the offsets specified in the file (one offset per line)
| x @@=off1 off2 ..                        manual list of offsets
| x @@/x 9090                              temporary set cmd.hit to run a command on each search result
| x @@k sdbquery                           run 'x' on all offsets returned by that sdbquery
| x @@t                                    run 'x' on all threads (see dp)
| x @@b                                    run 'x' on all basic blocks of current function (see afb)
| x @@i                                    run 'x' on all instructions of the current function (see pdr)
| x @@f                                    run 'x' on all functions (see aflq)
| x @@f:write                              run 'x' on all functions matching write in the name
| x @@s:from to step                       run 'x' on all offsets from, to incrementing by step
| x @@c:cmd                                the same as @@=`` without the backticks
| x @@=`pdf~call[0]`                       run 'x' at every call offset of the current function

Running the Binary now gives the flag!

$ ./optimize_me  | grep CTF
CTF{....}