专栏名称: 看雪学苑

致力于移动与安全研究的开发者社区，看雪学院(kanxue.com)官方微信公众帐号。

看雪.万能钥匙 CTF 2017 第二题点评及解题思路

看雪学苑 · 公众号 · 互联网安全 · 2017-06-05 17:59

正文

“

今天是周一，上海在淅淅沥沥的雨水中进入新的一周，比赛也进入新的一题。中午 12 点第二题结束。经过一个周末的奋战，小伙伴们的战绩如何呢？

截止目前，第二题，一共有 17 个小伙伴破解成功。

经过 4 天激烈的争夺，比赛排名发生了较大的变化，一些熟悉的选手进入我们的视线，如 HighHand、风间仁、谖草、HHHso等。

这些选手在看雪 CTF 2016 的比赛中表现突出，不知今年是否依然会不负众望？还是会有黑马，给我们惊喜呢？

让我们拭目以待吧！

接下来我们来看看第二题的点评与解析。

看雪评委 netwind 点评

作者设计了一个计算位数为 0x400 位的大数计算类，要求利用公式 R=(N*9)^M 以及 R 和 N 的限制条件来求解 N。此题在分析出算法后根据限制条件爆破可求解。

作者的设计说明：

1. 作者设计了一个十进制大数计算类 BigNum，计算位数暂定为 0x400 位，算法仅实现了加法和乘法。

2. 要求输入8－20 位非 0 数字N，乘以 9 后循环计算乘方结果：R=(N*9)^M，同时符合以下四条规则时为正确答案：

  1) R 位数为奇数；

  2) R 最中间位与 N 首位相等；

  3) R 最后几位与 N 除首位外的字符相同；

  4) R 最开始几位与 N 除首位外的字符逆序排列。

破解思路：

穷举不太可能实现，根据检测规则，如果结合数学上的一个“幻数”12345679 就非常简单了：

12345679*9=111111111
111111111^2=1234567898765432

作者简介

lelfei，业余 crack 爱好者。学生时代对电脑产生了浓厚的兴趣，经历了很长时间的游戏沉迷后，开始慢慢转向学习技术，工作后自学了ASM，VB，VC，HTML，ASP，Python等语言的入门。工作原因上网较少，对单机的逆向分析、算法比较感兴趣，但是由于缺少系统的学习，水平处于“入行较早层次较低知识较杂”的阶段。

破解分析

本文就纯 OD 手工完成算法分析，过程比较累，你有什么更好的办法请不吝分享。如果有猪蹄汤、排骨汤应该提前服用。

为了节省篇幅，本文直接拿事后算出来的注册码作为测试输入，更直观。功力有限，有些地方分析不到位，请见谅。

另外，我对本题作者无任何不敬之意，权当学习交流了。

一、首先，算法很绕，能破解出来也有一定的运气成分。看到群里有人提到是否可以直接修改CrackMe汇编代码，让它自己完成穷举，我觉得这个思路值得探索，事后补上了这章。开头先讲讲如何利用 ODbgScript 实现自动化穷举代码的写入和结果显示，就当开拓思维吧，以后在其他场合还是有用武之地的。

// Ctf.pediy.com crackme 2# Ollydbg 穷举脚本
// 本例测试穷举效率不高，每秒几千到一万多次，可能跟Crackme的算法很绕有关
// 所以直接通过本Crackme自身写入代码进行穷举需要几个小时时间才能完成
// OdbgScript 1.83
// Written by 爱琴海
// 2017/06/04

CMP $VERSION, "1.82"
//比较是否大于1.82版,脚本基于1.82版本以上
JAE Initialize
  MSG "需要1.82版本以上的ODbgScript才能支持本程序，请更新!"
  RET

Initialize:
  //定义变量
  VAR Sn_address
  //储存注册码地址
  VAR Eip_bak
  //备份恢复原始Eip
  PUSHA
  //高版本OdbgScript才支持该指令，保存寄存器现场

Set_break:
  //设置相关断点，提示用户
  BP 4010BC
  BPGOTO 4010BC,Catch_break
  //设置4010BC断点，接管算法流程
  BP 401257
  BPGOTO 401257,Succes
  //设置401257断点，找到注册码时候接管流程
  MSG "请在CrackMe输入窗口输入8位非0数字并回车继续"
  RUN

Catch_break:
  //捕捉到4010BC断点，让程序自己完成一些初始化工作再接管
  BC 4010BC
  //取消4010BC断点，有始有终
  MOV Eip_bak,eip
  //保存当前eip，穷举结束时得恢复eip

Start:
  //循环穷举主程序，为提高运行效率采用补丁方式，交给程序自己完成
  MOV Sn_address,ecx
  //储存注册码地址，成功时需要调用显示
  MOV [ecx],#313131313131313000#
  //我已经测试CrackMe自身穷举效率较低，穷举需要几个小时才能完成
  //穷举初值11111110（接下里的累加1，将实际初值变为11111111）

Inc_check:
  //写入代码，修改程序流程，实现穷举注册码功能
  MOV [4010BC],#E95F660000909090909090#
  // JMP 00407720 以及 nop 填充，接管算法流程
  MOV [40122B],#909090909090E976FEFFFF#
  // NOP JE 004010FA
  // JMP 004010AC 错误时继续
  MOV [407700],#60B80800000083F8017413807C08FF397609C64408FF31FE4408FE48EBE861C3FE4107E8D8FFFFFF8039397601C3E99499FFFF#
  //累加、检查进位子程序，选择407700位置写入代码
  // 407700:
  // PUSHAD
  // MOV EAX,0x8
  // CMP EAX,0x1
  // JE 0040771E
  // CMP BYTE PTR DS:[EAX+ECU-0x1],0x39 不是ECU而是ECX，显示乱码搞不懂
  // JBE 0040771B
  // MOV BYTE PTR DS:[EAX+ECU-0x1],0x31 不是ECU而是ECX，显示乱码搞不懂
  // INC BYTE PTR DS:[EAX+ECU-0x2]      不是ECU而是ECX，显示乱码搞不懂
  // DEC EAX
  // JMP 00407706
  // POPAD
  // RETN
  // 407720:
  // INC BYTE PTR DS:[ECX+0x7]
  // CALL 00407700
  // CMP BYTE PTR DS:[ECX],0x39  最高位超过9就结束
  // JBE 0040772E
  // RETN
  // 40772E:
  // JMP 004010C7
  RUN

Succes:
  //成功穷举到注册码
  BC 401257
  //取消401257断点，有始有终
  MSG [Sn_address]
  //显示注册码

End:
  //收尾工作
  POPA
  //高版本OdbgScript才支持该指令，彻底恢复寄存器现场
  MOV eip,Eip_bak
  //穷举结束恢复eip
  MSG "穷举结束"
  ret
  //结束脚本

你猜结果如何？虽然能穷举到注册码，但每秒几千次到上万次，效率比较低，需进一步分析算法实现破解。这章事后补充的，希望能有启发。

二、查壳，Microsoft Visual C/C++(6.0)[libc]，木有壳。

三、OD载入，查找字符串，定位到：“WELL DONE！”，往上翻翻就到了主要代码。

四、在401053设断点，运行。动态跟踪时发现有检测GetTickCount，记得设置返回为0，避免干扰分析。

五、输入“97654321”之后回车断下，一步步跟踪：

要求注册码为：8-20位，且1-9（非0数字）

六、跟踪到 4010CF：

此时感觉 CALL 4014E0 可疑，单步进入：

原来此段代码是将输入字符当做十进制，逐位存放，逐位检查格式、进位，出题作者自己实现了最大0x400位十进制计算功能。比如输入“97654321”得到 12345679。 CALL 00401970 各位可以自己跟踪看看，这里省点篇幅以免过于啰嗦。

七、返回到上一步，继续：

此处 CALL 401730 明显得跟踪进入：

跟踪 CALL 00401540：

留意到401567、40156B分别处理了当前计算结果所储存的地址和内容，为了方便后续分析，在这两处分别下条件记录断点记录
ECX+EBP*4+0x8、EBX，并命名“地址、密码”：

继续跟进 CALL 004016E0 定位核心功能：

可以看到：

0040170C y |. 0FAFDF |IMUL EBX,EDI ; *9 *7 *6 ......*3 *2 *1

这句就是作者实现自定义乘法的“乘法之根本法”，后续频繁调用这个子程序，为了减少劳动量，请设置 401708、40170C、40170F 条件记录断点，永不中断，分别永远记录 EBX、EDI、EBX 值，并标明表达式名称为“x、y、x * y”，以免后续搞混了。

在4017B5下断，清空记录窗口，运行，查看记录窗口：

Log data
地址       消息
00401567   COND: 地址 = 001289B0
0040156B   COND: 密码 = 00000009
00401567   COND: 地址 = 00128664
0040156B   COND: 密码 = 00000007
00401567   COND: 地址 = 0012823C
0040156B   COND: 密码 = 00000006
00401567   COND: 地址 = 00128D00
0040156B   COND: 密码 = 00000005
00401567   COND: 地址 = 00128234
0040156B   COND: 密码 = 00000004
00401567   COND: 地址 = 001284E0
0040156B   COND: 密码 = 00000003
00401567   COND: 地址 = 00127F94
0040156B   COND: 密码 = 00000002
00401567   COND: 地址 = 00128C14
0040156B   COND: 密码 = 00000001
00401708   COND: x     = 00000009
0040170C   COND: y     = 00000009
0040170F   COND: x * y = 00000051
00401708   COND: x     = 00000007
0040170C   COND: y     = 00000009
0040170F   COND: x * y = 0000003F
00401708   COND: x     = 00000006
0040170C   COND: y     = 00000009
0040170F   COND: x * y = 00000036
00401708   COND: x     = 00000005
0040170C   COND: y     = 00000009
0040170F   COND: x * y = 0000002D
00401708   COND: x     = 00000004
0040170C   COND: y     = 00000009
0040170F   COND: x * y = 00000024
00401708   COND: x     = 00000003
0040170C   COND: y     = 00000009
0040170F   COND: x * y = 0000001B
00401708   COND: x     = 00000002
0040170C   COND: y     = 00000009
0040170F   COND: x * y = 00000012
00401708   COND: x     = 00000001
0040170C   COND: y     = 00000009
0040170F   COND: x * y = 00000009
004017B5   断点位于 2.004017B5

取消 4017B5 断点，保留条件记录断点，跟踪 CALL 004015E0：

可以看到：

00401641 b |. 012A |ADD DWORD PTR DS:[EDX],EBP ; 加法

这句就是作者实现自定义加法的“加法之根本法”，后续频繁调用这个子程序，为了减少劳动量，请设置40163D、401641、401643条件记录断点，永不中断，分别永远记录EBP、DWORD PTR DS:[EDX]、条件EDX>400记录DWORD PTR DS:[EDX]值，并标明表达式名称为“a、b、a + b”，以免后续搞混了。

此时还没到用到加法的时候，所以你也记录不到加法信息，别着急，保留条件记录断点，回到4010EE下断点，清空记录窗口，运行。

断下之后，查看记录窗口：

通过上述记录信息，很快就可以理解本步骤算法含义：12345679 * 9 = 111111111

八、从上文 4010EE 继续：

CALL 401840 和 CALL 401730 是算法的核心，分别实现了逐位乘法、加法，累加得到最终结果。（CALL 401730 在上文中已经分析过了）

清空记录窗口，在 401137 设置断点，运行，此时查看记录窗口正在迅速回显记录，条数很多，此时静下心来逐条查看计算记录，因为条数太多，这里只罗列最后结果那几行，剩下的记录请见附件log：

00401567   COND: 地址 = 0012C728
0040156B   COND: 密码 = 00000001
00401567   COND: 地址 = 0012CCFC
0040156B   COND: 密码 = 00000002
00401567   COND: 地址 = 0012C584
0040156B   COND: 密码 = 00000003
00401567   COND: 地址 = 0012C48C
0040156B   COND: 密码 = 00000004
00401567   COND: 地址 = 0012C154
0040156B   COND: 密码 = 00000005
00401567   COND: 地址 = 0012C3EC
0040156B   COND: 密码 = 00000006
00401567   COND: 地址 = 0012CC8C
0040156B   COND: 密码 = 00000007
00401567   COND: 地址 = 0012C220
0040156B   COND: 密码 = 00000008
00401567   COND: 地址 = 0012C188
0040156B   COND: 密码 = 00000009
00401567   COND: 地址 = 0012C740
0040156B   COND: 密码 = 00000008
00401567   COND: 地址 = 0012BFD0
0040156B   COND: 密码 = 00000007
00401567   COND: 地址 = 0012C8D8
0040156B   COND: 密码 = 00000006
00401567   COND: 地址 = 0012C11C
0040156B   COND: 密码 = 00000005
00401567   COND: 地址 = 0012C0BC
0040156B   COND: 密码 = 00000004
00401567   COND: 地址 = 0012CBEC
0040156B   COND: 密码 = 00000003
00401567   COND: 地址 = 0012C598
0040156B   COND: 密码 = 00000002
00401567   COND: 地址 = 0012BFEC
0040156B   COND: 密码 = 00000001
00401137   断点位于 2.00401137

整理计算记录、步骤：

根据追踪记录，不难看出本作品是以用户输入倒置为十进制数，自定义了0x400位十进制计算乘法、加法（从低位到高位，逐位乘法、加法并进行进位）

Python 实现该部分算法：

先在 Python 中测试：
输入“11111111”--> 11111111 -- > 16位：9999999800000001
输入“87654321”--> 12345678 -- > 17位：12345676987654404
输入“99999999”--> 99999999 -- > 18位：809999983800000081
输入8位-->16-18位
输入9位-->18-21位
依次类推，先得到大概输入、输出位数的范围，便于后续选择。

九、跟踪关键比较程序：

与计算结果的第7-1位相等

与计算结果的17-11位相等

0040120F |. 03F0 |ADD ESI,EAX
00401211 |. 74 44 |JE X2.00401257 ; 正确出口

其中：

00401168 |. /0F85 A7000000 |JNZ 2.00401215 ; 当输入8位数时，结果16-18位，所以可以假设

17 位

提示了计算结果极有可能是奇数位。

004011A2 |. /75 78 |JNZ X2.0040121C ; 不能跳

提示了用户输入的第1位（十进制个位）== 计算结果的中间位。

CALL 004013E0 关键比较，逐位比较用户输入的第2-8位是否与计算结果的第7-1位相等；用户输入的第8-2位是否与计算结果的17-11位相等：

至此算法部分基本清楚了。

十、算法逆向：

输入：“97654321”--> 12345679

输出：12345678987654321

满足条件1：每个输入字符为1-9数字

满足条件2：输出结果奇数位

满足条件3：输出结果中间位必须等于输入第1位（十进制末位）

满足条件4：用户输入的第2-8位（十进制7-1位）必须与计算结果的第7-1位相等

满足条件5：用户输入的第8-2位（十进制1-7位）必须与计算结果的17-11位相等

考虑先从8位数开始穷举：（也许算法深入分析后会有一些简便运算方法或者效率提升，但是人生苦短，只要出答案即可，不浪费时间）

Python Keygen：

如果换好一些的电脑、不采用脚本计算，速度应该会有显著提升。

十一、总结

本题作者自定义实现了最大 0x400 位十进制乘法、加法运算，注册码算法对原文和密文都有关联，一时半会儿我认为穷举是最合适的。

本题难点在于对众多汇编指令的跟踪、理解、总结，对模拟大数运算的了解，以及调试方法的恰当应用，否则会把你绕晕。

最后感谢 WiFi 万能钥匙安全应急响应中心的赞助支持，

接下来的比赛大家一定要使出洪荒之力哦！↖(^ω^)↗

比心 ❤

赞助商

上海连尚网络科技有限公司成立于 2013 年，是一家专注于提供免费上网和内容服务的移动互联网企业。连尚网络自主研发的核心产品 WiFi 万能钥匙，以分享经济的模式，通过云计算和大数据技术，利用热点主人分享的闲置WiFi资源，为用户提供免费、稳定、安全的上网服务，以帮助更多的人上网，找到属于他们的机会，改变自己的命运。

往期热门内容推荐

更多优秀文章，长按下方二维码，“关注看雪学院公众号”查看！

看雪论坛：http://bbs.pediy.com/

微信公众号 ID：ikanxue

微博：看雪安全

商务合作：[email protected]

点

阅读原文了解更多