Defusing a (binary) bomb

     This very good x86 assembly training has a nice final exercise which is a job to defuse  a binary bomb - an executable, without source code, with more phases, each one needing a password.
     I understand that there are many variants of this bomb, so my answer won't fit every bomb, but anyway it's a spoiler, be aware!
     Each level introduces also a programming construction (simple string manipulations, array, functions, cases, linked lists, trees...) so it's very interesting to actually do them and understand them.
    The long version of the solutions is at this project.  The short version below.
I've created a file with commands for easy debugging, and started the bomb like this:

$ gdb -q -x commands bomb
(gdb) run bomb-answers.txt

Phase 1
Here there's a simple string comparison in place
The two strings are compared:
- first one is our input string for the first phase:

(gdb) x /x $ebp+0x8
0xbffff440: 0x0804b680
(gdb) x /s 0x0804b680
0x804b680 <input_strings>: "test"

- and second one is the password for phase_1:

(gdb) x/s 0x80497c0
0x80497c0:    "Public speaking is very easy."

Phase 2
Now 6 numbers are read from into an array, and an algorithm is applied  as follows:

v[0] = 1
v[i] = (i+i) * v[i-1]

So we find the solution of phase 2:
1 2 6 24 120 720

Phase 3
 This expects as input a number, a character and another number:

   0x08048bb1 <+25>: push   0x80497de --> the format string for sscanf, "%d %c %d"
   0x08048bb6 <+30>: push   edx
   0x08048bb7 <+31>: call   0x8048860 <sscanf@plt>

The rest of the disassembled instructions are a case structure, which checks the letter and the second number based on the first value

Phase 4
This phase is more interesting. It introduces a recursive function, which in the end turns out to be a much known one. A-Ha! 
Func4 is as follows:

func4(x):
 if x <= 1 :
  return 1;
 else :
  y = func4(x-1);
  z = func4(x-2);
  return y + z;

Phase 5
In this phase, the input password string is parsed character by character, and each parsed character gives an index into an input string. This way,  final password has to be constructed. 

We have to form the password 'giants' from the source string "isrveawhobpnutfg".

phase_5 function should be something like:

phase_5(s) {
 src = "isrveawhobpnutfg";
 dest = "12345";
 
 for (i=0; i<=5; ++i) {
  idx = s[i] && 0xf; // cuts the most significant hex digit
  dest[i] = src[idx];
 }
}

Phase 6
This was the most difficult to figure out from the assembly code, as it's split into more stages, and involves linked lists structures. Complete details are in the link from beginning. 
6 numbers are read. There is a predefined linked list also. Another important variable used is an array containing addresses of list elements. 
- stage1: check that all 6 numbers read are between [1,..,6] and all different
- stage2: builds and arranges a second array with pointers to list elements
- stage3: fixes the links between elements from the input list to match the array constructed in stage2
- stage4: checks that the elements of the linked list are in reverse sorted order. 

The second stage is the most important: we have to arrange the values of the list elements, so that we can pass stage 4 check (should be in reverse order).
Current order :

func4(x):
(gdb) printf "%08x %08x %08x %08x %08x %08x \n", *0x0804b26c, *0x0804b260, *0x0804b254, *0x0804b248, *0x0804b23c, *0x0804b230
000000fd 000002d5 0000012d 000003e5 000000d4 000001b0 

The pseudo-code for this step could be something like:

   // 2nd stage
 i = 0
 ecx = v[0]
 eax = v2
 y = v2
 while i<=5 : 
  elem = list_head
  elem = head
  j = 1
  edx = i
  if ( j < v[i] ):
   do {
    elem = elem.next
    j ++
   }while (j < v[i])
  v2[i] = elem
  i++
  

This stage builds a list of pointers to elements, which is used in stage 3 and 4.
Using the previously deduced agorithm, the input numbers (0
which mean how much we move an element, to have them in reverse order, should be:
pos 1: 3 (head->next->next->next which is the biggest num)
pos 2: 1 (head->next, which is the second biggest )
. . . and so on.

Because of the advancing algorithm, we add 1 to the previous, and get the solution: 4 2 6 3 1 5

Secret Phase 

In the phase_difused function, we have another function called secret_phase, activated only after first stages are difused:

0x08049533 <+7>: cmp    DWORD PTR ds:0x804b480,0x6    
0x0804953a <+14>: jne    0x804959f <phase_defused+115> 

The passphrase from phase 4 is parsed again, now looking for a string. As we see below, we can get that string and advance:

0x08049544 <+24>: push   0x8049d03   --> "%d %s"    
0x08049549 <+29>: push   0x804b770   --> "9"  this is the input from phase_4    
0x0804954e <+34>: call   0x8048860 <sscanf@plt>    
0x08049553 <+39>: add    esp,0x10    
0x08049556 <+42>: cmp    eax,0x2    
0x08049559 <+45>: jne    0x8049592 <phase_defused+102>    
0x0804955b <+47>: add    esp,0xfffffff8    
0x0804955e <+50>: push   0x8049d09  --> "austinpowers"
0x08049563 <+55>: push   ebx    
0x08049564 <+56>: call   0x8049030 <strings_not_equal> 

We add the password "austinpowers" and get the following 2 messages printed:
Curses, you've found the secret phase!
But finding it and solving it are quite different...  
The secret_phase function calls another function, fun7 (very fun:) with an address and our input as a second parameter.

After digging int othe disassebly, the last fun7 is something like this:

int fun7(int *adr, int x) {
  if(adr == NULL) {
  ret = -1;  // 0xffffffff   
  goto exit;  
 }  
 if (x >= *adr) {
  if (x == *adr) {
   ret = 0   
  } else {
   ret = fun7(*(adr+8), x)
    ret *= 2;
    ret ++;
  }  
 } else {
  ret = fun7(*(adr+4), x)
   ret *= 2
 }  
exit:   
 return ret; 
} 

Initial address passed to the function is 0x804b320. At this address there is a tree with 4 levels, as below. We navigate to the left or right branch depending on the input value.  If input x is equal to value in branch, we return 0.
0x24
0x8 0x32
0x6 0x16 0x2d 0x6b
................................. 0x3e9
We want fun7() to return 7.

7 = 2*3+1 = 2*(2*1+1)+1.
According to the tree and deduced algorothm, we have:
f(0x24) = 0
f(0x32) = 2*f(0x24)+1 = 1
f(0x6b) = 2*f(0x32)+1 = 3
f(0x3e9) = 2*f(0x6b)+1 = 7

0x3e9 is 1001 decimal, and is accepted by the first check (param-1 <= 1000).

End
# ./bomb bomb-answers.txt

Welcome to my fiendish little bomb. You have 6 phases with which to blow yourself up. Have a nice day!
Phase 1 defused. How about the next one?
That's number 2. Keep going!
Halfway there!
So you got that one. Try this one.
Good work! On to the next...
Curses, you've found the secret phase!
But finding it and solving it are quite different...
Wow! You've defused the secret stage!
Congratulations! You've defused the bomb!
    Thanks to the guys at Open Security Trainings for the interesting materials there!