第十三题 机器人历险记
早上的时候验证码出不来，补发一下
观察
描述写着是“智能硬件PWN”，但是没有给出服务器地址。解压下载到的压缩包之后用给出的 QEMU 命令行运行起来，发现其实还是个传统的输入答案告诉你对不对的逆向题。
$ file kanxuectf2018
kanxuectf2018: ELF 32-bit MSB executable, MIPS, MIPS-I version 1 (SYSV), statically linked, stripped
$ strings kanxuectf2018
<...>
gmp: overflow in mpz type
<...>
GCC: (GNU) 6.2.0
<...>
$ strings -n30 rootfs.img
<...>
/mnt/clfs/cross-tools/mips-linux-musleabi/include
<...>
../../../gcc-6.2.0/libgcc/soft-fp
<...>
GNU C11 6.2.0 -meb -minterlink-mips16 -msoft-float -mllsc -mabi=32 -g -g -g -O2 -O2 -O2 -fbuilding-libgcc -fno-stack-protector -fPIC -fexceptions -fnon-call-exceptions -fvisibility=hidden
<...>
可以看出给出的程序是一个大端的 MIPS-I 机器上运行的 Linux 中运行的 ELF，静态链接。其采用 GCC 6.2.0 编译，使用了 GMP 这个库。观察 rootfs 可以看出其似乎是作者对着 CLFS 编译出来的一套系统，采用了 musl 作为 libc，soft-fp，还能看到若干命令行。
分析
直接在反汇编器里裸分析 kanxuectf2018 显然是不太明智的，原因是程序中用到了大量 GMP 中的函数，如果不识别出来的话分析起来会比较困难。注意到上面提到的 CLFS 这个 tutorial 中给的 GCC 版本也是 6.2.0，不妨认为作者这一整套库就是这么编译出来的，于是照抄其中的 configure 参数，编译 cross GCC，交叉编译出 musl 和 GMP 的静态库，然后用 FLIRT 做出函数签名来，在 IDA Pro 里应用，即可识别出大部分 libc 函数和几乎所有的 GMP 函数，之后这个程序阅读起来就会容易很多。
接下来就是一通读代码了，可以找到 main 在 00405A00，逻辑十分简单，就是在一个 while (true) 中不断打出 banner，读入输入，验证，如果验证通过的话就退出（根据 init.d 里写的启动脚本来看，退出之后会被丢进一个 shell 里，可能就是这样强行掰成所谓的 PWN 的吧……）。
验证分几块：
- 首先验证输入的长度要大于等于 16，小于 129。
- 接下来调用 0040602C 验证前 16 个字符，将 00436FA0 处存储的固定字符串异或上
"Welcome to KanXue CTF 2018" 之后和输入比较，可以得出正确答案应该是 3f43ed6ff36724ca。另外对着那个异或的函数找一下交叉引用可以发现在 SIGTRAP 的 handler 里还用到了，对应的字符串解出来是 hint:k is 5532091271463842210，不妨记下备用。
- 接下来把整个输入分成两半，前一半调用 00406614 验证，后一半调用 0040615C 验证。
k 是一串数字这个 hint 提示我们我们可能要跟某种密码学算法较一会儿劲。
00406614 和 0040615C 这两个验证函数里面不止有调用 GMP，还有使用一些自己写的函数，我们经过一番观察之后会发现其实现了一些 GF(p) 上的椭圆曲线操作（暂时没时间写具体的分析教程，不熟悉 ECC 的可以去看 这个教程，是我见过的所有 tutorial 里面质量最高的之一），贴一下标注好的函数名和结构体：
00401520 NewCurve
004018B4 SetCurveParameters
00401BB0 shanzhai_mpz_powmod
00401F4C shanzhai_mpz_powmod_ui
00401FF8 TonelliShanks
00402BBC shanzhai_mpz_invert
004033F0 InitCurve
004034D0 NewPoint
00403670 LoadPoint
00403710 LoadPointHex
004037F4 PointDouble
00403838 PointAdd
00404620 ScalarPointMul
004047E8 LoadPointFromCompressedRep
00404F60 NewSignature
00405004 LoadSignature
00000000 Point struc # (sizeof=0x1C, mappedto_2)
00000000 x: __mpz_struct ?
0000000C y: __mpz_struct ?
00000018 field_18: .word ?
0000001C Point ends
0000001C
00000000 # ---------------------------------------------------------------------------
00000000
00000000 Curve struc # (sizeof=0x44, mappedto_3)
00000000 field_0_str: .word ?
00000004 p: __mpz_struct ?
00000010 a: __mpz_struct ?
0000001C b: __mpz_struct ?
00000028 G: .word ?
0000002C n: __mpz_struct ?
00000038 field_38: __mpz_struct ?
00000044 Curve ends
00000044
00000000 # ---------------------------------------------------------------------------
00000000
00000000 Signature struc # (sizeof=0x18, mappedto_4)
00000000 r: __mpz_struct ?
0000000C _s: __mpz_struct ?
00000018 Signature ends
找到初始化曲线参数的地方，把曲线参数抄出来：
p = 0x8d5b53dd2e70fc93
a = 0x348020e40410f914
b = 0x22bb96de83b3eb71
Gx = 0x1323f564d7976e65
Gy = 0x2a193d3e7a6b1e29
00406614 实现的是 ECDSA 签名验证，里面硬编码了一个公钥，验证输入是不是 "Welcome to KanXue CTF 2018" 的签名（hash 用的是 SHA-1）。到这里，0040602C 限制死的部分就很明确了，就是 ECDSA 签名的 (r, s) 里的 r。hint 里的 k 多半也就是签名过程中作为 "ephemeral key" 随机生成的那个 k 了。距离能还原还差一个私钥，考虑到 64 位对椭圆曲线上的离散对数来说算是一个不大不小的 key size，如果它没什么特殊性质的话要跑出来还是需要投入一些算力的，跑之前拿 sage 先胡乱算一算试一试：
E = EllipticCurve(GF(p), [0, 0, 0, a, b])
G = E(Gx, Gy)
n = G.order()
def DecompressPoint(pnt):
x = int(pnt[2:], 16)
y_selector = int(pnt[:2], 16) ^^ 2
ys = (GF(p)(x) ** 3 + a * x + b).sqrt(all=True)
y = ys[0] if int(ys[0]) % 2 != y_selector else ys[1]
return E(x, y)
pubkey = DecompressPoint('023ed6cee8b10a0da1')
dA = G.discrete_log(pubkey)
print dA
等一会儿之后会发现居然跑了出来，dA = 997247，看来是这个 key 放了水啊。
0040615C 实现的是是把输入的点加上一个写死的点，判断必须等于另一个点，没有难度，直接算出来即可。
解决
Sage 代码。
import hashlib
p = 0x8d5b53dd2e70fc93
a = 0x348020e40410f914
b = 0x22bb96de83b3eb71
Gx = 0x1323f564d7976e65
Gy = 0x2a193d3e7a6b1e29
k = 5532091271463842210 # via hint
E = EllipticCurve(GF(p), [0, 0, 0, a, b])
G = E(Gx, Gy)
n = G.order()
def DecompressPoint(pnt):
x = int(pnt[2:], 16)
y_selector = int(pnt[:2], 16) ^^ 2
ys = (GF(p)(x) ** 3 + a * x + b).sqrt(all=True)
y = ys[0] if int(ys[0]) % 2 != y_selector else ys[1]
return E(x, y)
pubkey = DecompressPoint('023ed6cee8b10a0da1')
# dA = G.discrete_log(pubkey)
dA = 997247
e = int(hashlib.sha1("Welcome to KanXue CTF 2018").hexdigest(), 16) % n
r = 0x3f43ed6ff36724ca
R = k * G
assert R.xy()[0] == r
s = Integer(Mod(e + dA * r, n) / k)
part1 = hex(r) + hex(s)
print part1
pnt2 = DecompressPoint('035aec40380efb5c07')
pnt3 = DecompressPoint('0379bd33edc62545df')
pnt1 = pnt3 - pnt2
x, y = pnt1.xy()
xstr = hex(Integer(x))
ystr = hex(Integer(y))
assert DecompressPoint('03' + xstr) == pnt1
part2 = xstr + ystr
print part2
print 'Answer:', part1 + part2
print 'Another solution:', hex(r) + hex(s + n) + part2
多解
ECDSA 那个验证的时候验证输入的时候把本来应该是 if (r >= 1 && r < n && s >= 1 && s < n) 的判断写成了 if (r >= 1 || r < n || s >= 1 || s < n)，相当于可以绕过对 r 和 s 的范围的检查。注意到 s + n 之后依然不超过 2**128，所以这样自然就可以构造出另一组解 3f43ed6ff36724cae43cb416321007c25f1524ad31c1c5667111e3d30e553e0e。
另外注意到输入的长度没有判断死，但是 buffer 的大小比较蛋疼，会有缺00的情况，但仔细构造的话应该还是能有办法构造出更多多解的，懒得搞了。
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
