====================================分析篇====================================
代码被混淆了
混淆规律
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 是唯一通过的解！
[培训]《安卓高级研修班(网课)》月薪三万计划，掌握调试、分析还原ollvm、vmp的方法，定制art虚拟机自动化脱壳的方法
最后于 2021-12-12 00:45
被海风月影编辑
，原因：
