首页
论坛
专栏
课程

看雪CTF2019Q2-第10题 开启时间之轮

2019-6-19 01:54 1048

看雪CTF2019Q2-第10题 开启时间之轮

2019-6-19 01:54
1048
设置name(4个name中随机选1个),
按换行符分隔转换成16进制
name_part1记为Y, name_part2记为G
.text:004040D0 x_set_rnd_name

.text:00403F0C                 push    offset aDS      ; "%d\n%s"
.text:00403F11                 push    ecx             ; char *
.text:00403F12                 call    _sscanf

Y: 67
G: 1DB49DFF25CFF1A955529516A2B1D92728988B150F53514B6ABB26A8EC6F4FE3

Y: 66
G: 54D8FFDD81B50AC27A20DBD697C9A530841471595B691B7F4336FF5313867ABC

Y: 65
G: 6F7570369DA6669C5F2E620CCB6F2379BF5E790929BC7989B5AE5E088D510782

Y: 64
G: 14681B5AB4AA11E0CE7AF892923160F7C975EE6688141717927C2A0904B38767

sn以XXXX分隔, 前半部分记为v1(256进制), 后半部分记为v2(10进制)
.text:00403FA1                 call    x_extract_XXXX

验证sn, 返回结果必须为0
.text:00404004                 call    x_404270

素数p=2^255-19=7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED
phi(p)=p-1=7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC
.text:00403E94                 mov     [esp+8CCh+prime_arg], 2
.text:00403E9C                 mov     [esp+8CCh+prime_arg+4], 0FFh
.text:00403EA4                 mov     [esp+8CCh+prime_arg+8], 0FFFFFFEDh

.text:0040445E                 call    big__set_int
.text:0040446F                 call    big__pow_int
.text:00404480                 call    big__add_int
.text:00404492                 call    big__sub_int
.text:004044A2                 call    big__set_int

4*v2 < p
.text:00404587                 call    big__add
.text:004045A1                 call    big__add
.text:004045B1                 call    big__compare

x=v2-v1
验证 64x^4+x^2+3 mod p == v1 
.text:00404607                 call    big__sub
.text:0040462A                 call    big__powmod_int
.text:0040464A                 call    big__ax_plus_b_mod_p

.text:00404683                 call    big__sub
.text:0040468F                 call    big__get_int

v1的最后1个字符+10, 判断是否为25进制(ABCDEFGHKJILMNOPQRSTUVWYZ)
v1最大值: ZZZZZZZZZP (0x56bc75e2d630)
验证 gcd(phi(p), v1) == 1
验证 G==Y^(v1^(-1) mod phi(p)) mod p
验证 Y==G^v1 mod p
.text:004046B2                 push    'X'
.text:004046B4                 call    x_get_index
...
.text:00404729                 mov     dl, [edx+0Ch]
.text:0040472C                 add     [ebp+var_40708], dl

.text:00404835                 call    x_gcd
.text:00404841                 call    big__get_bits

.text:00404867                 call    big__invert
.text:00404889                 call    big__powmod
.text:004048A0                 call    big__sub
.text:004048AC                 call    big__get_int

.text:004048D9                 call    big__powmod
.text:004048F6                 call    big__sub
.text:00404909                 call    big__get_int

任选一组Y,G, 用readyu的dlp工具算出v1(25进制): KCTFREADYK
Discrete log of y= 4898F769D4A5 (16进制)
Total Time cost: 17 sec, 129 ms.
DLP v1.1 cfg file, readyu

G ^ X = Y (mod P), solve X
Knowing Order PHI, G ^ PHI = 1 (mod P)
and all prime factors of PHI

[START OF CONFIG FILE]
// must keep this line

[VERSION]

[SEED]
0

[NUMBER BASE]
16

[BITS]
256

[LIMIT1]
1
[LIMIT2]
56bc75e2d630

[P/MODULUS]
7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFED

[PHI/ORDER]
7FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEC

[G/BASE]
1DB49DFF25CFF1A955529516A2B1D92728988B150F53514B6ABB26A8EC6F4FE3

[Y/PUB]
67

[X/PRI]


[PHI PRIME FACTORS NUMBERS]
4

[PHI PRIME FACTORS LISTS]
2^(2)
3^(1)
FE7B^(1)
ABAF8C6B094FD0F32C2CCABAB864DBECD99144679C1ADF804898FB2042B^(1)

[TEST]


[END OF CONFIG FILE]

v2: 

v1=0x4B435446524541445955
x=v2-v1
64x^4+x^2+3 mod p = v1 

令x=x^2, a=64, b=1, c=3-v1
令y=2ax+b
y^2=b^2-4ac=0x4B43544652454144595201 mod p

YXP -> G
y=0x5A7487C5DDFEA4F75939B04AA9BB4553325DFEB8C2B498797DEFA98F8397F495

x^2=(y-b)/(2a)=0x1CB4E90F8BBBFD49EEB273609553768AA664BBFD71856930F2FBDF531F072FE5
YXP -> G
x=0x36C5C760BB1CE43DA26FE9A9DBD6DC764B83D3D809FD79009D85903C247B429

v2= x + v1=0x36C5C760BB1CE43DA26FE9A9DBD6DC764B83D3D80A022D35E1EAB49038C0D7E



组合v1,v2得到sn:  KCTFREADYKXXXX1548396171915056368526513804948765619094392315806578461796159505215278288254




[挑战]看雪.纽盾 KCTF 2019晋级赛Q3攻击方进行中……,华为P30 Pro、iPad、kindle等你来拿!

最新回复 (2)
htg 1 2019-6-24 20:53
2
0
最后的求解GCD方法没看出来,但是基本每次得到的结果都是1。
对求逆元、求幂余运算没看出来,代码太长,估计以后就不用看了,根据输入输出值,拿工具验算一下就行了。
前面的代码基本上跟了一遍。
htg 1 2019-6-24 20:56
3
0
有一点:我跟踪了前缀码(10以内),与0x19的运算:
类似
a*19^9+b*19^8+……,原来这就是25进制。我把它理解成了多项式之和的结果,有点low。后面跟踪的结果需为较大的素数。
游客
登录 | 注册 方可回帖
返回