二進制炸彈 - 階段4

Question

我在追查下面的二進制炸彈的彙編代碼時非常困難（一個學校需要拆卸炸彈的任務，這個炸彈包含6個階段，所有階段都有1個正確的輸入來繼續到下一個階段）。我目前在phase_4上，它有一個稱爲func4的遞歸函數。我發現輸入是「％d％d」，它是兩個整數。然而，我無法弄清楚func4正在做什麼，即使在每一步都獲得了所有寄存器的信息之後。

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

我希望這是顯而易見的phase4被檢查的第一個數字範圍爲0 .. 14包容性（見線+44 .. +57 ） 然後它用三個參數調用func4：輸入的第一個數字，0和14（行+62 .. +85）。接下來，它會檢查返回值是0x25（37進制）上線+90的形式進入第二個數字也37（線+95）

讓我們轉移到func4。我會打電話給三個參數x,low和high。最初你不知道他們當然是什麼。行+23 .. +34計算(high - low)/2。醜陋的混亂是因爲編譯器生成代碼來處理截斷爲零的負數。我們不會看到任何負數。行+36只是一個奇特的加法，所以在ebx我們現在有low + (high - low)/2這也被稱爲兩個數字的平均值。然後代碼將該平均值與作爲第一個參數提供的數字x進行比較。行+43 .. +62得到執行，如果x < average和他們調用func4(x, low, average - 1)並將返回的值添加到平均值。同樣，如果x > average和average + func4(x, average + 1, high)計算行+70 .. +89得到執行。如果x == average那麼只是平均本身返回。

它基本上是做二進制搜索和總結猜測，因爲它走了。鑑於間隔有15個元素，它最多需要4次猜測。第一個猜測是7，所以要得到37的所需結果，我們需要更多的30。我們至多再有3次嘗試，所有猜測都將小於7或超過7.因爲7 * 3 = 21並且不能給我們30這意味着數字必須大於7.第二個猜測因此將是(8 + 14)/2 = 11，使我們的款項18與19更多。如果這個數字超過了11，這意味着我們超過了目標，那麼這個數字必須大於7並且小於11.因此第三個猜測是(8 + 10)/2 = 9，它帶來的總和爲27且10更多，只是一個猜測，所以這意味着號碼是10。

TL; DR：正確的輸入應該是10和37