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
椭圆曲线: 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
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
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
.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
.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, loc_405DE8
.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, loc_405DE8
5. 验证r
xor_buf(g_r_enc, "Welcome to KanXue CTF 2018") == hex2bin(sn[0:16])
得到r: 3f43ed6ff36724ca (根据这个可知sn是全部小写的)
[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课
最后于 2019-1-2 14:20
被风间仁编辑
，原因： 备份下论坛上的ecdlp solver
