看雪CTF.TSRC 2018 团队赛-第13题-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

看雪CTF.TSRC 2018 团队赛-第13题

2018-12-26 12:04 5345

看雪CTF.TSRC 2018 团队赛-第13题

风间仁

2018-12-26 12:04

5345

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, loc_405DE8

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     mpz_cmp

根据 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进制字符转换时没有验证大小写, 所以存在多解

有个叫fastecdsa的python模块, 用来做椭圆曲线计算很方便, 可自定义曲线参数

import itertools
from fastecdsa.curve import Curve
from fastecdsa.point import Point
from gmpy2 import *


def test_mul():
    p = 0x8d5b53dd2e70fc93
    a = 0x348020e40410f914
    b = 0x22bb96de83b3eb71
    n = 0x8d5b53dd4b7d51eb
    gx = 0x1323f564d7976e65
    gy = 0x2A193D3E7A6B1E29
    rx = 0x3ed6cee8b10a0da1
    c64 = Curve('', p, a, b, n, gx, gy)
    G = Point(gx, gy, c64)
    for i in itertools.count(1):
        if i >= n:
            break
        if (i * G).x == rx:
            print('d: %s' % hex(i))
            break
        i += 1
    return


def test_sign():
    h = 0x2ABB294436DE91F4
    r = 0x3f43ed6ff36724ca
    d = 0xF377F
    k = 0x4CC5EFB37CA431A2
    n = 0x8d5b53dd4b7d51eb
    s = (h + r*d) * invert(k, n) % n
    print('s: %s' % hex(s))
    return


def test_add():
    p = 0x8d5b53dd2e70fc93
    a = 0x348020e40410f914
    b = 0x22bb96de83b3eb71
    n = 0x8d5b53dd4b7d51eb
    gx = 0x1323f564d7976e65
    gy = 0x2A193D3E7A6B1E29
    c64 = Curve('', p, a, b, n, gx, gy)

    x1 = 0x5aec40380efb5c07
    y1 = 0x1C3F07414C1B41C2
    x2 = 0x79bd33edc62545df
    y2 = 0x538788838577ED90

    p1 = Point(x1, y1, curve=c64)
    p2 = Point(x2, y2, curve=c64)
    p0 = p2 - p1
    print('P0(%s,%s)' % (hex(p0.x), hex(p0.y)))
    return


def test():
    test_mul()
    test_sign()
    test_add()
    return


test()

[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界

最后于 2019-1-2 14:20 被风间仁编辑，原因：备份下论坛上的ecdlp solver

上传的附件：

ECDLP Solver v0.2a.zip （628.75kb，10次下载）

收藏・0

点赞・2

打赏

最新回复 (1)
lukarl 雪币： 26 活跃值： (1307) 能力值： ( LV2，RANK：10 ) 在线值：发帖 14 回帖 162 粉丝 16 关注私信	lukarl 2018-12-29 12:12 2 楼 0 这么强，不知道是怎么修炼的，跪舔
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复