看雪论坛
发新帖
16

[原创]CTF2017参赛题CrackMe

lelfei 2017-5-25 07:27 537

lelfei参赛题目:CrackMe

答案:97654321

设计说明:

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

其他说明:

无法确定答案的唯一性,不过这么有特点的数应该不多吧。。

--------------------------------------------------------

设计感想:

最开始设计时,苦于没有既好玩又设计巧妙的算法,一直没有什么进展。后来突然想到12345679这个比较特殊的数,灵感来了。首先,12345679*9=111111111,这么有规律的数,肯定是没有几个的(到底有没有其他符合这种规律的数?我没有穷举过,不知道啊)。然后9个1的平方为12345678987654321,又跟初始值有了联系:前7位相同,后7位逆序排列,以此作为检测条件,肯定是非常巧妙的!

于是开始设计:语言选用经典的VC6,操作数值方便;平方数为17位,超过了32位数的上限,需要设计一个大数计算器,用于计算加法和乘法;大数计算器BigNum使用0x100位,使用0x100字节存储每一位的值;计算输入值*9,然后算平方值,比较前7位和后7位,后来又增加了比较中间位为输入值的末位这一条件。

对于BigNum类加法很好实现,按位相加,然后用CalcValue()校验一下进位就可以了。乘法的实现方法绕了一下,先设计了一个MulSingle(int v)单数乘法,不需要考虑进位;然后再加一个十进制移位操作LeftMove(int v),相当于N*10^v,只需要按位往前移,后面补0就可以了;最后把乘法转化成:N*(abcd)=N*10^3*a+N*10^2*b+N*10*c+N*10^0*c,把多位乘法简化成移位、单数乘法、加法,简单方便!

第一版设计出来了,后面的事就是增加难度了。考虑到个人能力和个人喜好,就不加壳、不加花、不加VM了,纯算法题,至少我是非常喜欢的。

1.只计算平方,难度太低,于是把检测条件转成循环检测乘方值,当乘方值溢出时跳出循环,让cracker不知道是在循环的哪一层检测成功的;

2.位数只有0x100位,乘方时很快就溢出了,增加到0x400位,把字节存储改成双字32位存储,再扩展起来也方便;

3.存储位是顺序存储的,太容易观察结果了,在BigNum类初始化时添加一个顺序ID列表int id[BBLEN],然后把每一位随机与其他位交换数值,生成一个随机列表,访问时使用bb[id[n]],避免内存中出现数值连续存储;

4.在计算乘法时,重新初始化随机数种子,让数值存储再次打乱;

5.在初始化时保存随机数种子GetTickCount,在最后比较数值时查看GetTickCount是否相差太大,如果差的太大则是调试状态,让比较的返回值始终返回错误。

经过这些难度增加,自认为对算法的隐藏做的差不多了,等放出来时才发现大大低估了cracker的水平,基本上在编程时留的后门全部都被发现了。。

最后总结一下设计上存在的不足:

首先是初始化随机列表时,为了让自己观察方便,先初始化顺序列表,然后再随机交换,当处于调试模式时跳过随机交换的过程。结果果然有cracker发现了这个漏洞,直接跳过随机交换的过程,大大降低了观察的难度。

其次是对输入值限制的太窄,8-20位数值,刚开始我觉得0x400位的乘方值应该会延迟穷举的时间,但是忽略了穷举的顺序,大部分cracker会先从平方开始穷举,我自己试了一下8位数的平方值穷举,不到1秒就出结果了。

再次是算法的比较过程太简单了,有几个人是看到算法比较是前面顺序后面逆序,直接上网搜回环数,直接找到了111111111,再除以9就得到结果了。

最后是算法隐藏的还是不够好,很多人猜测是大数算法后,都不用去分析计算过程,直接看结果比对就可以了。应该把大数算法拆分,让cracker不那么容易猜出大数结构。


我自己总结的这一题的特点是:纯分析题,分析出算法后非常容易解出答案。

最后,附上程序源码,祝大家玩的开心!

上传的附件:
本主题帖已收到 0 次赞赏,累计¥0.00
最新回复 (5)
12
netwind 2017-5-25 19:24
2
在XP正常运行  依据提供的注册码  可以成功注册

请提供一下破解思路  或者题目结束时尽快提交也可
16
lelfei 2017-5-26 12:09
3
额。。。上面的破解思路不行吗?了解算法了很简单,不了解算法的话,我也不知道要怎么破解。。。
12
netwind 2017-5-26 23:05
4
要暴力枚举的吧  这个时间不能太长了    你可以试试解题时间
16
lelfei 2017-5-31 09:23
5

刚用python跑了一下8位数的暴力枚举,不到1秒就出结果了,我的这心剜凉剜凉的。。。

import time
print ("***Strat:",time.time())
for a in range(1,10):
	for b in range(1,10):
		for c in range(1,10):
			for d in range(1,10):
				for e in range(1,10):
					for f in range(1,10):
						for g in range(1,10):
							for h in range(1,10):
								n=a*10000000+b*1000000+c*100000+d*10000+e*1000+f*100+g*10+h
								m=n*n*81
								if (m%10000000==g*1000000+f*100000+e*10000+d*1000+c*100+b*10+a):
									s='%d' %m
									if (int(s[int(len(s)/2)])==h) and (int(s[:7])==a*1000000+b*100000+c*10000+d*1000+e*100+f*10+g):
										print (n,m,time.time())
print ("***End:",time.time())

结果:

c:\Python36>python 1.py
***Strat: 1496193477.4848373
12345679 12345678987654321 1496193478.3458867
***End: 1496193532.07996
c:\Python36>


wjllz 2017-8-21 03:54
6
请问大大可以做一期视频教学么  我没有看懂
返回



©2000-2017 看雪学院 | Based on Xiuno BBS | 域名 加速乐 保护 | SSL证书 又拍云 提供 | 微信公众号:ikanxue
Time: 0.012, SQL: 10 / 京ICP备10040895号-17