看雪CTF.TSRC 2018 团队赛 第十一题『伊甸园』 解题思路
第十一题《伊甸园》在今天（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