首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 茶余饭后
    3. 发新帖
[推荐]看雪CTF.TSRC 2018 团队赛 第十三题『 机器人历险记』 解题思路
发表于: 2018-12-27 18:07 1476

[推荐]看雪CTF.TSRC 2018 团队赛 第十三题『 机器人历险记』 解题思路

Editor 活跃值
2018-12-27 18:07
1476


第十三题《机器人历险记》在今天（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 团队赛 解题思路汇总： 















[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

收藏
免费 ・0
支持
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//