作者Editor

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

发布于:2017-06-29 17:48:53 阅读:506 回帖:0


今天是周一,上海在淅淅沥沥的雨水中进入新的一周,比赛也进入新的一题。中午 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 手工完成算法分析,过程比较累,你有什么更好的办法请不吝分享。如果有猪蹄汤、排骨汤应该提前服用。

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

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

1

一、首先,算法很绕,能破解出来也有一定的运气成分。看到群里有人提到是否可以直接修改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
  //结束脚本


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

2

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

3

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

4

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

5


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



要求注册码为:8-20位,且1-9(非0数字)


6

六、跟踪到 4010CF:



此时感觉 CALL 4014E0 可疑,单步进入:



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

7

七、返回到上一步,继续:

此处 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

8

八、从上文 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位
依次类推,先得到大概输入、输出位数的范围,便于后续选择。

9

九、跟踪关键比较程序


与计算结果的第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位相等:


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

10

十、算法逆向

输入:“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:

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

11

十一、总结

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

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


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

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

比心

赞助商

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


返回