[原创]KCTF2021[秋季赛][第十题][生命的馈赠]wp-CTF对抗-看雪-安全社区|安全招聘|kanxue.com

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

2021-12-12 10:59 18682

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

ccfer

2021-12-12 10:59

18682

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

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键被严重磨损，整理一下算法如下：

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求解代码：

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