Hackergame 2021 writeup 0x01

今年我认为难度适中的题目,可能需要一些基础知识,以及一些搜索能力。
这些题目会带来一些挑战,但也也会从中获得更多知识(o゜▽゜)o☆

Easy RSA

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

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

关于RSA是什么,需要哪些基础知识我这里不再赘述,有篇知乎的文章写的不错:RSA算法原理

我们来看看指数的生成过程:

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)

getPrime函数可以获取指定位数的质数,因此我们这里需要枚举找到那个起始的质数,不妨从已知的最后一个往前减去一千开始尝试,找到当前的为止,经过一番枚举,可以得到最初始的质数,放入guess得到我们的序列以及我们的n:

known = 80096058210213458444437404275177554701604739094679033012396452382975889905967
guess = [80096058210213458444437404275177554701604739094679033012396452382975889905121]

for i in range(1,10):
    guess.append(sympy.nextprime(guess[-1]))

assert(guess[-1] == known)

n = 1
for i in range(10):
    n = n * guess[i]

value_q 是 $q ^ e \ mod \ n$ ,类似于RSA的求解方法,我们可以知道解密密钥 $d$ 应当满足

$$ed \equiv 1 (mod \ \phi(n))$$

$$\phi(n) = \prod_{i=1}^{10} (p_i - 1)$$

故计算:

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

d = inverse(e, phi)
print(e * d % phi)
q = pow(value_q, d, n)

得到 q = 10477925992460766451892208516181598312750484426056814542870756188277177949099084361476539803367804757559880919838828678145609717295215924948786830953571811

再来看 p 的求法:

def get_p():
    x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
    y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
    value_p = sympy.nextprime((math.factorial(y)) % x)
    # Hint:这里直接计算会溢出,请你仔细观察 x 和 y 的特征
    return value_p

这里需要知道威尔逊定理:

当且仅当 $p$ 为质数时,有 $(p - 1)! \equiv -1(mod \ p)$

已知 $x,y$ 均为质数,因此我们可以推导:

$$
\begin{align*}
(x - 1)! \equiv& -1 \equiv x - 1 &(mod \ x)\\
y!(y + 1)(y + 2) \dots (x - 1) \equiv& x - 1 &(mod \ x) \\
y!(y + 1)(y + 2) \dots (x - 2) \equiv& 1 &(mod \ x) \\
y! \equiv& [(y + 1)(y + 2) \dots (x - 2)]^{-1} &(mod \ x)
\end{align*}
$$

于是我们的问题就转化为求(y + 1)(y + 2) ... (x - 2) 在取其关于x的逆元,也即:

x = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391760451
y = 11124440021748127159092076861405454814981575144744508857178576572929321435002942998531420985771090167262256877805902135304112271641074498386662361391661439
# cal (y! % x)
prd = 1
for i in range(y + 1,x - 1):
    prd *= i
    prd %= x

p = inverse(prd, x)
p = sympy.nextprime(p)

得到 p = 10569944080090591401315432556965818857327680380269154543273468441025963038065648915158194147019839932524599260058098616377893091051396090650574162446875263

再进行解密c

c = 110644875422336073350488613774418819991169603750711465190260581119043921549811353108399064284589038384540018965816137286856268590507418636799746759551009749004176545414118128330198437101472882906564195341277423007542422286760940374859966152871273887950174522820162832774361714668826122465471705166574184367478
phi = (p - 1) * (q - 1)
n = p * q
d = inverse(e, phi)
m = pow(c, d, n)
print(long_to_bytes(m))

得到答案。

flag{CRYPT0_1s_Interesting!}

minecRaft

kk 同学很喜欢玩 Minecraft,他最近收到了一张 MC 地图,地图里面有三盏灯,还有很多奇奇怪怪的压力板。

但他发现这些灯好像不太符合 MC 电磁学(Red stone),你能帮他把灯全部点亮吗?

注:本题解法与原版 Minecraft 游戏无关。

补充说明:flag 花括号内为让三盏灯全部点亮的最短的输入序列。例如,如果踩踏压力板输入的最短的序列为 abc,则答案为 flag{abc}。

他们居然真的写了个网页版MC的样子出来!然而对于这道题来说,MC只是表面的,正如标题里大写的 R 一样,重点在于逆向和反混淆一段 js 代码。

一般来说此类 js 混淆来讲,最好的入手点就是那个字符串数组,以及协助解码字符串的函数。跟踪修改变量名称可以发现,这一字符串数组被包装进了函数里,并且在几乎全部的地方都能看到它的影子,纵使换了很多变量名称依然不改其本质。他们一般会在各种需要常量的地方出现,比如在题目所给代码中的字符串常量数组:

function _0x381b() {
  const _0x4af9ee = [
    "encrypt",
    "33MGcQht",
    "6fbde674819a59bfa12092565b4ca2a7a11dc670c678681daf4afb6704b82f0c",
    "14021KbbewD",
    "charCodeAt",
    "808heYYJt",
    "5DlyrGX",
    "552oZzIQH",
    "fromCharCode",
    "356IjESGA",
    "784713mdLTBv",
    "2529060PvKScd",
    "805548mjjthm",
    "844848vFCypf",
    "4bIkkcJ",
    "1356853149054377",
    "length",
    "slice",
    "1720848ZSQDkr",
  ];
  _0x381b = function () {
    return _0x4af9ee;
  };
  return _0x381b();
}

以及获取字符串的函数:

function _0x2c9e(_0x49e6ff, _0x310d40) {
  const _0x381b4c = _0x381b();
  return (
    (_0x2c9e = function (_0x2c9ec6, _0x2ec3bd) {
      _0x2c9ec6 = _0x2c9ec6 - 0x1a6;
      let _0x4769df = _0x381b4c[_0x2c9ec6];
      return _0x4769df;
    }),
    _0x2c9e(_0x49e6ff, _0x310d40)
  );
}
const _0x22517d = _0x2c9e;

以及对应的初始化函数,检查计算当前字符串数组的哈希值,并进行数组的更改操作,以得到正确的数组:

(function (_0x2018e5, _0xd122c5) {
  const _0x4a600d = _0x2c9e,
    _0x2e34d2 = _0x2018e5();
  while (!![]) {
    try {
      const _0x4d38c4 =
        (-parseInt(_0x4a600d(0x1b1)) / 0x1) * (parseInt(_0x4a600d(0x1ad)) / 0x2) +
        (-parseInt(_0x4a600d(0x1b2)) / 0x3) * (parseInt(_0x4a600d(0x1b6)) / 0x4) +
        (-parseInt(_0x4a600d(0x1ae)) / 0x5) * (-parseInt(_0x4a600d(0x1b4)) / 0x6) +
        (parseInt(_0x4a600d(0x1ab)) / 0x7) * (parseInt(_0x4a600d(0x1af)) / 0x8) +
        parseInt(_0x4a600d(0x1b5)) / 0x9 + -parseInt(_0x4a600d(0x1b3)) / 0xa +
        (-parseInt(_0x4a600d(0x1a9)) / 0xb) * (-parseInt(_0x4a600d(0x1a7)) / 0xc);
      if (_0x4d38c4 === _0xd122c5) break;
      else _0x2e34d2["push"](_0x2e34d2["shift"]());
    } catch (_0x416145) {
      _0x2e34d2["push"](_0x2e34d2["shift"]());
    }
  }
})(_0x381b, 0x21c08);

在 node 环境中我们可以直接执行这三者,并在运行后为他们赋予别名,比如:

let get_table = _0x381b;
let get_str = _0x22517d;

这里的例子比较简单,在更复杂的情况下,通常只需定位函数和其对应的变量名,在反混淆过程中,先在 node 环境中运行,获取到真正的字符串获取函数后,当遇到需要获取字符串时候,直接在 node 环境中调用解码即可。

这样我们就可以顺利解码可见的第二个函数的意义了,既然函数名为 encrypt,即可合理推测几个变量名,反混淆整理后可得:

String["prototype"]["encrypt"] = function (keystr) {
  const result = new Array(2), key = new Array(4);
  let ans = "";
  plaintext = escape(this);
  for (var i = 0; i < 4; i++)
    key[i] = Str4ToLong(keystr.slice(i * 4, (i + 1) * 4));
  for (i = 0; i < plaintext.length; i += 8) {
    result[0] = Str4ToLong(plaintext.slice(i, i + 4));
    result[1] = Str4ToLong(plaintext.slice(i + 4, i + 8));
    code(result, key);
    ans += LongToBase16(result[0]) + LongToBase16(result[1]);
  }
  return ans;
};

以及调用它的地方:

function gyflagh(_0x111955) {
  const _0x50051f = _0x22517d;
  let _0x3b790d = _0x111955[_0x50051f(0x1a8)](_0x50051f(0x1b7));
  if (_0x3b790d === _0x50051f(0x1aa)) return !![];
  return ![];
}

利用字符串数组解码后,其逻辑也就是

function gyflagh(ans) {
  return ans.encrypt("1356853149054377") === "6fbde674819a59bfa12092565b4ca2a7a11dc670c678681daf4afb6704b82f0c";
}

目前为止我们最关心的,是那个被明文指明为code的函数。计算0x52cfb2de + 0x4b67c6db可以发现它是0x9e3779b9,它可以说是类TEA算法的magic number,同时左移四右移五的操作也让人更加确信这就是一个类TEA加密。

将用逗号分隔的语句展开、重命名变量名称后便得到了如下的编码函数:

function code(v, k) {
  let highbit = v[0], lowbit = v[1];
  const delta = 0x9e3779b9, tot = delta * 0x20;
  let sum = 0x0;
  while (sum != tot) {
    highbit += (((lowbit << 4) ^ (lowbit >>> 5)) + lowbit) ^ (sum + k[sum & 3]);
    sum += delta;
    lowbit += (((highbit << 4) ^ (highbit >>> 5)) + highbit) ^ (sum + k[(sum >>> 11) & 3]);
  }
  v[0] = highbit;
  v[1] = lowbit;
}

与之对应可以写出解码函数,TEA的解码一般就是换个顺序、加法变减法即可:

function decode(v, k) {
  let highbit = v[0], lowbit = v[1];
  const delta = 0x9e3779b9;
  let now = delta * 0x20;
  while (now != 0) {
    lowbit -= (((highbit << 4) ^ (highbit >>> 5)) + highbit) ^ (now + k[(now >>> 11) & 3]);
    now -= delta;
    highbit -= (((lowbit << 4) ^ (lowbit >>> 5)) + lowbit) ^ (now + k[now & 3]);
  }
  v[0] = highbit;
  v[1] = lowbit;
}

既然如此可逆,又发现 Base16ToLong 是每次接受8位16进制,那么不妨写个 decrypt 函数:

String["prototype"]["decrypt"] = function (keystr) {
  const result = new Array(2),
    key = new Array(4);
  let ans = "";
  ciphertext = escape(this);
  for (var i = 0; i < 4; i++)
    key[i] = Str4ToLong(keystr.slice(i * 4, (i + 1) * 4));
  for (i = 0; i < ciphertext.length; i += 16) {
    result[0] = Base16ToLong(ciphertext.slice(i, i + 8));
    result[1] = Base16ToLong(ciphertext.slice(i + 8, i + 16));
    decode(result, key);
    ans += LongToStr4(result[0]) + LongToStr4(result[1]);
  }
  return ans;
};

最后的最后,是谁被编码了呢?—— 想必就是 flag 了。

let ciphertext =
  "6fbde674819a59bfa12092565b4ca2a7a11dc670c678681daf4afb6704b82f0c";
let key = "1356853149054377";
let flag = ciphertext.decrypt(key);

console.log('flag{' + flag + '}');

flag{McWebRE_inMlnCrA1t_3a5y_1cIuop9i}

Micro World

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

题目附件

嗯,打开程序,一大堆蓝色点点在动。那就逆一下吧——随即就看到了 __main__ 字样,那还逆什么逆啊,直接解包反汇编啊(

python 打包器打包出的 exe 可以通过 pyinstxtractor 解包,而后可以通过 uncompyle6 对核心文件 2.py 进行反汇编 ——

然后就得到了很接近于源文件的 python 代码了,但是尝试运行时发现运行后的蓝点数量明显下降,怀疑程序自身逻辑问题。检查后发现在函数 next_pos_list 中错误地存在着两个 for-else 结构,修复后输出点图,发现依然无法识别。

最后在初始化点列的过程中将速度直接反向:

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

在第二十七帧左右的位置可以用得到较为清晰的 flag:

ax = plt.gca()
ax.invert_yaxis()

for _ in range(27):
    Pointlist = next_pos_list(Pointlist)

plt.scatter([item.x for item in Pointlist], [item.y for item in Pointlist])
plt.show()

可以得到答案:

flag{Rev3sEtiM^5}

卷王与野生的 GPA

“24 岁,是卷王。”

即便一早学会了养生、收获了强者的发型,24 岁的科大卷王仍然无法超脱开“电子鸦片”的荼毒。
最近,他喜欢玩一款经典的掌机。这台掌机推出于 2001 年,曾经风靡全球,销量累计 8100 万台。
令卷王非常快乐的是,这台掌机使用了 ARM 指令集,正好就是上个学期在《微机原理与嵌入式系统》中学习的内容。
就算是沉迷“电子鸦片”,卷王也不忘记要在轻松娱乐的时光中获取 GPA。

这天,卷王得到了一张破旧的游戏卡带。(顺带地,他还得到了卡带烧录之前编译的 ELF 文件)
当年在这台游戏机上,少年们夜以继日捕捉着传说中的精灵;
而就在卷王冒险的过程中、野生的 GPA 跳了出来!
手上没有任何装备的卷王卷不起来,不愿躺平的他在惊慌之中输入了经典的作弊码。

就在他向野生的 GPA 扔出球时,他发现,要抓住野生的 GPA,远没有那么简单……

题目附件

做这道题最大的一件事在于选好模拟器……

最开始我使用的是一个随意下载的GBA模拟器,用起来不太舒服,而且很没用头绪怎么去搞。

之后逆向了ELF文件,看到了 decrypt 函数,提取出相应的数据进行解码,但是还是没能得到 flag 的图片,像素点的组织、颜色的映射等各方面都不是很确定。

之后换了个模拟器,mGBA,它甚至支持中文,也比上一个好用很多。

当时因为没有工具将ELF转换为gba的文件,所以一直都没想着直接修改程序(做完时候意识到代码的字节应该会直接拷贝过去不会改变,mcfx 的 wp 也证明了这一事实)

——

直到因为手滑点错,给mBGA直接扔了个 .elf 文件进去,然后它正常运行了!!!!!!!!┗|`O′|┛ 嗷~~

那么 —— 题目到此结束,直接将 ELF 中的某一常规函数调用 patch 为 BL decrypt 即可。

在二进制层面,只需要将67054 - 67055 两个字节改为 \xc2\xff 即可。

再次运行,随意操作一下,即可得到:

flag{FuR4Gu_geto_da2e!}

p😭q

学会傅里叶的一瞬间,悔恨的泪水流了下来。

当我看到音频播放器中跳动的频谱动画,月明星稀的夜晚,深邃的银河,只有天使在浅吟低唱,复杂的情感于我眼中溢出,像是沉入了雾里朦胧的海一样的温柔。

这一刻我才知道,耳机音响也就图一乐,真听音乐还得靠眼睛。

(注意:flag 花括号内是一个 12 位整数,由 0-9 数位组成,没有其它字符。)

题目附件

虽然描述很少,但是思路却很明确:傅立叶变换将音频时域转换为了频域信息,频域信息的能量值被转换为分贝,而后存于每一帧的高度上。

因此我们可以先使用ffmpeg -i flag.gif ./frames/%4d.png导出每一帧。然后可以通过三十二个采样列按行计数得到响度数组。

from PIL import Image
import numpy as np

BAR_NUM = 32
BAR_POS = [3 + i * 4 for i in range(BAR_NUM)]

res = []

for i in range(1, 588):
    line = np.zeros((32), dtype=np.uint32)
    img = Image.open(f'frame/{i:04}.png')
    for height in range(92):
        row = [1 if img.getpixel((i, height))[1] == 0 else 0 for i in BAR_POS]
        line = line + np.array(row)
    res.append(line)

查阅 librosa手册可以得到有关于采样逆变换的相关方法,照着题目给出的代码一步一步逆向变换,就能得到结果了。

import librosa
import soundfile

sample_rate = 22050
frame_step_size = 512
min_db = -60

spectrogram = np.array(res).transpose() + min_db
spectrogram = librosa.db_to_power(spectrogram)
audio = librosa.feature.inverse.mel_to_audio(spectrogram, hop_length=frame_step_size)
soundfile.write('result.wav', audio, sample_rate)

得到音频:

一段简单的英语听力测试(bushi

flag{634971243582}

Amnesia

轻度失忆

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

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

运行指令:./a.out

编译器版本:Docker 镜像 ustclug/debian:10apt update && apt -y upgrade && apt install -y gcc=4:8.3.0-1 gcc-multilib=4:8.3.0-1 的版本

轻度失忆

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

判题脚本:下载

.data.rodata 段中的代码被清零之后最大的影响就是我们不能存储常量了,也就是字符串常量不能被存储。因此可以用一种只会用到函数栈的输出方法:

#include <stdio.h>
int main()
{
    int buf = 72;
    putchar(buf);
    buf += 29;
    putchar(buf);
    buf += 7;
    putchar(buf);
    buf += 0;
    putchar(buf);
    buf += 3;
    putchar(buf);
    buf += -67;
    putchar(buf);
    buf += -12;
    putchar(buf);
    buf += 87;
    putchar(buf);
    buf += -8;
    putchar(buf);
    buf += 3;
    putchar(buf);
    buf += -6;
    putchar(buf);
    buf += -8;
    putchar(buf);
    buf += -67;
    putchar(buf);
    return 0;
}

flag{S0_S1mp1e_r1ght_a6edd8c49e}

记忆清除

记忆清除

编译后 ELF 文件的 .text 段会被清零。

判题脚本:下载

汇编与指令集相关知识我只是略知一二,并没有体系化和完整地学过。
为了知识的正确性,如有错误的地方也请指出和斧正。
部分问题我没有遇到过的原因是我本地环境与远程环境行为一致,因此没有过多考虑和了解一些朋友遇到的差异。

首要解决的问题是,由于.text段被清空,我们需要找一个新的段来存放可执行的代码。此时.xdata就是个不错的选择,当然你也可以在编译参数中增加一个段,并且将自己的函数放上去,相关操作需要用到__attribute((section(".xdata")))来进行函数声明。

当程序在正常编译时,_start__libc_start_main和其他的一些函数会进行堆栈空间的初始化等等,他们的存在可能会影响我们的程序,因此选择使用__asm()直接编写内联汇编,系统调用调用sys_write输出字符串并使用sys_exit手动退出。

在这样编译之后,进行.text段的删除,发觉被修改后的程序会报出segmentation fault。于是用 gdb 进行调试,发觉每次到 main 的核心逻辑之前会有一个奇怪的段错误和寄存器访问,而这一访问在IDA中没有见到,最开始怀疑是 gdb 为了调试而插桩。

当时潜意识中还一直认为在x86中nop对应的汇编是0x00,而当意识到nop0x90之后事情迎来了转机。

在 Intel x86 指令集中,0x00 0x00 -> add BYTE PTR [eax], al;

但面对一大段的 0x00,CPU 可能会忽略过长的无法被正确识别的指令,而 Intel x86 现有结构最长15个字节,可以猜测如果我们刚刚好能对齐 15 的整数倍,是否就可以跳过这样的非法访问呢?

基于这样的思路,成功构造出过关所用的两个 payload:

int __attribute((section(".xdata"))) main()
{
    __asm(
          ".byte 0x00                      \n" // padding 0x00
          "mov $4, %eax                    \n" // sys_write
          "mov $str, %ecx                  \n" // from -> str
          "mov $1, %ebx                    \n" // to -> stdout
          "mov $14, %edx                   \n" // length -> 14
          "int $0x80                       \n" // syscall
          "mov $1, %eax                    \n" // sys_exit
          "mov $0, %ebx                    \n" // ret -> 0
          "int $0x80                       \n" // syscall
          "str: .ascii \"Hello, world!\\n\"\n");
}

这个 payload 只有在被删除 .text 段之后才能被正常运行。使用IDA分析可见第一句指令变成:
add [eax+4], bh,所以……我也不太清楚为什么(逃,不过执行的时候似乎那一句因为恰好被忽略而顺利输出了。

int __attribute((section(".xdata"))) main()
{
    __asm(
          "mov $0, %eax                    \n" // clear %eax
          "mov $4, %eax                    \n" // sys_write
          "mov $str, %ecx                  \n" // from -> str
          "mov $1, %ebx                    \n" // to -> stdout
          "mov $14, %edx                   \n" // length -> 14
          "int $0x80                       \n" // syscall
          "mov $1, %eax                    \n" // sys_exit
          "mov $0, %ebx                    \n" // ret -> 0
          "int $0x80                       \n" // syscall
          "str: .ascii \"Hello, world!\\n\"\n");
}

这个 payload 可以顺利执行,无论是否清空 .text 段,而用IDA查看也可以得到预期的汇编,检查十六进制,或许是遇到0xB8,修正了指令吧。

不管怎么说,探索这道题目的过程还是十分有趣的,重复在编译,IDA,改汇编的循环中,最后摸索出结果的体验中,也学到了不少东西。

mcfx 的非预期解也是超出了我的预料……

flag{B3_sure_t0_c1e4r_BSS_d58668df85}

灯,等灯等灯

没有听到吗?在耳边回荡着的钟声。

传闻中,远古文明能够捕猎闪电,将其封印在蜿蜒曲折的法阵中,用以驱动炼金术的最高成就——机械之心。

而在诸多机械之心的流派里,蔚蓝是曾经的王者。无信者窃取神明的奇迹,沉湎于蔚蓝创造出来的虚幻之间,得以逃避残酷的现实。

只是,火已渐熄,位不见王影。那一抹纯净的蔚蓝也逐渐染上铜锈和铁锈的颜色。破落的圣殿中只剩无名的巡礼者,还在追寻当年先知摩尔留下的足迹。

此时才明白,那则预言的含义:火焰熄灭之时,钟声响起,余灰纷沓而来,解开沉寂千年的机关,点亮传承的图腾。无火的余灰不能成为柴薪,可也许正因这样,才会如此向往光明吧。

还没有听到吗?那回荡在耳边的,古老而熟悉的,钟声——

灯,等灯等灯

在这道题中,你可以点击方块,而周围 5*5 范围内的某些方块会受到影响,并且亮度是在模 256 的意义下计算的,如果超出会重置为 0,你的目标是点击这些方块以使得它显示为上述的样子。

换句话说,操作矩阵通过和一个固定的卷积核做卷积后再对 256 取模,其结果与预期结果诸位比较做差,取其绝对值之和作为分数。

分析可知,操作矩阵共 144 个变元,有 144 个方程进行约束,求在模 256 意义下的一组解。这一方程组是一次线性的,因此我们可以模拟高斯消元的过程进行求解,不过需要考虑的就是在模意义下怎么更改其算法。

首先需要进行的是将卷积转换为系数矩阵:

import numpy as np

kernel = np.array([
        [0,0,1,0,0],
        [0,0,2,0,0],
        [1,2,3,2,1],
        [0,0,2,0,0],
        [0,0,1,0,0],
    ])

coefficients = np.zeros((144,144))

for x in range(12):
    for y in range(12):
        for dx in range(-2, 3, 1):
            for dy in range(-2, 3, 1):
                xx = x + dx
                yy = y + dy
                if xx < 0 or xx >= 12 or yy < 0 or yy >= 12:
                    continue
                if (tmp := kernel[dx + 2][dy + 2]) > 0:
                    coefficients[x * 12 + y][xx * 12 + yy] = tmp

以及方程组右侧的常数,使之构造为增广矩阵,而这些常数就是我们将所要求的目标进行一维化得到的:

target = np.array([
    [189] * 5 + [33] * 3 + [189] * 4,
    [189] * 3 + [33] * 3 + [189,33,44] + [189] * 3,
    [189] * 5 + [33] * 4 + [189] * 3,
    [189] * 5 + [33,189,33,33] + [189] * 3,
    [189] * 3 + [33,33,189,189,33,33,33] + [189] * 2,
    [189,134] + [33] * 2 + [189] * 4 + [33] * 2 + [189] * 2,
    [189,144] + [33] * 2 + [189] * 4 + [33] + [189] * 3,
    [189,142] + [33] * 2 + [189] * 4 + [33] * 3 + [189],
    [189,100,142,33] + [189] * 4 + [33] * 3 + [189],
    [189] + [142] * 2 + [189] * 6 + [33] + [189] * 2,
    [189,59,142,33] + [189] * 4 + [33] + [189] * 3,
    [189] * 2 + [33] * 2 + [189] * 8,
]).reshape((144))

然后就是算法的核心了,在模意义下的 Gauss 消元法:

from Crypto.Util.number import inverse

def gauss(c, d, modulus = 256):
    size = c.shape[0] # 默认的输入为方阵
    assert(c.shape[0] == c.shape[1])
    # 将方阵转化为上三角阵
    # [x x x]    [x x x]
    # [x x x] -> [0 x x]
    # [x x x]    [0 0 x]
    for i in range(size - 1): # 对于每一行
        for j in range(i + 1, size): # 对于它下面的每一行
            while c[j][i] != 0: # 如果这一行的第 i 列仍然不为 0
                t = c[j][i] // c[i][i] # 计算倍率
                # 因为存在交换,辗转相除,直至一方为 0

                # 整行减去第 i 行对应倍数
                c[j] = (c[j] - t * c[i]) % modulus
                d[j] = (d[j] - t * d[i]) % modulus

                # 交换两行
                if c[j][i] != 0:
                    c[[i, j]] = c[[j, i]]
                    d[[i, j]] = d[[j, i]]

    # 从下至上按行求解方程
    for i in range(size - 1, -1 ,-1):
        # 第 i 行的常数减去它下方已经求解完毕的未知数的的系数倍
        d[i] -= sum([(c[i][j] * d[j]) % modulus for j in range(i + 1, size)])
        d[i] %= modulus

        # 如果可以整除
        if d[i] % c[i][i] == 0:
            d[i] //= c[i][i]
        # 否则求解模意义下的逆元并相乘
        else:
            d[i] *= inverse(c[i][i], modulus)
            d[i] %= modulus
    return d

如此得到的 d 便是所要求的结果了,由于当时没有逆出来提交的 API,而想通过 js 实现点击又遇到了很多困难,于是直接用 win32 的 API实现模拟点击的功能了。

如果要使用的话,第一次采集信息时候将鼠标放在左上角的方块中间,第二次放在左上角右移一个的方块,程序会根据此数据计算方块偏移量,并模拟点击:

import win32api
import win32con
import time

def click_cur(pos, times):
    win32api.SetCursorPos(pos)
    for _ in range(times):
        win32api.mouse_event(win32con.MOUSEEVENTF_LEFTDOWN|win32con.MOUSEEVENTF_LEFTUP,0,0,0,0)

def get_cur():
    print('[+] waiting...',end='')
    for i in range(5):
        time.sleep(1)
        print(5 - i,end='...')
    print()
    return win32api.GetCursorPos()

def init():
    print('[+] please place your mouse the block at (0,0) in 5s')
    origin = get_cur()
    print(f'[!] (0,0) at {origin}')
    print('[+] please place your mouse the block at (0,1) in 5s')
    now = get_cur()
    print(f'[!] (0,1) at {now}')
    step = now[0] - origin[0]
    return origin, step

origin, step = init()
ans = ans.reshape((12,12))
for i in range(12):
    for j in range(12):
        click_cur((origin[0] + step * j, origin[1] + step * i), ans[i][j])
        time.sleep(0.1)

输入后得到 flag:

flag{Lights_are_Linear_0ae7af96f3b90954}

阵列恢复大师

2021 年 10 月 3 日,阴转小雨。

你发现你运行在实验室机器上的炼丹脚本挂了。

「好好的国庆假期,怎么我还得来改程序……」收到邮件通知后,你登录了机器,看到的却是一大堆 Input/Output Error,回过神来才发现,放数据的阵列好像出了问题。

「完了!上面的数据我从来没有备份过!这下赶不上 DDL 发不了 paper 了!」你赶忙跑到机房,检查了一下阵列的情况——看起来盘没坏,都能读,只是可能是受到神秘宇宙射线(误)的影响,阵列的管理页面看不了,每块盘的 RAID 元数据好像也全不见了,更要命的是,你忘了当初组阵列时候盘的顺序和其他的参数。怎么恢复数据呢?上网搜索一下,好像得花不少钱。但你听说你的同学最近在搞信息什么大赛——或许可以让他们试试?

以下是两个压缩包,分别是一个 RAID 0 阵列的磁盘压缩包,和一个 RAID 5 阵列的磁盘压缩包,对应本题的两小问。你需要解析得到正确完整的磁盘阵列,挂载第一个分区后在该分区根目录下使用 Python 3.7 或以上版本执行 getflag.py 脚本以获取 flag。磁盘数据保证无损坏。

RAID 0 阵列压缩包,SHA256: f73bee3a2dce201566573f51bd28026c467182601eb6e55130db10c7c0c8127f

RAID 5 阵列压缩包,SHA256: 5eb1d2042ab5f8e2ee1508bf5e66632b4c307a595099e499aa9bc2a7255a6009

raid5

这道题 raid5 本质上比 raid0 更加简单,说起来真正对阵列有进一步的了解还是因为实验室 sas 服务器因为电源问题异常断电,导致八个硬盘中的一个不正常,造成了不小的麻烦。虽然没有着手解决,但也对 raid5 有了些更加好的理解。不过也因此,一直使用的镜像站挂了,换源之后开始怀念校内的千兆镜像了……

使用 file *.img 可以很快地看出来硬盘的基本信息:

$ file *.img
3D8qN9DH91Q.img: data
3RlmViivyG8.img: DOS/MBR boot sector; partition 1 : ID=0xee, start-CHS (0x0,0,2), end-CHS (0x3ff,255,63), startsector 1, 262143 sectors, extended partition table (last)
60kE0MQisyY.img: DOS/MBR boot sector; partition 1 : ID=0xee, start-CHS (0x0,0,2), end-CHS (0x3ff,255,63), startsector 1, 262143 sectors, extended partition table (last)
IrYp6co7Gos.img: data
QjTgmgmwXAM.img: data

因此,由于 raid5 的特性,第一块和第五块盘也就确定了,剩下的可能性一共 12 种,稍作实验,用 diskgenius 打开,选择组建虚拟raid,依次调整顺序,就可以得到想要的结果了。

只需将其导出为 img 镜像,并且使用 linux 系统挂载,根目录执行 getflag.py 即可。听说有不少人卡在了这里,毕竟 linux 和 windows 的目录分隔符号可能不一样啊(逃

flag{a18325a1ec0f58292908455c2df8ffcd}

raid0

用同样的方法确认一下第一块盘:

file *.img
1GHGGrmaMM0.img: data
5qiSQnlrA4Y.img: data
ID7sM2RWkyI.img: data
RApjvIxRlu0.img: data
d3Be7V0EVKo.img: data
eRL2MQSdOjo.img: data
jCC60mutgoE.img: data
wlOUASom2fI.img: DOS/MBR boot sector; partition 1 : ID=0xee, start-CHS (0x0,0,2), end-CHS (0x3ff,255,63), startsector 1, 262143 sectors, extended partition table (last)

raid0 是纯粹把数据分布式存储了,同时直接使用 010 Editor 查看,也可以发现块大小是 128KB,人肉搜索几块的连续数据块,可以得到对应的序列,然而在 diskgenius 中并看不到文件系统,再定睛一看才发现是 xfs,windows 和 diskgenius 都不支持。

将其整个磁盘克隆到新的虚拟磁盘内,而后就能将其拖入 ubuntu 虚拟机,直接可以打开。

于是运行,得到结果:

flag{4857cdeac07d8456fcaedb61d07b0b7d}


未完待续… Hackergame 2021 Writeup 0x02