看雪CTF.TSRC 2018 团队赛 第十三题『 机器人历险记』 解题思路
第十三题《机器人历险记》在今天（12月27日）中午12:00 结束攻击！只有两支团队成功破解防守方的题目。
Ta们是冠军热门人选：tekkens 和 中午放题搬砖狗哭哭，其中 tekkens以 78857s 的成绩夺得本题第一名！
本题结束后，出题团队 飘向北方 位居防守团队总排行榜第二名。
防守团队排行榜如下：
最新赛况战况一览
第十三题之后，攻击方最新排名情况如下：
中午放题搬砖狗哭哭名列榜首， tekkens上升一名至第二名，金左手下降一名至第三名，111new111从第十名上升至第六名，进步很大~！
回归第二名的 tekkens 会是 中午放题搬砖狗哭哭 最大的威胁吗？
最后两题会改变哪些团队的命运？
crownless：
“机器人历险记”此题的主程序特立独行地采用了MIPS架构，因此考验了参赛者的MIPS反汇编水平。另外，题目使用素域64bit弱椭圆曲线，要求参赛者掌握相关的密码学知识。总的来说，这道题风格独特。
出题团队：飘向北方
飘向北方，团队就我一个人，之所以叫这个名字是因为这段时间很喜欢这首歌，我目前在在做智能加密设备的开发，对这块有所了解，而且在学习的过程中，得到了看雪论坛的很多帮助，所以出了这样一道题目。
由看雪论坛 gxustudent 原创
1. 题目答案：
3f43ed6ff36724ca56e16038e692b5d75f1524ad31c1c5667111e3d30e553e0e
2. 题目设计说明：
题目使用素域64bit弱椭圆曲线，曲线参数如下：
p: "8d5b53dd2e70fc93"
a: "348020e40410f914"
b: "22bb96de83b3eb71"
Gx: "1323f564d7976e65"
Gy: "2a193d3e7a6b1e29"
n: "8d5b53dd4b7d51eb"
h: "01"
该参数可以通过查看二进制文件的字符串直接获得;
答案分为两部分：
第一部分为根据字符串"Welcome to KanXue CTF 2018"使用椭圆曲线算法(ECDSA)进行签名所得到的签名值的R和S。
生成R和S需要曲线私钥, 为了减少破解时间，使用弱私钥0xF377F，私钥可以使用暴力穷举在1分钟内得到；
公钥可以通过反汇编程序得到。同时。（因为ECC可以有不同的签名）为了防止出现多组答案，会对输入的头16个字符和xor加密后的答案进行比较。另外，程序中有关于ECDSA的提示：
"hint:k is 5532091271463842210;"，其中k值是ECC标准X9.62中用于计算签名R值的k。
第二部分为椭圆曲线上的点A的X坐标和Y坐标，该点与椭圆曲线上的固定点B相加得到椭圆曲线上的固定点C；
求该点的办法为执行椭圆曲线减法： A=C-B
点B和点C的值可以通过查看二进制文件的字符串直接得到。
题目运行时需要先安装qemu。
题目运行命令如下:
qemu-system-mips -kernel ./vmlinux -hda rootfs.img -append "root=/dev/sda console=ttyS0" -serial stdio -m 256
题目提供两个文件：
rootfs.img: 文件系统文件
vmlinux linux内核文件
需要反编译的文件在文件系统/bin/kanxuectf2018中，大小为246k，使用mips指令集
文件系统为ext4文件格式。
题目有两种反调试手段：
# ptrace反调试
# SIGTRAP反调试
3. 破解思路
3.1 通过反汇编拿到曲线参数, 曲线公钥,C点坐标, B点坐标；
3.2 暴力穷举得到私钥,进行签名,得到答案第一部分；
3.3 C- B 得到答案第二部分。
原文链接：
https://bbs.pediy.com/thread-247857.htm
本题解析由看雪论坛 风间仁 原创。
1. 总体逻辑
sn格式：[r][s][P0_x][P0_y]
(r,s)为ecdsa签名，P0为椭圆曲线上的点
椭圆曲线：y^2=x^3+ax+b
已知G(基点)， R(公钥)，a, b, p, n, h(hash), r
求解s
椭圆曲线相关知识参考:
https://bbs.pediy.com/thread-152615.htm
(1)签名
h为要签名的hash, 私钥为d, 公钥R = d*G
随机数k , 范围在(1, n)
r = k * G mod n
s = (h + rd)/k mod n
(2)验证
u = h/s
w = r/s
v = u * G + w * R mod n
验证v == r
2. IDA调试
qemu-mips -g 23946 ./kanxuectf2018
IDA调试选择"Remote GDB debugger", 下好断点附加上去
3. 初始化
椭圆曲线参数初始化
G: (1323f564d7976e65, 2A193D3E7A6B1E29)
a: 348020e40410f914
b: 22bb96de83b3eb71
p: 8d5b53dd2e70fc93
n: 8d5b53dd4b7d51eb
.text:004069F8 x_init
.text:00403430 la $v0, g_NP # "8d5b53dd4b7d51eb"
.text:00403438 sw $v0, 0x38+var_1C($sp)
.text:0040343C la $v0, g_G_y # "2a193d3e7a6b1e29"
.text:00403444 sw $v0, 0x38+var_20($sp)
.text:00403448 la $v0, g_G_x # "1323f564d7976e65"
.text:00403450 sw $v0, 0x38+var_24($sp)
.text:00403454 la $v0, g_B # "22bb96de83b3eb71"
.text:0040345C sw $v0, 0x38+var_28($sp)
.text:00403460 lui $v0, 0x43 # 'C'
.text:00403464 addiu $a3, $v0, (g_A - 0x430000) # "348020e40410f914"
.text:00403468 lui $v0, 0x43 # 'C'
.text:0040346C addiu $a2, $v0, (g_P - 0x430000) # "8d5b53dd2e70fc93"
.text:00403470 lui $v0, 0x43 # 'C'
.text:00403474 addiu $a1, $v0, (a8d5b53d - 0x430000) # "8d5b53d"
.text:00403478 lw $a0, 0x38+arg_0($fp)
.text:0040347C la $v0, ecurve_init
.text:00403480 nop
.text:00403484 move $t9, $v0
.text:00403488 bal ecurve_init随机数k的提示
x_decrypt_k_hint这个函数不会被调用
xor_buf(g_k_hint_enc, "Welcome to KanXue CTF 2018")
得到k: 4CC5EFB37CA431A2
.text:00406A68 addiu $a1, $v0, (x_decrypt_k_hint - 0x400000)
.text:00406A6C li $a0, 5
.text:00406A70 la $v0, sub_430370
.text:00406A74 nop
.text:00406A78 move $t9, $v0
.text:00406A7C jalr $t9 ; sub_430370
.rodata:00436F80 g_k_hint_enc4. sn长度验证
0x10 <= len(sn) < 0x81
.text:00405C1C lw $v0, 0x430+sn_len($fp)
.text:00405C20 nop
.text:00405C24 sltiu $v0, 0x81
.text:00405C28 beqz $v0, loc_405DDC
.text:00405C2C nop
.text:00405C30 lw $v0, 0x430+sn_len($fp)
.text:00405C34 nop
.text:00405C38 sltiu $v0, 0x10
.text:00405C3C bnez $v05. 验证r
xor_buf(g_r_enc, "Welcome to KanXue CTF 2018") == hex2bin(sn[0:16])
得到r: 3f43ed6ff36724ca (根据这个可知sn是全部小写的)
.text:00405CAC addiu $v0, $fp, 0x430+sn
.text:00405CB0 move $a0, $v0
.text:00405CB4 jal x_verify_r
.rodata:00436FA0 g_r_enc6. 验证签名(h,r,s)
G: (1323f564d7976e65, 2A193D3E7A6B1E29)
R: (3ed6cee8b10a0da1, 11c6014cdcc1fd13)
h = mpz(sha1("Welcome to KanXue CTF 2018")) % p = 2ABB294436DE91F4
ecdsa_verify(h, r, s)
.text:00405D30 jal x_verify_sign
公钥R
.text:004066EC bal epoint_set
.rodata:00436FD8 g_R
epoint_set中根据y的计算方式可知是椭圆曲线
y=(x^3+ax+b)^((p+1)/4) % p
因为p是素数, 所以 x^p % p = x
y^4=(x^3+ax+b)^((p+1)) % p=(x^3+ax+b)^2 % p
y^2=(x^3+ax+b) % p
计算h
.text:004066F8 la $v0, aWelcomeToKanxu # "Welcome to KanXue CTF 2018"
.text:00406714 bal sha1
.text:00406760 bal mpz_init_set_str
.text:004067D8 bal mpz_mod
验证签名
.text:00406974 bal ecdsa_verify
u = h/s
.text:00405638 bal mpz_invert
.text:0040566C bal mpz_mod
.text:0040569C bal mpz_mul
.text:004056D4 bal mpz_mod
w = r/s
.text:00405704 bal mpz_mul
.text:0040573C bal mpz_mod
u*G
.text:00405774 bal ecurve_mult
w*R
.text:004057A0 bal ecurve_mult
v = u * G + w * R mod n
v == r
.text:004057C8 bal ecurve_add
.text:004057F4 bal根据 R = d*G 穷举私钥d, 得到d: F377F
void test_d()
{
big a = mirvar(0);
big b = mirvar(0);
big p = mirvar(0);
cinstr(a, "348020E40410F914");
cinstr(b, "22BB96DE83B3EB71");
cinstr(p, "8D5B53DD2E70FC93");
ecurve_init(a, b, p, MR_AFFINE);
big G_x = mirvar(0);
big G_y = mirvar(0);
cinstr(G_x, "1323f564d7976e65");
cinstr(G_y, "2A193D3E7A6B1E29");
epoint* G = epoint_init();
if (!epoint_set(G_x, G_y, 0, G))
{
return;
}
big R_x = mirvar(0);
cinstr(R_x, "3ed6cee8b10a0da1");
big d = mirvar(0);
big x = mirvar(0);
epoint* ep = epoint_init();
char tmp[256];
for (DWORD64 i = 0x1; i < 0x8d5b53dd4b7d51eb; i++)
{
sprintf(tmp, "%016I64x", i);
cinstr(d, tmp);
ecurve_mult(d, G, ep);
epoint_get(ep, x, x);
if (compare(x, R_x) == 0)
{
print_big(d); // F377F
break;
}
}
}计算sign
h: 2ABB294436DE91F4
r: 3f43ed6ff36724ca
d: F377F
k: 4CC5EFB37CA431A2
n: 8d5b53dd4b7d51eb
s = (h + rd)/k mod n
得到s: 56e16038e692b5d7
void test_sign()
{
big n = mirvar(0);
big d = mirvar(0);
big h = mirvar(0);
big k = mirvar(0);
big k_inv = mirvar(0);
big r = mirvar(0);
cinstr(n, "8d5b53dd4b7d51eb");
cinstr(d, "0F377F");
cinstr(h, "2ABB294436DE91F4");
cinstr(k, "4CC5EFB37CA431A2");
invert(k, n, k_inv);
cinstr(r, "3f43ed6ff36724ca");
multiply(r, d, r);
add(r, h, r);
multiply(r, k_inv, r);
divide(r, n, n);
print_big(r);
}7. 验证(P0_x, P0_y)
P0, P1, P2为椭圆曲线上的点
P1: (5aec40380efb5c07, 1C3F07414C1B41C2)
P2: ( 79bd33edc62545df, 538788838577ED90 )
P0 + P1 == P2, 得到P0: (5F1524AD31C1C566, 7111E3D30E553E0E)
.text:00405D80 jal x_verify_P0
P0 + P1 == P2
.text:00406460 bal epoint_set
.text:00406490 bal epoint_set
.text:004064C4 bal ecurve_add
.text:004064F0 bal mpz_cmp
.text:00406530 bal mpz_cmp
.rodata:00436FB0 g_P1
.rodata:00436FC4 g_P2得到sn：
3f43ed6ff36724ca56e16038e692b5d75f1524ad31c1c5667111e3d30e553e0e
[r][s][P0_x][P0_y] 中除了r之外, 其他16进制字符转换时没有验证大小写, 所以存在多解。
原文链接：
https://bbs.pediy.com/thread-248656.htm
第十四题【 你眼中的世界】正在火热进行中
第14题/共15题
《你眼中的世界》将于 12月29 日中午 12:00 结束
赶紧参与进来吧~！
热门图书推荐：
合作伙伴
腾讯安全应急响应中心
TSRC，腾讯安全的先头兵，肩负腾讯公司安全漏洞、黑客入侵的发现和处理工作。这是个没有硝烟的战场，我们与两万多名安全专家并肩而行，捍卫全球亿万用户的信息、财产安全。一直以来，我们怀揣感恩之心，努力构建开放的TSRC交流平台，回馈安全社区。未来，我们将继续携手安全行业精英，探索互联网安全新方向，建设互联网生态安全，共铸“互联网+”新时代。
- End -
公众号ID：ikanxue
官方微博：看雪安全
商务合作：wsc@kanxue.com