看雪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_enc
4. 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 $v0
5. 验证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_enc
6. 验证签名(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
#include <miracl.h>
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交流平台，回馈安全社区。未来，我们将继续携手安全行业精英，探索互联网安全新方向，建设互联网生态安全，共铸“互联网+”新时代。
转载请注明：转自看雪学院
看雪CTF.TSRC 2018 团队赛 解题思路汇总：
看雪CTF.TSRC 2018 团队赛 第一题 『初世纪』 解题思路
看雪CTF.TSRC 2018 团队赛 第二题 『半加器』 解题思路
看雪CTF.TSRC 2018 团队赛 第三题 『七十二疑冢』 解题思路
看雪CTF.TSRC 2018 团队赛 第五题 『交响曲』 解题思路
看雪CTF.TSRC 2018 团队赛 第六题 『追凶者也』 解题思路
看雪CTF.TSRC 2018 团队赛 第七题 『魔法森林』 解题思路
看雪CTF.TSRC 2018 团队赛 第九题『谍战』 解题思路
看雪CTF.TSRC 2018 团队赛 第十题『侠义双雄』 解题思路
看雪CTF.TSRC 2018 团队赛 第十一题『伊甸园』 解题思路
看雪CTF.TSRC 2018 团队赛 第十二题『移动迷宫』 解题思路