ranwen's blog

随便写写

USTC Hackergame 2022 真划水记

目录

这一段时间是真的非常忙:各种期中考试和作业DDL什么的都堆在一起了。因此今年也主要是参与图一乐了,总共应该打了十多个小时的样子,至少达到了两位数排名的目标了。有很多题看都没看,附件也都没下载,甚至代码都不想写(其实还是有不少题会做但是不想写代码的),除了第一天以外只有最后一天写了写比较长的代码。这次WP也就是随便写一写了,主要写一些想法而不是答案和具体做法什么的。

0x00 签到

随便试一试,F12打开Network看看请求,发现是直接请求的前端识别结果。手动修改一下然后访问就行了。

0x01 猫咪问答喵

反正会提示你对了几道题,题目挨个尝试枚举看有没有多做对题就好了。

对于第一题,可以随便找到一个早期成员,是17年加入的,在日期附近试一试就好了。

对于第二题,容易找到一个B站直播链接,猜测也有B站录播,找到 https://www.bilibili.com/video/BV11e411M7t9 后看看就行了。

对于第三题,随便试试就好了。

对于第四题,按照CVE编号搜索commit,很容易搜到。

对于第五题,把文本原样复制到Google就可以搜出来一个IP,访问一下这个IP就能看到主页,拿到域名。

对于第六题,找不到相关内容,但是找到了 http://wlt.ustc.edu.cn/cgi-bin/ip 。常见问题里面有一个日期。可以猜测相关规定实施日期一定是月初或者月末,写个脚本试一下好了。

0x02 家目录里的秘密

第一问直接在文件夹里面grep就能拿到flag了。

看一下第二问文件,应该是要反混淆rclone的密码obfs。上网搜索容易找到文件 https://github.com/rclone/rclone/blob/master/fs/config/obscure/obscure.go 。这里面自带了解混淆函数,调用一下就好了。

0x03 HeiLang

写个脚本做一下字符串替换,之后直接运行即可。

0x04 Xcaptcha

手动点一点,从Network里面可以找到发送的包,格式很简单。直接copy as fetch后,从题目网页中提取算式后直接eval就可以得到结果,然后粘贴到第二段fetch的参数中即可。注意eval的时候要把数字先转成BitInt。

0x05 旅行照片 2.0

第一问随便找个EXIF读取工具就能全部做出来了。

第二问比较复杂。

球馆正门的文字还是比较清楚的,结合一点点模糊搜索容易找到地点为千叶海洋球场。用Google Map就能找到邮政编码。

EXIF信息里面有处理器型号,结合处理器型号很容易找到红米的相关机型,得到分辨率。

航班用flightradar24的playback功能即可,非常准确(就是得开试用比较烦),以及结合拍照方向,注意到照片中飞机的方向应该是朝北飞的。

这题比较坑的主要在于,日本邮政编码单位还挺小的,拍照可能地点的周围那一片有好几个邮政编码,可以试一试。

0x06 猜数字

看到题猜到出题人(确信)。

第一感觉还以为是个随机数crack,再一看用得这个似乎不太能crack。结合一下题目位置什么的,更不可能了。

看一下源码,拿到flag当且仅当某次猜数一次猜中,即isTalented=1。这也对应着isPassed=1和该次没有其他猜数。

isPassed=1(guess < this.number)==false(guess > this.number)==false。显然已经有答案了,直接喂一个NaN即可。

注意这个后端对NaN写法还是比较敏感的,也需要手造一下请求。

0x07 Flag 的痕迹

随便点点,发现该题把历史记录列表关了。参照一下原版Dokuwiki,改一改url,容易发现历史版本还是可以访问的,只是No such revision。因此我们只需要找到这个版本就行。

因此开始看源码,主要看两个内容:版本号如何生成(其实容易直接看出来是时间戳之类的),以及有没有其他地方也有版本号列表。

https://github.com/splitbrain/dokuwiki/blob/1287b4f5b9e6e23d2610137b3ce4fc420415ea70/inc/Ui/PageRevisions.php 的源码,容易发现版本号rev就是时间戳。此时已经可以直接大力枚举时间戳了,但不好。显然查看历史版本的函数是getRevisions,直接在GitHub上点开就能找到所有ref。看看有哪些地方用了,能利用的地方看起来有:feed, Changelog, Diff。看起来Diff就好使,因此再在原版dokuwiki上随便点点,发现和上一个版本diff只需要当前的版本号,dokuwiki会自动找到上一个版本的版本号(更进一步地,直接删掉当前版本号也会被自动填充为最新版本)。因此我们直接访问题目页面的diff页,就可以找到所有版本的diff了,进而拿到flag。

0x08 线路板

下载一个KiCad套件(这玩意挺大,最开始想找替代,但是都不好使)。之后里面自带了一个gbr viewer。点开后容易看到flag,但是被几个圆圈挡住了。随便点点发现这个圆圈确实是独立的元件,但也确实没法移除。再检查软件UI发现,viewer自带了一个导出为KiCad可编辑电路板形式的功能,因此直接把他导出为可编辑电路板,之后在另一个软件随便点点就能找到flag。

0x09 Flag 自动机

作为一个完全不会二进制的人,其他题看都不想看。这题也只是看过的人多了才去看的。

打开程序,显然只需要点击按钮即可,但是点不了。打开IDA,strings里面有个flag_machine.txt,找到ref,发现这个地方明显是输出flag的地方。同时简单看一下这个大函数的样子,猜测这个函数是处理窗口事件的。

由于我也懒得去打patch,所以直接开了IDA调试,在这个函数里面下个断点。点击退出按钮,会跳转到处理按钮点击的那个switch下,而此时我们只需要修改a3和lparam为指定的值即可跳转到输出flag的地方了。因此慢慢单步执行,同时在对应位置修改内存就行了。

0x0A 微积分计算小练习

看看源码,直球XSS题。简单点开网页随便写点答案看看源码。使用innerHTML将URL中的result base64解码后塞入标签了。显然这块有注入点。注意innerHTML直接注script的话是不能自动执行的(因为网页已经加载完了),随便用个什么img的onerror就能执行了。

本来想试试这题能不能传出连接,结果不行,正想应该怎么传出结果,突然发现可以直接alert打出log。

payload:

btoa("0:lol<img src=a onerror='alert(document.cookie);'>")
/share?result=MDpsb2w8aW1nIHNyYz1hIG9uZXJyb3I9J2FsZXJ0KGRvY3VtZW50LmNvb2tpZSk7Jz4=

0x0B 不可加密的异世界

挺有意思的题。经典分组加密。

第一问要求明文和密文相等,可以控制分组加密方式,以及(部分)明文、key、IV。显然我们知道有的分组加密方式是直接将明文密文异或一下的。例如CFB和OFB模式,都是将Enc的输出直接异或明文得到密文的。因此我们只需要让Enc的输出为0即可保证明文等于明文。随便掏出一个key,将全0跑一下Dec就能得到需要的IV了。

import os
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
from magic_box import *

algo="AES"
mode="OFB"
blocksize=16

payx="Open the door!".encode()
payx=pad(payx,16)

print(payx)

xk=os.urandom(2*16)
tbx=Magic_box(algo,"ECB",xk[:16])
niv=tbx.auto_dec(b"\x00"*16)

xu=xk[:16]+niv

nbx=Magic_box(algo,mode,xu)
ntc=nbx.auto_enc(payx)
print(ntc)

print(xu.hex())

第二问要求将一个很长的随机信息全部加密,之后某个特定块位置的明文和密文相等,仍然可以控制key和IV。显然这思路和上一问一样。简单一点采用OFB模式,则要求特定位置Enc的输出为0,进而可以使用Dec算出特定块的Enc输入。而OFB中下一个块Enc的输入恰好是上一个块Enc的输出,因此可以简单地逐块递推,得到IV。

import os
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.Util.Padding import pad, unpad
from magic_box import *

algo="AES"
mode="OFB"
blocksize=16

payx=bytes.fromhex("114514")
payx=pad(payx,16)

for nt in range(10):
    xk=os.urandom(2*16)
    tbx=Magic_box(algo,"ECB",xk[:16])
    lasm=b"\x00"*16
    for j in range(nt+1):
        lasm=tbx.auto_dec(lasm)
    xu=xk[:16]+lasm
    nbx=Magic_box(algo,mode,xu)
    ntc=nbx.auto_enc(payx)
    #print(ntc[nt*16:(nt+1)*16],payx[nt*16:(nt+1)*16])
    print(xu.hex())

第三问鸽了没做。要求原文两次加密后和密文相同,同时只能控制明文,key是通过明文的可逆变换(crc)得到的,IV随机。明文至少要有16个字节。

其实这块思路有两种。一种是仍然利用分组加密的方式。第二次加密时使用的IV,正好是第一次加密时剩余的变量,这个性质很好。在原文只有一个块的时候(由于长度限制,这意味着只能使用AES算法),能推出很多看着非常好看的关系。例如CBC模式下,第二次加密的IV正好是第一次加密的密文,因此可以得到等式Enc(key,0)=plain;OFB模式下,经过多次化简可以得到等式Enc(key,iv)=iv。这两个式子都很好看,然而并没有什么卵用。第一个式子需要将plain和key的关系带入,然而这样AES就很难分析了;第二个更是要求存在一个key使得加密无效,看着就不正常。另外在有两个块的时候就没有非常好看的性质了,不好。

另一种思路是利用DES CBC的弱点。众所周知DES都不知道被干了多少次了。其中一个点就是DES存在一些weak key,使得以这些key作为密钥时加密的信息会有奇妙的性质(比如之前看的有一个key会有2^32个不动点)。当然,这些性质还得查一查。当时没仔细去查(当时分别查了double des和des weak key,实际上两个放一块就能得到结果了),还以为最终会表现为一个奇怪的关系(当时看到key只用了8位,因此每个key还会对应2^64种明文,还可以随着明文长度变长变多,我当时怀疑是像不动点那样有条件的),也不想研究就咕了。后来发现原来对于所有输入直接就能输出id。因此直接拿这个weak key,倒推逆出明文即可。当然其实也不用逆,直接扔进z3就行了。

0x0C 置换魔群

挺有意思的题,把置换群拿来出题了。不过对于对群论有一定了解的人来说都不难。

显然,这一个大的置换可以分为多个小的置换(对应代码中的标准形式),每个置换构成一个环。每做一次置换,相当于每个环中的元素都沿着环边前进一步。显然每个环会以环长循环,进而整个置换的阶就是所有环长的LCM。

对于第一问,模仿了RSA的计算。重复做了e次置换,相当于每一个环中的元素都前进了e步,考虑这个前进过程构成的新环,由于大指数步数e和环长必然互质,因此新环长度和旧环长度一样。也就是说e次方不改变置换群的阶。因此我们拿到这个c后求一下阶order,参照RSA的方式,求一下e关于order的逆d,将密文置换再做d次幂就可以得到原文了。

from concurrent.futures import process
from pwn import *
import time
from permutation_group import permutation_element, permutation_group
import gmpy2

def s2n(x): return [int(x) for x in re.findall(r"\-?\d+\.?\d*", x)]

s=remote('202.38.93.111',10114)
s.sendline(b'TOKEN')
time.sleep(2)
s.sendline(b'1')

for i in range(15):
    s.recvuntil(b'RSA public key:')
    s.recvuntil(b'n =')
    n=int(s.recvuntil(b', e =',drop=True))
    e=int(s.recvline())
    print(n,e)
    s.recvuntil(b'here:')
    s.recvline()
    c=str(s.recvline())
    c=s2n(c)
    print(c)

    elc=permutation_element(n,c)
    ord=elc.order()
    d=gmpy2.invert(e,ord)
    sc=elc**d
    assert sc**e==elc
    pay=str(sc)
    s.sendline(pay.encode())

s.interactive()

对于第二问,要求一个置换群上的离散对数问题。其实题目已经提示很明显了,置换群的阶是很光滑的。而对于光滑阶的离散对数是很简单的。当然,这一题有比直接用光滑离散对数求解更好理解的方法(但本质其实是一样的)。我们可以发现,置换操作时,每个小环是独立的。而每个小环的阶只有他的长度那么大,是很小的。我们可以把所有小环单独挑出来,通过枚举的方式,得到某个特定小环,在基g对应小环上是多少次方。而总次数和小环的次数是相等的(在对小环的阶取模后),因此每个小环都能得到一个关于总次数的同余式,进而使用中国剩余定理即可求解。

from concurrent.futures import process
from pwn import *
import time
from permutation_group import permutation_element, permutation_group
import gmpy2
from crt import *

def s2n(x): return [int(x) for x in re.findall(r"\-?\d+\.?\d*", x)]

def subeq(seq1,seq2,subs):
    for x in subs:
        if seq1[x-1]!=seq2[x-1]:
            return False
    return True

s=remote('202.38.93.111',10114)

s.sendline(b'TOKEN')

time.sleep(2)
s.sendline(b'2')

for _ in range(15):
    s.recvuntil(b'DH public key: n = ')
    n=int(s.recvuntil(b', g =',drop=True))
    gs=s2n(str(s.recvline()))
    print(n,gs)
    s.recvuntil(b'my public key = ')
    cs=s2n(str(s.recvline()))
    print(cs)

    c=permutation_element(n,cs)
    g=permutation_element(n,gs)
    stg=g.standard_tuple
    ts=len(stg)
    mxod=max([len(x) for x in stg])
    tar=[None]*ts
    print(ts,mxod)
    px=g
    for i in range(1,mxod+1):
        for j in range(0,ts):
            if subeq(c.permutation_list,px.permutation_list,stg[j]):
                tar[j]=i%len(stg[j])
        px=px*g
    pa=[]
    for i in range(ts):
        assert tar[i]!=None
        pa.append((len(stg[i]),tar[i]))
    print(pa)
    sec=crt(pa)
    assert g**sec==c
    print(sec)

    s.sendline(str(sec).encode())

s.interactive()

对于第三问,显然做法和第二问一模一样。唯一不同的区别是,你需要指定两个基g1和g2,同时私钥会非常大。显然我们利用中国剩余定理的方法,将g1和g2的结果合并,可以得到次数对LCM(g1.order,g2.order)取模后的结果。因此我们只需要构造g1和g2,使得这个数足够大,比私钥的上界大即可。由于使用的LCM,因此我们希望每个环的长度都是互质的。同时环长的总和即为置换的大小n。显然如果一个环长能分解成两个互质的乘积,那么分解一定更好,即元素一定是质数(或其的幂)。即我们将这些元素分出两组,这两组的和不超过n,其乘积最大即可。一个比较简单的做法是直接贪心从小到大分每个质数,对边界可以稍微优化一下,我写了个python代码试了一下发现差得还挺远的(平均能差几十倍)。一个必然能求出最优解的做法是写一个背包类似物:以两组数中当前和为下标,值为所有数的乘积(的对数)。数字的和在1000左右2000以内的范围,而可能成为元素的数字都为小于200的质数(或其的幂),这总共大约一亿次的计算量,写python肯定不行了,还得写数据交互,所以咕咕了。

0x0D 光与影

经典GL题。打开后F12看看加载的文件列表,瞅瞅资源文件是哪个。显然fragment-shader.js有大量的重复性的信息。

稍微再看一下,都在一个t*SDF的函数内,每个重复单元都是一个顶点与变量的距离对0.4取差,最后取min。结合画面中出现的flag都是点状的,合理猜测这些函数是描绘这些flag点的,每一个小圆对应一个单元。

再看一下调用这些函数的地方sceneSDF,发现只有t5长得和别人不一样。简单看一下,看起来就像个矩形。因此可以先把t5删掉看看。

比较省事的做法是,直接把网页ctrl+s保存下来,之后修改相关js,而且只需要把t5改成t4就行(毕竟最后是取min,只改一个字符好)。打开网页后得到flag。

0x0E 链上记忆大师

经典链题。第一问没啥意思,随便写写solidity就行了,而且看着就是第三问的子集,不如不做。

关于第二问,如果看过mcfx在去年Hackergame的链上预言家-预测未知的题解,就很容易想到这题的做法:利用gas携带信息。具体地,在memorize的时候执行n次循环,之后在recall部分的剩余gas应该和n是线性相关的。

在具体写的时候,注意到call执行的gas是有上限的,如果每次循环消耗的gas太多可能会超过geth的执行上限(例如本题使用的新版solidity如果不套uncheck不检查越界那么消耗的gas还是挺多的),因此此处我使用Yul实现了。同时为了避免环境差异出事(其实是不必要的),我只是用了gas的低22位,并在执行循环前使得低22位尽量为全0,进而达到对齐的效果。剩下只需要写recall部分即可。我们可以先让recall返回gas而不是value,调用不同的n来观察一下线性参数。

但是在调用的时候,又遇到了坑:从小数字递增增长,发现根本不是等差数列;如果直接用两个大数字做差,发现每单位消耗gas完全不是整数。这太怪了,于是大力trace一下,回去仔细看gas计算规则。看记录,发现调用call后剩余gas和调用call前的限制gas完全不一致,读到AA-F可以发现内部的gas少了1/64,因此要还原调用上层的gas应该再加回去(常数gas消耗不重要)。加上后,发现在某些地方还是不够等差,简单尝试一下可以发现和n中含00字节的个数有关,这个很好理解,00消耗的gas会少一些。只要意识到这个问题后,就不重要了,因为显然大部分的数字都不会含有00,我们只需要拿这些数字(比如0x0101和0xffff)去拟合参数就好了。之后可以得到线性参数。

contract solve {
    function memorize(uint16 n) external
    {
        while(((gasleft()>>2)&((1<<20)-1))!=0){}
        assembly
        {
            for { let i := 0 } lt(i, n) { i := add(i, 1) }
            {
            }
        }
    }
    function recall() external view returns (uint256)
    {
        unchecked
        {
            uint x=gasleft();
            uint jx=(x*64/63)&((1<<22)-1);
            uint sb=((0x1765df+(1<<22)-jx+20)&((1<<22)-1))/51+0x101;
            sb=sb&((1<<16)-1);
            return sb;
        }
    }
}

再看第三问。显然受第二问启发,尽管用了view后调用staticcall不能改变链上数据,但是可以改变tx执行时状态。如果仔细读了gas的文档,很容易看到EIP-2929的相关内容:相同的存储位置,在同一个tx内(而不是call,这很好)多次访问,后续访问算热访问,消耗的gas比冷访问低。因此思路就很简单了:memorize时,根据n每个bit的值读取存储,之后在recall时再次枚举每一位读取存储并衡量消耗的gas,来判断这一位是0或1。为了保证测量准确,我还写了Yul(实际上没什么必要,因为冷热访问差距挺大的)。

contract solve {
    function memorize(uint256 n) external view
    {
        for(uint i=0;i<256;i++)
        {
            uint x=(n>>i)&1;
            uint v=0;
            if(x==1)
            {
                assembly
                {
                    v:=sload(i)
                }
            }
        }
    }
    function recall() external view returns (uint256)
    {
        uint r=0;
        for(uint i=0;i<256;i++)
        {
            uint bef=0;
            uint aft=0;
            assembly
            {
                bef:=gas()
                let v:=sload(i)
                aft:=gas()
            }
            uint det=bef-aft;
            if(det<2100)
            {
                r+=1<<i;
            }
        }
        return r;
    }
}

0x0F 量子藏宝图

量子题,慢慢玩。

第一问量子通讯,这个我(大概)会!无脑发送一组相同的基和量子态就行。这块我发了一串+和0。之后收到的状态中,我也不知道啥对应啥(也懒得查),但是肯定是某一类被丢弃,另外一类为0或1,随便试试,发现是x丢弃,+对应0。

第二问量子电路,这个我真不会。只能找规律,发现电路大部分连线都非常简单,怀疑是不是大部分位都可以直接按字节对应到flag上。从下往上读每一条横线,看看有没有竖线构成的节点,如果有则为1,否则为0,发现前几位flag的ASCII都能对上,而且看起来还是有一点量子门的,因此怀疑这个电路可能没什么用,纯找规律(所以过了一串人)。于是按照猜测的规则把所有位都写出来了,提交后flag正确。

0x10 企鹅拼盘

电路题,好。

第一问随便玩玩(第一天还莫名其妙没玩出来,不懂),直接在GUI上尝试所有情况,拿到flag。

后面几问都没做,虽然有点想法,但看起来还是有点麻烦。首先能观察到每次操作空块都在右下角,也就是说剩余的15块正好是个置换。有结合无交换,好。再观察第一问的文件,发现虽然每一位出现时操作不一样,但是似乎有部分置换是一样的(我没完整检验,咕了)。而看比较复杂的文件的位出现顺序,看起来非常有规律。而每一步是两个置换中选一个相乘,这看着就像我之前在知乎的某篇介绍iO的文章中看到的MBP的电路表示方法(虽然我也没有去检验)。不过后面我就不会了,所以这题也没动力去学,更没动力去做了(看题解发现出题idea来自iO还是感觉挺有意思的,以及没想到是构造了一个比较简单的电路)。最后就咕咕了,第二问也懒得写代码试了(反正能保前100了)。

0xFF 感想

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

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

明年一定再来。

日期: 2022-10-29

标签: CTF