机器人历险记-机器人历险记主角

第十三题《机器人大冒险》的攻关已于今日（12月27日）中午12点圆满结束！全场仅有两支队伍成功破解卫冕题。

他们是夺冠热门：铁拳和中午出题的砖家哭。其中，铁拳以78857分的成绩夺得了这道题的第一名！

这道题完成后，出题队伍朴香北方在答辩队伍总排名中位居第二。

防守队伍排名如下：

最新赛事情况概览

经过13个问题之后，攻击者的最新排名如下：

中午的时候，搬砖狗库库登顶榜首，铁拳上升一位来到第二位，黄金左手下降一位来到第三位，111new111从第十位上升到第六位，进步很大啊~！

重回第二位的铁拳会成为午间混战的最大威胁吗？

最后两个问题将改变哪些球队的命运？

对问题 13 的评论

无冠：

本题《机器人大冒险》主程序独特地采用了MIPS架构，因此考验选手的MIPS反汇编能力。另外，题目采用的是素数域64位弱椭圆曲线，要求选手掌握相关的密码学知识。总体来说，本题风格独特。

Question 13 团队简介

提问小组：向北漂流

北漂，团队里就我一人，之所以叫这个名字，是因为最近很喜欢这首歌，目前在做智能加密设备的开发，对这个领域有些了解，在学习的过程中得到了看学论坛的很多帮助，于是就想出了这么一个题目。

问题 13 设计思路

最初由 Snow Watching Forum 的 gxustudent 创建

1. 回答问题：

3f43ed6ff36724ca56e16038e692b5d75f1524ad31c1c5667111e3d30e553e0e

2.标题设计说明：

题目采用的是素数域64位弱椭圆曲线，曲线参数如下：

该参数可以通过查看二进制文件的字符串直接获取；

答案分为两部分：

第一部分是利用椭圆曲线算法（ECDSA）对字符串“Welcome to KanXue CTF 2018”进行签名得到的签名值R和S。

生成R和S需要曲线私钥，为了减少破解时间，采用弱私钥0xF377F，暴力破解1分钟内即可获取私钥。

通过反汇编该程序可以得到公钥。同时为了防止出现多组答案（因为ECC可以有不同的签名），输入的前16个字符会和异或加密后的答案进行对比。另外程序中还有关于ECDSA的提示：

“hint:k is 5532091271463842210;”，其中k值即为ECC标准X9.62中计算签名R值的k。

第二部分是椭圆曲线上点A的X坐标和Y坐标，将此点和椭圆曲线上的定点B相加，得到椭圆曲线上的定点C。

找到该点的方法是执行椭圆曲线减法：A=CB

通过查看二进制文件的字符串可以直接获取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 得出第二部分的答案。

原文链接：

问题 13：机器人历险记解决方案

此问题的解析由看学论坛的金凤建原创。

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（哈希）、r

解决

椭圆曲线相关知识参考：

（1）签名

h 是需要签名的哈希，私钥是 d，公钥 R = d*G

随机数 k，范围为 (1, n)

r = k * G 模 n

s = (h + rd)/k 模 n

（2）验证

u = h/s

宽度 = 长度 / 秒

v = u * G + w * R 模 n

验证 v == r

2.IDA调试

qemu-mips -g 23946 ./kanxuectf2018

选择“远程GDB调试器”进行IDA调试，设置断点并附加

3.初始化

椭圆曲线参数初始化

网关：（1323f564d7976e65，2A193D3E7A6B1E29）

答案：348020e40410f914

b: 22bb96de83b3eb71

邮件地址：8d5b53dd2e70fc93

名称：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, "欢迎参加 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