查看原文
其他

看雪CTF.TSRC 2018 团队赛 第十一题『伊甸园』 解题思路

小雪 看雪学院 2019-05-25


第十一题《伊甸园》在今天(12月23日)中午12:00 结束攻击!仅4支团队攻击成功,其中, 金左手 以 48489s 攻速夺得本题第一名!


本题结束后,防守团队排行榜如下:




最新赛况战况一览


第十一题之后,攻击方最新排名情况如下:


中午放题搬砖狗哭哭 依然在Top 10 的首席座位,AceHub下降一名至第五名,萌新队上升一名至第四名,其他排名不变。


距离比赛结束,仅剩4题,潜力团队是时候登场了!来“hack"这个局势吧!



第十一题 点评


crownless:

“伊甸园”此题涉及到了数学中的微分和积分知识,但不完全是单纯的微积分,还要求破解者利用数学基础知识对反编译代码化繁为简,并结合Base62编码求出最终答案。


第十一题 出题团队简介


出题团队: CR_Reborn 






第十一题 设计思路


由看雪论坛  ElssZion 原创


题目答案:


BpLDc1LExvZywqLC0sUG9A3ZXJfYXgsMjMsLSxQb3dlcl9A4YSwrLExvZyxQb3dlcl9AheCw5MCxMb2c


这道题的设计思路,取自《孙子兵法·谋攻》


孙子曰:夫用兵之法,全军为上,破军次之。是故百战百胜,非善之善也;不战而屈人之兵,善之善者也。故善用兵者,屈人之兵而非战也,此谋攻之法。知可以战与不可以战者胜,识众寡之用者胜。此知胜之道也。


我们的程序里存储着一个残缺的数学函数 f,还有一个数学函数 g;


破解者输入的数据会用于补全 f;


如果 f 的微分结果 与 g 相匹配,解题成功,这时程序会输出字符串,告知破解者已破解成功。


下面,我们给出正确的积分过程和每个步骤所应用的数学公式:


《恢复辅助项》和《积分步骤》这2个文件详细描述了从 g 推导出 f 的过程。


其中,每个步骤所使用到的数学公式 被记录在了《恢复依据公式》和《积分依据公式》2个文件中。


正确的积分结果 f 记录在《公式》中。


f 经过 base62 编码的结果储存在 《编码后公式》 中。


为了补齐 f 所需的正确输入序列号 记录在 《key》 中。


祝大家破解顺利!


原文链接:

https://bbs.pediy.com/thread-248030.htm



第十一题  伊甸园 解题思路



本题解析由看雪论坛 kkHAIKE 原创。


程序流程


用 IDA 分析程序,流程如下


全局类初始化表部分:


1、以 10000 字节为分割初始化了7段表达式,最后汇成最终表达式 F;

2、初始化三段字符串 enc0(1000) enc1(8000) enc2(8335)。


主函数部分:


1、读入输入 ipt,合成 enc = enc0 + ipt + enc1 + enc2,校验长度 17415;

2、用 Base62[^1x] 解码,得到表达式 f,校验长度 12715;

3、解析 f,得到由 CTreeNode 组成的 tree(PS:后文有类似解析代码);

4、执行了某种运算,再准备硬啃时,经过队友 新手慢慢来 提点,推断出应该是 微分(求导)、化简 过程。

5、将微分结果输出成前缀表达式 f_,与 F 对比;

6、用 StrCheck 校验 enc(PS:不影响解题,可能是为了确保唯一解加的)。



长度分析:


1、enc0 + enc1 + enc2 长度 17335,所以 ipt 长度 17415 - 17335 = 80;

2、enc0 直接解 b62 会报 pad 错误,多余 2 字节,令 dec0 = b62dec(enc0[:-2]),长度 726;

3、根据多余的 2 字节分析,接下来应该是 ',x,' 或 ',pi,';

4、enc1_2 多余第一字节,令 dec2 = b62dec(enc1_2[1:]),长度 11929;

5、根据多余的 1 字节分析,前面是 ',',从内容看也是;

6、所以剩下 12715 - 726 - 11929 = 60,令这一部分为 code,其以 ',x,' 或 ',pi,' 开头,以 ',' 结尾。


[^1x]: Base62:网上没有标准,是一种为了 URL 而存在的 Base64 改进型,替换了 URL 敏感的 '+' '/' 符号,本实现具体为 '+'->'9B' '/'->'9C' '='->'9D' '9'->'9A'



前缀解析


先上解析代码

with open("yidian.exe", "rb") as f:

   f.seek(0x3cc18)

   func = f.read(10000)

   f.seek(0x3f330)

   func += f.read(10000)

   f.seek(0x41A60)

   func += f.read(10000)

   f.seek(0x44188)

   func += f.read(10000)

   f.seek(0x468a8)

   func += f.read(10000)

   f.seek(0x48fc8)

   func += f.read(10000)

   f.seek(0x4b6e0)

   func += f.read(4875)



   f.seek(0x4c9f0)

   enc0 = f.read(1000)

   f.seek(0x4cdf8)

   enc1_2 = f.read(8000) # 组合 enc1 + enc2

   f.seek(0x4ed40)

   enc1_2 += f.read(8335)



class Node:

   def __init__(self, s):

       self.left = self.right = None

       self.val = s

       if s in ["+", "-", "*", "/", "Power_xa", "Power_ax", "Log", "Sin", "Cos"]:

           # 运算符

           self.type = 1

       elif s in ["x", "e", "pi"]:

           # 未知数和常数

           self.type = 2

       else:

           # 立即数

           self.type = 0



   # 运算符求目

   def opernum(self):

       if self.type != 1:

           raise Exception("not oper")

       if self.val in ["Sin", "Cos"]:

           return 1

       return 2



   # 转前缀表达式

   # 最后的结果要去除最尾逗号

   def __str__(self):

       if self.type == 1:

           if self.opernum() > 1:

               s = "{},{}{}".format(self.val, self.left, self.right)

           else:

               s = "{},{}".format(self.val, self.left)

       else:

           s = self.val + ","

       return s



   # 转中间表达式

   def mid(self, n, m):

       # 深度限制

       if n == m:

           return "j"



       if self.type == 1:

           if self.val in ["+", "-", "*", "/"]:

               s = "{} {} {}".format(self.left.mid(n+1, m), self.val, self.right.mid(n+1, m))

           elif self.val in ["Power_xa", "Power_ax"]:

               s = "{} ^ {}".format(self.left.mid(n+1, m), self.right.mid(n+1, m))

           elif self.val == "Log":

               s = "log({}, {})".format(self.left.mid(n+1, m), self.right.mid(n+1, m))

           else:

               s = "{}{}".format(self.val.lower(), self.left.mid(n+1, m))

       else:

           s = self.val



       return "(" + s +")"



pfunc = func



def parseinit(s):

   global pfunc

   pfunc = s



def parse(parent):

   global pfunc

   if pfunc is None:

       return



   idx = pfunc.find(",")

   if idx != -1:

       x = pfunc[:idx]

       pfunc = pfunc[idx + 1:]

   else:

       x = pfunc

       pfunc = None



   n = Node(x)

   if n.type == 1:

       # 若是运算符则递归解析

       parse(n)



   if parent is not None:

       if parent.left is not None:

           if parent.right is not None:

               raise Exception("must die")

           else:

               parent.right = n

       else:

           parent.left = n

           if parent.type == 1 and parent.opernum() > 1:

               # 双目则继续右边

               parse(parent)



   return n



import base64



def b62dec(b):

   b = b.replace("9D", "=").replace("9C", "/").replace("9B", "+").replace("9A", "9")

   return base64.b64decode(b)



def b62enc(b):

   b = base64.b64encode(b)

   return b.replace("9", "9A").replace("+", "9B").replace("/", "9C").replace("=", "9D")



微积分


从流程上看,好像关键就是求这个 微分 的逆转了,好像对 F 求积不就拿到 f 了吗?

 

其实这是作者故意给出的陷阱,不过同时,作者也给出了糖果:


1、仔细分析表达式 f 以及 F,发现第一字节(最外层运算符)均为 ‘/’(除法);

2、令 f = u / v;

3、结合除法的求导公式;
 

4、你会发现其实 f_(也就是 F)中,是包含原 f 组成部分 u v 的;

5、使用代码验证设想并输出原始 u v。

def check_uv():

   tree = parse(None)



   # 先输出至多 3 级表达式

   print tree.mid(0, 3)

   # 输出

   # (((j * j) - (j * j)) / ((j * j) ^ (2)))

   # 满足求导公式



   # 进一步验证满足条件,分子中的 v 与分母中的 v 相等

   assert str(tree.left.left.right) == str(tree.right.left)



   u = tree.left.right.left

   v = tree.right.left

   # 输出 u v

   print str(u)[:-1]

   print str(v)[:-1]


这么一来,微积分到此结束。



化简求繁


从上一章看,好像提取出 u v 就能直接得出 f 了,其实不行,具体就是从原始的 dec2 中搜不到 v

 

那么,定义上章获得的为 u_ v_

 

从 dec0(以原 u 开头) 和 u_ 对比来看,发现 dec0 到 u_ 进行了一种化简(还好 dec0 短,全手动),具体如下:


1、*,Log,x,x, log(x,x) 为 1,所以这一段可以直接搜索全删;

2、剩下的Log,x,x替换为 1;

3、+,g(x),g(x) 化简为 *,g(x),2;

4、*,g(x),g(x) 化简为Power_xa,g(x),2

将得到的 dec0_ 与 u_ 对比,得到 code 的开头处,为 ',pi,' 与之前的推理一致。

 

将 dec2 替换*,Log,x,x,,分析 dec2 与 code 开头处部分(关键字 38,故意调整了对齐)。

 

得到要补充的部分,刚好 60 字节


code = ",pi,75,Log,*,-,Power_ax,23,-,Power_xa,+,Log,Power_ax,90,Log,"

 

使用代码求得 ipt


print b62enc(b62dec(enc0[:-2]) + code + b62dec(enc1_2[1:]))[1000: 1080]


原文链接:

https://bbs.pediy.com/thread-248585.htm








第十二题【移动迷宫】正在火热进行中


第12题/共15题


《 移动迷宫》将于 12月25 日中午 12:00 结束


赶紧参与进来吧~!


热门图书推荐:



合作伙伴 



腾讯安全应急响应中心 

TSRC,腾讯安全的先头兵,肩负腾讯公司安全漏洞、黑客入侵的发现和处理工作。这是个没有硝烟的战场,我们与两万多名安全专家并肩而行,捍卫全球亿万用户的信息、财产安全。一直以来,我们怀揣感恩之心,努力构建开放的TSRC交流平台,回馈安全社区。未来,我们将继续携手安全行业精英,探索互联网安全新方向,建设互联网生态安全,共铸“互联网+”新时代。







- End -


公众号ID:ikanxue

官方微博:看雪安全

商务合作:wsc@kanxue.com

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存