Difficulty understanding logic in disassembled binary bomb phase 3

Question

I have the following assembly program from the binary-bomb lab. The goal is to determine the keyword needed to run the binary without triggering the explode_bomb function. I commented my analysis of the assembly for this program but I am having trouble piecing everything together.

I believe I have all the information I need, but I still am unable to see the actual underlying logic and thus I am stuck. I would greatly appreciate any help!

The following is the disassembled program itself:

0x08048c3c <+0>:     push   %edi
   0x08048c3d <+1>:     push   %esi
   0x08048c3e <+2>:     sub    $0x14,%esp
   0x08048c41 <+5>:     movl   $0x804a388,(%esp)
   0x08048c48 <+12>:    call   0x80490ab <string_length>
   0x08048c4d <+17>:    add    $0x1,%eax
   0x08048c50 <+20>:    mov    %eax,(%esp)
   0x08048c53 <+23>:    call   0x8048800 <malloc@plt>
   0x08048c58 <+28>:    mov    $0x804a388,%esi
   0x08048c5d <+33>:    mov    $0x13,%ecx
   0x08048c62 <+38>:    mov    %eax,%edi
   0x08048c64 <+40>:    rep movsl %ds:(%esi),%es:(%edi)
   0x08048c66 <+42>:    movzwl (%esi),%edx
   0x08048c69 <+45>:    mov    %dx,(%edi)
   0x08048c6c <+48>:    movzbl 0x11(%eax),%edx
   0x08048c70 <+52>:    mov    %dl,0x10(%eax)
   0x08048c73 <+55>:    mov    %eax,0x4(%esp)
   0x08048c77 <+59>:    mov    0x20(%esp),%eax
   0x08048c7b <+63>:    mov    %eax,(%esp)
   0x08048c7e <+66>:    call   0x80490ca <strings_not_equal>
   0x08048c83 <+71>:    test   %eax,%eax
   0x08048c85 <+73>:    je     0x8048c8c <phase_3+80>
   0x08048c87 <+75>:    call   0x8049363 <explode_bomb>
   0x08048c8c <+80>:    add    $0x14,%esp
   0x08048c8f <+83>:    pop    %esi
   0x08048c90 <+84>:    pop    %edi
   0x08048c91 <+85>:    ret  

The following block contains my analysis

  5 <phase_3>
  6 0x08048c3c <+0>:     push   %edi // push value in edi to stack
  7 0x08048c3d <+1>:     push   %esi // push value of esi to stack
  8 0x08048c3e <+2>:     sub    $0x14,%esp // grow stack by 0x14 (move stack ptr -0x14 bytes)
  9 
 10 0x08048c41 <+5>:     movl   $0x804a388,(%esp) // put 0x804a388 into loc esp points to
 11 
 12 0x08048c48 <+12>:    call   0x80490ab <string_length> // check string length, store in eax
 13 0x08048c4d <+17>:    add    $0x1,%eax // increment val in eax by 0x1 (str len + 1) 
 14 // at this point, eax = str_len + 1  = 77 + 1 = 78
 15 
 16 0x08048c50 <+20>:    mov    %eax,(%esp) // get val in eax and put in loc on stack
 17 //**** at this point, 0x804a388 should have a value of 78? ****
 18 
 19 0x08048c53 <+23>:    call   0x8048800 <malloc@plt> // malloc --> base ptr in eax
 20 
 21 0x08048c58 <+28>:    mov    $0x804a388,%esi // 0x804a388 in esi 
 22 0x08048c5d <+33>:    mov    $0x13,%ecx // put 0x13 in ecx (counter register)
 23 0x08048c62 <+38>:    mov    %eax,%edi // put val in eax into edi
 24 0x08048c64 <+40>:    rep movsl %ds:(%esi),%es:(%edi) // repeat 0x13 (19) times
 25 // **** populate malloced memory with first 19 (edit: 76) chars of string at 0x804a388 (this string is 77 characters long)? ****
 26 
 27 0x08048c66 <+42>:    movzwl (%esi),%edx // put val in loc esi points to into edx
***** // at this point, edx should contain the string at 0x804a388?
 28 
 29 0x08048c69 <+45>:    mov    %dx,(%edi) // put val in dx to loc edi points to
***** // not sure what effect this has or what is in edi at this point
 30 0x08048c6c <+48>:    movzbl 0x11(%eax),%edx // edx = [eax + 0x11]
 31 0x08048c70 <+52>:    mov    %dl,0x10(%eax) // [eax + 0x10] = dl
 32 0x08048c73 <+55>:    mov    %eax,0x4(%esp) // [esp + 0x4] = eax
 33 0x08048c77 <+59>:    mov    0x20(%esp),%eax // eax = [esp + 0x20]
 34 0x08048c7b <+63>:    mov    %eax,(%esp) // put val in eax into loc esp points to
***** // not sure what effect these movs have
 35 
 36 // edi --> first arg
 37 // esi --> second arg
 38 // compare value in esi to edi
 39 0x08048c7e <+66>:    call   0x80490ca <strings_not_equal> // store result in eax
 40 0x08048c83 <+71>:    test   %eax,%eax 
 41 0x08048c85 <+73>:    je     0x8048c8c <phase_3+80>
 42 0x08048c87 <+75>:    call   0x8049363 <explode_bomb>
 43 0x08048c8c <+80>:    add    $0x14,%esp
 44 0x08048c8f <+83>:    pop    %esi
 45 0x08048c90 <+84>:    pop    %edi
 46 0x08048c91 <+85>:    ret 

Update:

Upon inspecting the registers before strings_not_equal is called, I get the following:

eax            0x804d8aa        134535338
ecx            0x0      0
edx            0x76     118
ebx            0xffffd354       -11436
esp            0xffffd280       0xffffd280
ebp            0xffffd2b8       0xffffd2b8
esi            0x804a3d4        134521812
edi            0x804f744        134543172
eip            0x8048c7b        0x8048c7b <phase_3+63>
eflags         0x282    [ SF IF ]
cs             0x23     35
ss             0x2b     43
ds             0x2b     43
es             0x2b     43
fs             0x0      0
gs             0x63     99

and I get the following disassembled pseudocode using Hopper:

I even tried using both the number found in eax and the string seen earlier as my keyword but neither of them worked.

Answer 1

The function makes a modified copy of a string from static storage, into a malloced buffer.

---

This looks weird. The malloc size is dependent on strlen+1, but the memcpy size is a compile-time constant? Your decompilation apparently shows that address was a string literal so it seems that's fine.

Probably that missed optimization happened because of a custom string_length() function that was maybe only defined in another .c (and the bomb was compiled without link-time optimization for cross-file inlining). So size_t len = string_length("some string literal"); is not a compile-time constant and the compiler emitted a call to it instead of being able to use the known constant length of the string.

But probably they used strcpy in the source and the compiler did inline that as a rep movs. Since it's apparently copying from a string literal, the length is a compile-time constant and it can optimize away that part of the work that strcpy normally has to do. Normally if you've already calculated the length it's better to use memcpy instead of making strcpy calculate it again on the fly, but in this case it actually helped the compiler make better code for that part than if they'd passed the return value of string_length to a memcpy, again because string_length couldn't inline and optimize away.

---

   <+0>:     push   %edi // push value in edi to stack
   <+1>:     push   %esi // push value of esi to stack
   <+2>:     sub    $0x14,%esp // grow stack by 0x14 (move stack ptr -0x14 bytes)

Comments like that are redundant; the instruction itself already says that. This is saving two call-preserved registers so the function can use them internally and restore them later.

Your comment on the sub is better; yes, grow the stack is the higher level semantic meaning here. This function reserves some space for locals (and for function args to be stored with mov instead of pushed).

---

The rep movsd copies 0x13 * 4 bytes, incrementing ESI and EDI to point past the end of the copied region. So another movsd instruction would copy another 4 bytes contiguous with the previous copy.

The code actually copies another 2, but instead of using movsw, it uses a movzw word load and a mov store. This makes a total of 78 bytes copied.

  ...
      # at this point EAX = malloc return value which I'll call buf
<+28>:    mov    $0x804a388,%esi            # copy src = a string literal in .rodata?
<+33>:    mov    $0x13,%ecx
<+38>:    mov    %eax,%edi                  # copy dst = buf
<+40>:    rep movsl %ds:(%esi),%es:(%edi)   # memcpy 76 bytes and advance ESI, EDI

<+42>:    movzwl (%esi),%edx
<+45>:    mov    %dx,(%edi)        # copy another 2 bytes (not moving ESI or EDI)
 # final effect: 78-byte memcpy

On some (but not all) CPUs it would have been efficient to just use rep movsb or rep movsw with appropriate counts, but that's not what the compiler chose in this case. movzx aka AT&T movz is a good way to do narrow loads without partial-register penalties. That's why compilers do it, so they can write a full register even though they're only going to read the low 8 or 16 bits of that reg with a store instruction.

After that copy of a string literal into buf, we have a byte load/store that copies a character with buf. Remember at this point EAX is still pointing at buf, the malloc return value. So it's making a modified copy of the string literal.

<+48>:    movzbl 0x11(%eax),%edx
<+52>:    mov    %dl,0x10(%eax)             # buf[16] = buf[17]

Perhaps if the source hadn't defeated constant-propagation, with high enough optimization level the compiler might have just put the final string into .rodata where you could find it, trivializing this bomb phase. :P

Then it stores pointers as stack args for string compare.

<+55>:    mov    %eax,0x4(%esp)               # 2nd arg slot = EAX = buf
<+59>:    mov    0x20(%esp),%eax              #  function arg = user input?
<+63>:    mov    %eax,(%esp)                  # first arg slot = our incoming stack arg
<+66>:    call   0x80490ca <strings_not_equal>

---

How to "cheat": looking at the runtime result with GDB

Some bomb labs only let you run the bomb online, on a test server, which would record explosions. You couldn't run it under GDB, only use static disassembly (like objdump -drwC -Mintel). So the test server could record how many failed attempts you had. e.g. like CS 3330 at cs.virginia.edu that I found with google, where full credit requires less than 20 explosions.

Using GDB to examine memory / registers part way through a function makes this vastly easier than only working from static analysis, in fact trivializing this function where the single input is only checked at the very end. e.g. just look at what other arg is being passed to strings_not_equal. (Especially if you use GDB's jump or set $pc = ... commands to skip past the bomb explosion checks.)

Set a breakpoint or single-step to just before the call to strings_not_equal. Use p (char*)$eax to treat EAX as a char* and show you the (0-terminated) C string starting at that address. At that point EAX holds the address of the buffer, as you can see from the store to the stack.

Copy/paste that string result and you're done.

Other phases with multiple numeric inputs typically aren't this easy to cheese with a debugger and do require at least some math, but linked-list phases that requires you to have a sequence of numbers in the right order for list traversal also become trivial if you know how to use a debugger to set registers to make compares succeed as you get to them.

Answer 2

rep movsl copies 32-bit longwords from address %esi to address %edi, incrementing both by 4 each time, a number of times equal to %ecx. Think of it as memcpy(edi, esi, ecx*4).

See https://felixcloutier.com/x86/movs:movsb:movsw:movsd:movsq (it's movsd in Intel notation).

So this is copying 19*4=76 bytes.