ranwen's blog

随便写写

USTC Hackergame 2021 划水记

其实这段时间非常忙。本来第一天打完后已经不准备碰了。后来周三突然想到了某个题解法,过了后感觉进个前10不会特别费劲,于是又爆肝20小时左右,最终拿了个第6。

0x00 签到

随便点一点,发现url里头就是时间戳。懒得查对应时间具体数值了,于是人肉倍增一下,只要把url里头参数改成1635000000即可。

0x01 进制十六——参上

当然是直接对左边截图进行OCR,之后复制到赛博厨子(https://gchq.github.io/CyberChef/)拿到flag。

0x02 去吧!追寻自由的电波

稍微看一下,只需要对音频进行慢放即可。然而现在大量播放器和音频处理软件都会在调整速度时一并处理频率。因此找到是直接暴力伸缩波形的软件花了一段时间。做完慢放后,网上搜一下字母表做一做英语听力即可。

0x03 猫咪问答 Pro Max

第一题:当然是选择从 web.archive.org 找。比较好找,注意一下时间别写错了。

第二题:社团主页有。没看到5年内,直接数了数个数,是5个,正好碰上了。

第三题:稍微看一下,发现活动室是搬过的。那猜测搬活动室的时候肯定有个新闻稿,这个新闻稿最有可能出现这题的答案。于是在社团官网上搜索"活动室",找到了照片。

第四题:google到原论文,翻到最后一页数框框,是13个。

第五条:RFC8962,稍微浏览一下得到答案 /dev/null。

0x04 卖瓜

不知道后端到底怎么处理的,只能瞎试。当然这个瞎试不能在前端试,还是要自己造请求的。试了试后发现输入5e18可以搞出一个负数,之后加上1148914691236517205*6可以搞到-2。那么只需要再搞一个-2,最后计算4*6-6即可。

0x05 透明的文件

浏览一下,有经验的人一眼就能看出这是带VT100控制符的文件。当然少了ESC。补上\033后写一个cpp输出这个字符串即可。不过搞出来的可能看起来不是很清楚。我们对原文的空格做一个字符替换就能输出清晰的(彩色)flag了。

0x06 旅行照片

既然已经说了左边那个是KFC,这个KFC看起来就不正常。直接搜索"海边 KFC",直接就能搜出来这个(没想到还算个地标)。之后就是简单的看地图和照片猜信息时间了。

看地图知道方向是东南。看大楼阴影知道时间是傍晚。搜索一下这个分店就能拿到电话0335-7168800。随便找个街景就可以看到左边是海豚馆。最后楼层高度我们暴力一下就行,这个显然是十几层,答案是14。

不过得注意一下左边那个KFC其实是右边KFC店的甜品站,以及时间比较老的街景没有这个甜品站,如果没意识到这个可能会被坑。

0x07 FLAG 助力大红包

点开题目观察一下,需要一堆不同/8的ip请求这题得到后端。那显然是经典伪造ip题,使用xff(X-Forwarded-For)头伪造即可,注意一下ip还在请求参数中出现了一次。

不过需要观察一下后端限频策略,没记错的话做10个歇1s就可以。

以及这个助力我本地前端直接点会失败,因为我校是多出口的,到题目后端是教育网出口,到前端检测ip的js是联通出口。

0x08 Amnesia

第一问还是比较简单的,清除data和rodata,只需要程序内不存常量即可。把常量字符串都放到栈内一个一个处理。

#include<stdio.h>
char s[1000];
int main()
{
    s[0]='H';
    s[1]='e';
    s[2]='l';
    s[3]='l';
    s[4]='o';
    s[5]=',';
    s[6]=' ';
    s[7]='w';
    s[8]='o';
    s[9]='r';
    s[10]='l';
    s[11]='d';
    s[12]='!';
    s[13]=0;
    printf(s);
    return 0;
}

第二问清除了.text,看起来什么可执行代码都不剩了。实际上不然。稍微了解一下ELF文件,发现里面有一个.preinit的section可以放可执行代码,并且在加载ELF后就会立刻执行。因此考虑在这上面放输出的代码,并且在执行完后直接调用exit(0)。

https://stackoverflow.com/questions/32700494/executing-init-and-fini 有一个回答讲了怎么利用.preinit_array提前执行某个函数。但是光这么做还有个问题,这个函数本身也是放在.text段的。不过我们还可以利用gcc提供的特性把它放到一个自定义名字的段内。

但是还有一个问题。因为程序会开PIE,因此这个函数开头会调用一个由gcc生成的存在.text的函数。观察一下汇编发现这个函数不是必须的,因此我们可以直接手写这个函数的所有汇编代码来避免gcc调用那个在.text的函数。

本来我想直接把汇编存到数组,但是发现存的位置被标记了NX,于是作罢。

以及注意一下32位函数传参要通过栈进行。

#include<stdio.h>
#include<stdlib.h>

char ss[15]="Hello, world!";

static void testf(int argc, char **argv, char **envp) __attribute__ ((section (".lol")));

static void testf(int argc, char **argv, char **envp) {
    asm("pushl    $ss\n\r");
    asm("movl    $ss, %edi\n\r");
    asm("call    puts\n\r");
    asm("pushl    $0\n\r");
    asm("movl    $0, %edi\n\r");
    asm("call exit\n\r");
}

__attribute__((section(".preinit_array"), used)) static typeof(preinit) *preinit_p = testf;

int main(void) {
    return 0;
}

0x09 图之上的信息

搜索 "GraphQL ctf",找到了一篇知乎文章(https://zhuanlan.zhihu.com/p/390876937),里头有详细的介绍。直接复制里头的payload即可得到数据库结构。最后再查询一下user表的privateEmail字段即可。

0x0A Easy RSA

显然这题需要我们分别求出p和q。

对于p,有知道威尔逊定理的人一下就能看出。我们直接算一个(x1)!modx(x-1)!\bmod x,之后用逆元逐项推出y!modxy!\bmod x即可得到p。

对于q,显然value是一堆相邻的质数,因此我们可以利用其最后一项推出value的每一项,之后就能求出q。

import math
import sympy
from Crypto.Util.number import *
import gmpy2

e = 65537


def get_p():
    x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
    y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
    #value_p = sympy.nextprime((math.factorial(y)) % x)  # Hint:这里直接计算会溢出,请你仔细观察 x 和 y 的特征
    gg=x-1
    for i in range(y+1,x):
        gg=gg*gmpy2.invert(i,x)%x
    value_p = sympy.nextprime(gg)
    return value_p


def get_q():
    value = [getPrime(256)]
    for i in range(1, 10):
        value.append(sympy.nextprime(value[i - 1]))
    print("value[-1] = ", value[-1])
    # value[-1] = 80096058210213458444437404275177554701604739094679033012396452382975889905967

    ndv=80096058210213458444437404275177554701604739094679033012396452382975889905967
    stv=sympy.nextprime(80096058210213458444437404275177554701604739094679033012396452382975889905967-10000)
    value=[stv]
    while value[-1]!=ndv:
        value.append(sympy.nextprime(value[-1]))
    value=value[-10:]
    print(len(value))

    n = 1
    phi=1
    for i in range(10):
        n = n * value[i]
        phi=phi*(value[i]-1)
    q = getPrime(512)
    value_q = pow(q, e, n)
    d=gmpy2.invert(e,phi)
    print("value_q = ", value_q)
    # value_q = 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
    pvq= 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
    q=pow(pvq,d,n)
    return sympy.nextprime(q)

# this destroyes the rsa cryptosystem
p = get_p()
q = get_q()

print(p)
print(q)

c=110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478
phi=(p-1)*(q-1)
d=gmpy2.invert(e,phi)
m=pow(c,d,p*q)
print(long_to_bytes(m))

0x0B 加密的 U 盘

稍微搜索一下,发现luks改密码几乎时瞬间的。想都不用想肯定是硬盘里存了个master key。用户输入的password只是给这个master key加密的密钥,硬盘文件加密用的是master key。因此稍微搜索一下,找到这两篇文章。

https://ce-automne.github.io/2019/03/12/BSidesSF-CTF-2019-GoodLuks-WriteUp/

https://unix.stackexchange.com/questions/119803/how-to-decrypt-luks-with-the-known-master-key

用第一个镜像dump出master key后,用这两篇文章的做法解密第二个镜像即可。

这才意识到对于这种全盘镜像题,按偏移量挂载是个好方法(雾)。

0x0C 赛博厨房

只做了前两问。搞清楚题目规则比较烦。

第一问就是熟悉一下规则。提前写好一个程序完成这个任务即可。

第二问数了一下需要0的个数,以及最长指令数,发现必须要写一个循环。借助空地也能放物品的特性,可以用一个空地作为循环变量的存储位置。之后就写一个循环好了。

0x0D 灯,等灯等灯

第一问很简单,我们把所有约束都列出来,发现就是要求我们解一个有12*12个变量的线性同余方程组。

把这个约束表示成矩阵形式,之后转换一下,喂给SageMath,发现解不出来!!!(可能是因为那个是列出所有解的原因)

之后转换一下,喂给Mathematica,发现还是解不出来!!!即使我用的是那个,求特解的函数。

只能亲自写高斯消元了。先在网上搜了好多个,结果发现都写的非常臭,于是改了大部分代码。

以及又踩到了numpy的一个坑。如果要交换数组的两行,如果写 a[i,:],a[j,:]=a[j,:],a[i,:]会gg,必须写a[[i,j],:]=a[[j,i],:],调了我半个多小时才发现是交换出了问题。

mats=[[189, 189, 189, 189, 189, 33, 33, 33, 189, 189, 189, 189], [189, 189, 189, 33, 33, 33, 189, 33, 44, 189, 189, 189], [189, 189, 189, 189, 189, 33, 33, 33, 33, 189, 189, 189], [189, 189, 189, 189, 189, 33, 189, 33, 33, 189, 189, 189], [189, 189, 189, 33, 33, 189, 189, 33, 33, 33, 189, 189], [189, 134, 33, 33, 189, 189, 189, 189, 33, 33, 189, 189], [189, 144, 33, 33, 189, 189, 189, 189, 33, 189, 189, 189], [189, 142, 33, 33, 189, 189, 189, 189, 33, 33, 33, 189], [189, 100, 142, 33, 189, 189, 189, 189, 33, 33, 33, 189], [189, 142, 142, 189, 189, 189, 189, 189, 189, 33, 189, 189], [189, 59, 142, 33, 189, 189, 189, 189, 33, 189, 189, 189], [189, 189, 33, 33, 189, 189, 189, 189, 189, 189, 189, 189]]
SIZE=12

yx={(0,0):3,(1,0):2,(-1,0):2,(0,1):2,(0,-1):2,(2,0):1,(-2,0):1,(0,2):1,(0,-2):1}

from os import DirEntry
import numpy as np
import gmpy2
import urllib.parse as urlp
import json

np.set_printoptions(threshold=114514)

mat_a=np.zeros((SIZE*SIZE,SIZE*SIZE),dtype=np.uint8)
mat_b=np.zeros((SIZE*SIZE,),dtype=np.uint8)

banlist=[(2,2),(2,4),(3,2)]

for i in range(SIZE):
    for j in range(SIZE):
        if (i,j) in banlist:
            continue
        mat_b[i*SIZE+j]=mats[i][j]
        for fx,fd in yx.items():
            nxx=i+fx[0]
            nyy=j+fx[1]
            if nxx>=0 and nxx<SIZE and nyy>=0 and nyy<SIZE:
                mat_a[nxx*SIZE+nyy,i*SIZE+j]=fd

omat_a=np.array(mat_a)
omat_b=np.array(mat_b)

pers=[i for i in range(SIZE*SIZE)]

def SequentialGauss(mat_a):
    for i in range(0, (mat_a.shape[0])-1):
        if mat_a[i, i]%2 == 0:
            for j in range(i+1, mat_a.shape[0]):
                if mat_a[j, i]%2 != 0:
                    mat_a[[i,j],:] = mat_a[[j,i],:]
                    break
        if mat_a[i, i]%2 == 0:
            flag=False
            for j in range(i+1, mat_a.shape[0]):
                for k in range(i+1, mat_a.shape[0]):
                    if mat_a[k, j]%2 != 0:
                        mat_a[:,[i,j]] = mat_a[:,[j,i]]
                        pers[i], pers[j] = pers[j], pers[i]
                        mat_a[[i,k],:] = mat_a[[k,i],:]
                        flag=True
                        break
                if flag:
                    break
        if mat_a[i, i]%2 == 0:
            print("REV",i)
            break
        for j in range(i+1, mat_a.shape[0]):
            mat_a[j:j+1 , :] = mat_a[j:j+1,:] - (mat_a[j,i]*gmpy2.invert(int(mat_a[i,i]),256))*mat_a[i, :]
    return mat_a

def rdiv(a,b):
    if b==0:
        if a==0:
            return 0
        else:
            print("ERR")
            return 0
    return a*gmpy2.invert(int(b),256)%256
 
def revert(new_mat):
    x = np.zeros(new_mat.shape[0], dtype=np.uint8)
    number = x.shape[0]-1
    # print(number)
    b = number+1
    x[number] = rdiv(new_mat[number,b],new_mat[number, number])
    for i in range(number-1,-1,-1):
        x[i] = rdiv((new_mat[i,b]-np.sum(np.multiply(new_mat[i,i+1:b],x[i+1:b]))),(new_mat[i,i]))
    return x
mat_b=np.array([mat_b])
new_mat = SequentialGauss(np.hstack((mat_a, mat_b.T)))
print(new_mat)
retv=revert(new_mat)

nmt1=new_mat[:,:SIZE*SIZE]
nmt2=new_mat[:,SIZE*SIZE:].T
print([email protected]==nmt2)
nresv=np.zeros((SIZE*SIZE,),dtype=np.uint8)
for i in range(SIZE*SIZE):
    nresv[pers[i]]=retv[i]

[email protected]
print(okv==omat_b)

pomatb=omat_b.astype(np.int16)
pokv=okv.astype(np.int16)
print(np.sum(np.abs(pomatb-pokv)))

print(okv)
print(omat_b)

pmatr=[]
for i in range(SIZE):
    pmatr.append([])
    for j in range(SIZE):
        pmatr[i].append(int(nresv[i*SIZE+j]))
    print(pmatr[i])


pmatr=json.dumps(pmatr)

print(urlp.quote(pmatr))

关于第二问和第三问,我看到题后就想到了格密码中SVP问题。奈何我开这题第一问的时候都以及凌晨三点多了,以及我对格密码也没有那么熟悉,于是作罢,最终只写了第一问。

以及为什么前端要用canvas,我为了拿到矩阵的数字还专门写了个py处理截图。

import numpy as np
from PIL import Image

SIZE=12

img=Image.open('m.png')

img=np.array(img)
x=img.shape[0]
BS=x//SIZE

o=[]

for i in range(SIZE):
    o.append([])
    for j in range(SIZE):
        pcol=img[i*BS+BS//2,j*BS+BS//2]
        gpcol=pcol[0]
        assert gpcol==pcol[1]==pcol[2]
        o[i].append(gpcol)

print(o)

0x0E Micro World

拿到可执行文件,扔到IDA里头看strings。发现了一堆Py开头的东西。仔细看一下,里头居然还有个Pyinstaller。因此直接搜索Pyinstaller解包器。搜到了一个github上的repo(https://github.com/countercept/python-exe-unpacker)。照着使用教程解了个包,得到了主程序的pyc。注意一下对于主程序我们需要手动添加pyc后缀名和pyc文件头,网上的一些使用说明应该有写。

之后就是反编译pyc。使用uncompyle6即可。但是这个反编译出来的有坑。有些分支的缩进是有问题的。通过分析逻辑和运行调试可以完全还原代码。

之后阅读一下题目,要还原某个时间点的结果,只需要把速度向量取个反即可。降低一下运行tps即可即时截图到flag图片。

# uncompyle6 version 3.7.4
# Python bytecode 3.8 (3413)
# Decompiled from: Python 3.8.10 (default, Sep 28 2021, 16:10:42) 
# [GCC 9.3.0]
# Embedded file name: 2.py
# Compiled at: 1995-09-28 00:18:56
# Size of source mod 2**32: 272 bytes
import time, pygame, random, math
WIDTH = 800
HEIGHT = 480
FPS = 3
RADIUS = 6
WHITE = (255, 255, 255)
BLACK = (0, 0, 0)
RED = (255, 0, 0)
GREEN = (0, 255, 0)
BLUE = (0, 0, 255)
pygame.init()
pygame.mixer.init()
screen = pygame.display.set_mode((WIDTH, HEIGHT))
pygame.display.set_caption('Micro world')
clock = pygame.time.Clock()
running = True
count = 0
list_ = [
 (104.57999766036382, 294.30576115498934, 0.1577677901040423, 0.41776948474620357), (97.87091160071468, 284.0771467313936, -0.05370797410649919, -1.5117973702589511), (394.1386262922653, 342.409197651039, 1.257922260374631, -0.6461638773589035), (383.764164219779, 351.02042667556873, 0.20006041825672996, 0.6886413335669115),
 (180.44019240845162, 133.7535956479616, -1.2484762435639396, -0.24929662016190135), (184.78982911642964, 145.40211792122318, -0.0022636999589985274, 0.5513600856872762), (115.03335937165885, 300.9993063319222, -0.5676054221924623, -0.6695938101055833), (428.3301722808014, 85.83680504269783, -0.0513590947698387, 0.2619177140188991), (421.5916683285764, 72.17809124687787, 0.2014421765254144, -1.4100046681437837), (162.58901945971377, 126.99241616764206, 0.030293407742100736, -0.8004786559033131), (160.9895035322225, 145.70895141366148, 0.34929641702611086, 1.0244323100199488), (99.54962866775641, 349.46917135540673, 0.8725254958889044, 0.18026779894381553), (113.4935960089335, 350.07171367926867, 1.3948726673436584, -0.054645034381742424), (243.53937023444496, 324.4815163708293, 0.7754113027163299, -0.35104389069767705), (236.07107039080046, 336.93661006373446, 0.48878994205902065, 0.3668410462786823), (142.25100857351947, 107.18317281548164, 0.8769918696942771, 0.3381787797086514), (126.65532126550701, 101.44841747837386, -0.23643662821636835, -0.7474233162903591), (93.89796091125481, 337.69531331910224, 1.0011924240124088, 0.3786722871573705), (80.48068970171919, 325.1970583485235, -0.7399280117105376, -0.1701776000030069), (562.4548633698985, 293.8157173337281, 0.9232890949122534, -0.6707164772798287), (544.2230504332125, 298.5096170399827, -0.45781767619323493, 0.20143165105280758), (591.0728484545633, 384.0271820277358, -0.3546100658269741, -0.11818203300203947), (587.8300731972232, 397.21466538385005, 0.1658293862635661, 0.42343564083856233), (160.96290809954047, 113.1243147430774, 0.3297720052539864, -0.9088842057483848), (341.609111706211, 174.90102865131772, -0.6451128281395191, 0.6625764312805231), (361.89732768708996, 171.7398998209568, 0.9626383465113062, -0.45377732846689295), (413.2372099784884, 109.2059457838029, 0.06068110806079574, 0.7460129288950222), (428.03790114833487, 103.0981885607253, 0.7102816563423606, 0.5965135218875973), (632.823035103914, 183.41308729879773, 0.9426699419434019, -0.17948947163331008), (619.693443152725, 171.6281942118759, -0.4050225991049363, -0.3004630650084027), (234.93804029190275, 314.4850986917503, 0.6079647151190387, -0.3527147434952942), (388.84210326921414, 329.1140520966929, -0.25641606835531666, 0.013640064895390436), (431.54831561818656, 328.2835752571257, 0.0862740779218544, 0.30203328636401916), (449.4737324005318, 318.59090969779714, 0.8493162548457772, -0.39087008306977955), (414.9662287493531, 321.7992369591167, -0.38427287382474645, -0.8225562013945713), (393.14019608044197, 166.3219823104028, -0.8606903726780473, 0.44501048112586244),
 (407.74279750683405, 174.07932270043037, -0.41221110195676625, 0.5621672919603494), (459.79766287684146, 367.8798142900581, -0.013886373621122439, -0.3180180360181074), (481.3079661009345, 389.2929845754805, 1.308536261884114, 0.6279064260682542), (299.0319011022105, 142.56295134440845, 0.5129247847316193, 0.6861624164039957), (284.8757848267405, 115.44737423970206, -0.39395187391162256, -0.7247085199267874), (721.0242237005709, 208.11018311759165, 0.5031252275481168, 0.45273074175310746), (698.5559327045538, 206.46532762419102, -0.4253037092008059, -0.10234863067289382), (238.01728536837834, 96.94484935393817, -1.0004911938691854, -0.649305316642717), (231.42367571047265, 113.24222441346936, -1.0247825937879875, -0.17624171000468863), (219.78600179605175, 374.1104577170864, -0.6368728728325652, -0.17569384553335526), (246.11065722883504, 371.79606791842366, 0.5219343181987446, -0.3462866864847798), (61.288999430029705, 325.3049764118085, 0.06327048049117068, 0.43129466994014554), (44.508614390256625, 300.0898728637909, -0.6949149408422702, -0.6606674558084397), (444.7436476698611, 97.43495673585237, 0.0767541318435591, -0.2776251496223229), (744.2355976846196, 142.86962390689527, 0.9981335574540283, -0.24606523573449057), (722.4382189578434, 148.50423479439266, 0.17497076263720399, -0.184532590143744), (418.5327228664219, 136.72695351434712, 0.5475576395865829, -0.8913163462276698), (695.9021288583592, 180.5828160193858, -0.9488479900701872, -0.7148885273332122), (514.3530295181225, 176.69505705865964, 0.4250410294309581, 0.24872469962151272), (491.3217475016306, 192.06501755019133, -0.5852344731438237, 0.6683151007063167), (404.93366351040646, 355.33847789785887, -0.2208752264067056, 0.5785115096521176), (660.6042829909404, 388.98594646068375, -0.2802404219269444, -0.8854758825918975), (657.1412902684084, 422.0142602600062, -0.09955316106014461, 0.6262242796545058), (324.601539532362, 71.99880574130555, -0.44523640628825367, -0.7982939572849916), (313.7688791782026, 100.51158011600064, -0.8550429986673138, 0.23687636012864005), (463.05020279897207, 354.3841115016863, 0.5259364738387711, -0.030002820893658896), (307.8633146779248, 151.5952286725273, 0.6622908641009807, -0.03664136082024409), (398.41892028466214, 111.78772135693538, 0.11954324115479029, -0.8254277998217231), (381.45123257781245, 136.6036806395423, -0.6799079499520264, -0.08600175586428575), (292.6839863142225, 92.60685790044825, 0.536452531252875, -0.7140993636579337), (107.00966574475697, 373.9070654764243, -0.7010200558637464, -0.1381120246392485), (145.16889322345122, 365.860466913724, 0.5965222398714648, -0.5001275164663491), (353.3938458530145, 92.28564527857638, 0.27648661676701847, 0.4055937158607218), (332.6003342739462, 150.35292606144606, 0.16791054337808475, 0.19838069473157122), (333.2155442174266, 135.41367942003444, -0.1948746996045789, -0.8713050639597644), (341.7828985904844, 176.40085292375244, 0.15777998878645658, 0.45702848410002833), (352.9649338991208, 63.40320810353417, 0.31005939791813875, -0.35531540613337653), (558.759849975508, 335.82850463010334, -0.3751838713627865, 0.6972047893312435), (658.9879897953409, 243.4647341215956, -0.2407221233734072, -0.9276449712809698), (680.2245351443412, 296.75251078114536, 0.4337786026208906, 0.9727281158269319), (341.72634396514303, 378.7867598373575, -0.03596521226118493, 0.51167641447653), (697.0597317905844, 409.2588838533252, 0.9048830590914927, -0.4657488561253242), (665.1731546911783, 437.3925803649936, -0.007368744952089001, 0.3787660493964195), (67.00785464657952, 103.1274278061125, 0.03732794987331456, -0.5508360071810254), (105.96964960562794, 128.97178091353496, 0.8136907261343687, 0.4063622560568454), (105.07041437177854, 61.05750261646497, 0.26186719895475497, -0.5163887919827821), (68.49603305059723, 73.94521027290915, -0.7594061833112205, -0.7798070269292883), (71.34190872889897, 124.87773643827933, -0.4688181952259638, -0.5600838356192892), (64.27757202298889, 159.8496885573903, -0.6934232584078162, -0.042604127504053846), (70.57044794264237, 176.93801328964406, -0.4233167428650957, -0.11340691519836832), (144.63770817171127, 69.41378490162104, -0.08749228993661817, -0.28097092956958947), (137.8210753472867, 150.33804975066357, -0.191812024174572, 0.6051129537282753), (137.26460390655052, 180.16854638211603, -0.21242207753516196, 0.11735356970799926), (165.50112593068218, 175.5434604690403, 0.3148565159511876, -0.3132051678133363), (158.21970276683984, 160.0662466663162, -0.399270267894807, -0.47902790124753714), (162.68670402259963, 93.7322224457243, -0.9745665176814846, -0.9728806501583553), (200.74175804924195, 121.50562533623162, -0.6762311833614205, -0.2034953579173453), (224.47067029408507, 148.9360402550957, 0.46187667755869377, -0.22459110166312768), (249.5998504282539, 128.78709867759278, 0.8740685343797732, -0.6745519008298879), (222.1623163178933, 162.24461613732666, -0.40139569192986624, 0.04609689397505523), (270.1496673364134, 119.26292107574434, 0.44998767912644677, -0.8791510712687354), (251.7055547368385, 167.7628397486525, -0.9368313060430262, 0.6578829536537905), (275.1172494773191, 184.09798794704585, -0.5141759452844961, -0.033407853813111066), (265.9957830031348, 199.51750836889886, -0.25941544432835606, 0.056204013662934704), (282.07956665413514, 164.958740535395, 0.8918358020049804, -0.7422688690594414), (353.4402011639725, 114.78109493306745, 0.7570444875545246, -0.415515002478986), (356.5222794940665, 213.68778310329276, 0.6860103516321112, 0.9143623371590044), (330.49971249176855, 226.5949460000718, -0.6111217595640996, 0.873886888891541), (454.61901786077544, 150.71441166327446, 0.8747784392879676, 0.9153485801212855), (388.60627446909075, 197.93977442346403, -0.23680464929294276, 0.14591757123939741), (423.67540627845943, 205.2755085720821, -0.5305405082052022, 0.8620558730400902), (477.52821141998515, 197.94782386045253, 0.8714152377772004, -0.11304356072398081), (509.7764508897392, 142.38940000013736, -0.3416129300096671, 0.4959037037087939), (517.4542284218678, 157.00198576512298, -0.8720656140048659, 0.7778513246341929), (489.14570184081595, 143.71628106431027, -0.43904807996975315, 0.17467707645594244), (484.36624455679043, 162.18554614981508, -0.3197687201188777, 0.006872079622769922), (538.1915570784884, 186.90845701394394, 0.2663539658698997, 0.9595724819979277),
 (558.4402698588482, 151.2562488554182, 0.20149147625361707, -0.1756944868363639), (498.8936687068798, 219.16941966684988, -0.522456714559989, 0.747015543216671), (557.5264047150413, 194.47492406099926, 0.686163137594151, -0.13055836811114152), (572.2642293852141, 133.05544915189392, -0.36058409684388026, 0.18723885747756386),
 (593.233462901164, 148.90845332339745, 0.11975788522826214, -0.04042765468897547), (592.1067952919601, 200.97587238888386, -0.2553038780755985, 0.7398471255142076), (620.8001885800545, 156.51793210692475, -0.5999930155535687, 0.3525160039601669), (630.0497687231773, 138.21403356381515, -0.7018604176601002, 0.3042234653264848), (656.2600646659411, 156.841032404578, -0.9903679753354846, 0.7348530520214087), (711.2887269504378, 97.8513508705996, 0.3810639611272786, -0.8943944122000136), (738.7664844418454, 116.88118100970506, 0.6209809052535715, -0.41180811075166335), (703.8040510631283, 152.5920657076647, 0.511261150486223, -0.5706642330494665), (740.09107559372, 198.6981029696348, 0.5218916886562541, 0.1740038136901716), (657.6864804602145, 215.93482850112167, -0.9745747977698767, 0.034623277819314735), (71.54711083768379, 350.36060634700226, 0.6498929939882905, -0.6162738389999025),
 (150.9033697831391, 276.73234512286984, 0.9223470290051474, 0.582679448995163), (172.75073798985846, 238.05776406669546, 0.9907680736984741, -0.886749479011274), (166.14454393170783, 261.9146208279891, -0.10575763215896572, -0.04019922859299774), (135.8179319546022, 304.5167891568187, 0.51177525757786, 0.6117329317340197), (109.29600036825342, 324.14080376797784, -0.32237035673135206, -0.47626652711191975), (128.25054047146125, 342.5039087606924, 0.41668668412819376, -0.6480033792336315), (160.9435843133916, 336.7772890102673, 0.22013275234783625, 0.4732329263061923), (159.99063987213424, 357.3713520468878, 0.14780147674570876, -0.8751351093745308), (203.82463986148133, 294.85292265982395, 0.36387555042522823, -0.8943361977843205), (238.77834673828744, 257.8957469467245, 0.69549432364027, -0.966824187158376), (234.71098679446786, 302.43763534262735, 0.6189254368321369, -0.02082832064340412), (199.13592069493149, 350.92258754952445, -0.5134844187062317, -0.2621263870546515), (246.08239218788768, 387.5706266290919, 0.5215700810328909, -0.12701382855216137), (279.81163336690304, 310.1193743783627, -0.5995691345591287, 0.8192360880875091), (312.43826713316605, 326.3110183009928, 0.6088247086357645, -0.02551784070396379), (278.3124563204679, 346.2774946054354, -0.618057173316024, 0.23249980020133165), (309.0606334597058, 364.2832298989901, 0.5578012392483811, 0.34382332959224393),
 (277.86613144487796, 384.4110746203211, -0.5605136501896855, 0.422632393345197), (297.7963837815137, 417.4215462126431, 0.1776438437597616, 0.978575785653446), (308.64648313310744, 389.32195957645587, -0.8279080321071313, 0.048961465794687076), (332.9030266443413, 352.59935912758954, -0.9665545687281056, 0.614791078799594), (348.26013943242486, 314.11612768512305, -0.842217058058359, -0.032736011662137576), (360.3306887191309, 292.2383422919451, -0.7655300474395692, -0.32450584103905666), (396.9404109804546, 370.8911519658965, -0.15035514887206558, -0.04106844570751811), (400.104874692782, 411.57211198606, -0.1442639002673347, 0.761930073557795), (440.30114216085207, 361.3409051871098, 0.9000423022537898, -0.2836701782551865), (429.3543769941238, 341.9294444418788, 0.3094213701527606, -0.33594650215266264), (447.43603366759595, 277.2285471339229, 0.38651976546653843, -0.880424180225089), (481.7939322275633, 301.5421301772078, -0.15578028786801723, -0.09103221565894848), (496.05798504633856, 291.5141421831062, -0.0719264797652579, -0.09206880803313222), (509.5366997343411, 286.81707674748407, -0.16530741724662823, 0.14137321286975357), (512.6359971378648, 331.33312820778906, -0.7542223282272489, 0.9012269706588789), (565.2777793457861, 322.789250206497, -0.8786007649708629, 0.6588611187591347), (616.2993903993898, 307.1147976370016, 0.30738482960705515, 0.07832583840747809), (549.4707698926467, 355.7327131244734, -0.6862677817538163, 0.5086190046101378), (566.0048628120813, 359.0888370802809, -0.8146347106636107, 0.521808780751152), (603.0173174232779, 355.65724327656727, -0.22158083617492497, 0.09841641765061859), (627.8321653818715, 343.97419893606997, 0.4011913104396747, -0.9268815208862793), (537.4339433151019, 408.0628758894442, -0.9839280253666145, 0.5949213292386479), (640.8558916665046, 286.24303230003744, -0.30163364198134635, 0.3052974925939915), (693.3776564065166, 322.7209553086005, 0.6806539409820418, 0.8785539003185334), (677.9197897159304, 332.5251925812629, 0.1451773968863177, 0.42685898449123116), (715.7380915196851, 359.6720022622894, 0.8791885748031647, 0.9508148986033234), (654.241096201209, 350.8310224121308, -0.8058853258811696, 0.25300083007890595), (660.0062961624873, 367.58093595080226, -0.6293964384264055, 0.09559022040005982), (674.0852620040955, 376.20299215975325, -0.07091622207048798, -0.362852142231338)]

class Point:

    def __init__(self, pos, vx, vy):
        self.x, self.y = pos
        self.vx = vx
        self.vy = vy
        self.flag = 1


def dotproduct(v1, v2):
    return v1[0] * v2[0] + v1[1] * v2[1]


def checkcrush(point1, point2):
    distance = math.sqrt((point1.x - point2.x) ** 2 + (point1.y - point2.y) ** 2)
    a = (point1.vx - point2.vx) ** 2 + (point1.vy - point2.vy) ** 2
    b = 2 * (point1.x - point2.x) * (point1.vx - point2.vx) + 2 * (point1.y - point2.y) * (point1.vy - point2.vy)
    c = distance ** 2 - 4 * RADIUS ** 2
    delta = b ** 2 - 4 * a * c
    if delta < 0:
        return
    time = (-b - math.sqrt(delta)) / (2 * a)
    if time > 0:
        if time < 1:
            return time
    return


def get_new_point(time, point1, point2):
    distance = math.sqrt((point1.x - point2.x) ** 2 + (point1.y - point2.y) ** 2)
    standard_displacement = ((point2.x - point1.x) / distance, (point2.y - point1.y) / distance)
    v_1 = (point1.vx, point1.vy)
    v_2 = (point2.vx, point2.vy)
    v_par_1 = dotproduct(standard_displacement, v_1)
    v_par_2 = dotproduct(standard_displacement, v_2)
    v_ver_1 = (point1.vx - v_par_1 * standard_displacement[0], point1.vy - v_par_1 * standard_displacement[1])
    v_ver_2 = (point2.vx - v_par_2 * standard_displacement[0], point2.vy - v_par_2 * standard_displacement[1])
    v_after_par_1 = v_par_2
    v_after_par_2 = v_par_1
    v_after_1 = (v_after_par_1 * standard_displacement[0] + v_ver_1[0], v_after_par_1 * standard_displacement[1] + v_ver_1[1])
    v_after_2 = (v_after_par_2 * standard_displacement[0] + v_ver_2[0], v_after_par_2 * standard_displacement[1] + v_ver_2[1])
    afterpos_1 = (point1.x + point1.vx * time + v_after_1[0] * (1 - time), point1.y + point1.vy * time + v_after_1[1] * (1 - time))
    afterpos_2 = (point2.x + point2.vx * time + v_after_2[0] * (1 - time), point2.y + point2.vy * time + v_after_2[1] * (1 - time))
    return (Point(afterpos_1, v_after_1[0], v_after_1[1]), Point(afterpos_2, v_after_2[0], v_after_2[1]))


def drawpoint(screen, list_):
    for item in list_:
        pygame.draw.circle(screen, BLUE, (round(item.x), round(item.y)), RADIUS, 3)


def next_pos_list(Pointlist):
    pointlist = []
    for i in range(len(Pointlist)):
        for point in Pointlist[i + 1:]:
            times = checkcrush(Pointlist[i], point)
            if times != None:
                #print("crash")
                a, b = get_new_point(times, Pointlist[i], point)
                pointlist.extend([a, b])
                Pointlist[i].flag = 0
                point.flag = 0
    else:
        for item in Pointlist:
            if item.flag != 0:
                pointlist.append(Point((item.x + item.vx, item.y + item.vy), item.vx, item.vy))
            for poi in pointlist:
                poi.x = poi.x % WIDTH
                poi.y = poi.y % HEIGHT
        else:
            return pointlist


Pointlist = []
for item in list_:
#     Pointlist.append(Point((item[0], item[1]), item[2], item[3]))
# for item in list_:
    Pointlist.append(Point((item[0], item[1]), -item[2], -item[3]))
else:

    def value(lis):
        count = 0
        for item in lis:
            count = count + (item.x - round(item.x)) ** 2 + (item.y - round(item.y)) ** 2
        else:
            return count

    #print(Pointlist)
    while running:
        print(len(Pointlist))
        clock.tick(FPS)
        for event in pygame.event.get():
            if event.type == pygame.QUIT:
                running = False
        screen.fill(BLACK)
        drawpoint(screen, Pointlist)
        Pointlist = next_pos_list(Pointlist)
        pygame.display.flip()

    pygame.quit()
# okay decompiling microworld.exe_extracted/2.pyc

0x0F 卷王与野生的 GPA

拿到elf和gba,当然是先下载一个gba模拟器。

把elf扔到IDA,稍微观察一下逻辑,再看一看题目,显然这题要用"上上下下左右左右BABA"才能执行主逻辑。然而运行后发现毫无卵用。观察下左边的函数列表,发现有一个decrypt函数。这个函数里头用了flagenc这个数组,而也没有别的函数调用decrypt。观察发现这个函数和showtext十分相似,仅仅是显示的内容不同了。因此我们可以猜测,调用这个函数后屏幕下方就会显示出flag。

之后就是如何调用这和函数了。我们需要对gba打patch。简单搜索一下,发现elf和gba文件在代码上是一模一样的。我们只需要打path,使某个BL跳到decrypt即可。我最开始改的是trickplay里的调用的showtext,但是这个显然是不好。因为原文是向上跳转,而被我改成了向下跳转(我还专门去翻了ARM指令编码)。所以改了后也莫名奇妙没有成功。于是思考能不能用一个向上跳转。发现可以改main函数的调用。因此我改了对fail的调用到decrypt。发现莫名奇妙成功了,就是flag会闪现(毕竟没有等待key的操作)。于是使用传统录屏技巧,得到了flag闪现时的画面。

0x10 阵列恢复大师

当然是先做raid5啊。

拿到raid5的几块盘后,这题目的显然是让我们恢复顺序。用010 editor浏览了一下,发现有一片有大量的可见字符信息,能明显在0x10000倍数处看到分界。也就是说块大小是0x10000。而raid5有一个校验盘,这个校验盘的对应块就没有这么多可见字符了。因此我写了这个程序来找校验盘。

import os
import string


ps=string.ascii_letters+string.digits

BS=0x10000

imgs=os.listdir('.')
imgs=[x for x in imgs if x.endswith('.img') and x!='src.img']
print(imgs)
ctimgs=[]

for x in imgs:
    f=open(x,'rb')
    g=f.read()
    f.close()
    ctimgs.append(g)

def countchar(st):
    cnt=0
    #print(st)
    for x in st:
        if chr(x) in ps:
            cnt+=1
    return cnt

for pos in range(20,70):
    ccps=[]
    for x in ctimgs:
        ccps.append(countchar(x[pos*BS:(pos+1)*BS]))
    pps=ccps*1
    pps.sort()
    pbv=None
    if pps[0]<35000 and pps[1]>40000:
        pbv=pps[0]
    pbp=None
    for i,x in enumerate(ccps):
        if x==pbv:
            pbp=i
    if pbp!=None:
        print("Check %d: %d"%(pos,pbp))
    #print(ccps)

之后可以推断出校验盘位出现的顺序了。根据这个顺序可以逆推出数据盘顺序。然而根据网上查到的raid5的信息,得到的数据盘顺序怎么也不对。最后人肉看了有内容部分几块的顺序,猜到了内部排列方式(即官方题解提到的left-symmetric)。之后合并得到完整镜像,按偏移挂载一下即可。

import os
import string


ps=string.ascii_letters+string.digits

BS=0x10000

imgs=os.listdir('.')
imgs=[x for x in imgs if x.endswith('.img') and x!='src.img']
print(imgs)
ctimgs=[]

for x in imgs:
    f=open(x,'rb')
    g=f.read()
    f.close()
    ctimgs.append(g)

sts=[2,4,0,3,1]
strx=sts[::-1]

BC=(len(ctimgs[0])+BS-1)//BS

f=open("src.img","wb")

for i in range(0,BC):
    for j in range(4):
        jx=strx[(j-i)%5]
        f.write(ctimgs[jx][i*BS:(i+1)*BS])
    
f.close()

之后再看raid0。这个盘数量多了好多。然后文件里也几乎没有什么文本信息。这就很烦。不过我们还可以推出盘位。文件内有两三个大的二进制块,可以根据这个块头尾分布的块位置来推测镜像间的相对顺序。同时还有一些零散分布的小块,其中一些可以推测某两个镜像的顺序。注意一下这个块大小是0x20000。推测大致盘位仍然使用上一问程序输出可见字符密度,之后肉眼查看。两块间顺序就用010 editor人肉查看。最后得到可能顺序有7,5,0,1,2,3,6,47,5,0,1,2,6,3,4,都试一试就好了。

import os
import string


ps=string.ascii_letters+string.digits

BS=0x20000

imgs=os.listdir('.')
imgs=[x for x in imgs if x.endswith('.img') and x!='src.img']
print(imgs)
ctimgs=[]

for x in imgs:
    f=open(x,'rb')
    g=f.read()
    f.close()
    ctimgs.append(g)


sts=[7,5,0,1,2,3,6,4]

BC=(len(ctimgs[0])+BS-1)//BS

f=open("src.img","wb")

print(len(ctimgs))
print(len(ctimgs[0]))

for i in range(0,BC):
    for j in range(8):
        jx=sts[j]
        f.write(ctimgs[jx][i*BS:(i+1)*BS])
    
f.close()

0x11 链上预言家

题目非常好,需要对EVM有一定了解才能做出来。

第一问其实比较显然,比较CREATE2计算地址的方法是公开的。只需要有sender,salt和code即可计算。

而sender是已知的,salt可以通过询问题目合约得到,code也是公开的。网上也能之间搜到代码(https://solidity-by-example.org/app/create2/)。

但是有个小坑:如果你用题目的sol编译出来的Dummy的代码来做这题可能过不了,因为你编译的和服务器上的不一样。因此我使用了特技把服务端部署的代码dump了出来,之后逆向一下,直接拿服务端部署的代码来算hash即可。

具体dump的方法就是利用revert的message可以传递信息的特点(见代码中crack合约,可能需要少量修改代码)。

提交只需要提交rwdo合约编译后的结果。需要注意下因为字节码太长,可能需要手写一个提交程序。

pragma solidity =0.8.9;

interface Predictor {
    function predict(address challenge) external returns (address);
}

contract Dummy {
    function hello() public pure returns (string memory) {
        return "Hello!";
    }
}

contract Challenge {
    bytes32 public seed;

    constructor(bytes32 _seed) {
        seed = _seed;
    }

    function create_child() public returns (address) {
        return address(new Dummy{salt:seed}());
    }

    function predict_child(Predictor p) public returns (bool) {
        address predicted = p.predict(address(this));
        address real = create_child();
        return predicted == real;
    }
}

contract crack {

    constructor() {
    }
    function getBytecode() public pure returns (bytes memory) {
        bytes memory bytecode = type(Dummy).creationCode;

        return abi.encodePacked(bytecode);
    }
    function getAddress(bytes memory bytecode,address send, bytes32 _salt)
        public
        view
        returns (address)
    {
        bytes32 hash = keccak256(
            abi.encodePacked(bytes1(0xff), send, _salt, keccak256(bytecode))
        );

        // NOTE: cast last 20 bytes of hash to address
        return address(uint160(uint(hash)));
    }
    function toHex(bytes memory data) public pure returns(bytes memory res) {
    res = new bytes(data.length * 2);
    bytes memory alphabet = "0123456789abcdef";
    for (uint i = 0; i < data.length; i++) {
        res[i*2 + 0] = alphabet[uint256(uint8(data[i])) >> 4];
        res[i*2 + 1] = alphabet[uint256(uint8(data[i])) & 15];
    }
}
        function at(address _addr) public view returns (bytes memory o_code) {
        assembly {
            // retrieve the size of the code, this needs assembly
            let size := extcodesize(_addr)
            // allocate output byte array - this could also be done without assembly
            // by using o_code = new bytes(size)
            o_code := mload(0x40)
            // new "memory end" including padding
            mstore(0x40, add(o_code, and(add(add(size, 0x20), 0x1f), not(0x1f))))
            // store length in memory
            //mstore(o_code, size)
            mstore(o_code, 0x19c)
            // actually retrieve the code, this needs assembly
            //extcodecopy(_addr, add(o_code, 0x20), 0, size)
            extcodecopy(_addr, add(o_code, 0x20), 0x035f, 0x19c)
        }
    }
    function predict(address send) public returns (address) {
        //address predicted = p.predict(address(this));
        uint256 size;
          assembly {
    size := extcodesize(send)
  }
  bytes memory jb=abi.encodePacked(size);
  //string memory aa=bytes32ToString(bytes32(jb));
  //string memory aa=bytes32ToString(bytes32("abcdefg"));
  //bytes memory ds=toHex(send.code);
  bytes memory ds=toHex(at(send));
  string memory aa=string(bytes(ds));
  require(false,aa);
        return send;
    }
}

contract rwdo {

    constructor() {
    }

    function getBytecode() public pure returns (bytes memory) {
        bytes memory bytecode = type(Dummy).creationCode;

        return abi.encodePacked(bytecode);
    }
    function getAddress(bytes memory bytecode,address send, bytes32 _salt)
        public
        view
        returns (address)
    {
        bytes32 hash = keccak256(
            abi.encodePacked(bytes1(0xff), send, _salt, keccak256(bytecode))
        );

        // NOTE: cast last 20 bytes of hash to address
        return address(uint160(uint(hash)));
    }
        function at(address _addr) public view returns (bytes memory o_code) {
        assembly {
            // retrieve the size of the code, this needs assembly
            let size := extcodesize(_addr)
            // allocate output byte array - this could also be done without assembly
            // by using o_code = new bytes(size)
            o_code := mload(0x40)
            // new "memory end" including padding
            mstore(0x40, add(o_code, and(add(add(size, 0x20), 0x1f), not(0x1f))))
            // store length in memory
            mstore(o_code, 0x19c)
            // actually retrieve the code, this needs assembly
            extcodecopy(_addr, add(o_code, 0x20), 0x035f, 0x19c)
        }
    }
    function predict(address send) public returns (address) {
        //address predicted = p.predict(address(this));
        bytes32 tmp=Challenge(send).seed();
        //bytes memory codev=getBytecode();
        //bytes memory codev=send.code;
        bytes memory codev=at(send);
        
        //codev=codev[:];
        address calc=getAddress(codev,send,tmp);
        return calc;
    }
}

第二问比较有意思。拿不到salt的时候怎么完成这个task呢。

总的思路有两个。一个是不拿到地址,直接让predict_child返回true。然而在这题,以及EVM模型下是不太可能了。只剩下另外一个选择:在predict内拿到合约地址,而不创建合约(即让后边执行create_child不会出错)。

拿到地址又有两种方法。一种是直接计算,也就是第一问的方法。然而直接计算需要在链上直接拿到别的合约的存储,这几乎是不可能的(当然链下很容易)。一种是,我偷偷创建一个,然后把这个合约销毁/这个动作撤销。

销毁也不是很可行,那么就剩撤销了。利用EVM的revert机制可以实现这个撤销。revert会撤销所有的状态更改,因此我们可以先创建一个dummy,拿到地址后自己revert,这个创建合约操作就被撤销了。但是既然撤销了状态,那怎么传出这个地址呢。一个最简单的方法是利用revert message。revert会像函数返回一样返回一个信息,这个信息也是可以控制的。当然还可以利用gas这种不会撤销的状态传出信息(可以看mcfx的wp)。那么代码如下。

pragma solidity =0.8.9;

interface Predictor {
    function predict(address challenge) external returns (address);
}

contract Dummy {
    function hello() public pure returns (string memory) {
        return "Hello!";
    }
}

contract Challenge {
    bytes32 seed;

    constructor(bytes32 _seed) {
        seed = _seed;
    }

    function create_child() public returns (address) {
        return address(new Dummy{salt:seed}());
    }

    function predict_child(Predictor p) public returns (bool) {
        address predicted = p.predict(address(this));
        address real = create_child();
        return predicted == real;
    }
}



contract crack {

    constructor() {
    }
    function getBytecode() public pure returns (bytes memory) {
        bytes memory bytecode = type(Dummy).creationCode;

        return abi.encodePacked(bytecode);
    }
    function getAddress(bytes memory bytecode,address send, bytes32 _salt)
        public
        view
        returns (address)
    {
        bytes32 hash = keccak256(
            abi.encodePacked(bytes1(0xff), send, _salt, keccak256(bytecode))
        );

        // NOTE: cast last 20 bytes of hash to address
        return address(uint160(uint(hash)));
    }
    function toHex(bytes memory data) public pure returns(bytes memory res) {
    res = new bytes(data.length * 2);
    bytes memory alphabet = "0123456789abcdef";
    for (uint i = 0; i < data.length; i++) {
        res[i*2 + 0] = alphabet[uint256(uint8(data[i])) >> 4];
        res[i*2 + 1] = alphabet[uint256(uint8(data[i])) & 15];
    }
}
        function at(address _addr) public view returns (bytes memory o_code) {
        assembly {
            // retrieve the size of the code, this needs assembly
            let size := extcodesize(_addr)
            // allocate output byte array - this could also be done without assembly
            // by using o_code = new bytes(size)
            o_code := mload(0x40)
            // new "memory end" including padding
            mstore(0x40, add(o_code, and(add(add(size, 0x20), 0x1f), not(0x1f))))
            // store length in memory
            //mstore(o_code, size)
            mstore(o_code, 0x19c)
            // actually retrieve the code, this needs assembly
            //extcodecopy(_addr, add(o_code, 0x20), 0, size)
            extcodecopy(_addr, add(o_code, 0x20), 0x035f, 0x19c)
        }
    }
    function predict(address send) public returns (address) {
        //address predicted = p.predict(address(this));
//         uint256 size;
//           assembly {
//     size := extcodesize(send)
//   }
//   bytes memory jb=abi.encodePacked(size);
//   //string memory aa=bytes32ToString(bytes32(jb));
//   //string memory aa=bytes32ToString(bytes32("abcdefg"));
//   bytes memory ds=toHex(send.code);
//   //bytes memory ds=toHex(at(send));
// bytes memory ds=toHex(abi.encodePacked(block.number,msg.sender,tx.origin,address(this)));
//   string memory aa=string(bytes(ds));
//   require(false,aa);
    address jb=Challenge(send).create_child();
    // (bool st,bytes memory res)=send.staticcall(abi.encodeWithSignature("create_child()"));
    require(false,string(toHex(abi.encodePacked(jb.code))));
    //address jb=address(res);
    //    return jb;
    return send;
    }
}

contract rwdo {
    address toaddr;

    constructor(){
    }

    function getBytecode() public pure returns (bytes memory) {
        bytes memory bytecode = type(Dummy).creationCode;

        return abi.encodePacked(bytecode);
    }
    function getAddress(bytes memory bytecode,address send, bytes32 _salt)
        public
        view
        returns (address)
    {
        bytes32 hash = keccak256(
            abi.encodePacked(bytes1(0xff), send, _salt, keccak256(bytecode))
        );

        // NOTE: cast last 20 bytes of hash to address
        return address(uint160(uint(hash)));
    }
        function at(address _addr) public view returns (bytes memory o_code) {
        assembly {
            // retrieve the size of the code, this needs assembly
            let size := extcodesize(_addr)
            // allocate output byte array - this could also be done without assembly
            // by using o_code = new bytes(size)
            o_code := mload(0x40)
            // new "memory end" including padding
            mstore(0x40, add(o_code, and(add(add(size, 0x20), 0x1f), not(0x1f))))
            // store length in memory
            mstore(o_code, 0x19c)
            // actually retrieve the code, this needs assembly
            extcodecopy(_addr, add(o_code, 0x20), 0x035f, 0x19c)
        }
    }
    function crack() public returns (address)
    {
        //return address(this);
        address ret=Challenge(toaddr).create_child();
        require(false,string(abi.encodePacked(ret)));
    }
    function predict(address send) public returns (address) {
        //address predicted = p.predict(address(this));
        //bytes32 tmp=Challenge(send).seed();
        //bytes32 tmp="1";
        //bytes memory codev=getBytecode();
        //bytes memory codev=send.code;
        //bytes memory codev=at(send);
        
        //codev=codev[:];
        //address calc=getAddress(codev,send,tmp);
        toaddr=send;
        (bool st,bytes memory res)=address(this).call(abi.encodeWithSignature("crack()"));
        bytes memory sb=new bytes(20);
        for(uint i=0;i<20;i++)
            sb[i]=res[68+i];
        address fk=address(bytes20(sb));
        return fk;
    }
    function test(address send) public returns (bytes memory)
    {
        toaddr=send;
        (bool st,bytes memory res)=address(this).call(abi.encodeWithSignature("crack()"));
        bytes memory sb=new bytes(20);
        for(uint i=0;i<20;i++)
            sb[i]=res[68+i];
        address fk=address(bytes20(sb));
        return res;
    }
}

0x12 助记词

看到Java 17就能猜到出题人了(雾)。

可以下载源码,那显然就是一个阅读代码题。

拿到flag的条件是某个代码片段消耗了较长的时间。先搜索一下代码有没有sleep之类的东西。发现果然有。在Phrase对象中判断相等的函数有一个无条件sleep 20ms。那么再观察一下哪用到了判断相等。发现只有Instance中的LinkedHashSet可能会用到。那么显然我们希望这个哈希表中尽可能产生哈希冲突,这样比较次数就会很多,进而消耗时间多。

先看第一问,只要求时间600ms,而这只需要30次比较。显然我们提交一个32长度的数组,每个数组的元素一模一样。每次插入的时候就会稳定进行一次比较(当然其实这有一半的概率拿不到flag,原因和第二问有关)。这个操作似乎必须通过手动发送web请求完成。

再看第二问,时间是9000ms,即450次比较。显然是数组中32个元素,每个元素的哈希值都完全相同,但是又是不同的东西。之后我们观察一下对象哈希方法。翻阅java文档可以得知,所有对象的哈希值都是32位有符号整数,而这个对象的哈希值为31*31*hash(str)+31*time+uid。uid是固定的,那我们只关心31*hash(str)+time即可。而字符串的哈希值为isini1i\sum_is_i^{n-i1-i}

我们先考虑,对于一个指定的字符串哈希,如何求出这个哈希值对于的所有的字符串。我们考虑"a b c d"形式的字符串,把它分成两部分"a"和" b c d"。之后我们枚举所有的bcd,算出后边的哈希值。那么我们要求的就是target=hash(a)*pow(31,len(bcd))+hash(bcd)。对于所有的hash(a)我们可以预处理并放到一个哈希表内,之后我们只要找到一个a,满足hash(a)=(targer-hash(bcd))*invert(pow(31,len(bcd)))即可。这一过程可以轻松完成。我们只需要600^3次枚举就可以求出某个特定哈希值所对应的所有字符串。至于为什么是把a单独拉出来而不是d单独拉出来,因为拉出来d的话,对hash(abc)需要乘上一个d的长度,这不便于我们之间反向查找d。

有了这个工具后,再考虑如何解决这题。这题的坑点来了。因为前边的比较中有sleep,因此处理到后续的对象时,时间可能会发生改变。但是这个影响是可以抵消到的。我们先假设开始这题的时候时间的毫秒数为0(如果不是,那就多请求几次,总有一次在误差可接受范围内)。那么以后每一个对象被处理的时间是可以计算的。当然我们只关心这个时间和第一条时间的差值。我们把这个差值计算出来,那么在hash(str)*31的部分就要减去这个差值。此处又一次用到逆元的知识。我们不妨钦定一下第一个字符串的hash,之后算一下接下来的10秒,这个需要的hash会变成哪些新的hash值。我们对所有这些数都要找到其对应的字符串。之后再根据我们计算的延迟来选择要使用哪些字符串作为提交的内容即可。

因为开始时间的不确定性,最后还得写个提交脚本多次提交。

我在做的时候先找到了哪个哈希值产生的冲突尽可能多,实际上这是不必要的,因为冲突是在太多了。这个初始哈希值可以随便选。

寻找所有的hash(str)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<unordered_map>
using namespace std;
template<typename __T>
inline void read(__T &x)
{
    x=0;
    int f=1;char c=getchar();
    while(!isdigit(c)){if(c=='-')   f=-1;c=getchar();}
    while(isdigit(c))   {x=x*10+c-'0';c=getchar();}
    x*=f;
}
//typedef pair<int,int>pi;
//pi mp(int a,int b)
//{
//    return make_pair(a,b);
//}
const long long mod=1ll<<32;
long long qpow(long long a,long long b=mod-2)
{
    long long ans=1;
    while(b)
    {
        if(b&1)    ans=ans*a%mod;
        b>>=1;
        a=a*a%mod;
    }
    return ans;
}
long long Exgcd(long long a, long long b, long long &x, long long &y) {
  if (!b) {
    x = 1;
    y = 0;
    return a;
  }
  long long d = Exgcd(b, a % b, x, y);
  long long t = x;
  x = y;
  y = t - (a / b) * y;
  return d;
}
long long invert(long long a,long long b)
{
    long long x,y;
    Exgcd(a,b,x,y);
    return (x%b+b)%b;
}
typedef unsigned int ui;
//unsigned char cnts[1ll<<32];
unsigned char *cnts;
ui memhash[666];
ui memlength[666];
const int n=600;
char mems[20];
char haha[666][20];
ui pows[100];
ui powi[100];
ui iv31;
unordered_map<ui,ui>hsmp;
int main()
{
    cnts=new unsigned char[1ll<<32];
    freopen("mnemonics.txt","r",stdin);
    pows[0]=1;
    for(int i=1;i<100;i++)
        pows[i]=pows[i-1]*31;
    for(int i=0;i<100;i++)
        powi[i]=invert(pows[i],mod);
    iv31=invert(31,mod);
    for(int i=0;i<n;i++)
    {
        cin>>mems;
        strcpy(haha[i],mems);
        memlength[i]=strlen(mems);
        int hs=0;
        for(int j=0;j<memlength[i];j++)
        {
            hs=hs*31+mems[j];
        }
        memhash[i]=hs;
        hsmp[hs]=i;
    }
    int jb=0;
    for(int a=0;a<n;a++)
    {
        ui hasha=memhash[a]*31+' ';
        for(int b=0;b<n;b++)
        {
            ui hashb=hasha*pows[memlength[b]+1]+memhash[b]*31+' ';
            for(int c=0;c<n;c++)
            {
                ui hashc=hashb*pows[memlength[c]]+memhash[c];
                ui lel=2+memlength[a]+memlength[b]+memlength[c];
                ui hashd=' '*pows[lel]+hashc;
                lel++;
                for(int del=0;del<11;del++)
                {
                    ui target=(2128968203*31u-del)*iv31;
                    ui ndc=(target-hashd)*powi[lel];
                    if(hsmp.count(ndc))
                    {
                        jb++;
                        int d=hsmp[ndc];
                        cout<<""<<haha[d]<<' '<<haha[a]<<' '<<haha[b]<<' '<<haha[c]<<","<<del<<""<<endl;
                    }
                }
            }
        }
    }
    return 0;
}

制作提交数组。

dual=20

f=open("crs")
x=f.read().split('\n')[:-1]
f.close()
#print(x)
pl=[]
for i in range(11):
    pl.append([])

for ln in x:
    ws,it=ln.split(',')
    it=int(it)
    pl[it].append(ws)


#print(pl)
gres=[]
myt=0
for i in range(32):
    gt=myt//1000
    print(gt)
    emmm=pl[gt]
    wd=emmm[0]
    del emmm[0]
    gres.append(wd)
    myt+=dual*(i)

print(gres)


sb=repr(gres)
sb=sb.replace('\'','\"')
print(sb)

0x13 Co-Program

只有第一问。主要是没时间做了。

给定表达式构造变量,大多数人都会用z3吧。我当时寻思z3处理不了取模,于是就没用。并没有注意到这题取模的是2^36。于是我给了个对于任意模数都能工作的做法。

观察一下这个表达式,发现大多都比较简单,而最多只会出现6个变量。因此我想到了一种神奇的构造。

我们考虑把6个变量中任意固定5个。把这5个变量全都赋一些类似-1/0/1的特殊值。之后这个表达式有一定概率被化简成为k1*x/k2+k3的形式。如果我们可以拿到这个k1 k2 k3,那么就有一定可能得到对应的x值,进而得到一个可能的赋值。

此处不如暴力。我们枚举一下这个k2,从1枚举到3好了。如果我们猜到的是正确的,那么我们对x带入一个等差数列,表达式的结果也应该是一个等差数列。我们把这个等差数列找出来,之后简单利用一下数论知识就可以算出x取多少,表达式是想要的值。

我们枚举一下选取哪个变量作为变量,以及剩余的变量分别赋值-1/0/1中的哪一个。几乎总会有一个能枚举到解。根据提交情况,这么做的正确率是高于90%的,足以拿到flag了。其实这个策略还可以优化。

import gmpy2
from pwn import *
import time

s=remote('202.38.93.111',10700)


s.sendline(b'ID:SIGN')

time.sleep(2)

MOD=2**36
class rint:
    n=0
    def __init__(self,n):
        self.n=n%MOD
    def __add__(self,other):
        return rint((self.n+other.n)%MOD)
    def __sub__(self,other):
        return rint((self.n-other.n)%MOD)
    def __mul__(self,other):
        return rint((self.n*other.n)%MOD)
    def __truediv__(self,other):
        if other.n==0:
            return rint(MOD-1)
        return rint((self.n//other.n)%MOD)
    def __mod__(self,other):
        if other.n==0:
            return rint(self.n)
        return rint((self.n%other.n)%MOD)
    def __neg__(self):
        return rint((MOD-self.n)%MOD)
    def __repr__(self):
        return "rint(%d)"%self.n
    def __eq__(self,other):
        return self.n==other.n

def doeval(kstr,pv):
    x=pv[0]
    y=pv[1]
    z=pv[2]
    i=pv[3]
    j=pv[4]
    k=pv[5]
    ret=eval(kstr)
    return ret

def genexp(pv):
    x=pv[0].n
    y=pv[1].n
    z=pv[2].n
    i=pv[3].n
    j=pv[4].n
    k=pv[5].n
    return "x=%d y=%d z=%d i=%d j=%d k=%d"%(x,y,z,i,j,k)

def getresult(kstr,ndr):
    for st in range(3**6):
        pv=[]
        tmp=st
        for i in range(6):
            pv.append(rint(tmp%3-1))
            tmp//=3
        rsv=doeval(kstr,pv)
        if(ndr==rsv.n):
            return genexp(pv)
        for i in range(6):
            opv=pv*1
            rsa=[rsv]
            for step in range(1,4):
                for t in range(4):
                    opv[i]=opv[i]+rint(step)
                    rsa.append(doeval(kstr,opv))
                bzc=rsa[1]-rsa[0]
                if bzc.n==0:
                    continue
                flag=True
                for t in range(1,4):
                    if bzc!=rsa[t+1]-rsa[t]:
                        flag=False
                        break
                if not flag:
                    continue
                cz=(ndr-rsv.n)%MOD
                pc=bzc.n
                #print(pc,cz)
                tv=gmpy2.gcd(pc,cz)
                cz//=tv
                pc//=tv
                if pc%2==0:
                    continue
                ccz=cz*gmpy2.invert(pc,MOD)%MOD
                opv=pv*1
                opv[i]=opv[i]+rint(ccz*step)
                rz=doeval(kstr,opv)
                if rz.n==ndr:
                    return genexp(opv)
    return ""
                #return opv
                #print(opv)

#print(getresult("(((-x)/(-y))*((z%y)%(y/x)))",0))


s.recvuntil(b"!")
s.recvline()
for i in range(100):
    nx=s.recvline().strip().decode()
    nv=int(s.recvline().strip())
    print(nx,nv)
    ans=getresult(nx,nv)
    print(ans)
    s.sendline(ans.encode())


s.interactive()

0x14 马赛克

观察一下代码,这个马赛克的求法是块内所有像素的平均值。那么做法其实挺显然的。

对于每一个块,先算出这个块内对于了哪些二维码块。之后枚举这些二维码块是黑是白(能确定下来的就不用枚举了),再计算一下这个情况的平均数和给定图中的是否一致。注意到每个二维码块在马赛克块中占的面积几乎总是不同的,因此枚举能得到唯一解的概率很大。对于已经找到唯一解的我们之间

还有个小问题,由于枚举顺序的问题,某个马赛克块可能在其中一个二维码块确定时才可被求解,而可以解出这个二维码块的马赛克块还没被枚举到。对于这个问题,一个最简单的方法就是多做几遍。迭代不到10次便可收敛。

做完后,发现大部分马赛克都还原了。仔细观察一下,有不少马赛克块包含了二维码的定位标记块。如果我们手动恢复这些块并多做几次迭代还能恢复更多。不过我们为什么不先掏出宇宙最强扫码工具微信试一试呢。于是我们直接得到了flag。

import string
import random
import math
#import qrcode
import numpy as np
from PIL import Image

X, Y = 103, 137     # 马赛克左上角位置(单位为像素)
N = 20              # 马赛克块的数量(共N*N块)
BOX_SIZE = 23       # 每个马赛克块的大小(边长,单位为像素)
PIXEL_SIZE = 11     # 二维码每个块的大小(边长,单位为像素)

BC=57

img=Image.open('pixelated_qrcode.bmp')


img=np.array(img)
SIZE=img.shape[0]

rimg=img.copy()

#print(img.shape)

def getcol(x,y):
    sx=x//PIXEL_SIZE
    sy=y//PIXEL_SIZE
    res=None
    for i in range(PIXEL_SIZE):
        for j in range(PIXEL_SIZE):
            tpc=rimg[sx*PIXEL_SIZE+i,sy*PIXEL_SIZE+j]
            if tpc!=0 and tpc!=255:
                continue
            if res is None or res==tpc:
                res=tpc
            else:
                return None
    return res

def setblock(x,y,col):
    for i in range(PIXEL_SIZE):
        for j in range(PIXEL_SIZE):
            rimg[x*PIXEL_SIZE+i,y*PIXEL_SIZE+j]=col

for x in range(BC):
    for y in range(BC):
        pcol=getcol(x*PIXEL_SIZE,y*PIXEL_SIZE)
        if pcol!=None:
            setblock(x,y,pcol)

for it in range(6):
    for mx in range(20):
        for my in range(20):
            mopox=X+mx*BOX_SIZE
            mopoy=Y+my*BOX_SIZE
            gcol=img[mopox,mopoy]
            if gcol==0 or gcol==255:
                continue
            blockset={}
            for i in range(BOX_SIZE):
                for j in range(BOX_SIZE):
                    psx=(mopox+i)//PIXEL_SIZE
                    psy=(mopoy+j)//PIXEL_SIZE
                    if (psx,psy) not in blockset:
                        blockset[(psx,psy)]=0
                    blockset[(psx,psy)]+=1
            ffc=gcol*BOX_SIZE*BOX_SIZE
            ndc={}
            for x in blockset:
                pcol=getcol(x[0]*PIXEL_SIZE,x[1]*PIXEL_SIZE)
                if pcol!=None:
                    ffc-=pcol*blockset[x]
                    continue
                ndc[x]=blockset[x]
            pcs=len(ndc)
            pbx=[]
            for st in range(1<<pcs):
                msum=0
                for i,x in enumerate(ndc.keys()):
                    if (st>>i)&1:
                        msum+=ndc[x]*255
                if msum-ffc>=0 and msum-ffc<BOX_SIZE*BOX_SIZE:
                    pbx.append(st)
            assert(len(pbx)>0)
            if len(pbx)==1:
                st=pbx[0]
                for i,x in enumerate(ndc.keys()):
                    if (st>>i)&1:
                        setblock(x[0],x[1],255)
                    else:
                        setblock(x[0],x[1],0)
        #print(len(pbx))
        #print(len(ndc))
        #print(gcol)
    res=Image.fromarray(rimg, mode='L')
    res.save("result%d.png"%it)

0x15 minecRaft

稍微试一下,发现这是个纯前端游戏,于是开始看源码。

先看html里头的,获胜逻辑在printcinput中,会根据调用的gyflagh函数的返回结果来判断。同时引用了一个flag.js。这个js尾部有函数gyflagh的定义。

看一下这个函数,发现混淆地是在恶心。于是本地起了个node,输出了一下这些混淆后变量名的值。通过字符串替换简单反混淆了下。

这个逻辑是调用了一个encrypt函数,之后把encrypt的结果和一个硬编码明文比较。这个encrypt函数就是开头的String['prototype'][_0x22517d(0x1a8)]

再做一些变量名替换,于是有了下边这些函数。

String['prototype'][_0x22517d(0x1a8)] = function(keyv) {
    console.log("ENCRYPT!");
    //console.log(keyv);
    const _0x13519e = _0x22517d
      , tmparr1 = new Array(0x2)
      , tmparr2 = new Array(0x4);
    let ret = '';
    plaintext = escape(this);
    //console.log('PLAIN',plaintext);
    //console.log("length");
    for (var vi = 0x0; vi < 0x4; vi++)
        tmparr2[vi] = Str4ToLong(keyv["slice"](vi * 0x4, (vi + 0x1) * 0x4));
    for (vi = 0x0; vi < plaintext["length"]; vi += 0x8) {
        tmparr1[0x0] = Str4ToLong(plaintext['slice'](vi, vi + 0x4)),
        tmparr1[0x1] = Str4ToLong(plaintext["slice"](vi + 0x4, vi + 0x8)),
        code(tmparr1, tmparr2);
        //decode(tmparr1,tmparr2);
        //code(tmparr1, tmparr2);
        ret += LongToBase16(tmparr1[0x0]) + LongToBase16(tmparr1[0x1]);
    }
    //console.log('RET',ret);
    return ret;
}
);

其中keyv在gyflagh中是固定常量_0x50051f(0x1b7)="1356853149054377"

观察一下,显然我们要逆向的核心逻辑是这个code函数。encrypt的外层循环只需要使用decode再做一次。

而这个code函数,也只需要把循环倒着做就可以得到逆函数。于是有了decode和decrypt。

function decrypt(plaintext, keyv) {
    let tmparr1 = new Array(0x2)
    , tmparr2 = new Array(0x4);
    let ret = '';
      for (var vi = 0x0; vi < 0x4; vi++)
          tmparr2[vi] = Str4ToLong(keyv["slice"](vi * 0x4, (vi + 0x1) * 0x4));
      for (vi = 0x0; vi < plaintext["length"]; vi += 0x10) {
        tmparr1[0x0] = Base16ToLong(plaintext['slice'](vi, vi + 0x8)),
        tmparr1[0x1] = Base16ToLong(plaintext["slice"](vi + 0x8, vi + 0x10)),
          decode(tmparr1, tmparr2);
          ret += LongToStr4(tmparr1[0x0]) + LongToStr4(tmparr1[0x1]);
      }
      return ret;
}

function decode(arr1, arr2) {
    let pars1 = arr1[0x0]
      , pars2 = arr1[0x1];
    const vs = (0x52cfb2de + 0x4b67c6db)
      , vm = vs * 0x20;
    let vi = vm;
    while(vi!=0)
    {
        pars2-= (pars1 << 0x4 ^ pars1 >>> 0x5) + pars1 ^ vi + arr2[vi >>> 0xb & 0x3],
        vi-=vs;
        pars1-= (pars2 << 0x4 ^ pars2 >>> 0x5) + pars2 ^ vi + arr2[vi & 0x3];
    }
    arr1[0x0] = pars1,
    arr1[0x1] = pars2;
}

console.log(decrypt(_0x22517d(0x1aa),"1356853149054377"));

0x16 JUST BE FUN

打开这题,发现就是给了你一个三维寻址的机器,以及对应的机器码,要求用这个机器码写代码构造一个奇怪的计算器。

这个计算器本身的计算过程是简单的,只需要从左往右依次计算即可。但是操作符是比较复杂的。总共需要支持加法,乘法,幂,异或,或,左移这几种计算。而这个机器的机器码只能支持加减乘除模运算,以及逻辑取反和比较。不过剩下的运算,借助条件控制语句(循环或者一堆if)可以直接实现或者按二进制位实现。

那么我们再观察这个机器本身的特点。这个机器是一个基于栈的机器(很难让人不去想diep),而没有任何的随机存储使用方法(很难让人不去想没有STORE的EVM)。这个机器的指令码有好好几种。首先是已经介绍过的算数操作,每次从栈内弹出一些数,进行计算然后把结果放入栈内。之后是跳转操作。具体地,无条件的决定下一条指令以及之后PC前进的方向是向上还是向下,或者向左向右向前向后。还支持三个维度上的条件跳转。从栈顶取一个数,根据是否为0来决定前进方向是向上还是向下(或者其他维度的其他方向)。当然还有必须的STOP指令,以及常见的NOP指令。剩下都是栈上数据的操作指令了。可以无条件地从栈顶弹出一个数,可以直接往栈上放入一个0-9之间的数字,也可切换到str_mode往栈上连续放入多个在0-255之间(除了34)的数。还可以无条件地复制栈顶的元素,并把这个元素也压到栈顶。也可以交换栈内任意两个位置的数。具体地,从栈内先弹出两个数,之后把这两个数对应栈位置的元素交换一下。还有三个输入输出指令。一个是从用户输入读入一个字节,一个是把当前栈顶以数字形式输出,一个是把当前栈顶以字符形式输出。

看到这里,首先能猜到这个指令集是图灵完全的。再其次,看到这个规则,我实在是觉得这和EVM的指令集太像了。EVM基于栈能进行那么多操作,一个很大的原因是可以使用SWAPX和DUPX之类的指令。而这个机器显然可以实现SWAPX和DUP1,同时借助以下SWAPX可以把DUP1扩展到DUPX。那么我就一直在想,能不能把EVM指令转换到这个机器码呢。

显然,能不能转换主要影响因素是控制流和数据流能不能完全模拟。我们已经做到了SWAPX,DUPX,POP,还有小数的PUSHX。对于大数的PUSHX,我们可以把大数分解一下,分解成一个255进制数,把每一位还有255都压到栈内,之后不断地进行乘法加法便可实现大数地PUSHX。关于输入输出的处理,我在以太坊的合约中实现了两个函数,input和output。这俩函数和这个机器的输入输出是等价的功能。当我们发现EVM在调用这两个函数时,只需要把相关指令直接替换成机器码即可(不过EVM在调用函数的时候会提前往栈上压入一个返回地址,因此我们也要把这个压入返回地址的指令找到并删去)。

之后就只剩下控制流了。先考虑顺序执行。我们显然可以把所有顺序执行的指令都部署到一个平面上,之后第一行正着走过去,遇到边界后往下一行,并接着掉头倒着走回来。以此类推,我们可以用一层实现256*254条指令空间的顺序执行。

对于跳转,有两个组成部分。一个是跳走语句(即JUMP),一个是跳到语句(即JUMPDEST)。我们考虑利用第三维实现跳转功能。对于一个跳转语句,我们让他离开这一层朝上走,到达某一层后在平面内进行寻路,找到JUMPDEST对应位置,之后再往下走。到达代码层后,注意到方向还是向下的方向,因此JUMPDEST的位置需要替换成一个无条件转向语句,把方向变成当前行的执行方向(这正好和EVM的JUMPDEST对应)。为了避免多个跳转间寻路冲突,我规定了对于每个JUMPDEST会分配一个固定的层数,之后所有跳到这个JUMPDEST的跳转语句都会在这一次进行平面寻路。而进行平面寻路时,为了避免上边有个JUMP下穿到这条路中间,我又规定了平面寻路时不能经过任何一个跳转点(JUMP/JUMPDEST等)的投影中。那么这么分配的跳转路径一定不会冲突(当然有一定概率找不到)。

对于条件跳转JUMPI,我们使用上下方向的条件跳转。不过这和我们的需求不太吻合。我们希望的是符合条件往下走,不符合的话前进。而机器的行为,不符合时会往上走。我们可以在代码层的上一层放两个机器码。第一个把代码执行方向变成平面,并指向下一条指令的位置,第二个把执行方向改为向下,这样就可以回到代码层了。但是回到代码层后,我们的方向并不会变成代码执行方向,而EVM中JUMPI的后边不会插入一个JUMPDEST。因此我直接手动在JUMPI后边插入一个JUMPDEST,就能解决这个转向问题了。

只剩下不是很重要的计算部分了。这题EVM生成代码中会被用到但机器码不含的指令只有EQ,我们只需要把它变成SUB+ISZERO即可。但是这块还有个问题,对于SUB,DIV,MOD,EVM中操作数顺序和机器中顺序是相反的。因此还需要在他们前面手都加一个SWAP1。

实现的时候还要注意把从栈内取地址的JUMP/JUMPI改成使用常数作为地址。由于大部分的跳转(除了函数返回)都是在跳转前PUSH了地址,因此我们把这个PUSH提取出来作为常数地址即可。而对于没有PUSH的JUMP,我们把它变成STOP就行(按道理也不应该执行到这个地方)。

剩下的是一些实现细节。具体实现请自行看程序。

我这个程序中因为要转换跳转,要用到指令的字节位置。虽然可以很容易处理(只有PUSHX不是定长),不过我还是选择了使用ethervm.io的反编译器的处理后结果。比较还是要做少量逆向的。

在生成程序时,会先从(0,0,0)跳转到计算表达式的函数的入口,然后再执行代码。

那么操作流程是这样。先把实现了题目逻辑的sol文件编译,并把合约(不是初始化代码)字节码放到ethervm.io中逆向一下。逆向本身只需要找三个地址,calc,getinput,setoutput的地址。把这几个地址放到conv.py的开头,同时把逆向生成的带标记的汇编复制到evm.txt中,执行conv.py,从code.txt复制代码提交即可。

有一个小坑:新版solidity编译出来的会自带safemath,最开始逆向时把我看傻了。所以此处使用旧版。以及为了避免函数调用被优化掉,此处不开编译优化。

pragma solidity =0.5.6;
    

contract calct {
    bytes input;
    uint public output;
    uint it;

    constructor() public {
    }
    
    function setinput(bytes memory iv) public
    {
        it=0;
        input=iv;
    }

    function getinput() public returns (uint)
    {
        uint retv=uint8(input[it]);
        it+=1;
        return retv;
    }
    
    function setoutput(uint otv) public
    {
        output=otv;
    }
    
    function calc() public {
        uint bv=getinput()-48;
        while(true)
        {
            uint nop=getinput();
            if(nop==0)
            {
                setoutput(bv);
                break;
            }
            uint nv=getinput()-48;
            if(nop==43)
            {
                bv+=nv;
            }
            else if(nop==42)
            {
                bv*=nv;
            }
            else if(nop==94)
            {
                uint cc=bv;
                nv--;
                while(nv!=0)
                {
                    nv--;
                    bv*=cc;
                }
            }
            else if(nop==60)
            {
                while(nv!=0)
                {
                    nv--;
                    bv*=2;
                }
            }
            else if(nop==120)
            {
                uint tmp=bv;
                bv=(bv/16)*16;
                if((tmp%2)!=(nv%2))
                    bv+=1;
                tmp/=2;
                nv/=2;
                if((tmp%2)!=(nv%2))
                    bv+=2;
                tmp/=2;
                nv/=2;
                if((tmp%2)!=(nv%2))
                    bv+=4;
                tmp/=2;
                nv/=2;
                if((tmp%2)!=(nv%2))
                    bv+=8;
            }
            else if(nop==124)
            {
                uint tmp=bv;
                if((tmp%2)==0)
                    if((nv%2)==1)
                        bv+=1;
                tmp/=2;
                nv/=2;
                if((tmp%2)==0)
                    if((nv%2)==1)
                        bv+=2;
                tmp/=2;
                nv/=2;
                if((tmp%2)==0)
                    if((nv%2)==1)
                        bv+=4;
                tmp/=2;
                nv/=2;
                if((tmp%2)==0)
                    if((nv%2)==1)
                        bv+=8;
            }
        }
    }
}
import enum
import os
import sys

f=open("evm.txt")
x=f.read()
f.close()
#calc: 0x96f1b6be
#input: 0x280c6e1e
#output: 
CALC_ADDR=0x021d
INPUT_ADDR=0x018b
OUTPUT_ADDR=0x0213

lns=x.split("\n")

codes=[]

for sln in lns:
    ln=sln.strip()
    if len(ln)==0:
        continue
    if ln[:2]=='//':
        continue
    if ln[-1]==':' and ln[:5]=='label':
        continue
    sx=ln.split()
    lnid=int(sx[0],16)
    lnc=" ".join(sx[2:])
    if lnc[0]=='*':
        lnc=lnc[1:]
    codes.append((lnid,lnc))
    #print((lnid,lnc))

pid=None
for id,x in enumerate(codes):
    if x[1]=="ASSERT":
        pid=id
if pid!=None:
    codes=codes[:pid]

# for i in range(len(codes)):
#     lnid=codes[i][0]
#     lnc=codes[i][1]
#     if lnc[:4]=='JUMP' and lnc!="JUMPDEST":
#         lic=codes[i-1][1]
#         if lic[:4]!="PUSH":
#             print("AEER ",hex(lnid),lnc)

def convertpush(ostr):
    a,b=ostr.split(" ")
    assert(a[:4]=="PUSH")
    if len(b)>2 and b[:2]=="0x":
        b=int(b[2:],16)
    else:
        b=int(b)
    return genpush(b)

def genpush(v):
    if v<10:
        return ["PUSHS "+str(v)]
    ret=["MODEC"]
    OPS=[]
    while v>0:
        adv=v%255
        if adv!=34:
            ret.append("PUSHV "+str(adv))
        else:
            ret.append("PUSHV "+str(adv-1))
            ret.append("PUSHV 1")
            OPS.append("ADD")
        v//=255
        if v!=0:
            OPS.append("ADD")
            ret.append("PUSHV 255")
            OPS.append("MUL")

    return ret+["MODEC"]+OPS[::-1]

def convertswap(ostr):
    assert(ostr[:4]=="SWAP" and len(ostr)>4)
    px=int(ostr[4:])
    return genswap(px)

def genswap(v,frp=0):
    fk=[]
    fk=fk+genpush(frp+1)
    fk=fk+genpush(v+1)
    return fk+["SWAPS"]

def convertdup(ostr):
    assert(ostr[:3]=="DUP" and len(ostr)>3)
    px=int(ostr[3:])
    return gendup(px)

def gendup(v):
    if v==1:
        return ["DUPS"]
    fk=genswap(v-1)
    fk=fk+["DUPS"]
    fk=fk+genswap(v,1)
    return fk

ncodes=[]

for i in range(len(codes)):
    lnid=codes[i][0]
    lnc=codes[i][1]
    if lnc[:4]=='JUMP' and lnc!="JUMPDEST":
        lic=codes[i-1][1]
        if lic[:4]!="PUSH":
            ncodes.append((lnid,lnc+"?"))
        else:
            pos=lic.split(' ')[1]
            if pos[:2]=="0x":
                pos=int(pos[2:],16)
            else:
                pos=int(pos)
            ncodes.pop()
            if pos in [INPUT_ADDR,OUTPUT_ADDR,CALC_ADDR] and ncodes[-1][1][:5]=="PUSH2":
                ncodes.pop()
            ncodes.append((lnid,lnc+" "+str(pos)))
        if lnc[:5]=="JUMPI":
            ncodes.append((lnid,"NOP"))
    else:
        ncodes.append((lnid,lnc))
    
codes=ncodes

ncodes=[]
for i in range(len(codes)):
    lnid=codes[i][0]
    lnc=codes[i][1]
    if lnc[:4]=='PUSH':
        rcode=convertpush(lnc)
        for x in rcode:
            ncodes.append((lnid,x))
    else:
        ncodes.append((lnid,lnc))
codes=ncodes

ncodes=[]
for i in range(len(codes)):
    lnid=codes[i][0]
    lnc=codes[i][1]
    if lnc[:4]=='SWAP':
        rcode=convertswap(lnc)
        for x in rcode:
            ncodes.append((lnid,x))
    else:
        ncodes.append((lnid,lnc))
codes=ncodes

ncodes=[]
for i in range(len(codes)):
    lnid=codes[i][0]
    lnc=codes[i][1]
    if lnc[:3]=='DUP':
        rcode=convertdup(lnc)
        for x in rcode:
            ncodes.append((lnid,x))
    else:
        ncodes.append((lnid,lnc))
codes=ncodes

ncodes=[]
for i in range(len(codes)):
    lnid=codes[i][0]
    lnc=codes[i][1]
    if lnc=='EQ':
        rcode=["SUB","ISZERO"]
        for x in rcode:
            ncodes.append((lnid,x))
    else:
        ncodes.append((lnid,lnc))
codes=ncodes

ncodes=[]
for i in range(len(codes)):
    lnid=codes[i][0]
    lnc=codes[i][1]
    if lnc in ['SUB','DIV','MOD']:
        rcode=genswap(1)+[lnc]
        for x in rcode:
            ncodes.append((lnid,x))
    else:
        ncodes.append((lnid,lnc))
codes=ncodes

codes=[(-1,"NOP")]+codes

#for x in codes:
#    print(x)

jmpdsts={}
jmpdstsR={}

for i in range(len(codes)):
    lnid=codes[i][0]
    lnc=codes[i][1]
    if lnc=='JUMPDEST':
        jmpdsts[lnid]=i
        jmpdstsR[i]=lnid

ncodes=[]

for i in range(len(codes)):
    lnid=codes[i][0]
    lnc=codes[i][1]
    if lnc[:5]=='JUMP ':
        hh=int(lnc.split(' ')[1])
        if hh==INPUT_ADDR:
            ncodes.append(("INPUT",))
        elif hh==OUTPUT_ADDR:
            ncodes.append(("OUTPUT",))
        else:
            nhh=jmpdsts[hh]
            ncodes.append(("JUMP",nhh))
    elif lnc[:6]=='JUMPI ':
        hh=int(lnc.split(' ')[1])
        nhh=jmpdsts[hh]
        ncodes.append(("JUMPI",nhh))
    else:
        pcx=lnc.split(' ')
        if len(pcx)>1:
            pcx[1]=int(pcx[1]) 
        ncodes.append(tuple(pcx))
codes=ncodes

ALLOW_OPC=["MODEC","PUSHV","PUSHS","POP","DUPS","SWAPS","ADD","MUL","DIV","MOD","SUB","ISZERO","JUMP","JUMPI","JUMPDEST","INPUT","OUTPUT"]
IGNORE_OPC=["NOP"]
HALT_OPC=["JUMP?"]

ncodes=[]
for i in range(len(codes)):
    lnc=codes[i][0]
    if lnc in ALLOW_OPC:
        ncodes.append(codes[i])
    elif lnc in IGNORE_OPC:
        ncodes.append(("NOP",))
    elif lnc in HALT_OPC:
        ncodes.append(("STOP",))
    else:
        #ncodes.append(codes[i])
        ncodes.append(("STOP",))
        print(("Unknown opcode at line %d: "%i)+lnc,file=sys.stderr)

codes=ncodes

for x in codes:
   print(x)

print("CALC %d"%jmpdsts[CALC_ADDR])
print("INPUT %d"%jmpdsts[INPUT_ADDR])
print("OUTPUT %d"%jmpdsts[OUTPUT_ADDR])

for nl,ol in jmpdstsR.items():
    print("JUMPDEST %d:[email protected]%d"%(ol,nl))

#x:0-255
#y:1-254
#z:252
#z0: __start
def getpos(lns):
    lnid=lns//254
    lnxx=lns%254+1
    if lnid%2==1:
        lnxx=255-lnxx
    return (lnid,lnxx)
def getline(x,y):
    lnid=x
    lnxx=y
    if lnid%2==1:
        lnxx=255-lnxx
    return lnid*254+lnxx-1

jmppos=set()
hdt=250
jmdstdepth={}

maps={}

for i,x in enumerate(codes):
    if x[0] in ["JUMP","JUMPI","JUMPDEST"]:
        jmppos.add(i)
        if x[0]=="JUMPDEST":
            jmdstdepth[i]=hdt
            hdt-=1

for ln,dp in jmdstdepth.items():
    print("JUMPDEST line %[email protected]%d"%(ln,dp))

pfxx={(1,0):ord('>'),(-1,0):ord('<'),(0,1):ord('v'),(0,-1):ord('^')}
dfsvis=set()
def dfs(sx,sy,tx,ty,dep,ste=False):
    global dfsvis
    if (sx,sy)==(tx,ty):
        return True
    if sx<0 or sy<0 or sx>=255 or sy>=255 or (sx==0 and sy==0):
        return False
    if sy>=1 and sy<=254 and (getline(sx,sy) in jmppos) and ste==False:
        return False
    fod=[]
    sod=[]
    if sx<tx:
        fod.append((1,0))
        sod.append((-1,0))
    else:
        fod.append((-1,0))
        sod.append((1,0))
    if sy<ty:
        fod.append((0,1))
        sod.append((0,-1))
    else:
        fod.append((0,-1))
        sod.append((0,1))
    fod=fod+sod
    for ndir in fod:
        nx=sx+ndir[0]
        ny=sy+ndir[1]
        if (nx,ny) in dfsvis:
            continue
        dfsvis.add((nx,ny))
        res=dfs(nx,ny,tx,ty,dep)
        dfsvis.remove((nx,ny))
        if res:
            maps[(sx,sy,dep)]=pfxx[ndir]
            return True
    return False

def genpath(sx,sy,tx,ty,dep):
    global dfsvis
    dfsvis=set([(sx,sy)])
    for i in range(dep+1,252):
        maps[(sx,sy,i)]=ord(']')
    dfs(sx,sy,tx,ty,dep,True)
    for i in range(dep,252):
        maps[(tx,ty,i)]=ord('[')

dirc=1
nposx=0
nposy=0

#["MODEC","PUSHV","PUSHS","POP","DUPS","SWAPS","ADD","MUL","SUB","ISZERO","JUMP","JUMPI","JUMPDEST","INPUT","OUTPUT"] STOP NOP
opsx={"MODEC":ord('"'),"POP":ord("$"),"DUPS":ord(":"),"SWAPS":ord("\\"),"ADD":ord("+"),"MUL":ord("*"),"SUB":ord("-"),"DIV":ord("/"),"MOD":ord("%"),"ISZERO":ord("!"),"INPUT":ord("~"),"OUTPUT":ord("."),"STOP":ord("@")}


for i in range(255):
    maps[(0,0,i)]=ord('[')
stx,sty=getpos(jmpdsts[CALC_ADDR])
for i in range(stx):
    maps[(i,0,255)]=ord('>')
for i in range(sty):
    maps[(stx,i,255)]=ord('v')

maps[(stx,sty,255)]=ord(']')
maps[(stx,sty,254)]=ord(']')
maps[(stx,sty,253)]=ord(']')


for i,x in enumerate(codes):
    nposy+=dirc
    if nposy==0:
        maps[(nposx,nposy,252)]=ord('>')
        maps[(nposx+1,nposy,252)]=ord('v')
        nposy=1
        nposx+=1
        dirc=1
    elif nposy==255:
        maps[(nposx,nposy,252)]=ord('>')
        maps[(nposx+1,nposy,252)]=ord('^')
        nposy=254
        nposx+=1
        dirc=-1
    if x[0] in opsx:
        maps[(nposx,nposy,252)]=opsx[x[0]]
        continue
    if x[0]=="PUSHS":
        maps[(nposx,nposy,252)]=x[1]+48
        continue
    if x[0]=="PUSHV":
        maps[(nposx,nposy,252)]=x[1]
        continue
    myd='v' if dirc==1 else '^'
    if x[0] in ["JUMPDEST","NOP"]:
        maps[(nposx,nposy,252)]=ord(myd)
        continue
    if x[0]=='JUMP':
        maps[(nposx,nposy,252)]=ord(']')
        tx,ty=getpos(x[1])
        genpath(nposx,nposy,tx,ty,jmdstdepth[x[1]])
        continue
    if x[0]=='JUMPI':
        maps[(nposx,nposy,252)]=ord('#')
        tx,ty=getpos(x[1])
        genpath(nposx,nposy,tx,ty,jmdstdepth[x[1]])
        maps[(nposx,nposy,253)]=ord(myd)
        maps[(nposx,nposy+dirc,253)]=ord(']')
        continue
    assert(False)

f=open("code.txt","w")

for k,v in maps.items():
    print(("(%d,%d,%d)->"%k)+str(v),end=' ')
print("END")

for k,v in maps.items():
    print(("(%d,%d,%d)->"%k)+str(v),end=' ',file=f)
print("END",file=f)
f.close()
    #print(x[0])
#print(maps)
# print(genpush(5))
# print(genpush(60))
# print(genpush(200))
# print(genpush(114514))
# print(genpush(34))
# print(genpush(34*255+34))
# print(gendup(3))

0x17 p😭q

观察一下程序,这题就是把一个音乐的mel频谱生成了一个gif之后输出,要求你拿到原始音频。

从gif拿到原始mel频谱比较简单。从mel恢复波形,通过搜索发现librosa库本身就提供了一个。从示例文档中直接复制代码即可恢复wav(亏我还看了半天怎么用sft手动恢复)。

这题注意头疼在调用各种API需要不断查文档上。

#!/usr/bin/env python3

#from array2gif import write_gif  # version: 1.0.4
import librosa  # version: 0.8.1
import numpy  as np
import imageio
from PIL import Image
import soundfile as sf

sample_rate=22050

#fs=imageio.get_reader('test1.gif')
fs=imageio.get_reader('flag2.gif')
num_freqs = 32
quantize = 2
min_db = -60
max_db = 30
fft_window_size = 2048
frame_step_size = 512
window_function_type = 'hann'
red_pixel = [255, 0, 0]
white_pixel = [255, 255, 255]

pp=[]


for x in fs:
    oo=np.zeros(num_freqs,dtype=np.int8)
    for i in range(num_freqs):
        tkv=min_db
        pts=quantize*(1+2*i)
        ih=0
        for th in list(range(min_db, max_db + 1, quantize))[::-1]:
            py=ih*2
            ih+=1
            if x[py][pts][1]==0:
                tkv=th+2
                break
        oo[i]=tkv
    pp.append(oo)

gg=np.array(pp)
gg=gg.T

print(gg.shape)
np.set_printoptions(threshold=114514)

emm=librosa.db_to_power(gg)
S=librosa.feature.inverse.mel_to_stft(emm, n_fft=fft_window_size)
yy=librosa.griffinlim(S)

sf.write("flag.wav", yy, sample_rate)

0x18 超 OI 的 Writeup 模拟器

听说这题要逆向一堆文件后,我提前看了看后边的,发现还是angr一把梭好。于是直接使用angr来找输入。当然对于第三关的部分angr就做不了了。

在用angr的时候,我最开始没限制输入长度,导致找解一度十分缓慢。最终经过查询把限制加上了,出解只需要十来秒。

(提交答案时5s一个太痛苦)

import angr
import claripy

res=[]

for i in range(16):
    flag = claripy.BVS('flag', 8*17)
    proj = angr.Project("./files/%d.bin"%i)

    st= proj.factory.entry_state(stdin=flag)
    sm = proj.factory.simgr(st)
    sm.explore(find=lambda s: b"Correct" in s.posix.dumps(1))
    print(sm.found[0].posix.dumps(0))
    res.append(sm.found[0].posix.dumps(0))
    print(res)

print("\n".join(res))

0xFF 感想

题出的好!难度适中,覆盖知识点广,题目又着切合实际的背景,解法比较自然。给出题人点赞!

可惜今年这段时间太忙,不然至少拿个rank3还是没问题的。

明年一定再来。

日期: 2021-10-31

标签: CTF