-
-
[原创]看雪CTF2018 - 密界寻踪 WriteUp
-
2018-6-23 12:49
-
第一次做密码类的CrackMe，踩了不少坑。以下该题的解题思路：
一、识别加密算法库
上网搜了一下miracl库，把相关的signature文件下载下来，加载到 IDA pro 中成功识别100多个函数
二、主要功能代码分析
.text:004031FA 68 18 61 48 00 push offset aS_0 ; "%s" .text:004031FF E8 BC B1 02 00 call _scanf ; 输入key .text:00403204 83 C4 0C add esp, 0Ch .text:00403207 8D 55 C8 lea edx, [ebp-38h] .text:0040320A 52 push edx ; char * .text:0040320B E8 B0 A4 02 00 call _strlen .text:00403210 83 C4 04 add esp, 4 .text:00403213 83 F8 17 cmp eax, 17h ; 长度不能超过0x17 .text:00403216 76 13 jbe short loc_40322B ; 取第4 - 23字节的字符串 .text:00403218 8D 45 E0 lea eax, [ebp-20h] ; error .text:0040321B 50 push eax ; char * .text:0040321C E8 1F A5 02 00 call _printf .text:00403221 83 C4 04 add esp, 4 .text:00403224 6A 00 push 0 ; int .text:00403226 E8 05 B0 02 00 call _exit .text:0040322B ; --------------------------------------------------------------------------- .text:0040322B .text:0040322B loc_40322B: ; CODE XREF: sub_403160+B6j .text:0040322B 8D 4D CB lea ecx, [ebp-35h] ; 取第4 - 23字节的字符串 .text:0040322E 51 push ecx ; char * .text:0040322F E8 8C A4 02 00 call _strlen .text:00403234 83 C4 04 add esp, 4 .text:00403237 50 push eax .text:00403238 68 60 56 49 00 push offset unk_495660 .text:0040323D 8D 55 CB lea edx, [ebp-35h] .text:00403240 52 push edx .text:00403241 E8 2C DF FF FF call j_ascii2hex ; 转换成十六进制数组存储在unk_495660 .text:00403246 83 C4 0C add esp, 0Ch .text:00403249 E8 0F E0 FF FF call j_powmod_check ; 将十六进制数组进行模幂运算，与存储在程序中的key进行对比 .text:0040324E 89 45 FC mov [ebp-4], eax .text:00403251 6A 03 push 3 ; size_t .text:00403253 8D 45 C8 lea eax, [ebp-38h] .text:00403256 50 push eax ; void * .text:00403257 8D 4D C4 lea ecx, [ebp-3Ch] .text:0040325A 51 push ecx ; void * .text:0040325B E8 60 A5 02 00 call _memcpy .text:00403260 83 C4 0C add esp, 0Ch .text:00403263 8D 55 C4 lea edx, [ebp-3Ch] .text:00403266 52 push edx .text:00403267 E8 20 DE FF FF call j_check_first_3_char_digit ; 检查输入key的前三个字节是否为数字 .text:0040326C 83 C4 04 add esp, 4 .text:0040326F 25 FF 00 00 00 and eax, 0FFh .text:00403274 85 C0 test eax, eax .text:00403276 74 11 jz short loc_403289 ; error .text:00403278 8D 45 C4 lea eax, [ebp-3Ch] .text:0040327B 50 push eax .text:0040327C E8 0E E0 FF FF call j_aes_check ; 将前三个字符串作一定变换后，计算aes加密，最后对比结果
主要功能是将输入的Key取第4-23字节，然后转换成十六进制数组，进行RSA加密，与隐藏在程序中的值进行比较，通过后，再检查前三个字节是否为数字，并将其进行一定变换，最后进行aes加密，并与程序中的隐藏的值对比，如果一致，则成功。
三、RSA加密及逆元d求解
现在来看一下j_powmod_check函数，反求Key的4-23字节。模幂运算主要是基于这个公式，c = (m ^ e) mod n;
.text:00402A42 8D 85 34 FF FF FF lea eax, [ebp-0CCh] .text:00402A48 50 push eax .text:00402A49 E8 2A E6 FF FF call j_xor_string_transform ; hidden_key = 0x208CBB7CD6ECC64516D07D978F5F0681F534EAD235D5C49ADD72D2DB840D5304 .text:00402A4E 83 C4 04 add esp, 4 .text:00402A51 8D 8D DC FC FF FF lea ecx, [ebp-324h] .text:00402A57 51 push ecx .text:00402A58 E8 1B E6 FF FF call j_xor_string_transform ; n = 0x7da39de66016477b1afc3dc8e309dc429b5de855f0d616d225b570b68b88a585 .text:00402A5D 83 C4 04 add esp, 4 .text:00402A60 8B 55 FC mov edx, [ebp-4] .text:00402A63 C7 82 34 02 00 00 10 00+ mov dword ptr [edx+234h], 10h .text:00402A6D 6A 00 push 0 .text:00402A6F E8 DC 68 00 00 call _mirvar .text:00402A74 83 C4 04 add esp, 4 .text:00402A77 89 85 D8 FC FF FF mov [ebp-328h], eax .text:00402A7D 6A 00 push 0 .text:00402A7F E8 CC 68 00 00 call _mirvar .text:00402A84 83 C4 04 add esp, 4 .text:00402A87 89 85 D4 FC FF FF mov [ebp-32Ch], eax .text:00402A8D 6A 00 push 0 .text:00402A8F E8 BC 68 00 00 call _mirvar .text:00402A94 83 C4 04 add esp, 4 .text:00402A97 89 85 CC FC FF FF mov [ebp-334h], eax .text:00402A9D 6A 00 push 0 .text:00402A9F E8 AC 68 00 00 call _mirvar .text:00402AA4 83 C4 04 add esp, 4 .text:00402AA7 89 85 D0 FC FF FF mov [ebp-330h], eax .text:00402AAD 68 60 56 49 00 push offset unk_495660 ; m = hex of user input .text:00402AB2 8B 85 CC FC FF FF mov eax, [ebp-334h] .text:00402AB8 50 push eax .text:00402AB9 E8 22 A7 00 00 call _cinstr .text:00402ABE 83 C4 08 add esp, 8 .text:00402AC1 8D 8D DC FC FF FF lea ecx, [ebp-324h] .text:00402AC7 51 push ecx .text:00402AC8 8B 95 D8 FC FF FF mov edx, [ebp-328h] .text:00402ACE 52 push edx .text:00402ACF E8 0C A7 00 00 call _cinstr .text:00402AD4 83 C4 08 add esp, 8 .text:00402AD7 68 A0 60 48 00 push offset a3e9 ; "3e9" .text:00402ADC 8B 85 D4 FC FF FF mov eax, [ebp-32Ch] ; e = 0x3e9 .text:00402AE2 50 push eax .text:00402AE3 E8 F8 A6 00 00 call _cinstr .text:00402AE8 83 C4 08 add esp, 8 .text:00402AEB 8B 8D D8 FC FF FF mov ecx, [ebp-328h] .text:00402AF1 51 push ecx .text:00402AF2 8B 95 CC FC FF FF mov edx, [ebp-334h] .text:00402AF8 52 push edx .text:00402AF9 E8 C2 77 00 00 call _mr_compare ; mr_compare(m, n) .text:00402AFE 83 C4 08 add esp, 8 .text:00402B01 83 F8 FF cmp eax, -1 .text:00402B04 0F 85 CA 00 00 00 jnz loc_402BD4 .text:00402B0A 8B 85 D0 FC FF FF mov eax, [ebp-330h] .text:00402B10 50 push eax .text:00402B11 8B 8D D8 FC FF FF mov ecx, [ebp-328h] .text:00402B17 51 push ecx .text:00402B18 8B 95 D4 FC FF FF mov edx, [ebp-32Ch] .text:00402B1E 52 push edx .text:00402B1F 8B 85 CC FC FF FF mov eax, [ebp-334h] .text:00402B25 50 push eax .text:00402B26 E8 E5 95 00 00 call _powmod ; (m ^ e) mod n
根据代码分析可知，0x00402A49处为隐藏Key，即 hidden_key = 0x208CBB7CD6ECC64516D07D978F5F0681F534EAD235D5C49ADD72D2DB840D5304，0x00402A58处为模数n，即 n = 0x7da39de66016477b1afc3dc8e309dc429b5de855f0d616d225b570b68b88a585, 0x002AD7处为指数 e = 0x3e9，需要求出 m 并于hidden_key进行比较。由于已知m，可以直接算出c。
相关原理为，加密过程：c = (m^e) mod n；解密过程：m = (c ^d) mod n；需要求出逆元d，首先需要将n进行分解质因数，n = 208096057845685678782766058500526476379 * 273086345401562743300402731618892888991，即 p = 208096057845685678782766058500526476379， q = 273086345401562743300402731618892888991，在求(p-1)*(q-1)，最后根据"扩展欧几里得算法"求解 d = 21005425588345339621950762401208703877439204233991217052799016669569632540401，最后根据公式反求 m = 0x69616d6168616e64736f6d656775796861686131，即字符串“iamahandsomeguyhaha1”
四、前三个字节求解
前三个字节的求解主要在j_aes_check函数中，相关代码分析如下：
.text:00402E5A 8D 95 74 FC FF FF lea edx, [ebp-38Ch]
.text:00402E60 52 push edx
.text:00402E61 E8 12 E2 FF FF call j_xor_string_transform ; "831GD47;?K2M=8:&U#$V#T\"-+\\*)*X'e" ==> "912CA2036A9A0656D17B6B552F157F8E"
.text:00402E66 83 C4 04 add esp, 4
.text:00402E69 8D 85 D0 FA FF FF lea eax, [ebp-530h]
.text:00402E6F 50 push eax
.text:00402E70 E8 03 E2 FF FF call j_xor_string_transform ; "123567389:;<=>?" ==> "0001314000000000"
.text:00402E75 83 C4 04 add esp, 4
.text:00402E78 8B 4D 08 mov ecx, [ebp+8]
.text:00402E7B 8A 11 mov dl, [ecx]
.text:00402E7D 88 95 D0 FA FF FF mov [ebp-530h], dl ; 第一个字节
.text:00402E83 8B 45 08 mov eax, [ebp+8]
.text:00402E86 8A 48 01 mov cl, [eax+1]
.text:00402E89 88 8D D1 FA FF FF mov [ebp-52Fh], cl ; 第二个字节
.text:00402E8F 8B 55 08 mov edx, [ebp+8]
.text:00402E92 0F BE 42 02 movsx eax, byte ptr [edx+2]
.text:00402E96 03 05 28 57 49 00 add eax, dword_495728 ; eax += 1
.text:00402E9C 88 85 D2 FA FF FF mov [ebp-52Eh], al ; 第三个字节+1
.text:00402EA2 68 FC 01 00 00 push 1FCh ; size_t
.text:00402EA7 6A 00 push 0 ; int
.text:00402EA9 8D 8D 04 FE FF FF lea ecx, [ebp-1FCh]
.text:00402EAF 51 push ecx ; void *
.text:00402EB0 E8 4B AD 02 00 call _memset
.text:00402EB5 83 C4 0C add esp, 0Ch
.text:00402EB8 6A 00 push 0
.text:00402EBA 8D 95 D0 FA FF FF lea edx, [ebp-530h]
.text:00402EC0 52 push edx
.text:00402EC1 6A 10 push 10h
.text:00402EC3 6A 00 push 0
.text:00402EC5 8D 85 04 FE FF FF lea eax, [ebp-1FCh] ; 猜测一下，前三个输入字节"520", aes的密钥为："52113140000000000"
.text:00402ECB 50 push eax
.text:00402ECC E8 8F A8 00 00 call _aes_init ; aes_init("52113140000000000" 0, 0x10, 0);
.text:00402ED1 83 C4 14 add esp, 14h
.text:00402ED4 8D 8D AC FB FF FF lea ecx, [ebp-454h]
.text:00402EDA 51 push ecx
.text:00402EDB 8D 95 04 FE FF FF lea edx, [ebp-1FCh]
.text:00402EE1 52 push edx
.text:00402EE2 E8 59 AD 00 00 call _aes_encrypt ; ase_encrypt("pediy", "52113140000000000"); 主要将输入的第一、二个字节填充到“0001314000000000”到前两个字节，第三个字节加1，填充到对应第三字节位置，将填充的字符串作为key对“pediy”进行aes加密，并与隐藏值0x912CA2036A9A0656D17B6B552F157F8E进行比较，通过则成功。顺便提一句，当大家看到“1314”的时候，估计已经猜到前三个字节为“520”了吧，顺手试一下，果然成功。
最后，完整的key为：520iamahandsomeguyhaha1
四、总结几点经验教训
踩坑1. 首次逆密码类的CrackMe，没有经验，居然没想到去先找找常用密码库的信息，后来逆着逆着感觉不对劲，赶紧又去翻翻程序中的字符串，才发现了miracl库。由于对密码学不熟悉，完全不知道有这个库。所以以后对于这类逆向问题，首相应该去识别密码算法库，找Signature文件和相应文档。
踩坑2. 同样由于不会密码学的缘故，对RSA算法主要流程的不是很了解，导致模幂求逆上都卡了好一阵子，翻了好多资料后，才大致知道咋回事。以后一定要恶补密码学
踩坑3. 比较尴尬，可能由于最近异或用的有点多，在利用 m = (c^d) mod n 公式时，误把“^”当作求指数运算，好久之后才发现；同时，直接在python中跑了m = (c ** d) % n，结果发现好久都没跑出来，无奈之下转身睡觉去了，几小时之后爬起来一看大吃一惊，居然还没跑出来，这才上网搜索，才发现python中pow函数自带求模幂功能，而且秒解，看来解题不可用蛮力啊。
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
最后于 2018-6-23 13:15
被Iamakiller编辑
，原因：
|
|
|---|---|
