Binary Bomba – Fase 4

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 input corretto per passare 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 : sub $0x2c,%esp 0x08048e27 : lea 0x1c(%esp),%eax 0x08048e2b : mov %eax,0xc(%esp) 0x08048e2f : lea 0x18(%esp),%eax 0x08048e33 : mov %eax,0x8(%esp) 0x08048e37 : movl $0x804a7f1,0x4(%esp) 0x08048e3f : mov 0x30(%esp),%eax 0x08048e43 : mov %eax,(%esp) 0x08048e46 : call 0x80488d0  0x08048e4b : cmp $0x2,%eax 0x08048e4e : jne 0x8048e5d  0x08048e50 : mov 0x18(%esp),%eax 0x08048e54 : test %eax,%eax 0x08048e56 : js 0x8048e5d  0x08048e58 : cmp $0xe,%eax 0x08048e5b : jle 0x8048e62  0x08048e5d : call 0x8049470  0x08048e62 : movl $0xe,0x8(%esp) 0x08048e6a : movl $0x0,0x4(%esp) 0x08048e72 : mov 0x18(%esp),%eax 0x08048e76 : mov %eax,(%esp) 0x08048e79 : call 0x8048dbb  0x08048e7e : cmp $0x25,%eax 0x08048e81 : jne 0x8048e8a  0x08048e83 : cmpl $0x25,0x1c(%esp) 0x08048e88 : je 0x8048e8f  0x08048e8a : call 0x8049470  0x08048e8f : add $0x2c,%esp 0x08048e92 : ret End of assembler dump. 

Func4:

 Breakpoint 2, 0x08048dbb in func4 () (gdb) disas Dump of assembler code for function func4: => 0x08048dbb : sub $0x1c,%esp 0x08048dbe : mov %ebx,0x14(%esp) 0x08048dc2 : mov %esi,0x18(%esp) 0x08048dc6 : mov 0x20(%esp),%eax 0x08048dca : mov 0x24(%esp),%edx 0x08048dce : mov 0x28(%esp),%esi 0x08048dd2 : mov %esi,%ecx 0x08048dd4 : sub %edx,%ecx 0x08048dd6 : mov %ecx,%ebx 0x08048dd8 : shr $0x1f,%ebx 0x08048ddb : add %ebx,%ecx 0x08048ddd : sar %ecx 0x08048ddf : lea (%ecx,%edx,1),%ebx 0x08048de2 : cmp %eax,%ebx 0x08048de4 : jle 0x8048dfd  0x08048de6 : lea -0x1(%ebx),%ecx 0x08048de9 : mov %ecx,0x8(%esp) 0x08048ded : mov %edx,0x4(%esp) 0x08048df1 : mov %eax,(%esp) 0x08048df4 : call 0x8048dbb  0x08048df9 : add %eax,%ebx 0x08048dfb : jmp 0x8048e16  0x08048dfd : cmp %eax,%ebx 0x08048dff : jge 0x8048e16  0x08048e01 : mov %esi,0x8(%esp) 0x08048e05 : lea 0x1(%ebx),%edx 0x08048e08 : mov %edx,0x4(%esp) 0x08048e0c : mov %eax,(%esp) 0x08048e0f : call 0x8048dbb  0x08048e14 : add %eax,%ebx 0x08048e16 : mov %ebx,%eax 0x08048e18 : mov 0x14(%esp),%ebx 0x08048e1c : mov 0x18(%esp),%esi 0x08048e20 : add $0x1c,%esp 0x08048e23 : ret End of assembler dump. 

Spero sia ovvio che phase4 stia verificando che il primo numero sia compreso nell’intervallo 0 .. 14 incluso (vedi righe +44 .. +57 ) Quindi invoca func4 con tre argomenti: il primo numero inserito, 0 e 14 (righe +62 .. +85 ). Quindi controlla che il valore restituito sia 0x25 (37 decimale) sulla riga +90 e che anche il secondo numero immesso sia 37 (riga +95 )

Passiamo a func4 . Chiamerò i tre argomenti x , low e high . Inizialmente non sai cosa sono, naturalmente. Righe +23 .. +34 calcola (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 conosciuto 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 calcolano la average + func4(x, average + 1, high) . Se x == average media, viene restituita solo la media stessa.

Fondamentalmente sta facendo una ricerca binaria e riassumendo le ipotesi come va. 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 altri 30 . Abbiamo al massimo 3 più tentativi e tutte le ipotesi saranno inferiori a 7 o più di 7. Poiché 7 * 3 = 21 e che non può darci 30 significa che il numero deve essere maggiore di 7. Secondo indovinare è così sarà (8 + 14) / 2 = 11 , rendendo la nostra sum 18 con 19 più per andare. 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 sum a 27 con altri 10 a vai e basta una sola ipotesi, quindi significa che il numero è 10 .

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