看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

WriteUp 3年前 (2021) admin
864 0 0
此题没有反调试,只有一定的混淆。
对于初级参赛者,需要对抗本题的混淆。
对于中级参赛者,需要熟悉平方剩余算法。
对于高级参赛者,需要发现并修复CrackMe中的bug。

出题团队在赛前发布了一部情感短视频,并将解题思路隐藏于其中。赛后又发布了一部解析视频,深入讲解了破解方法。

作为第一个配短视频的CTF赛题,此题出题思路别致,视频制作专业,是一个有里程碑意义的CTF赛题!
看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

点击图片,观看解题分析视频看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析


截至比赛结束,此题共计围观人数:1957人,攻破战队数:4。

分别是:金左手、中娅之戒、mininep、辣鸡战队。从围观人数来看,此题吸引了不少参赛成员。特意为CTF赛题制作高水准的配套微电影还是头一次见吧!这不,解析版的视频也为大家奉上啦~

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析
点击图片看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析查看出题视频:《生命的馈赠》

出题团队简介


第十题《生命的馈赠》出题方:【GRAFFINDOR】战队。


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

【GRAFFINDOR】战队成员如下:

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析


赛题设计思路


题目设计说明:防守有两部分,程序代码混淆和数学保护。




混淆


1、代码乱序处理

行与行之间加入jmp,通过jmp衔接每一行代码。


定义:定义了一个结构体管理每行代码,结构体如下。

struct CodeLineToExpand{OrderType m_Type;//原来代码的类型Param1;Param2;OldAddr;  //原来代码的地址OldAddrToJmpOrCall;//原来代码中要跳转的目标地址OldIndexValue;NewSize;//已经加入了远相对jmp后的大小NewAddr;NewAddrToJmpOrCall;RamdomValue;//随机值NewCode;//新的代码}CTE[nCodeLines];
int MapNewToOld[nCodeLines];//存储新的Line和旧的Line之间的对应关系int CodeLineOldAddrBegin;//原来代码地址的开始int CodeLineOldAddrEnd;//原来代码地址的结束(不包含本地址)


步骤:

(1)将某一行代码nCodeLines的原始信息填入CTE数组。
计算出nCodeLines,填好CTE数组的每个元素的m_Type、Param1、Param2、OldAddr、OldAddrToJmpOrCall、OldIndexValue。


(2)对CTE每个元素赋予随机值,以该随即值的从小到大顺序重新组合代码。
计算出随机值填入RamdomValue,然后以此排序,排序后的结果放入MapNewToOld数组。


MapNewToOld数组按照索引顺序(NewIndex)来放置OldValue的值,顺序为从小到大。


(3)某行代码新地址的计算方法(CTE: NewAddr)
遍历MapNewToOld数组,除去第0个,每个元素对应的CodeLineToExpand结构体的NewAddr都为前面的元素CodeLineToExpand结构体的NewAddr+NewSize


(4) 新CodeLine中的远相对跳转中相对地址的计算方法
遍历CTE数组,找它下一个元素的NewAddr配合自己的NewAddr进行计算。


(5)新的jmpcall目标地址的计算方法(假设源代码仅为代码,不做它用,且代码为Jmp或者Call)


相对跳转的修正:若原来代码要跳转的地址not in [CodeLineOldAddrBegin,
CodeLineOldAddrEnd]
中,则用NewAddr和OldAddrToJmpOrCall进行修正;反之,寻找原来代码跳转地址对应的CodeLineToExpand,用NewAddr和原来代码跳转地址对应的CodeLineToExpand中的NewAddr进行修正。


绝对跳转的修正:若原来代码要跳转的地址not in [CodeLineOldAddrBegin,
CodeLineOldAddrEnd]
中,则不需要修正;反之,寻找原来代码跳转地址对应的CodeLineToExpand,原来代码跳转地址对应的CodeLineToExpand中的NewAddr进行修正。


2、初步替换jmp指令


按长度分为9种。

// 第一种  长度:6push Addrret
// 第二种 长度:0x1Cpush eaxmov eax,Addrpush eaxmov [esp-4],eaxmov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxpop eaxret
// 第三种1 长度:0xCmov dword ptr[esp-4],Addrjmp[esp - 4]         // 第三种2 长度:Cmov dword ptr[esp-4],Addrsub esp,4ret
// 第四种 长度:0x2Dpush eaxmov dword ptr[esp-4],Addrmov eax,[esp-4]mov [esp-8],eaxsub esp,4mov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxmov eax,[esp]add esp,8   //add esp,4jmp [esp-4] //ret
// 第五种 长度:0x34push Addrpush eaxmov eax,Addrmov eax,[esp]//push eaxmov eax,Addrpush eaxmov [esp-4],eaxmov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxpop eax//add esp,4pop eaxadd esp,4jmp [esp-4]
// 第六种(4+5) 长度:0x86push Addrpush eaxmov eax,Addrpush eaxmov dword ptr [esp-4],Addrmov eax,[esp-4]mov [esp-8],eaxsub esp,4mov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxmov eax,[esp]add esp,8   //add esp,4mov eax,[esp]push eaxmov eax,Addrpush eaxmov [esp-4],eaxmov eax,[esp+4]push eaxmov dword ptr[esp-4],Addrmov eax,[esp-4]mov [esp-8],eaxsub esp,4mov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxmov eax,[esp]add esp,8   //add esp,4mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxpop eaxadd esp,4pop eaxadd esp,4jmp [esp-4]
// 第7种 长度:0x59push Addrpush 0x7FFA08ACjmp [esp]nopnopnopnopnopnopnopnopnopnopnopnopnoppush ebpmov ebp,espadd esp,-34push ebxpush ecxpush eaxpush esipush edilea edi,[ebp-34h]mov ecx,Dmov eax,0x0CCCCCCCCrep stos dword ptr [edi]mov [ebp-4],ecxmov eax,[ebp+8]mov edx,dword ptr [esp+4]mov ecx,dword ptr [esp+8]mov dword ptr [ebp-30h],1mov edx,dword ptr [ebp-30h]mov dword ptr [ebp-34h],edxmov ecx,[ebp-4h]pop edipop esipop eaxpop ecxpop ebxleaveret
// 第8种 长度:0x42pushfdpush eaxmov eax, 4mul eaxlea eax, [4 * eax]mov[esp - 4], eaxmov eax, 4shl eax, 4sub eax, 4sub[esp - 4], eaxmov eax, [esp - 4]sub eax, 4mov[esp - 4], eaxpop eaxjne $ + 0x13call $+5add dword ptr [esp],0x13mov eax,[esp+4]mov [esp-4],eaxpopfdadd esp,4mov dword ptr[esp - 4], Addrsub esp, 4ret
// 第9种(7+8) 长度:0x99
// 第10种 长度:0x46pushfdpush eaxxor eax,Addrxor eax,64test eax,eax//push eaxmov eax,Addrpush eaxmov [esp-4],eaxmov eax,[esp+4]mov [esp],eaxmov eax,[esp-4]mov [esp+4],eaxpop eaxadd esp,4//xor eax,64xor eax,[esp]push eaxadd esp,8popfdsub esp,8pop eaxpop [esp-4]jmp [esp-C]7FFBDD3B pushfd + retn7FFAF6DF popfd + retnaddreaxfd


3、通过计算得出jmp的目标地址


有8种计算方式,以长度区分。

// 第1种 长度:0x2dpushfdnpush eaxnpush $1nadd dword ptr[esp], $2nshl dword ptr[esp], $3nxor dword ptr[esp], $4nadd dword ptr[esp], $5nxchg eax,[esp]nxchg eax,[esp+8]nxchg eax,[esp]npopfdnpop eaxnret 
// 第2种 长度:0x31push eaxnmov eax, $1nlea eax, [eax + $2]npush eaxnmov[esp - 4], eaxnmov eax, [esp + 4]nmov[esp], eaxnmov eax, dword ptr[esp - 4]npushfdnshl eax, $3nadd eax, $4nxor eax, $5npopfdnmov[esp + 4], eaxnpop eaxnret
// 第3种 长度:0x2fpushfdnpushfdnadd esp,8nmov dword ptr[esp - 4], $1nshl dword ptr[esp - 4], $2nadd dword ptr[esp - 4], $3nxor dword ptr[esp - 4], $4nadd dword ptr[esp - 4], $5nsub esp, 8npopfdnret
// 第4种 长度:0x65pushfdnpush eaxnmov dword ptr[esp - 4], $1nmov eax, [esp - 4]nmov[esp - 8], eaxnsub esp, 4nshl dword ptr[esp - 4], $2nmov eax, [esp + 4]nadd dword ptr[esp - 4], $3nmov dword ptr[esp], eaxnmov eax, [esp - 4]nmov[esp + 4], eaxnmov eax, [esp]nmov [esp-8],eaxnadd dword ptr[esp + 4], $4nxor dword ptr[esp + 4], $5nmov eax,[esp+4]nmov [esp-8],eaxnlea esp, [esp + 8]npopfdnlea esp,[esp-4]nmov eax,[esp-4]nmov [esp],eaxnmov eax,[esp-8]nret
// 第5种 长度:0x5dpushfdnpush $1npush eaxnmov eax, $2nmov eax, [esp]nshl dword ptr[esp + 4], $2npush eaxnmov eax, 1npush eaxnmov[esp - 4], eaxnmov eax, [esp + 4]nmov[esp], eaxnmov eax, [esp - 4]nmov[esp + 4], eaxnpop eaxnxor dword ptr[esp + 8], $3nadd esp, 4nmov eax, $4nadd eax, $5nadd dword ptr[esp + 4], eaxnpop eaxnadd esp,4npopfdnlea esp,[esp-4]nmov eax,[esp-4]nmov [esp],eaxnmov eax,[esp-8]nret
// 第6种 长度:0x82push $1npush eaxnmov eax, edinpush eaxnpushfdnpushfdnpushfdnadd esp, 0chnmov dword ptr[esp - 4], $3nmov eax, [esp - 4]nmov[esp - 8], eaxnsub esp, 4nmov eax, [esp + 4]nmov[esp], eaxnmov eax, [esp - 4]nmov[esp + 4], eaxnmov eax, [esp]nadd esp, 8nmov eax, [esp]nxor eax, [esp]nmov eax, [esp + 4]nadd eax, $2nxor eax, $3nmov[esp + 4], eaxnpush eaxnmov eax, $4npush eaxnmov[esp - 4], eaxnmov eax, [esp + 4]nmov[esp], eaxnmov eax, [esp - 4]nmov[esp + 4], eaxnpop eaxnadd esp, 4npop eaxnshl dword ptr[esp], $4nadd dword ptr[esp], $5nsub esp,14hnpopfdnlea esp,[esp + 10h]nret
// 第7种 长度:0x98push $1npush eaxnmov eax, $4npush eaxnmov[esp - 4], eaxnmov eax, [esp + 4]nmov[esp], eaxnmov eax, [esp - 4]nmov[esp + 4], eaxnpop eaxnlea esp, [esp + 4]nnopnnopnnopnnopnnopnnopnnopnnopnnopnnopnnopnnopnnopnpush ebpnmov ebp, espnlea esp, [esp - 34h]npushfdnpush ebxnpush ecxnpush eaxnpush esinpush edinpush edxnlea edi, [ebp - 34h]nmov ecx, 0xDnmov eax, 0x0CCCCCCCCnrep stos dword ptr[edi]nmov[ebp - 4], ecxnmov eax, [ebp + 8]nmov eax, ebpnmov edx, dword ptr[esp + 4]nmov ecx, [eax + 4]nadd ecx, $2nxchg ecx, edxnmov ecx, dword ptr[esp + 8]nmov dword ptr[ebp - 30h], 1nadd edx, $3nshl edx, $4nmov ecx, edxnmov edx, dword ptr[ebp - 30h]nxor ecx, $5nlea ebx, [eax + 4]nmov dword ptr[ebp - 34h], edxnmov [ebx], ecxnmov ecx, [ebp - 4h]npop edxnpop edinpop esinpop eaxnpop ecxnpop ebxnpopfdnleavenret
// 第8种 长度:0xafpushfdnpush $1npush eaxnpush edxnmov eax, 4nmul eaxnlea eax, [4 * eax]nmov[esp - 4], eaxnmov eax, 4nshl eax, 4nsub eax, 4nsub[esp - 4], eaxnmov eax, [esp - 4]nsub eax, 4nmov[esp - 4], eaxnpop edxnpop eaxnnopnnopnnopnnopnnopnnopnnopnnopnnopnnopnnopnnopnnopnpush ebpnmov ebp, espnadd esp, -34hnpush edxnpush ebxnpush ecxnpush eaxnpush esinpush edinlea edi, [ebp - 34h]nmov ecx, 0xDnmov eax, 0xCCCCCCCCnrep stos dword ptr[edi]nmov[ebp - 4], ecxnmov eax, [ebp + 8]nmov edx, dword ptr[esp + 4]nmov ecx, dword ptr[ebp + 4]ntest edx, 3nlea ebx, [ebp + 8]nmov dword ptr[ebp - 30h], 1nmov edx, ecxnxor edx, $2nshl edx, $3nmov eax, edxnmov edx, dword ptr[ebp - 30h]nmov dword ptr[ebp - 34h], edxncmp dword ptr[ebp - 34h], 0nadd eax, $4nadd eax, $5n


4、替换后的代码进行拆分成块 

拆分的方法和步骤0一致,相当于做二次处理。


5、为了降低拆分后代码的规律性,引入了无效的代码片段 


四种片段,随机填充。

1、长度 58push ebpmov ebp, esplea esp, [esp - 34h]push ecxpush edxpush ebxpush esipush edipushfdmov edi, fs: [30h]lea edi, [edi + 8h]mov edi, [edi]lea ebx, [ebp]mov ecx, edixchg edx, [ebp]add ecx, 3chmov ecx,[ecx]add edi, ecxcall $ + 5pop ecxlea edi,[edi + 74h]lea ecx,[ecx + 29h]sub ebp, 4mov[ebp], edxlea ebx,[ebp]mov[ebx + 4], ecxcmp edi, 12hje $ - 55hpopfdpop edipop esipop ebxpop edxpop ecxleaveretnopnopnopnopnopnopnop        2、长度 21push ebpmov ebp,espsub esp,-34hpushadmov edi,fs:[30h]lea edi,[edi+8h]mov edi,[edi]mov eax,edilea eax,[4*eax]push eaxpop edipopadleave
3、长度 21mov edi,edipush ebpmov ebp,esplea esp,[esp-22h]mov dword ptr [ebp-4h],ecxmov dword ptr [ebp-8h],ecxmov dword ptr [ebp-ch],ecxmov dword ptr [ebp-1ch],ecxmov esp,ebppop ebpjmp $+8nopnopnop
4、长度 42call $ +0x2Emov eax, eaxcall $ +0xBmov eax, eaxlea esp, [esp + 12]lea esp, [esp + 10h]mov eax, eaxmov eax, eaxcall $ +0x24mov eax, eaxmov eax, eaxcall $ +0x14mov eax, eaxlea esp, [esp - 4]call $ -0xDmov eax, eaxmov eax, eaxcall $ -0x30mov eax, eaxlea esp, [esp + 8h]
5、长度 42call $ +0x2Emov eax, eaxcall $ +0x37mov eax, eaxlea esp, [esp + 12]lea esp, [esp + 10h]mov eax, eaxmov eax, eaxcall $ +0x24mov eax, eaxmov eax, eaxcall $ +0x14mov eax, eaxlea esp, [esp - 4]call $ -0xDmov eax, eaxmov eax, eaxcall $ -0x30mov eax, eaxlea esp, [esp + 8h]





数学保护


数学公式(逆运算):((format(Serial) ^2 mod P) * A + B) mod P) ^2 mod P = MD5(name)


参数:

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

验证:
(((S^2 Mod P) * A + B) Mod P) ^2 Mod P = N 满足该式子则成功。

破解思路:

1、把无效的代码片段替换为空,去除垃圾代码,保留有效代码。
2、去除拆分后成块的代码中的jmp,将代码块整合成有序代码。
3、通过trace找出最终跳转地址的计算模板,然后通过文本处理计算出地址进行替换。
4、处理乱序:通过trace跟踪出执行乱序的代码,截获原始地址进行处理。


赛题解析


一、分析篇

代码被混淆了。

混淆规律:6个call之后,类似下面这样平衡堆栈的指令下面一条,就是真实指令。
lea     esp, dword ptr ss:[esp+0x14]
lea esp, dword ptr ss:[esp+0x8]

二、逆向篇

输入预设的 name/serial,内存访问断点,返回到这里。
0043D6E1    51              push    ecx0043D6E2    E8 82FAFDFF     call    0041D169 ; 获取serial0043D6E7    68 80B57D1F     push    0x1F7DB580 ; 这里能看到name/serial0043D6EC    89DB            mov     ebx, ebx0043D6EE    50              push    eax0043D6EF    89E4            mov     esp, esp0043D6F1    B8 1D000000     mov     eax, 0x1D0043D6F6    90              nop

然后serial比较长度,必须是32字节:

00466750    5D              pop     ebp00466751    83F8 20         cmp     eax, 0x20                                       ; 比较长度00466754    9C              pushfd

单步到这:
004DD1DE   C785 00FFFFFF 7>mov   dword ptr ss:[ebp-0x100], 0x10325476 ;md5初始化

看看内存中:
0019FD38  01 23 45 67 89 AB CD EF FE DC BA 98 76 54 32 10  #Eg壂惋簶vT2

猜测是md5算法,但此时内存中已经出现了正确的md5值:
0019FDC4  F4 D5 16 EF CE 55 11 93 B6 6E E1 68 26 51 5A 4F  粽镂U摱n醜&QZO

这正好是name(1A5FBFD826E1D12E)的md5值,所以,这里应该是serial逆推回去算出来的,改一个字节会发现验证错误。

重新分析,发现这个call是关键:
004C4F17    E8 8840F7FF     call    00438FA4  ; 验证call,ecx = name, edx = serial004C4F1C    68 66757D1C     push    0x1C7D7566 ; 这里验证完毕, al = 1 成功, al = 0 失败004C4F21    50              push    eax
0049BFAE    B8 F8414000     mov     eax, 004041F8                              ; ASCII "验证正确n"0049BFB3    9C              pushfd0049BFB4    89E4            mov     esp, esp0049BFB6    9C              pushfd0049BFB7    89DB            mov     ebx, ebx
004CA73A    8D6424 08       lea     esp, dword ptr ss:[esp+0x8]004CA73E  ^ 0F85 BE38FAFF   jnz     0046E002                                   ; 爆破点,jmp,验证成功004CA744    68 BAEB7025     push    0x2570EBBA
call 438fa4004318D5    81EC 28010000   sub     esp, 0x128

这里提升堆栈空间,可以直接清0堆栈,看看堆栈会出现哪些变量。
0043E967                      8D6424 14                               lea     esp, dword ptr ss:[esp+0x14]0043E96B                      E8 A3B90900                             call    004DA313 ; 似乎是 string to bignum0043E970                      9C                                      pushfd

004C0B29                      89C0                                    mov     eax, eax004C0B2B                      8D6424 14                               lea     esp, dword ptr ss:[esp+0x14]004C0B2F                      E8 D059F9FF                             call    Mul ; 这里似乎是 pow2 004C0B34                      9C                                      pushfd

456504这个函数,传入2个参数(eax, ecx) ,传出1个参数([esp+4])。

执行完看输出地址,这个正好是:
EEA43B9D52515B49838AFAA50490DA0B * EEA43B9D52515B49838AFAA50490DA0B = DE75C834F482A299391D073F5D424CAB9AA9FE2AAE920EE2228766F45E16BC790019FDA4  79 BC 16 5E F4 66 87 22 E2 0E 92 AE 2A FE A9 9A  y?^鬴??挳*?0019FDB4  AB 4C 42 5D 3F 07 1D 39 99 A2 82 F4 34 C8 75 DE  獿B]?9櫌傯4萿?

所以上面是Mul,在Mul上面下断点。

然后经过一个函数:
00444D59                      67:E8 21020100                   call    <modN>00444D5F                      50                               push    eax                                                          ; 返回1

返回结果为:
0019FDA4  C3 E1 2D 54 FD 5A A8 FC 4F DC D5 D1 6D D8 04 93  冕-T齔O苷裮??0019FDB4  00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00  ................
看上去像是取模。

我们用:
DE75C834F482A299391D073F5D424CAB9AA9FE2AAE920EE2228766F45E16BC79 - 9304D86DD1D5DC4FFCA85AFD542DE1C3 = 
DE75C834F482A299391D073F5D424CAB07A525BCDCBC329225DF0BF709E8DAB

然后用yafu分解一下:
factor(0xDE75C834F482A299391D073F5D424CAB07A525BCDCBC329225DF0BF709E8DAB6)

fac: factoring 100621555269000733341031010157969998386759504095520400047147427430100793612982fac: using pretesting plan: normalfac: no tune info: using qs/gnfs crossover of 95 digits

starting SIQS on c72: 146405049556078485019294860272741026808150808686274920697977580425648851

==== sieving in progress (1 thread):   16656 relations needed ========           Press ctrl-c to abort and save state           ====

SIQS elapsed time = 0.6650 seconds.Total factoring time = 0.6730 seconds

factors found

P39 = 340282366920938463463374607424628147107P33 = 430245771712568276625619760299793ans = 1

其中P33太小,P39 = FFFFFFFFFFFFFFFFFFFFFFFE566B43A3。


验证一下:
DE75C834F482A299391D073F5D424CAB9AA9FE2AAE920EE2228766F45E16BC79 Mod FFFFFFFFFFFFFFFFFFFFFFFE566B43A3 = 9304D86DD1D5DC4FFCA85AFD542DE1C3

所以上面那个函数是 Mod 0xFFFFFFFFFFFFFFFFFFFFFFFE566B43A3。

设N=FFFFFFFFFFFFFFFFFFFFFFFE566B43A3,在ModN位置下断点,然后F9跑,然后发现Mul断下来了。
6805A57D5B006445AC1B0675EB188435 *  9304D86DD1D5DC4FFCA85AFD542DE1C3  = 3BBD360EF483631109E77CAB8B604BE7252D7537F13655FA919F38844130495F

断下了后,发现内存中值发生了变化:
3BBD360EF483631109E77CAB8B604BE768906BBC53C8BB20F644044205801BE2

跟上面乘的结果比较,发现是大了一点点:
3BBD360EF483631109E77CAB8B604BE768906BBC53C8BB20F644044205801BE2 - 3BBD360EF483631109E77CAB8B604BE7252D7537F13655FA919F38844130495F = 4362F6846292652664A4CBBDC44FD283

再跑,发现ModN断下来了:
00473134                      E8 471EFEFF                      call    <modN>00473139                      50                               push    eax

结果:24938628338F43651192F4F03FD24328

再跑,Mul断下来了:
24938628338F43651192F4F03FD24328 * 24938628338F43651192F4F03FD24328 = 0539D2BEA6F99DC5F4B8C6AAD5DCBB1F9927D007969D817073CB54BFEF3DF640
0019FD10 40 F6 3D EF BF 54 CB 73 70 81 9D 96 07 D0 27 99 @?锟T藄p仢???
0019FD20 1F BB DC D5 AA C6 B8 F4 C5 9D F9 A6 BE D2 39 05 卉摘聘襞濝?

再跑,ModN断下来,正好是0x4F5A512668E16EB6931155CEEF16D5F4

内存中结构,恰好等于 md5(name)的值:
0019FD10  F4 D5 16 EF CE 55 11 93 B6 6E E1 68 26 51 5A 4F  粽镂U摱n醜&QZO

3、算法篇

整理一下算法:
设N = FFFFFFFFFFFFFFFFFFFFFFFE566B43A3
A = 6805A57D5B006445AC1B0675EB188435
B = 4362F6846292652664A4CBBDC44FD283

M = MD5(name) , 注意,内存中是little eddian的
S = hex(serial)

整个验证算法,可以用表达式来表示:
M = (((S ^ 2) Mod N) * A + B) ^ 2 Mod N

看数学表达式,实际上是 两次平方模,然后比较name的md5。逆运算就是求平方剩余。

平方剩余公式是:
当 Y = X^2 Mod N ,且 N mod 4 = 3的时候
X1 = Y ^ ((N+1)/4) Mod N

平方剩余有多解:另一解是 X2 = N – X1

所以这题其实有4解。

name: 1A5FBFD826E1D12E

serial: 
EEA43B9D52515B49838AFAA50490DA0B
115BC462ADAEA4B67C75055951DA6998
41B8103BEC6C05BC8D4E37DD2DF5D1E8
BE47EFC41393FA4372B1C821287571BB

经测试,这4解都可以通过验证。

4、音乐篇

但是,当我们使用KCTF的时候:

MD5(‘KCTF’) = 0xA0D99FB4D5ABF597979F99A2C6B11A7A ( 内存中字节码:7A 1A B1 C6 A2 99 9F 97 97 F5 AB D5 B4 9F D9 A0 )

求出来的4解是:
2EA6060B597BA4D12D2FC0A1DF7A5FB5
D159F9F4A6845B2ED2D03F5C76F0E3EE
48538B7EADCDD321FB83E1F4D227BAD9
B7AC748152322CDE047C1E09844388CA

遗憾的是,一个都无法通过!

看了一遍又一遍《生命的馈赠》,“所有曲目我都试过了,这密码还是打不开”

为什么会不对呢?各种百度,谷歌,原来,平方剩余是有条件的。

Y = X^2 Mod N,X有解的条件是 Y^ ((N-1)/2) == 1 Mod N

第一次的时候,是有平方剩余的,所以能解出两解。
Z1 = 0000000000000000B0D3C2D4E7B7A3BA
Z2 = 6E000A013A6DF57F8ABD86D0120C88AD

但是第二次的时候,两组数据都没有平方剩余!

这就有意思了,到底哪里出问题了呢?再看一遍视频,发现缺了个琴音是破解的关键!

有没有可能,Mod的时候,没有模尽,使得结果多了一个N,然后取了低128bit,正好就有平方剩余了呢?

于是,把Z1,Z2,分别 
Z1 + 2^128 – N = B0D3C2D6914C6017

求两组平方剩余:
05A6CC68CF60E9606195E9912BBF332A
FA593397309F169F9E6A166D2AAC1079

Z2 + 2^128 – N = 6E000A013A6DF57F8ABD86D1BBA1450A

求两组平方剩余:
6E66D51BBB5DFD0200F5BF564A7F1052
91992AE444A202FDFF0A40A80BEC3351

验证发现,FA593397309F169F9E6A166D2AAC1079 是唯一通过的解!


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析


注意:【最受欢迎战队奖】&【新思路奖】正在火热评选中!欢迎大家投上宝贵的一票~

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

待评选(1):【最受欢迎战队奖】


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

长按二维码立即投票!

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

【最受欢迎战队奖】


【最受欢迎战队奖】


评选对象:

2021 KCTF秋季赛 参赛战队(包含防守方所有战队+攻击方前20名战队)


评选方式:

登陆看雪账号,在本帖为喜欢的战队投票,每个账号可投1票。


投票时间:

12月15日 14:00 ~12月22日 14:00


奖品:

【最受欢迎战队奖】得票第一名:可获得「HUAWEI WATCH GT2 华为手表」

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

待评选(2):【新思路奖】


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

长按二维码立即投票!

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

【新思路奖】



【新思路奖】


评选对象:

2021 KCTF秋季赛 参赛防守方战队


评选方式:

1、会员投票(占比50%):在KCTF答题页面投票,只有提交答案的选手才可投票。【快使用你们的特权~】

2、看雪KCTF专家评审团投票(占比50%):评审团成员投票,每人一票。

投票时间:

比赛开始,直到比赛结束后一周。(12月22日12:00关闭投票通道)


奖品:

【新思路奖】得票第一名:可获得「HUAWEI WATCH GT2 华为手表」

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析






看雪CTF(简称KCTF)是圈内知名度最高的技术竞技之一,从原CrackMe攻防大赛中发展而来,采取线上PK的方式,规则设置严格周全,题目涵盖Windows、Android、iOS、Pwn、智能设备、Web等众多领域。

看雪CTF比赛历史悠久、影响广泛。自2007年以来,看雪已经举办十多个比赛,与包括金山、360、腾讯、阿里等在内的各大公司共同合作举办赛事。比赛吸引了国内一大批安全人士的广泛关注,历年来CTF中人才辈出,汇聚了来自国内众多安全人才,高手对决,精彩异常,成为安全圈的一次比赛盛宴,突出了看雪论坛复合型人才多的优势,成为企业挑选人才的重要途径,在社会安全事业发展中产生了巨大的影响力。






众安信息技术服务有限公司(简称:众安科技)

基于区块链、人工智能、大数据、云计算等前沿技术探索,以科技构建生态新基建。经过实际业务验证,围绕三大核心产品系列——业务增长系列、业务生产系列、业务基建系列,覆盖保险经营中的产品设计、精准营销、核保核赔、服务与运营管理等关键环节,打造高效、安全、可靠的技术产品与解决方案,助力保险生态及更多金融、电商、在线教育、融媒体等行业客户实现数字化升级。


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

往期解析


1、看雪·众安 2021 KCTF 秋季赛 | 第二题设计思路及解析


2、看雪·众安 2021 KCTF 秋季赛 | 第三题设计思路及解析


3、看雪·众安 2021 KCTF 秋季赛 | 第四题设计思路及解析


4、看雪·众安 2021 KCTF 秋季赛 | 第五题设计思路及解析


5、看雪·众安 2021 KCTF 秋季赛 | 第六题设计思路及解析


6、看雪·众安 2021 KCTF 秋季赛 | 第七题设计思路及解析


7、看雪·众安 2021 KCTF 秋季赛 | 第八题设计思路及解析


8、看雪·众安 2021 KCTF 秋季赛 | 第九题设计思路及解析


9、看雪·众安 2021 KCTF 秋季赛 | 第十一题设计思路及解析


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析
– End –


看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析
公众号ID:ikanxue
官方微博:看雪安全
商务合作:[email protected]




看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

球分享

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

球点赞

看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

球在看



看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析
阅读原文”,参与投票!

原文始发于微信公众号(看雪学苑):看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析

版权声明:admin 发表于 2021年12月18日 上午10:01。
转载请注明:看雪·众安 2021 KCTF 秋季赛 | 第十题设计思路及解析 | CTF导航

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...