首页
论坛
课程
招聘
[原创]KCTF2021秋 生命的馈赠 writeup
2021-12-9 18:13 16091

[原创]KCTF2021秋 生命的馈赠 writeup

2021-12-9 18:13
16091



====================================分析篇====================================

代码被混淆了


混淆规律

6个call之后,类似下面这样平衡堆栈的指令下面一条,就是真实指令

lea     esp, dword ptr ss:[esp+0x14]

lea     esp, dword ptr ss:[esp+0x8]


====================================逆向篇====================================


输入预设的 name/serial


内存访问断点,返回到这里



0043D6E1    51              push    ecx

0043D6E2    E8 82FAFDFF     call    0041D169 ; 获取serial

0043D6E7    68 80B57D1F     push    0x1F7DB580 ; 这里能看到name/serial

0043D6EC    89DB            mov     ebx, ebx

0043D6EE    50              push    eax

0043D6EF    89E4            mov     esp, esp

0043D6F1    B8 1D000000     mov     eax, 0x1D

0043D6F6    90              nop




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

00466750    5D              pop     ebp

00466751    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 = serial

004C4F1C    68 66757D1C     push    0x1C7D7566                                 ; 这里验证完毕, al = 1 成功, al = 0 失败

004C4F21    50              push    eax


0049BFAE    B8 F8414000     mov     eax, 004041F8                              ; ASCII "验证正确\n"

0049BFB3    9C              pushfd

0049BFB4    89E4            mov     esp, esp

0049BFB6    9C              pushfd

0049BFB7    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 438fa4

004318D5    81EC 28010000   sub     esp, 0x128

这里提升堆栈空间,可以直接清0堆栈,看看堆栈会出现哪些变量


0043E967                      8D6424 14                               lea     esp, dword ptr ss:[esp+0x14]

0043E96B                      E8 A3B90900                             call    004DA313 ; 似乎是 string to bignum

0043E970                      9C                                      pushfd



004C0B29                      89C0                                    mov     eax, eax

004C0B2B                      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 = DE75C834F482A299391D073F5D424CAB9AA9FE2AAE920EE2228766F45E16BC79

0019FDA4  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 = 

DE75C834F482A299391D073F5D424CAB07A525BCDCBC329225DF0BF709E8DAB6


然后用yafu分解一下:


factor(0xDE75C834F482A299391D073F5D424CAB07A525BCDCBC329225DF0BF709E8DAB6)


fac: factoring 100621555269000733341031010157969998386759504095520400047147427430100793612982

fac: using pretesting plan: normal

fac: 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 = 340282366920938463463374607424628147107

P33 = 430245771712568276625619760299793

ans = 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



====================================算法篇====================================


整理一下算法:

设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解都可以通过验证


====================================音乐篇====================================


但是,当我们使用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 是唯一通过的解!








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

最后于 2021-12-12 00:45 被海风月影编辑 ,原因:
收藏
点赞3
打赏
分享
最新回复 (0)
游客
登录 | 注册 方可回帖
返回