Hackergame 2023 Summary(part2)

前言

成功挤进校内前5，总榜前70

欣慰地看到这一年来的努力没有白费，自己的技术力有见长

也欣慰地看到今年的排行榜分数比去年更卷了，这是好事，说明网安圈高技术力的师傅们越来越多了，以后也能看到更多大佬们的技术分享文章

题解

流式星球

该程序将视频转化为维度是(frame_count, frame_height, frame_width, 3)的矩阵

由于转出的文件并不包含元数据，所以长宽信息需要我们自己来爆破

爆破脚本如下

import cv2
import numpy as np

def create_video(input_file, output_file, frame_height, frame_width):
    buffer = np.fromfile(input_file, dtype=np.uint8)
    drop = buffer.size % (frame_width*frame_height*30)
    buffer = buffer[:(drop*-1)].reshape((-1, frame_height, frame_width, 3))

    fourcc = cv2.VideoWriter_fourcc(*"mp4v")
    out = cv2.VideoWriter(output_file, fourcc, 30, (frame_width, frame_height))

    for frame in buffer:
        out.write(frame)

    out.release()

if __name__ == "__main__":
    for i in range(500,800,10):
        create_video("video.bin", f"videos/output_width{i}.mp4", 500, i)

我们将高度先固定，爆破宽度从500到800，然后人工翻阅，查看是否有有效信息的视频

当宽度为640时，视频内容变得较为有语义

此时我们需要将宽度固定，来确认高度

当视频的内容上下流动的速度变慢时，说明我们离正确高度比较接近

for i in range(500,800,10):
    create_video("video.bin", f"videos/output_height{i}.mp4", i, 640)

我们发现高度从500到510时，视频内容从向向下流动变为向上流动

说明正确高度就在这个范围间

经过测试，505较为稳定

我们再来精细化宽度

由于一张图同时出现了三个帧，我们将宽度缩为原来的三分之一

经过细调，宽度为214

截得flag如下

视频内容为为什么？为什么要flag{it-could-be-easy-to-restore-video-with-haruhikage-even-without-metadata-0F7968CC}

低带宽星球

本题需要无损压缩一张图片

第一问从5.7KB压到2KB以下

考虑PNG转WEBP

得到flag

为什么要打开 /flag 😡

为了绕过open等函数，我们可以自行编写汇编代码使用系统调用号，调用sys_open，进而打开文件

编写汇编文件后还需要执行如下步骤：

1. 汇编：执行as exp.s -o exp.o将exp.s翻译成机器语言指令并打包为可重定向文件，结果保存在目标文件exp.o中

2. 链接：执行ld -o exp exp.o -lc将hello.o和其他库文件、目标代码链接后形成可执行文件。

提交可执行文件exp

得到flagflag{nande_ld_preload_yattano_40425457b9}

异星歧途

整个地图的概览如下

我们需要控制红框中的那些开关，使得各个部分正常工作

Part1

首先看第一部分

这一段的工作元件如下图所示

运输过来的煤炭给火力发电机供电，进而产生电力，电力则通过电线传输给下一部分

查看该微型处理器以及其链接的方块

该火力发电机受到微型处理器的控制，命名为generator1，同时开关switch1到switch8也在控制范围内

微处理器中的命令如下

sensor s1 switch1 @enabled
sensor s2 switch2 @enabled
sensor s3 switch3 @enabled
sensor s4 switch4 @enabled
sensor s5 switch5 @enabled
sensor s6 switch6 @enabled
sensor s7 switch7 @enabled
sensor s8 switch8 @enabled
jump 18 equal s1 false
jump 18 equal s2 true
jump 18 equal s3 false
jump 18 equal s4 true
jump 18 equal s5 true
jump 18 equal s6 false
jump 18 equal s7 true
jump 18 equal s8 false
control enabled generator1 1 0 0 0
end
control enabled generator1 0 0 0 0
end

目标是让generator1的enable状态置为1

而前面这些jump语句都会跳到18，导致generator1的enable状态为0

所以我们就需要使得这些jump的判断条件为False

此时开关s1到s8的值应该置为10100101

成功工作！

Part2

接下来看第二部分

很显然，抽水机和涡轮发电机需要同时工作，进而产生电力并传给下一部分

我们需要使panell和generator1的enable置为1

查看逻辑处理器的指令

sensor sw1 switch1 @enabled
sensor sw2 switch2 @enabled
sensor sw3 switch3 @enabled
sensor sw4 switch4 @enabled
sensor sw5 switch5 @enabled
sensor sw6 switch6 @enabled
sensor sw7 switch7 @enabled
sensor sw8 switch8 @enabled
op shl t sw1 7
set number t
op shl t sw2 6
op add number number t
op shl t sw3 5
op add number number t
op shl t sw4 4
op add number number t
op shl t sw5 3
op add number number t
op shl t sw6 2
op add number number t
op shl t sw7 1
op add number number t
set t sw8
op add number number t
set en 0
set i 0
jump 33 greaterThanEq i 16
op pow fl0 i 2
jump 31 notEqual fl0 number
set en 1
jump 33 always x false
op add i i 1
jump 26 always x false
op equal fl1 0 sw1
op equal fl2 0 sw6
op or fl3 fl1 fl2
jump 38 equal fl3 0
set en 0
control enabled generator1 en 0 0 0
control enabled panel1 en 0 0 0
end

我们需要将其翻译为更通俗易懂的python语言

switchs = [0,0,0,0,0,0,0,0]
number = 0
for i in range(switchs):
    t = switchs[i]<<(7-i)
    number += t
en = 0
i = 0
while(i<16):
    fl0 = i**2
    if fl0 != number:
        i += 1
        continue
    en = 1
fl1 = (0==switchs[0])
fl2 = (0==switchs[5])
fl3 = fl1 or fl2
if fl3 ==0 :
    print("success!")

那么我们需要满足两个条件：en = 1且fl3!=0

前一个条件决定了number为一个平方数，而后一个条件则限制了sw1和sw6必须均为1

这里我们可以使用爆破脚本找到满足条件的开关序列

需要注意的是switch8也在右侧的处理器范围内，一旦置为1，右侧模块则会爆炸

我们可以为该部分编写如下爆破脚本

import itertools
import gmpy2

dic = '01'
for x in itertools.product(dic, repeat=8):
    switchs = ''.join(x)

    number = 0
    for i in range(8):
        t = int(switchs[i]) << (7 - i)
        number += t
    if gmpy2.iroot(number,2)[1] \
            and gmpy2.iroot(number,2)[0]!=0 \
            and int(switchs[0])==1 \
            and int(switchs[5])==1 \
            and int(switchs[7])==0:
        print(switchs)
        exit()

得到正确序列11000100

Part3

接下来是第三部分

本段的结构更为复杂，需要我们深入理解工作原理才行

想要恢复电力，我们需要让反应堆1和2运作起来，也就是reactor1和2的enable需要置为1

但是反应堆需要散热，否则会爆炸

而散热则需要满足两个条件：冷冻液混合器工作且冷冻液原料和水能够运输到冷冻液混合器，同时冷冻液和水不会分流浪费

翻译为元件状态则是mixer1、extractor1和gate1的enable置为1，分流导管condult1和condult2的enable置为0

gate1为反溢流门，所以应该置为0

最后反应堆也需要原料钍，所以conveyor2的enable设为1

而那两天飞机则可有可无

我们再来看处理器内的指令

sensor sw1 switch1 @enabled
sensor sw2 switch2 @enabled
sensor sw3 switch3 @enabled
sensor sw4 switch4 @enabled
sensor sw5 switch5 @enabled
sensor sw6 switch6 @enabled
sensor sw7 switch7 @enabled
sensor sw8 switch8 @enabled
sensor sw9 switch9 @enabled
control enabled conveyor2 sw1 0 0 0
control enabled gate1 sw2 0 0 0
op equal nsw3 sw3 0
control enabled reactor1 nsw3 0 0 0
control enabled reactor2 nsw3 0 0 0
control enabled conduit1 sw4 0 0 0
control enabled conduit2 sw4 0 0 0
control enabled mixer1 sw5 0 0 0
control enabled extractor1 sw6 0 0 0
control enabled meltdown1 sw7 0 0 0
control enabled meltdown2 sw7 0 0 0
op equal result sw8 sw9
jump 28 equal result true
control enabled mixer1 0 0 0 0
control enabled conduit2 1 0 0 0
control enabled reactor1 1 0 0 0
control enabled reactor2 1 0 0 0
control enabled conveyor2 1 0 0 0
wait 5
end

sw1为1，sw2为0，nsw3为1，则sw3为0

sw4为0，sw5wei1，sw6为1，sw7为1

Jump的条件需要满足，所以result为True，sw8为0

此时序列为10001110

正常工作！

Part4

最后一部分则类似于一个迷宫，需要我们找到一个正确的电力传输路径

乍一看，我们能找到这题红色路径，接下来就是思考如何让路径上的节点工作

首先是switch3和4，他们置为1能让下图中框住的部分联通

接下来我们需要让下图中标红的线路工作

要想让红星的火力发电机工作，就需要关闭焚化炉3

而焚化炉3被涡轮发动机控制，所以需要关闭涡轮发动机，此时控制两个煤炭能源旁的溢流门即可

打开焚化炉2和4就能让涡轮发电机关闭，而这需要关闭焚化炉1

所以switch1为0，switch2为1

下面该思考如何连通下图的电路

我们需要关闭焚化炉3，即切断其旁边电力节点的电源

这需要我们打开焚化炉1、2和4，即swtich6、7、8均为1

此时开关序列为01110111

成功通电！

最终总的开关序列为10100101110001001000110001110111

启动反应堆，并从提交网站获得flag

小Z的谜题

源码如下

import itertools

bound = 5
constraints = ((1, 1, 3), (1, 2, 2), (1, 2, 4), (1, 4, 4), (2, 2, 2), (2, 2, 3))
count = [3, 4, 2, 2, 2, 3]
num_constraints = sum(count)
num_dims = len(constraints[0])
arrange = [[[0 for i in range(3)] for j in range(num_dims)] for k in range(num_constraints)]
print('Input a string:')
s = (c for c in input().strip())
for i in range(num_constraints):
    for j in range(num_dims):
        for k in range(3):
            if k == 2:
                arrange[i][j][k] = -1
            else:
                number = int(next(s))
                assert 0 <= number <= bound
                arrange[i][j][k] = number
print('Stage 0 passed')
assert arrange == list(sorted(arrange))
print('Stage 1 passed')
for i in range(num_constraints):
    for j in range(num_constraints):
        if i == j:
            continue
        assert any((arrange[i][k][1] <= arrange[j][k][0] or arrange[j][k][1] <= arrange[i][k][0]) for k in range(num_dims))
print('Stage 2 passed')
for i in range(num_constraints):
    for t in range(len(constraints)):
        if tuple(sorted([arrange[i][j][1] - arrange[i][j][0] for j in range(num_dims)])) == constraints[t]:
            count[t] -= 1
            break
assert not any(count)
print('Stage 3 passed')
score = len(set((x, y, z) for i in range(num_constraints) for x, y, z in itertools.product(*arrange[i])))
if score >= 157:
    print(open('/flag3').read())
elif score <= 136:
    print(open('/flag2').read())
else:
    print(open('/flag1').read())

为了更好地做题，我们需要深入理解这个程序

bound限制了我们输入的每个字符的范围为数字0到5

arrange数字的维度为(num_constraints,num_dims,3)

该数组用于将用户的输入字符串存为特定格式，存入的总元素数量为144

由于当k == 2，则arrange[i][j][k] = -1，所以用户输入长度其实只有总容量的三分之二，即96个字符

接下来会遇到第一个判断语句

assert arrange == list(sorted(arrange))
print('Stage 1 passed')

要想知道这句代码的规则，需要先了解sorted()函数

sorted() 函数用于对所有可迭代的对象进行排序操作。

语法：

sorted(iterable, cmp=None, key=None, reverse=False)

参数说明：

• iterable — 可迭代对象。
• cmp — 比较的函数，这个具有两个参数，参数的值都是从可迭代对象中取出，此函数必须遵守的规则为，大于则返回1，小于则返回-1，等于则返回0。
• key — 主要是用来进行比较的元素，只有一个参数，具体的函数的参数就是取自于可迭代对象中，指定可迭代对象中的一个元素来进行排序。
• reverse — 排序规则，reverse = True 降序 ， reverse = False 升序（默认）。

sorted只支持相同元素之间进行比较，例如int和int，list和list，元组和元组，如果可迭代对象中存在不同类型的元素，则会发生报错

当sorted传入的可迭代对象中的元素为列表时，则会取列表的第一个元素与可迭代对象的下一个元素进行比较，若相同，则会取该列表的下一个元素，以此类推

示例如下

arrange = [[1,2,3],[0,1,2]]
print(list(sorted(arrange)))
# [[0, 1, 2], [1, 2, 3]]
arrange = [[1,2,4],[1,2,3]]
print(list(sorted(arrange)))
# [[1, 2, 3], [1, 2, 4]]
arrange = [[1,[2,3],4],[1,[2,2],4]]
print(list(sorted(arrange)))
# [[1, [2, 2], 4], [1, [2, 3], 4]]

sorted的判断使得输入的字符串arrang[i][0]序列需要整体满足升序

接下来是第二个判断条件

for i in range(num_constraints):
    for j in range(num_constraints):
        if i == j:
            continue
        assert any((arrange[i][k][1] <= arrange[j][k][0] or arrange[j][k][1] <= arrange[i][k][0]) for k in range(num_dims))
print('Stage 2 passed')

在 Python 中，any() 是一个内置函数，用于检查可迭代对象中是否至少有一个元素为真。如果是，则返回 True，否则返回 False。

第三个判断条件如下

for i in range(num_constraints):
    for t in range(len(constraints)):
        if tuple(sorted([arrange[i][j][1] - arrange[i][j][0] for j in range(num_dims)])) == constraints[t]:
            count[t] -= 1
            break
assert not any(count)
print('Stage 3 passed')

前面设置的所有限制都需要得到满足

第二个条件和第三个条件的共同作用导致，arrange[i][j]和arrange[i][j+n]不能完全相同

得分机制如下

score = len(set((x, y, z) for i in range(num_constraints) for x, y, z in itertools.product(*arrange[i])))
if score >= 157:
    print(open('/flag3').read())
elif score <= 136:
    print(open('/flag2').read())
else:
    print(open('/flag1').read())

score与前面最小列表的种类个数有关

黑客马拉松

本题源码如下:

import random
import math
from sympy import isprime

# You do know that we SCGY students can factor RSA, right?
# So just give me p and q directly
p = int(input('p: '))
q = int(input('q: '))
assert isprime(p) and isprime(q) and p != q

# Prove me that p, q are strong primes
lfp = int(input('A large prime factor of p-1: '))
lfq = int(input('A large prime factor of q-1: '))
assert isprime(lfp) and isprime(lfq)
assert (p-1) % lfp == 0 and (q-1) % lfq == 0
assert lfp > 2**128 and lfq > 2**128

N = p*q
phi = (p-1)*(q-1)
Nbits = N.bit_length()
# N is large enough
assert Nbits == 1024

e = int(input('e: ')) % phi
d = pow(e, -1, phi)
# No Low Private Exponent Attack
assert d.bit_length() > 0.292*Nbits
# No Low Public Exponent Attack
k = Nbits - max(int(Nbits*2/e), 96)

# OK, we've got a safe RSA parameters
state = random.SystemRandom().randint(2, N-1)
randomNums = []
states = []

mission = int(input("Choose mission: "))
if mission == 1:
    for _ in range(100):
        state = pow(state, e, N)
        randomNums.append(int(state) & ((1 << k) - 1))
        states.append(state)
elif mission == 2:
    for _ in range(1):
        state = state >> k
        state = pow(state, e, N)
        randomNums.append(int(state) & ((1 << k) - 1))
        states.append(state)

# Not a small loop
for i in range(len(states)-1):
    assert (math.gcd(states[i] - state, N) == 1)

print(randomNums)
guess = int(input("Predict PRNG state: "))
if guess == state:
    print(open(f"/flag{mission}").read())

教练，有人抢跑！

题目需要我们生成满足条件的随机数

见多了各种chall.py中如何生成RSA公钥的我们可以很容易地写出如下脚本

from Crypto.Util.number import *
from sympy import isprime
def get_p(lfp):
   p=1
   while(p.bit_length()!=512 or isprime(p)==0):
      p = lfp*2*getPrime(512-lfp.bit_length()-1)+1
   return p
def get_pq():
   N=1
   while(N.bit_length()!=1024):
      lfp = getPrime(129)
      p = get_p(lfp)
      lfq = getPrime(129)
      q = get_p(lfq)
      N = p*q
   return lfp,p,lfq,q
lfp,p,lfq,q =get_pq()

print("p:",p)
print("q:",q)
print("lfp:",lfp)
print("lfq:",lfq)

生成固定的p、q参数后，我们来考虑e

本题能得到明密文的后k位，考虑coppersmith攻击

那么此时e不能太大，但是k的大小又和e有关，e越小k越小

但是这只是考虑了e为正数的情况，如果e为负数，那么k就恒为96

终端交互脚本如下

from pwn import *
context.log_level = 'debug'
p = 8130783200765099079371905805653275305530953408368486972439144538377172762778724178293921761601331901642956558545531112904308756365058449689105893951902947
q = 11454088000212950190744304417071055599116596384509623856814663255888235693331192150623151438185124694138841377055326544017433007065922209282946188611202987
lfp = 556695256623252691766599489994025390137
lfq = 625845849695411279745162870674729131439
n = p*q
e = -3
token = '123:MEQCIDydESRkW/h1aEuArWNCcOUqHC9UX9BmL0xBqZzaXnceAiAzrt9aK/g2oMXhW2iP+ON7DcClF3xMmhyzuN+w4qV2Xw=='

conn = remote('202.38.93.111', 20230)
conn.recvuntil(b'your token:')
conn.sendline(token.encode())
conn.recvuntil(b'p: ')
conn.sendline(str(p).encode())
conn.recvuntil(b'q: ')
conn.sendline(str(q).encode())
conn.recvuntil(b'p-1: ')
conn.sendline(str(lfp).encode())
conn.recvuntil(b'q-1: ')
conn.sendline(str(lfq).encode())
conn.recvuntil(b'e: ')
conn.sendline(str(e).encode())
conn.recvuntil(b'mission: ')
conn.sendline(b'1')
states = eval(conn.recvuntil(b'state: ')[:-21])
mbar = states[-2]
cbar = states[-1]
print(mbar)
print(cbar)
conn.interactive()

编写sage脚本如下

from Crypto.Util.number import *
import itertools
from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = PolynomialSequence([], f.parent())
    for i in range(m+1):
        power = N ^ (m-i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = power
            for variable, shift in zip(f.variables(), shifts):
                g *= variable ^ shift
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    B = B.change_ring(ZZ)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in B*monomials:
        if h.is_zero():
            continue
        H.append(h.change_ring(QQ))
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            V = I.variety(ring=ZZ)
            if V:
                roots = []
                for root in V:
                    root = map(R, map(root.__getitem__, f.variables()))
                    roots.append(tuple(root))
                return roots

    return []
p = 8130783200765099079371905805653275305530953408368486972439144538377172762778724178293921761601331901642956558545531112904308756365058449689105893951902947
q = 11454088000212950190744304417071055599116596384509623856814663255888235693331192150623151438185124694138841377055326544017433007065922209282946188611202987
lfp = 556695256623252691766599489994025390137
lfq = 625845849695411279745162870674729131439
N = p*q
e = -3

mbar = 573046980537607907730089729000433259422879383552606763033164754066292843681918904561070723206971334204344866440480927073770327173961454188585854505141069244788355571694396962542754658258199054695288751216512033298300658634987185377441765796869134184212323944158160885988500722088
cbar = 654623699439508739504705671022791775232662503157271314760513975989848071893308099460646567253762397788835192372411637701492138597346833898525007897948224992066710053594670104732362677192600705075779551377483754803864141595089548025417326462516667075558417906351163970399836100141

kbits = 96
beta = 1
nbits = N.nbits()

F.<x,y> = PolynomialRing(Zmod(N))
f = ((mbar + x*2^(nbits-96))^(e*-1))*(cbar+y*2^(nbits-96))-1

roots = small_roots(f,(2^96, 2 ^96),m=1,d=6)

if roots:
    x0 = roots[0][0]
    m = mbar + x0*(Integer(2)**(nbits-Integer(96)))
    state = pow(m,e,N)
    print("state: ",state)
else:
    print("No roots found.")

首先与终端交互得到最后两个随机数

使用sage跑出state

得到flag

一発勝負

第二问和第一问基本一致

只不过前一个state为96位

将sage脚本修改如下

from Crypto.Util.number import *
import itertools
from sage.rings.polynomial.multi_polynomial_sequence import PolynomialSequence

def small_roots(f, bounds, m=1, d=None):
    if not d:
        d = f.degree()

    R = f.base_ring()
    N = R.cardinality()

    f /= f.coefficients().pop(0)
    f = f.change_ring(ZZ)

    G = PolynomialSequence([], f.parent())
    for i in range(m+1):
        power = N ^ (m-i) * f ^ i
        for shifts in itertools.product(range(d), repeat=f.nvariables()):
            g = power
            for variable, shift in zip(f.variables(), shifts):
                g *= variable ^ shift
            G.append(g)

    B, monomials = G.coefficient_matrix()
    monomials = vector(monomials)

    factors = [monomial(*bounds) for monomial in monomials]
    for i, factor in enumerate(factors):
        B.rescale_col(i, factor)

    B = B.dense_matrix().LLL()

    B = B.change_ring(QQ)
    for i, factor in enumerate(factors):
        B.rescale_col(i, 1/factor)
    B = B.change_ring(ZZ)

    H = Sequence([], f.parent().change_ring(QQ))
    for h in B*monomials:
        if h.is_zero():
            continue
        H.append(h.change_ring(QQ))
        I = H.ideal()
        if I.dimension() == -1:
            H.pop()
        elif I.dimension() == 0:
            V = I.variety(ring=ZZ)
            if V:
                roots = []
                for root in V:
                    root = map(R, map(root.__getitem__, f.variables()))
                    roots.append(tuple(root))
                return roots

    return []
p = 8130783200765099079371905805653275305530953408368486972439144538377172762778724178293921761601331901642956558545531112904308756365058449689105893951902947
q = 11454088000212950190744304417071055599116596384509623856814663255888235693331192150623151438185124694138841377055326544017433007065922209282946188611202987
lfp = 556695256623252691766599489994025390137
lfq = 625845849695411279745162870674729131439
N = p*q
e = -3

cbar = 819212024021465240183460848146393861498847152851752305375003064596154363694419328851582400347264127493568263786494744431611241418449168299316709232129735483745080438685137492117863951945931260321536681990451901618835408354392089274304831850047887110473255104650685834245709041136

kbits = 96
beta = 1
nbits = N.nbits()

F.<x,y> = PolynomialRing(Zmod(N))
f = x^(e*-1)*(cbar+y*2^(nbits-96))-1

roots = small_roots(f,(2^96, 2 ^96),m=1,d=6)

if roots:
    x0 = roots[0][0]
    m = x0
    state = pow(m,e,N)
    print("state: ",state)
else:
    print("No roots found.")

得到flag