Z3Py在CTF逆向中的运用

前言

Z3是Microsoft Research开发的高性能定理证明器。Z3拥有者非常广泛的应用场景:软件/硬件验证和测试,约束求解,混合系统分析,安全性研究,生物学研究(计算机分析)以及几何问题。Z3Py是使用Python脚本来解决一些实际问题。

CTF逆向中的应用

现在的CTF逆向中,求解方程式或者求解约束条件是非常常见的一种考察方式,而ctf比赛都是限时的,当我们已经逆向出来flag的约束条件时,可能还需要花一定的时间去求解逆过程。而Z3求解器就给我们提供了一个非常便利求解方式,我们只需要定义未知量(x,y等),然后为这些未知量添加约束方式即可求解。Z3求解器能够求解任意多项式,但是要注意的是,当方程的方式为2**x这种次方运算的时候,方程式已经不是多项式的范畴了,Z3便无法求解。

基本使用

现在我们利用官方文档中的一个例子来粗略的看一下Z3Py的使用。

代码非常简单,首先利用Int()定义两个int型未知数x和y,然后利用三个约束条件进行相应的求解:

  1. x > 2
  2. y < 10
  3. x + 2*y == 7

由上述的代码看得出来Z3Py的使用方式比较简单,

  1. 定义未知量
  2. 添加约束条件
  3. 然后求解

CTF中的示例

XXX比赛中的逆向题

首先我们利用IDA去打开该文件,定位到关键点,发现关键函数如下:

可以看得出来这个题目的目的就是找出满足方程的flag。我们可以很方便的把方程式列出来,但是求解对于一些数学不是很好的人来说简直就是噩梦,这时候Z3求解器就可以很方便的给我们帮助。我们按照题目的意思一步一步利用Z3求解器来求解:

Solver()命令创建一个通用求解器。我们可以通过add函数添加约束条件。我们称之为声明约束条件。check()函数解决声明的约束条件,sat结果表示找到某个合适的解,unsat结果表示没有解。这时候我们称约束系统无解。最后,求解器可能无法解决约束系统并返回未知作为结果。

对于上面的题目我们首先定义x1,x2,x3,x4四个int变量,然后添加逆向中的约束条件,最后进行求解。Z3会在找到合适解的时候返回sat。我们认为Z3能够满足这些约束条件并得到解决方案。该解决方案被看做一组解决约束条件的模型。模型能够使求解器中的每个约束条件都成立。最后我们遍历model中的解。

得到x1,x2,x3,x4的解后,我们将其代入逆向题中,得出v1,v2,v7,v8,v9,v9,v10,v11,v12的值,然后进行下一步的求解:

这样的话我们就花了比较少的时间得到我们想要的flag,还是比较方便的。

但是现实中很多的逆向题都是基于位运算的,同样在Z3Py中可以使用Bit_Vectors进行机器运算。它们能够实现无符号和有符号二进制运算。Z3为符号数运算提供了一个特殊的运算符操作版本,其中运算符<,<=,>,> =,/,%和>>对应于有符号运算。 相应的无符号运算符是ULT,ULE,UGT,UGE,UDiv,URem和LShR。我们看一下如下的代码就能清楚许多:

Z3Py同样支持了Python中的创建List的方式,我们看如下代码:

在上面的例子中,表达式“x%s”%i返回一个字符串,其中%s被替换为i的值。命令pp与print类似,但是它使用Z3Py格式化程序而不是Python的格式化程序来使用列表和元组。

第八届极客大挑战的REConvolution

我们打开文件,也是比较直观的看到约束条件,我试着逆向了这个过程,花费了挺多的时间才得到答案,但是如果我们使用Z3Py来求解的话就会非常的快。

函数关键部分如下:

很简洁明了,我们利用Z3Py来进行变量的声明和约束的增加并进行求解

很简单的几行代码,声明0x22个8位BitVec的未知数,获取数据,然后增加约束条件,求解,这样就能够帮助我们获取flag。

题目链接:https://pan.baidu.com/s/1o8QdFIE

总结

虽然CTF逆向比赛中重点考察的是逆向的能力,采用求解器的方式来求解并不能锻炼到自己的逆向逻辑,REConvolution逆向题目有一个非常清晰明了的逆过程,还是很有趣的。

* 本文作者:foyjog,转载请注明来自FreeBuf.COM

原文发布于微信公众号 - FreeBuf(freebuf)

原文发表时间:2018-05-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吉浦迅科技

DAY34:阅读算术指令

18130
来自专栏技术翻译

Python中的NLP

自然语言处理(NLP)是数据科学中最有趣的子领域之一,数据科学家越来越期望能够制定涉及利用非结构化文本数据的解决方案。尽管如此,许多应用数据科学家(来自STEM...

39450
来自专栏程序员叨叨叨

7.2 uniform

Cg 语言将输入数据流分为两类(参见文献[3]Program inputs and Outputs ):

8440
来自专栏coolblog.xyz技术专栏

科普:String hashCode 方法为什么选择数字31作为乘子

某天,我在写代码的时候,无意中点开了 String hashCode 方法。然后大致看了一下 hashCode 的实现,发现并不是很复杂。但是我从源码中发现了一...

703190
来自专栏marsggbo

论文笔记模板

作者给了哪些strong conclusion, 又给了哪些weak conclusion?

10110
来自专栏蜉蝣禅修之道

网络流算法Push-relabel的Python实现

38250
来自专栏生信宝典

R语言学习 - 箱线图(小提琴图、抖动图、区域散点图)

箱线图 箱线图是能同时反映数据统计量和整体分布,又很漂亮的展示图。在2014年的Nature Method上有2篇Correspondence论述了使用箱线图的...

1K100
来自专栏量子位

PyTorch 0.2发布:更多NumPy特性,高阶梯度、分布式训练等

李林 编译整理 量子位 报道 | 公众号 QbitAI Facebook的机器学习框架(之一)PyTorch今天发布了新版本:0.2.0。 这一版本引入了Num...

381150
来自专栏祝威廉

从DataFrame自动化特征抽取的尝试

虽然提供了很多Estimator/Transformer, 正如这篇文章所显示的,如何基于SDL+TensorFlow/SK-Learn开发NLP程序,处理的代...

8830
来自专栏林欣哲

人工智能的无信息搜索

在人工智能中,当你面对一些问题不知道怎么解决的时候,有一类常用的解决问题的方法,叫做搜索。就好像你在一片迷雾的森林里,不知道怎么办时,走一步算一步,走起来再说。...

38050

扫码关注云+社区

领取腾讯云代金券