Binary Bomba - Fase 4

Question

Sto attraversando un periodo molto difficile per rintracciare il codice assembly per la seguente bomba binaria (un incarico da scuola in cui una bomba deve essere disinnescata, questa bomba contiene 6 fasi che hanno tutte 1 ingresso corretto per procedere alla fase successiva). Sono attualmente su phase_4 e ha una funzione ricorsiva chiamata func4. Ho identificato che l'input è "% d% d", ovvero due numeri interi. Tuttavia, non riesco a capire cosa sta facendo func4, anche dopo aver ottenuto le informazioni su tutti i registri in ogni fase.

Phase_4:

(gdb) disas 
Dump of assembler code for function phase_4: 
=> 0x08048e24 <+0>: sub $0x2c,%esp 
    0x08048e27 <+3>: lea 0x1c(%esp),%eax 
    0x08048e2b <+7>: mov %eax,0xc(%esp) 
    0x08048e2f <+11>: lea 0x18(%esp),%eax 
    0x08048e33 <+15>: mov %eax,0x8(%esp) 
    0x08048e37 <+19>: movl $0x804a7f1,0x4(%esp) 
    0x08048e3f <+27>: mov 0x30(%esp),%eax 
    0x08048e43 <+31>: mov %eax,(%esp) 
    0x08048e46 <+34>: call 0x80488d0 <__isoc99_sscanf@plt> 
    0x08048e4b <+39>: cmp $0x2,%eax 
    0x08048e4e <+42>: jne 0x8048e5d <phase_4+57> 
    0x08048e50 <+44>: mov 0x18(%esp),%eax 
    0x08048e54 <+48>: test %eax,%eax 
    0x08048e56 <+50>: js  0x8048e5d <phase_4+57> 
    0x08048e58 <+52>: cmp $0xe,%eax 
    0x08048e5b <+55>: jle 0x8048e62 <phase_4+62> 
    0x08048e5d <+57>: call 0x8049470 <explode_bomb> 
    0x08048e62 <+62>: movl $0xe,0x8(%esp) 
    0x08048e6a <+70>: movl $0x0,0x4(%esp) 
    0x08048e72 <+78>: mov 0x18(%esp),%eax 
    0x08048e76 <+82>: mov %eax,(%esp) 
    0x08048e79 <+85>: call 0x8048dbb <func4> 
    0x08048e7e <+90>: cmp $0x25,%eax 
    0x08048e81 <+93>: jne 0x8048e8a <phase_4+102> 
    0x08048e83 <+95>: cmpl $0x25,0x1c(%esp) 
    0x08048e88 <+100>: je  0x8048e8f <phase_4+107> 
    0x08048e8a <+102>: call 0x8049470 <explode_bomb> 
    0x08048e8f <+107>: add $0x2c,%esp 
    0x08048e92 <+110>: ret  
    End of assembler dump. 

Func4:

Breakpoint 2, 0x08048dbb in func4() 
(gdb) disas 
Dump of assembler code for function func4: 
=> 0x08048dbb <+0>: sub $0x1c,%esp 
    0x08048dbe <+3>: mov %ebx,0x14(%esp) 
    0x08048dc2 <+7>: mov %esi,0x18(%esp) 
    0x08048dc6 <+11>: mov 0x20(%esp),%eax 
    0x08048dca <+15>: mov 0x24(%esp),%edx 
    0x08048dce <+19>: mov 0x28(%esp),%esi 
    0x08048dd2 <+23>: mov %esi,%ecx 
    0x08048dd4 <+25>: sub %edx,%ecx 
    0x08048dd6 <+27>: mov %ecx,%ebx 
    0x08048dd8 <+29>: shr $0x1f,%ebx 
    0x08048ddb <+32>: add %ebx,%ecx 
    0x08048ddd <+34>: sar %ecx 
    0x08048ddf <+36>: lea (%ecx,%edx,1),%ebx 
    0x08048de2 <+39>: cmp %eax,%ebx 
    0x08048de4 <+41>: jle 0x8048dfd <func4+66> 
    0x08048de6 <+43>: lea -0x1(%ebx),%ecx 
    0x08048de9 <+46>: mov %ecx,0x8(%esp) 
    0x08048ded <+50>: mov %edx,0x4(%esp) 
    0x08048df1 <+54>: mov %eax,(%esp) 
    0x08048df4 <+57>: call 0x8048dbb <func4> 
    0x08048df9 <+62>: add %eax,%ebx 
    0x08048dfb <+64>: jmp 0x8048e16 <func4+91> 
    0x08048dfd <+66>: cmp %eax,%ebx 
    0x08048dff <+68>: jge 0x8048e16 <func4+91> 
    0x08048e01 <+70>: mov %esi,0x8(%esp) 
    0x08048e05 <+74>: lea 0x1(%ebx),%edx 
    0x08048e08 <+77>: mov %edx,0x4(%esp) 
    0x08048e0c <+81>: mov %eax,(%esp) 
    0x08048e0f <+84>: call 0x8048dbb <func4> 
    0x08048e14 <+89>: add %eax,%ebx 
    0x08048e16 <+91>: mov %ebx,%eax 
    0x08048e18 <+93>: mov 0x14(%esp),%ebx 
    0x08048e1c <+97>: mov 0x18(%esp),%esi 
    0x08048e20 <+101>: add $0x1c,%esp 
    0x08048e23 <+104>: ret  
End of assembler dump. 

Answer 1

Spero che sia ovvio che phase4 sta controllando che il primo numero è nel range 0 .. 14 compreso (vedi linee +44 .. +57 Quindi invoca func4 con tre argomenti: il primo numero immesso, 0 e 14 (righe +62 .. +85). Successiva verifica che il valore di ritorno è 0x25 (37 decimale) sulla linea +90 e che il secondo numero immesso è anche 37 (line +95)

Passiamo a func4. Chiamerò i tre argomenti x, low e high. Inizialmente non sai cosa sono, naturalmente. Righe +23 .. +34 calcolare (high - low)/2. Il pasticcio è che il compilatore genera codice per gestire numeri negativi con troncamento a zero. Non vedremo però numeri negativi. La linea +36 è solo un'aggiunta di fantasia, quindi in ebx ora abbiamo low + (high - low)/2 che è anche conosciuta come la media dei due numeri. Il codice confronta quindi questa media con il numero x che è stato fornito come primo argomento. Le righe +43 .. +62 vengono eseguite se x < average e invocano func4(x, low, average - 1) e aggiungono il valore restituito alla media. Allo stesso modo, le linee +70 .. +89 vengono eseguite se x > average e calcolare average + func4(x, average + 1, high). Se x == average viene restituita solo la media stessa.

Fondamentalmente fa una ricerca binaria e riassume le ipotesi mentre procede. Dato che l'intervallo ha 15 elementi, sarà necessario al massimo 4 ipotesi. La prima ipotesi sarà 7, quindi per ottenere il risultato richiesto di 37 abbiamo bisogno di 30 altro. Abbiamo al massimo altri 3 tentativi e tutte le ipotesi saranno meno di 7 o più di 7. Poiché 7 * 3 = 21 e che non ci può dare 30 significa che il numero deve essere maggiore di 7. La seconda ipotesi sarà quindi (8 + 14)/2 = 11, rendendo la nostra somma 18 con 19 altro ancora. Se il numero era superiore a 11 significa che supereremo il target, quindi il numero deve essere maggiore di 7 e minore di 11. Terza ipotesi è quindi (8 + 10)/2 = 9 che porta la somma a 27 con 10 in più da percorrere e solo una singola ipotesi, quindi ciò significa che il numero è 10.

TL; DR: l'ingresso corretto dovrebbe essere 10 e 37