MIPS PWN 入门

MIPS是一种采取精简指令集(RISC)的指令集架构,突出特点是高性能,广泛被使用在许多电子产品、网络设备、个人娱乐设备与商业设备上,在路由器领域也被广泛应用。虽然今年MIPS所属公司已经宣布放弃对该架构继续进行研发设计,但是其作为x86、arm之后的第三大CPU架构阵营,现在市面上仍有大量的MIPS架构的产品,尤其是路由器芯片。此外,MIPS在学术界也非常受到追捧,很多超算竞赛冠军的设计方案都是MIPS的。就目前来看,MIPS的安全研究还是相对较为有意义的。

MIPS架构基础知识

常用汇编与流水线操作 在MIPS PWN中所常用到的汇编指令如下表所示:

image.png

MIPS架构为精简指令集, 常见的MIPS芯片流水线操作为五级, 如下图

wiki-Fivestagespipeline.png

其中IF =指令提取,ID =指令解码,EX =执行,MEM =存储器访问,WB =寄存器写回. 垂直轴是连续的指令: 横轴是时间. 在图示的情况中,最早的指令处于WB阶段,而最新的指令正在进行指令提取. 对于跳转/分支指令, 当其到达执行阶段且新的程序计数器已经产生时, 紧随其后的下一条指令实际上已经开始执行了. MIPS 规定分支之后的指令总是在分支目标指令之前执行,紧随分支指令之后的位置称为 分支延迟槽. 在没有任何可用操作时,延迟槽将填充空指令(nop)占位. 例如下面这段MIPS汇编代码中,
“`move $a0, $s1“`会在“`jalr“`跳转前执行

.text:0007F944                 move    $t9, $s0
.text:0007F948                 jalr    $t9              
.text:0007F94C                 move    $a0, $s1

这个特性在我们查找gadgets和构造payload的时候要多注意, 这也是MIPS上的PWN相比x86架构来说较为特殊的点之一.

寄存器与调用约定 常用的MIPS寄存器作用如下:

  • “`\$a0“` – “`\$a3“`:函数调用时的参数传递,若参数超过 4 个,则多余的使用堆栈传递
  • “`\$t0“`-“`\$t7“`:临时寄存器
  • “`\$s0“` – “`\$s7“`:保存寄存器,使用时需将用到的寄存器保存到堆栈
  • “`\$gp“`:全局指针,用于取数据(32K访问内);“`\$sp“`:栈指针,指向栈顶
  • “`\$fp“`:栈帧指针;“`\$ra“`:存储返回地址

MIPS的调用约定为被调用者实现堆栈平衡, 参数 1 ~ 4 分别保存在
“`\$a0“` ~ “`\$a3“` 寄存器中,剩下的参数从右往左依次入栈. MIPS的栈布局如下图所示, 某寄存器在堆栈中的位置不是确定的, 例如“`\$ra“`在某函数栈中的偏移是“`\$sp“`+N, 而在另一函数栈中的偏移是“`\$sp“`+M.

image.png

当CPU执行跳转到被调用函数后, 被调用函数将会开辟新的栈帧, 根据本函数内是否还有其他函数调用决定是否将
“`\$ra“` 入栈, 再将“`\$sp“` 入栈. 对于“`\$ra“`, 当本函数为叶子函数(函数内无其他函数调用), 则“`\$ra“`不入栈, 否则将“`\$ra“`入栈. 对于栈溢出攻击而言, 当函数为非叶子函数时, 可以直接通过覆盖栈上的“`\$ra“`来劫持控制流.

缓存非一致性
继续阅读“MIPS PWN 入门”

任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B

前言

难以置信, 遇到这个问题竟然是因为做一道CTF Reverse的题, 实际上我以前打ACM的时候都没有写过任意模数的K次剩余这种东西. 最简单的模质数的K次剩余的例题是
“`HDU 3930 Broot“`, 进阶版本(模任意奇数的K次剩余)的例题是“`BZOJ 2219 数论之神“`, 而终极版本(任意模数的K次剩余)似乎可以交的题只有“`51nod 1123“`, 截至本文写作时只有44个AC. 然而这个CTF题本身就有50多个通过了. ~~CTF>ACM 实锤~~ (暴论)

其实是因为这个Reverse的题里面幂指数是质数,所以会跟模数互质,然后就可以用RSA的方法来做了. 其次该题目更多的工作在于去花指令混淆上, 而非算法破解.

OK那么就来看一下这个问题从最简单的版本到终极版本怎么求解吧…

模质数的K次剩余

已知$a$, $b$, $p$, 求使得

$$
x^{a} \equiv b \quad(\bmod \ p)
$$

成立的所有 $x$. 其中 $p$ 是质数.

由于 $p$ 是质数, 所以 $p$ 存在原根 $g$ , 此时对于模 $p$ 意义下的任意数 $w$ ($0\le w \le p-1$) 存在唯一的 $i$ ($0\le i \le p-1$) 使得 $w\equiv g^i\quad(\bmod \ p)$.

由此可以将最终的答案用 $g$ 来表示: $x=g^{c}$, 带入上式转化为求解

$$
(g^{c})^{a}\equiv (g^{a})^c\equiv b \quad(\bmod \ p)
$$

此时 $g$, $a$, $b$, $p$, 已知, 只需要解出来 $c$. 此时相当于求解离散对数, 使用 Baby-Step-Giant-Step 可以在 $\mathcal{O}(\sqrt{p})$ 时间内得到一个特解 $x_0 \equiv g^{c} \quad(\bmod \ p)$.

在已知一个特解的情况下求出所有解是简单的, 由原根的性质可知 $g^{\varphi(p)}\equiv 1 \quad(\bmod \ p)$, 因此:

$$
\forall t \in \mathbb{Z}, x^{a} \equiv g^{c \cdot a+t \cdot \varphi(p)} \equiv b \quad(\bmod \ p)
$$

因此所有的解为:

$$
\forall t \in \mathbb{Z}, a \mid t \cdot \varphi(p), x \equiv g^{c+\frac{t \cdot \varphi(p)}{a}} \quad(\bmod p)
$$

上面幂次部分要能整除必须要有$\frac{a}{\operatorname{gcd}(a, \varphi(p))} \mid t$, 可以设 $t=\frac{a}{\operatorname{gcd}(a, \varphi(p))} \cdot i$, 于是得到所有的解为:

$$
\forall i \in \mathbb{Z}, x \equiv g^{c+\frac{\varphi(p)}{\operatorname{gcd}(a, \varphi(p))} \cdot i} \quad(\bmod p)
$$

HDU 3930 Broot 代码:

继续阅读“任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B”

Codeforces Round #700 (Div. 2) 题解

链接 https://codeforces.com/contest/1480

闲着没事翻了翻以前的博客,感觉自己之前的文章质量太低了,尤其是很多题解东一篇西一篇的非常乱,以后类似题解之类的就整套整套地写好了。

image.png

Round 700 Div.2给人的感觉是手速场,基本上没有什么很需要思考的点。
继续阅读“Codeforces Round #700 (Div. 2) 题解”

逆向分析某X视频APP通信协议

声明:破解他人的软件是违法行为,本文的逆向工程仅供学习研究用途。

最近朋友间流行一个国产的X视频App,其特点是使用国内网络便可以自由地观看视频。但是支持国内网络环境的在线服务往往会承担被审查的风险,因此有点好奇他的视频存储和获取是怎么实现的,于是便对其APP客户端进行了逆向分析。本文出发点仅仅是技术学习,因此所有与该App有关的信息都将打码。在下文中将称该App为JK,其对应的几个关键api接口部分字符使用x替换。

  • 目标平台:Android
  • 分析对象:JK.apk,Version=3.13.2
  • 分析工具:Charles,Jadx,IDA Pro,Frida

TL;DR 最终对JK App的视频请求协议逆向分析结果如下图所示:


APP视频获取协议逆向结果

继续阅读“逆向分析某X视频APP通信协议”

[差分][前缀和][细节] codeforces 1452E Two Editorials

codeforces 1452E Two Editorials

题目链接:https://codeforces.com/problemset/problem/1452/E

题意:一次比赛中 2 个dalao来讲题,总共有 $m$ 个选手来听讲,题目总数为 $n$ ,编号从 $1$ 开始到 $n$ 。每个dalao都只会选择连续的 $k$ 个题目进行讲解,两个人可以交叉。而每一个听讲的人都只会选择听一个dalao的讲题,这是由哪个dalao讲的题目中覆盖的他感兴趣的题目数量较多决定的,第 $i$ 个人想听的题目范围是 $[l_i,r_i]$ . 问两个大佬怎么选可以使得两个人所获得的得分加一块最多,其中得分是他们讲的每个题目收听的人数。

数据范围:$1 \leq n, m \leq 2000,1 \leq k \leq n$, $1 \leq l_{i} \leq r_{i} \leq n$

输出:两个人采取某种讲题方案后加一块能获得的最大分数

题解:

把每个听讲的人看成一条线段,问题可以抽象成在数轴上找到两个长度为k的区间使得上述分数最大。从数据范围来看,可以 $O(n^2)$ 枚举两个人讲题的起点,之后如果能使用滑动窗口动态维护, $O(1)$ 更新答案这题就做完了。那么自然可以想到枚举第一个人讲题的范围之后,第二个人的范围在遍历的过程中动态维护。如果我们使用前缀和来做的话,是可以 O1 得到两个人各自的和的,但是题目要求两个人之间如果有均覆盖到的听讲者,那么只有覆盖的较多的讲题人才有得分。这是一个对每个听众来说取max的操作,但是我们要在数轴的维度来说要做到 O1 动态维护就是比较难的。我们假设第一个人对于自己内部的的得分和为sum1.第二个人的得分为sum2.先不考虑取max的情况,此时sum1和sum2都可以通过简单的积分前缀和得到。我们考虑把这个max操作转化成几个不同数组的差分和求和操作。简单的画一下第二个样例,就可以意识到当枚举到第一个人的讲课区间 [i,iend] 的时候,听众对应的线段可以分为三类:(1)在iend之前结束的;(2)在iend之后开始的;(3)在iend之前开始,在iend之后结束的。
继续阅读“[差分][前缀和][细节] codeforces 1452E Two Editorials”

[娱乐][代理][CF] 使用cloudflare worker反向代理codeforces,支持登录和提交代码评测

作为一个退役的ACM选 (蒟)手(蒻),偶尔也会回codeforces上做做题娱乐娱乐。。

但是codeforces作为一个外国网站,在国内访问的话速度十分感人,你懂的。

虽然绝大多数 业内人士 都有不可描述的方法让自己访问到国外的网站,但是还是有一些刚接触比赛的同学需要一个比较快的访问途径。当然国内之前也有一些dalao自制的codeforces镜像,例如 https://codeforc.es/ 等。

我这里提供一种免费自行搭建codeforces反向代理的方法,借用了cloudflare免费提供的serveless服务:workers。关于workers的简单介绍可以参见官方的blog:

Cloudflare Workers的名称来自Web Workers,更具体地说是Service Workers,一个用于在web浏览器后台运行并拦截HTTP请求的脚本的W3C标准API。Cloudflare Workers是针对相同的标准API编写的,但是是在Cloudflare的服务器上运行,而不是在浏览器中运行。
以下是您可以使用的工具:
– 使用最新的标准语言功能执行任意JavaScript代码。
– 拦截和修改HTTP请求和响应URL,状态,标头和正文内容。
– 直接从您的Worker响应请求,或将其转发到其他地方。
– 将HTTP请求发送到第三方服务器。
– 以串行或并行方式发送多个请求,并使用响应组成对原始请求的最终响应。
– 在响应已经返回到客户端之后发送异步请求(例如,用于记录或分析)。
– 控制其他Cloudflare功能,例如缓存行为。
– 显然我们要达到反向代理的目的只需要处理两件事:
– 处理客户端的请求,修改参数之后发送给真正的服务端(codeforces.com)
– 处理codeforces.com返回的响应,修改参数后发给客户端
继续阅读“[娱乐][代理][CF] 使用cloudflare worker反向代理codeforces,支持登录和提交代码评测”

[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意:给定一个长度1e5的数组$a$, $1 \le a_i \le 10^6$ ,满足 $a_i$的因子数量不超过7. 求 $a$ 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样,丢掉了很多东西,sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”

MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1

MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1

本文同步发布于本人知乎文章https://zhuanlan.zhihu.com/p/258405554

1. Introduction

MIT 6.858 是麻省理工学院一门著名的计算机安全系列课程。跟其相类似的其他名校的安全类课程还有Standford CS155OSU 系统安全与软件安全等。虽然是比较硬核的大学课程,其实验环境对于现实生活中的安全攻防来说也还是相对较为理想的。不过对于想尽快地熟悉基础的系统安全攻防知识的新手来说,这些实验的容量已经足够了。整个课程有4次实验和一个最终的Final Project,其中所有的实验都围绕一个由课程教师构建的一个名为zoobar的web application来展开。四次实验的主要内容是:

  • Lab 1: you will explore the zoobar web application, and use buffer overflow attacks to break its security properties.
  • Lab 2: you will improve the zoobar web application by using privilege separation, so that if one component is compromised, the adversary doesn’t get control over the whole web application.
  • Lab 3: you will build a program analysis tool based on symbolic execution to find bugs in Python code such as the zoobar web application.
  • Lab 4: you will improve the zoobar application against browser attacks.

即分别围绕缓存区溢出攻击、权限分离、符号执行和浏览器攻击四个主题来展开。我将在blog里陆续更新之后的内容。这一次我们先来看第一次实验,Buffer Oveflows
继续阅读“MIT 6.858: Computer Systems Security 计算机系统安全 #Lab1”

麻省理工学院(MIT)研究生学习指导–怎样做研究生 [转载]

麻省理工学院(MIT)研究生学习指导
怎样做研究生
本文的主旨是解释如何做研究。我们提供的这些建议,对于研究本身(阅读、写作和程序设计)、理解研究过程以及开始研究(方法论、选题、选导师和情感因素),都是极具价值的。

  1. 简介

这是什么?
并没有什么神丹妙药可以保证在研究中取得成功,本文只是列举了一些可能会对研究有所帮助的非正式意见。

目标读者是谁?
本文主要是为新入学的研究生而写。

如何使用?
要精读完本文,太长了一些,最好是采用浏览的方式。很多人觉得下面的方法很有效:先快速通读一遍,然后选取其中与自己当前研究项目有关的部分仔细研究。
本文被粗略地分为两部分。第一部分涉及研究者所需具备的各种技能:如阅读,写作和程序设计等等。第二部分讨论研究过程本身:即研究究竟是怎么回事,如何做研究,如何选题和选导师,如何考虑研究中的情感因素。很多读者反映,从长远看,第二部分比第一部分更有价值,也更让人感兴趣。

本文的主要内容包括: 继续阅读“麻省理工学院(MIT)研究生学习指导–怎样做研究生 [转载]”

图片转latex/word代码在线工具,mathpix的在线替代,完全免费,避免重复劳动

使用示例

使用方法

用截图工具(QQ 微信等的截图或者Windows自带的截图)截图或将图片复制到剪切板后在本页面按Ctrl+V粘贴即可在文本框内获取latex代码。注意Word的代码复制出来之后再Word里粘贴要用 右键-> 粘贴 -> 仅粘贴文本 的方式

地址: https://mathcode.herokuapp.com/ 建议加入书签。由于是部署在heroku美国上(买不起服务器和域名)所以国内直连会比较卡。

新地址:https://mathf.itewqq.cn/ 建议加入书签。为了方便国内连接我迁移到了自己的国内学生机上。网页打开速度变快了,但是腾讯云的学生机总带宽只有1M所以人多的时候用可能还是会卡(贫穷.jpg)

继续阅读“图片转latex/word代码在线工具,mathpix的在线替代,完全免费,避免重复劳动”