2021-10-29发表2021-10-29更新Writeup22 分钟读完 (大约3229个字)0次访问

「Hackergame 2021」#3 Writup 持续破防篇 0

完成了前面两篇说到的那些题后，剩下的就开始反复折磨我了qwq
每天基本都肝到一点左右，甚至四五个小时毫无成果_(´ཀ`」 ∠)__
其中有些题回过头来看其实很简单，但是做的时候就是死活想不出来（

这篇 Writeup 里面有：Amnesia1、RSA、LUKS、MicroWorld

Amnesia

轻度失忆

你的程序只需要输出字符串 Hello, world!（结尾有无换行均可）并正常结束。

编译指令：gcc -O file.c -m32

运行指令：./a.out

编译后 ELF 文件的 .data 和 .rodata 段会被清零。

ELF（Executable and Linkable Format）是 Linux 下常用的可执行文件格式，其中有很多不同的节：

.text 节：程序运行需要的代码
.data 节：存放可修改的数据，一般是非 const 全局变量和静态变量
.rodata 节：即 read only data，一般是常量或者字符串
.bss 节：没有被初始化的变量
……

而这道题目则是在编译生成可执行文件 a.out 后，清空 .data 和 .rodata
首先不妨正常编写一个输出 “Hello, world!” 的程序：

1	printf("Hello, world!\n");

然后编译，再拖到 IDA 里

可以发现，此时的 “Hello, world!” 被放到了 .rodata 节中，会被清除掉，所以这样写不行

直接使用字符串会被放到 .rodata 中清除，写成全局变量又会放到 .data 中
但是，如果写成局部变量呢：

1 2	char str[] = "Hello, world!\n"; printf(str);

编译，拖到 IDA 里

可以看出，这次的字符串直接写到了 .text 节中，删掉了 .data .rodata 也没有影响
所以把这个代码交上去就可以输出 “Hello, world!“ 拿到 flag 了

清除记忆直接把 .text 节全删掉了，想了很久也不知道咋搞，虽然可以 __attribute__ ((section (“…”))) 来把函数或变量塞到指定的节中。但还是不清楚要怎么解决段错误的问题qwq

Easy RSA

自从 Hackergame 2018 公然揭露了大整数可以被神童口算分解的事实，RSA 在 hackergame 中已经只能处于低分值的地位了。如果不在其名称前面加上 Easy 这个单词，似乎就会显得完全对不起其他题目。

更何况，在本题的附件中，你还获得了构造 p 和 q 的方式。数理基础扎实的你应该可以轻松解决这些问题吧。

~~谢邀，没有数理基础~~

看代码！

e = 65537

def get_p():
    x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
    y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
    value_p = sympy.nextprime((math.factorial(y)) % x)  # Hint：这里直接计算会溢出，请你仔细观察 x 和 y 的特征
    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
    n = 1
    for i in range(10):
        n = n * value[i]
    q = getPrime(512)
    value_q = pow(q, e, n)
    print("value_q = ", value_q)
    # value_q = 5591130088089053683141520294620171646179623062803708281023766040254675625012293743465254007970358536660934858789388093688621793201658889399155357407224541324547522479617669812322262372851929223461622559971534394847970366311206823328200747893961649255426063204482192349202005330622561575868946656570678176047822163692259375233925446556338917358118222905050574458037965803154233167594946713038301249145097770337253930655681648299249481985768272321820718607757023350742647019762122572886601905212830744868048802864679734428398229280780215896045509020793530842541217790352661324630048261329493088812057300480085895399922301827190211956061083460036781018660201163819104150988531352228650991733072010425499238731811243310625701946882701082178190402011133439065106720309788819
    return sympy.nextprime(q)

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

m = int.from_bytes(open("flag.txt", "rb").read(), "big")
c = pow(m, e, p * q)
print("c = ", c)
# c = 110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478

可以看到，其中要解决的就是 get_p() 中 y! % x 溢出的问题，以及 get_q() 中 q 是哪个随机的512位质数的问题

get_p

代码里也给了 Hint，观察 x 和 y 的特征。x 和 y 都很大，但是两个的差并不大；而且可以丢到 python 里验证出 x 是一个质数
所以可以使用威尔逊定理
也查到了威尔逊定理在 RSA 题目中的应用：BUU-RSA [RoarCTF2019]babyRSA

要求 y! % x（x是质数）
根据威尔逊定理，有

$$
(x - 1)! \equiv -1\pmod{x}
$$

所以：

$$
y!\times \frac{(x - 1)!}{y!}\equiv -1\pmod{x}
$$

令 $k = \dfrac{(x - 1)!}{y!} = (y+1)(y+2)…(x-1)x$ ，所以有：

$$
y!\equiv -\mathrm{inv}(k, x)\pmod{x}
$$

（其中 $\mathrm{inv}(k, x)$ 表示模 x 下 k 的逆元）
所以重写 get_p() 即可正确的得到 p：

def get_p():
    x = ...
    y = ...
    k = 1
    for i in range(y + 1, x):
        k = (k * i) % x 
    res = (-gmpy2.invert(k, x)) % x 
    return sympy.nextprime(res)

get_q

相比来说，get_q 就没那么需要技巧了
给出了 value[-1] 的值，所以可以直接用 sympy.prevprime 逆推出整个 value 数组

value = [80096058210213458444437404275177554701604739094679033012396452382975889905967]
for i in range(1, 10):
    value.append(sympy.prevprime(value[i - 1]))
print("value[-1] = ", value[-1])

后面计算 value_q 细看其实也是一个 RSA 算法：

q：密文
e：私钥
value_q：明文
n：就是 n，只不过不是两个质数相乘，是十个质数相乘

十个质数相乘得到 n 的 RSA 算法也一样，因为 RSA 的正确性并没有要求 n 一定是两个大质数相乘，这样只是难以破解保证安全性
解决这个同样也是需要公钥 d，所以需要 phi(n)
根据欧拉函数的性质，phi(n) 等于 n 的所有质因数减一的积
即 phi(n) = (value[0] - 1) * (value[1] - 1) * … * (value[9] - 1)

再解密即可得到密文 q，然后也就得到了 get_q 的结果

n = phi = 1
for i in range(10):
    n = n * value[i]
    phi *= (value[i] - 1)

value_q = ...
d = pow(e, -1, phi) 
q = pow(value_q, d, n)
return sympy.nextprime(q)

flag

搞定了 get_p 和 get_q 之后就可以直接解出 flag 了：

e = 65537
p = get_p()
q = get_q()

c = ...
d = pow(e, -1, (p-1) * (q-1))
m = pow(c, d, p * q)

print(int.to_bytes(m, 30, byteorder="big"))

加密的 U 盘

（本来挺好做的一道题，怎么题给的提示我就硬是没领会到）

这是一个关于 LUKS (Linux Unified Key Setup) 的故事。

第一天
小 T：「你要的随机过程的课件我帮你拷好了，在这个 U 盘里，LUKS 加密的密码是 suijiguocheng123123。」
小 Z：「啊，你又搞了 Linux 文件系统加密，真拿你没办法。我现在不方便用 Linux，我直接把这块盘做成磁盘镜像文件再回去处理吧。」

第二天
小 Z：「谢谢你昨天帮我拷的课件。你每次都搞这个加密，它真的安全吗？」
小 T：「当然了！你看，你还给我之后，我已经把这块盘的弱密码改掉了，现在是随机生成的强密码，这样除了我自己，世界上任何人都无法解密它了。」
小 Z：「我可不信。」
小 T：「你不信？你看，我现在往 U 盘里放一个 flag 文件，然后这个 U 盘就给你了，你绝对解密不出来这个文件的内容。当初搞 LUKS 的时候我可研究了好几天，班上可没人比我更懂加密！」

一共给了两个 img 文件，通过 file 可以看出都是 DOS/MBR boot sector

1
2
3

$ file *.img 
day1.img:      DOS/MBR boot sector; partition 1 : ID=0xee, start-CHS (0x0,0,2), end-CHS (0x3ff,255,63), startsector 1, 40959 sectors, extended partition table (last)
day2.img:      DOS/MBR boot sector; partition 1 : ID=0xee, start-CHS (0x0,0,2), end-CHS (0x3ff,255,63), startsector 1, 40959 sectors, extended partition table (last)

所以先直接 7z 提取，得到两个新的 img，再 file：

1
2
3

$ file *.img 
My Disk.img:   LUKS encrypted file, ver 2 [, , sha256] UUID: e9a660d5-4a91-4dca-bda5-3f6a49eea998
My Disk 2.img: LUKS encrypted file, ver 2 [, , sha256] UUID: e9a660d5-4a91-4dca-bda5-3f6a49eea998

发现都是 LUKS encrypted file

在 Kali Linux 里尝试直接挂载第一个 img，要求输入密码，把题给的密码输入就可以看到 “课件”

以上都是已知的试验部分，真正要做的是解开第二个未知密码的 LUKS img
已知磁盘的加密使用的是 luks2，在网上查了破解 luks2 之类的都说 luks2 不可破解，或者是使用已知的密码字典来爆破
但是题里说了 “随机生成的强密码”，所以也是没有密码字典的

其实这道题的最大提示就在于它给了两个 img，既然第一个 img 打开后仅仅是一个课件，如果它的用处仅仅是用来试验 luks 怎么打开的话，根本它没必要给出
所以第一个 img 肯定还是有用的。

再看题目，反复说了 U 盘，所以这两个 img 应该是同一个 U 盘的镜像文件，只是更改了密码而已（file 看到的 uuid 也是一致的）
于是继续必应，发现同一个磁盘的 master-key 是一样的，而且可以用 master-key 来添加密码恢复磁盘（见：10 Linux cryptsetup Examples for LUKS Key Management）

所以就跟着文章里的做法，从第一个 img 中提取出 master-key，然后用它来提供 AddKey 的权限。添加了新 passphrase 后就可以用新密码打开磁盘了：

$ cryptsetup luksDump --dump-master-key MyDisk.img  # 输出 master-key
...
MK dump:    be 97 db 91 5c 30 47 ce 1c 59 c5 c0 8c 75 3c 40 
            72 35 85 9d fe 49 c0 52 c4 f5 26 60 af 3e d4 2c 
            ec a3 60 53 aa 96 70 4d f3 f2 ff 56 8f 49 a1 82 
            60 18 7c 58 d7 6a ec e8 00 c1 90 c1 88 43 f8 9a
$ cat "be...9a" > master_key.txt # 存入文件
$ xxd -r -p master_key.txt master_key.bin # 转为二进制
$ cryptsetup luksAddKey MyDisk2.img --master-key-file <(cat master_key.bin) # 添加密码
Enter new passphrase for key slot:    # 输入新密码即可，因为master-key-file相当于提供了原始密码
Verify passphrase:

（一定要用 root 权限才可以加密码）
然后挂载、输入密码，就可以看到 flag.txt 了

Micro World

宇宙中某一片极其微小的区域里的粒子被一股神秘力量初始化设置成了 flag 的形状，程序忠实地记录了一段时间之后这片区域的粒子运动情况。

拿到了 exe 文件，看起来挺精致，运行起来是一些点运动碰撞的场景
拖到 IDA 里看看，发现了 __main__ 以及 .rdata 里一些 py 有关的字符串：

所以推测是使用 python 编写的，然后用 pyinstaller 打包

这样的话试着用 pyinstxtractor 解包 .exe，成功得到一个文件夹
里面是一堆 .pyc .pyd .dll 文件，从名字就可以看出大部分是 import 的包，只有一个特别的 2.pyc
所以这个应该就是编译后的源码了

接下来用 uncompyle6 来反编译 pyc 文件，输出得到了源码 2.py
尝试运行，发现跑起来之后只有一个点在运动，应该是反编译时出了些问题
于是开始看源码

基本上简单说就是，初始有一些数据，表示每个点的位置和速度，然后运行，每次运行都检测碰撞，然后获得新的点位置，再绘制出来
调试一下，输出每次的 pointlist，发现第一次是所有点，第二次变成2个，第三次往后就只有一个了
所以问题大概就出在了 next_pos_list 函数：

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:
                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

仔细读一读，可以发现这里面的 for-else 块很奇怪，导致循环结束和 return 都早了，所以根据函数的意思改一改：

def next_pos_list(Pointlist):
    pointlist = []
    for i in range(len(Pointlist)):
        for point in Pointlist[i + 1:]:
            ...
    for item in Pointlist:
        ...
    return pointlist

这样就可以成功运行了

但是画面仍然是杂乱的。因为题里说了 “记录了一段时间之后这片区域的粒子运动情况”
所以需要将轨迹往前推，最方便的方法就是更改每个点的速度方向：

1
2
3

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

运行后等待一小会儿就可以看到点逐渐有序，在某一刻汇成了 flag：

虽然不太清晰，但是也可以猜个大概

又写了蛮长的，剩下的放在下一篇(:з」∠)

Reference

< #2

#4 >

「Hackergame 2021」#3 Writup 持续破防篇 0

https://blog.tonycrane.cc/p/f152ab1f.html

作者

TonyCrane

发布于

2021-10-29

更新于

2021-10-29

许可协议

#CTF Writeup

「Hackergame 2021」#3 Writup 持续破防篇 0

Amnesia

轻度失忆

Easy RSA

get_p

get_q

flag

加密的 U 盘

Micro World

Reference

作者

发布于

更新于

许可协议

最新文章

归档

标签

分类

目录