TCTF 2019 Qualifier

Elements

IDA F5以后很容易定位到程序的验证逻辑

通过阅读反编译代码可以知道, 输入的flag格式是flag{[0-9a-f]{12}-[0-9a-f]{12}-[0-9a-f]{12}}

第一段是直接判断的0x391BC2164F0ALL 即flag{391bc2164f0a-[0-9a-f]{12}-[0-9a-f]{12}}

之后可以看到对几个变量的逻辑判断

if ( v24 <= v23 || v25 <= v24 || v23 + v24 <= v25 )
    break;
v19 = v24 * v24 + v23 * v23 - v25 * v25;
v20 = sqrt(4.0 * v23 * v23 * v24 * v24 - v19 * v19) * 0.25;
v21 = (v20 + v20) / (v23 + v24 + v25) + -1.940035480806554e13;
if ( v21 < 0.00001 && v21 > -0.00001 )
{
v22 = v23 * v24 * v25 / (v20 * 4.0) + -4.777053952827391e13;
if ( v22 < 0.00001 && v22 > -0.00001 )
    puts("Congratz, input is your flag");
}

令v24=a, b23=b, v25=c, v20=s 整理出以下逻辑:

s = $\frac{1}{4}$$\sqrt {4 a^2 b^2 - (a^2 + b^2 - c^2)^2}$

然后要满足两个条件

  • ${\frac{2 * s}{a + b + c}}\approx1.940035480806554e13$
  • ${\frac{a b c}{4 * s}}\approx4.777053952827391e13$

已知a = 0x391BC2164F0A

需要求得b和c

如果数学基础好的话可以看出来两个条件分别是三角形的内切圆和外接圆的半径公式,分别设为r和R

  • 由${\frac{a}{sin A}} = 2 * R$得$sin A = {\frac{a}{2R}}$
  • $cos A = {\frac{b^2 + c^2 - a^2}{2 b c}} = \sqrt{1-sin^2A}$
  • $b+c=a+b+c-a=a+4Rr(1+cosA){\frac{1}{a}}$
  • $bc=2Rr*\frac{(a+b+c)}{a}$
  • $c-b=\sqrt{(b + c)^2 - 4 * bc}$
  • $c = \frac{(b+c)+(c-b)}{2}$
  • $b = \frac{(b+c)-(c-b)}{2}$

由于在ida中的r和R会有一些精度丢失, 所以我在GDB中查看了这两个值:

gdb-peda$ p/f 0xc2b1a4ff41c1018b
$1 = -19400354808065.543
gdb-peda$ p/f 0xc2c5b939050828f4
$2 = -47770539528273.906

计算jio本:

from math import sqrt
a = 62791383142154.0
r = 19400354808065.543
R = 47770539528273.906
sinA = a / (2.0 * R)
cosA = sqrt(1.0 - sinA**2.0)
b_add_c = a + 4.0 * R * r * (1.0 + cosA) * (1.0 / a)
bc = 2.0 * R * r * (a + b_add_c) * (1.0 / a)
c_red_b = sqrt(b_add_c * b_add_c - 4.0 * bc)
c = (b_add_c + c_red_b) / 2.0
b = (b_add_c - c_red_b) / 2.0

print('flag{' + str(hex(int(a)))[2:] + '-' + str(hex(int(b)))[2:] + '-' + str(hex(int(c)))[2:] + '}')

flag{391bc2164f0a-4064e4798769-56e0de138175}

测试后发现不太对, 猜测是精度丢失问题, 在gdb中调试到两个字符串比较的位置看一下

测试b的比较:

gdb-peda$ b *0x400AE1
gdb-peda$ b *0x400AEB

测试c的比较:

gdb-peda$ b *0x400B0D
gdb-peda$ b *0x400B17

结果在0x400AE1发生了跳转, 即我们的输入计算出来的

$r - 19400354808065.543 >= 0.00001$

程序要求

$r-19400354808065.543 < 0.00001$

而$r = {\frac{2 * s}{a + b + c}}$, 即我们的b和c越大, 则r越小

尝试将b和c分别增加1

➜  ~ ./Elements
flag{391bc2164f0a-4064e4798770-56e0de138175}
➜  ~ ./Elements
flag{391bc2164f0a-4064e4798769-56e0de138176}
Congratz, input is your flag

最终flag: flag{391bc2164f0a-4064e4798769-56e0de138176}