看雪.WiFi万能钥匙 CTF 2017第十四题 点评及解题思路
看雪CTF 2017 比赛进行至第十四题
截止至今天中午12点，第十三题破解人数为 2 人！
防守方 hsadkhk 依然位居首位~
此题过后，风间仁依然处于第一位~，kkHAIKE位列第二位。
比赛明天就要结束了！
接下来我们来回顾一下第十四题
看看 看雪评委和出题者是怎么说的ヾ(๑╹◡╹)ﾉ"。
看雪评委 netwind 点评
该题采用了加密壳进行保护，程序中所有字符串都被加密隐藏，校验流程被隐藏在著名的Brainfuck虚拟机中，注册机制采用LFSR（线性反馈移位寄存器）模型，题目难度非常大；需要对程序脱壳后，对Brainfuck虚拟机代码还原，再破解LFSR算法才能解此题。
作者简介
半盲道人，在下合肥某科大天文系学子，毕业方十日，前程漫漫。书蠹诗魔，兴趣广泛。文理情兼具，儒玄道两全。上测星轨，下卜大衍。然裸眼视力0.1，其父嘲之曰半盲，因以为号焉。
反正啦，就是啥都会一点，深度学习啊，高性能计算啦，逆向其实还是刚刚接触，这次希望能在看雪结识大牛，也能学习到不少东西，也希望能给诸君带来有趣的破解体验，做了一点微小的工作，谢谢大家。
看雪 CTF 2017 第十二题设计思路
去年看了看CTF 2016，跃跃欲试之下准备参加今年的CTF。没想到竟然提前了。花了十天时间赶快写完，顺便专门写了一个壳。用了一些比较学术的黑科技，希望能给破解者带来不一样的体验。源代码和具体说明都放在压缩包里了。
参赛程序是CTF.exe，支持Windows 7 32/64位到Windows 10 Build 15063.250。XP未测试，应该也能运行。
为了保持简单与可移植性，此程序无图形界面，不需要任何额外的运行库。
如果key输入正确，会打印字符串“Yeah! You've got it”并自动退出。
杀毒软件可能会报毒，现在的杀软看到壳就报毒......这个问题在下也很头疼。有时候刚运行就被Windows Defender删掉了.......具体报毒情况参见：
https://www.virustotal.com/en/file/b5b1fb5642d811c0a0059ba41398ddac2716057ff01b6531dd814fb927d16369/analysis/1493728563/
http://r.virscan.org/report/e02d220087c3b8bc2cdc4e16f7f72bbc
正确的密钥是 ToBeOrNot2Be
CrackMe 目录下是主程序的代码，以及 VS2015 的工程文件。
PEZEncrypt 目录下是在下为本次比赛随手写的一个简单的壳，更通用的代码已经被在下放在https://github.com/emc2314/PEZEncrypt。
References目录下是参考文献。即这个程序用到的一些技术来源。
Brainfuck目录下是与Brainfuck虚拟机相关的文件。
Bin 目录下是一些手工处理的结果。libbf.exe是libbf的编译结果。CrackMe.exe是CrackMe工程编译所得，CrackMe-stolen是手工将程序入口点的几条指令去除后的结果。Project1.exe是PEZEncrypt的编译结果。将CrackMe-stolen.exe拖到Project1.exe上即为最终结果。
CTF.exe.checksum是CTF.exe的哈希，CTF.exe.checksum.asc是用在下的GPG私钥对CTF.exe.checksum的签名，均为ASCII文件。
程序大概分四个层次：
1. 加壳。加壳很简单，用XTEA算法对.text和.data区段进行加密，然后运行的时候自动解密。对输入表无处理。壳的代码中使用了SEH来混淆程序流程，并且检测CONTEXT中的硬件断点。为了防止ESP定律，壳的开头首先是一个虚假的pushad，然后把popad藏在花指令里，再sub esp, a_certain_value，然后才是真的pushad，在最后的跳转前add esp, a_certain_value。且将SEH藏在这个pushad的结构里，使得硬件断点（如果有的话）提前多次触发。为防止内存断点，在运行过程中将栈所在的页设为可读可写，覆盖可能的NO_ACCESS属性。在SEH处理中设置SetUnhandledExceptionFilter，以此检测调试器。并且运行中有两次内存校验，防止0xCC。
2. CrackMe。这个程序中的字符串都被异或了一个随机值（编译时），并在每次调用重要函数的时候使用模板元编程构成一个有限状态机，在状态转化的时候检测调试器，如果没有才会完成调用
3. Brainfuck。真正的校验流程被隐藏在著名的Brainfuck虚拟机中。这个语言只有[ ] + - < > . , 8条指令，CrackMe中实现了一个虚拟机，BF的代码被放在.rsrc段中（为了降低难度，并未加密字符串），注册流程大概是如果输入字符串长度为12，就将12个字符的ASCII码（96个bit）输入VM中运行（见CrackMe\lfsr.cpp）。然后VM会输出一个结果，CrackMe会将这个结果与预设的一个数组比较，如果相同就认为正确。
4. LFSR。注册机制是一个线性反馈移位寄存器（LFSR），这个是原来生成流密码的基本模型。这个模型存在很多问题所以现在渐渐被淘汰。本程序利用了其中一个漏洞：代数攻击（见References\lfsr algebraic attack.pdf）。具体的漏洞利用代码尚未放在文件夹中，如果此程序被本次比赛选中，在下再行公开。
破解思路：
说实话自己写的程序自己都觉得难破解。。。看着自己的源代码大概有这几个步骤：
1. 脱壳，找到OEP直接dump，怎么找OEP？慢慢跟踪呗。几个反调试需要插件才能过，毕竟很小的壳，耐心一点就好了
2. 识别主函数中的函数调用，找到几个重要函数（比如BF的VM相关代码）。这个主程序很小，也不难。
3. 最难的就是弄清楚BF要做什么。这个先将BF还原为C代码（非常简单），然后通过窥孔优化等技术简化这个流程（其实最简单的方法就是通过各种优化能力强的编译器比如gcc, intel c++ compiler编译这个C代码，再反汇编回来）。然后在程序中导出那个与VM输出想对比的数组
4. 最后就是破解lfsr了，这个通过论文中的方法，解一个3570（即12*7+（12*7）*（12*7-1）/2）元的线性方程组就行了。高斯消元法（或者用SAT的算法复杂度更低）的复杂度是N^3，大概几十秒就跑出来了。
最后，穷举的空间不大，只有10^26水平。但是这个程序我故意写的比较慢，所以想直接穷举的话不太可能。
下面选取攻击者 渡。的破解分析
随缘做题 2333
程序带壳，用查壳工具没能查出来是什么壳，那这个应该是作者原创的，只能手工脱壳了，可是......我不会脱壳，瞎捣腾一番，毫无结果。
在最后快要放弃的时候，尝试了一次投机的方法，运行程序，用OD附加，转到401000，然后dump，发现能dump！！！
这样就得到了疑似脱壳后的代码了，然后是字符串搜索，定位到sub_40679A()
其中sub_4074A3()如下
所以v0上的数据就是'Please enter the key: '
sub_40752A()的功能不清楚，不过看起来那么复杂，应该是库函数吧，根据实际就暂时把他当做printf之类的函数吧
找到调用sub_40679A的函数sub_407165()
这里的过程看上很怪。。。不过里面的函数有点特别，比如sub_40818E,sub_407918，sub_407E2F，他们的参数里都有一个函数地址，跟进分析这些函数地址，根据其代码，分析猜测其功能，然后推测出其验证过程：输入长度为12的字符串交由bf_vm验证。
bf_vm函数如下
这里输入的字符串会转成bit，然后程序根据预先准备好的bf代码生成字节码，然后再开始运行vm
bf_func函数如下
这里的功能跟bf的并没多大不同，只是case 5和case 6需要注意，case 5如下
case 6如下
试着把bf_data上的数据累加，发现和刚好为3600，那么综合分析可以知道，case 5的验证必须成功，而且次数刚好是bf_data的长度，不过当bit_add达到3600时，get_bf_input返回的数据有点变化，但现在还不知道有什么用，接下来就是对bf代码转义了
转义结果可以根据自己的语言习惯，我比较喜欢用Python，就按照python的格式来转义了
首先是常见的转义，代码如下
def cal(s): if '+' in s: return '+= %d'%len(s) else: return '-= %d'%len(s) ... ... ... pattern = re.compile(r'>+') match = pattern.match(s[p:]) if match: p += len(match.group()) ptr += len(match.group()) continue pattern = re.compile(r'' in s: return len(s) else: return -len(s) ... ... ... pattern = re.compile(r'([><]+)') match = pattern.match(s[p:]) if match: p += len(match.group()) groups = match.groups() ptr1 = ptr + sym2cal(groups[0]) ptr2 = ptr1 + sym2cal(groups[1]) ptr3 = ptr2 + sym2cal(groups[2]) # print tab+'mov mem[%d] mem[%d]'%(ptr1,ptr3) print tab+'mem[%d] = mem[%d]'%(ptr1,ptr3) for v in groups: ptr += sym2cal(v) continue pattern = re.compile(r'\[-\]') match = pattern.match(s[p:]) if match: p += len(match.group()) # print tab+'mov mem[%d] 0'%(ptr) print tab+'mem[%d] = 0'%(ptr) continue
这样得到的转义代码就好读多了，然后是算法分析，转义代码里有一段这样的代码
mem[51] = 0 mem[51] += 2 mem[21] = mem[55] mem[20] = mem[51] mem[50] = mem[21] while mem[21]: mem[21] -= 1 mem[20] -= 1 mem[19] = mem[20] mem[18] += 1 while mem[19]: mem[19] = 0 mem[18] -= 1 while mem[18]: mem[18] -= 1 mem[50] = mem[21] mem[20] = mem[51] mem[55] = mem[50] cmp mem[55] data[data_ptr]
其实这个就是mem[55] %= 2，既然结果mod2，那么前面的一些操作都可以简化为mod2上的操作，比如加可以简化为异或，乘可以简化为与，这样分析出其验证过程，然后是用z3来求解了，求解代码见附件。
得到 flag：
ToBeOrNot2Be
最后感谢 WiFi 万能钥匙安全应急响应中心的赞助支持，
接下来的比赛大家一定要使出洪荒之力哦！↖(^ω^)↗
比心 ❤
上海连尚网络科技有限公司成立于 2013 年，是一家专注于提供免费上网和内容服务的移动互联网企业。连尚网络自主研发的核心产品 WiFi 万能钥匙，以分享经济的模式，通过云计算和大数据技术，利用热点主人分享的闲置WiFi资源，为用户提供免费、稳定、安全的上网服务，以帮助更多的人上网，找到属于他们的机会，改变自己的命运。