0CTF 2019 Elements Writeup
0ctf 2019的一道逆向題
題目逆向
先拖進ida簡單看一下,又是典型的輸入flag過check的逆向題。如果通過check則輸出 Congratz
。我們一個一個檢檢視:
首先是一個常規的檢查,讀取輸入,然後檢查輸入的長度是0x2c,檢查輸入是否以 flag{
開頭,以 }
結尾。
之後對輸入掐頭去尾,對中間剩餘的內容用 -
來分割,得到一個字串序列。之後會解析這個序列裡的每一個元素,檢查其長度是否為12,把字串轉化為對應的數字,比如把字串 dead
轉化為數字0xdead,即57005。此外,如果是序列中的第一個元素,會判定其是否是一個特定值0x391bc2164f0a,程式碼如圖:
因此我們可以得到flag的第一部分就是 391bc2164f0a
檢查3是最複雜的部分。首先程式會把之前從字串解析出來的數字做一個轉換:
這個轉換用了一些奇怪的API,我們先不管。
當解析了3個序列之後會進入檢查3,程式碼如圖:
input1
, input2
, input3
分別是我們輸入的3個序列,其中 input1
已知。首先會對三個序列的大小關係做了一個比較,然後對這三個序列做了一系列複雜的運算,包括開根號和浮點數運算,最後得到兩個浮點數的值 tmp3
和 tmp4
,如果這兩個值分別是1.94003…和4.77705….則通過檢查。
雖然現在我們只有兩個未知數和兩個等式,但是這並不是一次方程,運算過程中有平方和開根號,可以嘗試用平方消去根號,最後得到了一個四次方程,很難直接求出 input2
和 input3
三角函式公式和三斜求積術
我們大膽猜測,題目所做的運算應該不是無意義隨便構造出來的,而是有其物理/數學意義的。經過一些搜尋,我們發現tmp2進行的運算,實際是秦九韶公式,或稱為三斜求積術,是海倫公式的一種等價表示。
對於三角形三邊a,b,c;其中c為最長邊,a為最短邊,則三角形的面積S可以表示為:
在題目中,根據check3中一開始對三個值的比較可知 input1
是最短邊(a), input3
是最長邊(c)。 tmp2
是三角形面積S。這樣我們可以把 tmp3
和 tmp4
改寫為:
tmp3 = 2S/(a+b+c) tmp4 = abc/(4*S)
根據三角函式的相關知識我們可以知道 tmp3
表示三角形內切圓半徑, tmp4
表示三角形外接圓半徑。
tmp3 = 2S/(a+b+c)=r tmp4 = abc/(4*S)=R
題目轉化為已知三角形最短邊a以及三角形外接圓半徑R和三角形內切圓r,求三角形的其他兩邊。
列出方程
下面就要列方程解這個三角函式問題。
首先利用正弦定理
a/sin A = 2*R
得到
sin A = a/(2R)
根據餘弦定理,
cos A = (b^2+c^2-a^2)/(2bc)= sqrt(1-(sin A)^2)
聯立上述多個等式得到
4Rr(1+cosA)/a = T1 = 4 * tmp3 * tmp4 *(b^2+c^2-a^2+2bc)/2bc =(abc) * (b+c+a) * (b+c-a)/(a * bc * (a+b+c)) = b + c - a
即 b + c = a + T1 = T2
之後聯立兩個面積公式得到
S = abc/4R = (a + b + c)r/2 abc = 2Rr(a+b+c)=2Rr(a+T2) bc= 2Rr(a+T2)/a = T3
得bc後計算c-b,並得到最終的解
c-b = sqrt((c+b)^2 - 4bc) = sqrt(T2^2-4T3) = T4 c = (T2+T4)/2 b = (T2-T4)/2
解題指令碼
from math import sqrt r = 1.940035480806554e13 R = 4.777053952827391e13 a = 62791383142154.0 sinA = a / (2.0 * R) cosA2 = 1 - sinA**2 cosA = sqrt(cosA2) T2 = a+4*R*r*(1+cosA)/a#b+c T3 = 2*R*r*(a+T2)/a #bc T4 = sqrt(T2*T2-4*T3)#c-b c = int((T2+T4)/2) b = int((T2-T4)/2) print c print b
這個指令碼算的b和c會有一些精度的丟失,我們可以手動調整一下b和c的個位,輸到程式裡檢查b和c是否正確。
最後得到 flag{391bc2164f0a-4064e4798769-56e0de138176}