Defcon17 Wargame Crypto_Badness 400 解題過程

接續上一篇 Defcon 17 Wargame 競賽解題心得，這次分享的是 Crypto_Badness 400 的題目解題過程。

此題提供下載一個檔案，題目說明表示，此程式正在 pwn11.ddtek.biz 主機上執行，該程式為一 FreeBSD 的可執行檔，執行時會開 TCP Port 7852。直接用工具 nc 連向 pwn11.ddtek.biz 7852，即出現詢問 Password。所以按照慣例，先來個 strings 指令，觀察檔案內容。



其中有個字串，”chickenfingers” 應該就是該 Password 要問的答案了。當 Password: 提示出現時，輸入 chickenfingers，出現 What is your name? 時，隨便亂輸入 1234567890，最後出現如下圖:


要求解出該加密過的字串，該加密字串的每一字元用 16 進制表示。
接下來就不知要幹嘛，只好把原來的 FreeBSD執行檔，再來作分析，這一次改用工具 objdump 作反組譯(Disassemble)以及逆向工程(Reverse Engineering)，分析結果如下:

• 為一對稱式加密法，先取得五個亂數數值，每個亂數值為 0~255 (0x00~0xff) 之間，再建立一個 256 字元的陣列，陣列中每個值介於 0 至255。利用此五個亂數數值為亂數種子，擴充成 256 個亂數數值，存於此陣列中。
• 利用簡單的 XOR 運算來加密，從明文中逐一取得字元，再從前面擴充成 256 個亂數陣列中，取一數值，來和明文的該字元 XOR，當明文的每一字元完成 XOR 後，即為密文。每次從 256 個亂數陣列中取值的方式則和明文字元的位置有關。
• 由於 XOR 的特性，若是把密文的每個字元和 Key 的每個字元作 XOR 就可以反解成明文。透過程式的逆向工程，可以知道加密演算法，甚至可以直接取用相關計算函式。如此一來，我們只要猜測一開始亂數取得的五個亂數字元，就可以把 256 字元的亂數陣列值計算出來。
• 不過，若是嘗試寫程式用暴力法計算，五個亂數數值全部猜測，就要計算 256 的 5 次方，而且，如何判斷該亂數值是否猜測正確呢?
• 由於明文是從純文字檔內讀取 32 個字元，所以假設明文都是可顯示之字元(包含大小寫英文、符號及空白字元)，那就可以在暴力法每回解出明文時，掃瞄一次明文字元是否都為可顯示之字元，若是，就假設為明文字串，全部顯示出來。
  

這下就可以寫程式，計算 256 的 5 次方，求解明文了！但是這樣跑程式實在太慢了，就算試著用一些最佳化或分散運算的方式，仍然要等上很久。


回過頭來重新檢視之前的輸入輸出。當 Password: 提示出現時，輸入 chickenfingers，出現 What is your name? 時，則輸入 1234567890，最後出現如下圖:



奇怪，1234567890 字串到 ? 字元出現的中間有一段空白，改用 hexedit 編輯看看:



這樣就看清楚了，在 1234567890 字串後面，接了 6 個空白字元(0x20)，然後一個字元(0xCE)，再一個 : (0x3A)字元。這個 0xCE 字元，即為一開始取五個亂數值中的第一個數值。
五個亂數值中，第一個數值已知，如此一來，就可以動手寫暴力破解程式，計算 256 的 4 次方，即可找出\x5f\x92\x84\xbc\xe\x16\xab\x2a\x92\x97\x63\x78\x06\x5f\xa1\x3a\xa3\xee\xa9\xc3\xee\x49\xea\xea\x92\x1a\x36\x2e\xa8\x7c\x28\x0cf 的明文。

透過分散數台電腦來分批執行暴力破解程式，但仍然很慢，花了數個小時仍找不出明文字串。這時想到，原來的程式中，輸出的函式有兩組，另一組會輸出兩倍長度的字元。假若我可以改變程式流程，跳躍至另一組輸出函式，也許可以輸出五個亂數值中的前兩個數值，這樣就可以跑計算次數降為 256 的 3 次方。

將所附的程式碼再重新反組譯，可以觀察出程式中有一個變數可以控制字元輸出的長度。該變數位在 -0x25(%ebp)，此變數值是由 -0x29(%ebp) 和 1 作 AND 運算後的結果，若此變數 -0x25(%ebp) 的值為 1 是，則會輸出兩倍長度的字元。



當 Password: 提示出現時，輸入 chickenfingersa (故意多打一個字元，造成 one byte 溢出)，出現 What is your name? 時，則輸入 ABCDEFGHIJKLMNOABCDEFGHIJKLMNO，最後出現如下圖:





在 ABCDEFGHIJKLMNOABCDEFGHIJKLMNO 字串後面，接了 2 個換行字元(0x0A)，然後三個字元(0xD9、0xE2、0x00)，再接一個 : (0x3A)字元。其中 0xD9、0xE2 字元，即為一開始取五個亂數值中的前兩個數值。這樣一來跑暴力破解程式實在快多了，不到十秒就出現一組明文。



不過這明文怎麼看都不像啊！讓暴力破解程式繼續執行，很快地，又發現第二組明文啦。

賓果! 解出明文了！

註: 暴力破解程式的解密函式是直接從原程式作逆向工程後取用，變數處理要注意 signed/unsigned 的問題，否則從亂數陣列取值時會計算不正確。