首页
论坛
课程
招聘
[原创]KCTF2021[秋季赛][第十题][生命的馈赠]wp
2021-12-12 10:59 16503

[原创]KCTF2021[秋季赛][第十题][生命的馈赠]wp

ccfer 活跃值
16
2021-12-12 10:59
16503

程序带混淆,看一下输入表,可以知道输入读取函数:__stdio_common_vfscanf
第一次读取name,第二次读取serial
第二次读取完返回程序以后,就是F7单步边调试边记录了,下面是一些记录点,每行记录中间夹杂了很多混淆代码,我也大概领悟到视频里那个钢琴键的暗示了,把F7键按坏了就离成功不远了:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
00428284   8D55 D8          LEA EDX,DWORD PTR SS:[EBP-28]       //serial
0047259D   8D8D D8FEFFFF    LEA ECX,DWORD PTR SS:[EBP-128]      //name
004C4F17   E8 8840F7FF      CALL CrackMe.00438FA4               //return al == 0?
004A02D4   8A08             MOV CL,BYTE PTR DS:[EAX]            //serial
004F06FF   40               INC EAX
004A1B74   84C9             TEST CL,CL
004754C7   0F85 4BF10400    JNZ CrackMe.004C4618
00466751   83F8 20          CMP EAX,20                          //serial_len == 0x20
0041D945   0F84 C3B90800    JE CrackMe.004A930E
0044BA1E   52               PUSH EDX
00470219   8D4D 80          LEA ECX,DWORD PTR SS:[EBP-80]
004AE7C1   C745 A0 358418EB MOV DWORD PTR SS:[EBP-60],EB188435  //一个128位的常数
004C91F9   C745 A4 75061BAC MOV DWORD PTR SS:[EBP-5C],AC1B0675
004CB3D7   C745 A8 4564005B MOV DWORD PTR SS:[EBP-58],5B006445
0041D6C8   C745 AC 7DA50568 MOV DWORD PTR SS:[EBP-54],6805A57D
004593BD   C745 B0 00000000 MOV DWORD PTR SS:[EBP-50],0
0044F51A   C745 B4 00000000 MOV DWORD PTR SS:[EBP-4C],0
00429E42   C745 B8 00000000 MOV DWORD PTR SS:[EBP-48],0
004D9EF5   C745 BC 00000000 MOV DWORD PTR SS:[EBP-44],0
0043E96B   E8 A3B90900      CALL CrackMe.004DA313               //16进制输入转换
004A5657   8D45 80          LEA EAX,DWORD PTR SS:[EBP-80]
0044F2A0   8D85 60FFFFFF    LEA EAX,DWORD PTR SS:[EBP-A0]
004B6124   8D4D 80          LEA ECX,DWORD PTR SS:[EBP-80]
004C0B2F   E8 D059F9FF      CALL CrackMe.00456504               //一个乘法过程,这里是serial*serial
004C925C   8D8D 60FFFFFF    LEA ECX,DWORD PTR SS:[EBP-A0]
00444D5A   E8 21020100      CALL CrackMe.00454F80               //取模,x = serial * serial % n
00476FE5   E8 1AF5FDFF      CALL CrackMe.00456504               //乘法,x * 0x6805A57D5B006445AC1B0675EB188435
0045C8FD   8106 83D24FC4    ADD DWORD PTR DS:[ESI],C44FD283     //加法,+ 4362F6846292652664A4CBBDC44FD283
0048FA1C   13D2             ADC EDX,EDX
004C3EEC   0356 04          ADD EDX,DWORD PTR DS:[ESI+4]
00452362   81C2 BDCBA464    ADD EDX,64A4CBBD
004667DD   0346 08          ADD EAX,DWORD PTR DS:[ESI+8]
0045B37F   05 26659262      ADD EAX,62926526
0049D1A7   81C2 84F66243    ADD EDX,4362F684
0048FBE1   8956 0C          MOV DWORD PTR DS:[ESI+C],EDX
004C2656   014E 10          ADD DWORD PTR DS:[ESI+10],ECX       //y = x * 0x6805A57D5B006445AC1B0675EB188435 + 0x4362F6846292652664A4CBBDC44FD283
 
... 后面又有一次二次剩余算法:z = y * y % n
 
0045891C   3B02             CMP EAX,DWORD PTR DS:[EDX]          //比较结果,目标结果是name的md5
0047ED6A  ^0F85 C141FDFF    JNZ CrackMe.00452F31
004CE6A6   83EE 04          SUB ESI,4
0041440E   0F83 02510900    JNB CrackMe.004A9516
004A73CA   8B55 EC          MOV EDX,DWORD PTR SS:[EBP-14]
0040D49E   83FA 10          CMP EDX,10
004A33F0  ^0F82 843BFBFF    JB CrackMe.00456F7A

调试过程很长,F7键被严重磨损,整理一下算法如下:

1
2
3
4
5
n = 0xFFFFFFFFFFFFFFFFFFFFFFFE566B43A3
x = serial * serial % n
y = x * 0x6805A57D5B006445AC1B0675EB188435 + 0x4362F6846292652664A4CBBDC44FD283
z = y * y % n
z = md5("KCTF") = 0xA0D99FB4D5ABF597979F99A2C6B11A7A

看起来解两次二次剩余和一次模逆乘法就可以了
实际却遇到了问题,其中一个二次剩余无解,这应该是遇到传说的坑了,然后找坑吧,此时纠结的是记录的算法是否有误?是否进入了假验证的分支?
只能小心翼翼的每个函数都重新核实了,最后反复多次尝试,输入范围从两边极限分别去观察,发现取模函数有缺陷:
w = 0x100000000000000000000000000000000
y = x - (x / w) n
z = y - (y / w)
n
这个取模函数当输入数值很大时,最后输出结果会比正常结果多了n:x%n+n
然后题目输出结果只保留了128位,第129位的1被舍弃了,相当于后面运算减掉了0x100000000000000000000000000000000
于是我们把这个0x100000000000000000000000000000000加回来就可以继续完成后面的二次剩余求解
对于大部分name是不需要触发这个缺陷也会有解的,比如公开那组,公开组用户名1A5FBFD826E1D12E可以算出4个注册码
而以KCTF作为用户名时,不触发缺陷会造成无解

 

sage求解代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
sage: n = 0xFFFFFFFFFFFFFFFFFFFFFFFE566B43A3
....: a = 0x4362F6846292652664A4CBBDC44FD283
....: h = (n - 1) / 2
....: d = inverse_mod(0x6805A57D5B006445AC1B0675EB188435, n)
....: namehash = 0xA0D99FB4D5ABF597979F99A2C6B11A7A
....: x = mod(namehash, n)
....: if x ^ h % n == 1:
....:     y = x.nth_root(2)
....:     z = (n + y - a) * d % n
....:     z += 1<<128
....:     if z ^ h % n == 1:
....:         r = z.nth_root(2)
....:         print(hex(r).upper()[2:])
....:         print(hex(n-r).upper()[2:])
....:
5A6CC68CF60E9606195E9912BBF332A
FA593397309F169F9E6A166D2AAC1079

得到两个解,取大的一个,刚好使得题目中有缺陷的二次剩余算法输出结果第129位是1
FA593397309F169F9E6A166D2AAC1079


【公告】 [2022大礼包]《看雪论坛精华22期》发布!收录近1000余篇精华优秀文章!

最后于 2021-12-12 11:13 被ccfer编辑 ,原因:
收藏
点赞1
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回