用图片讲一个故事——第五届强网杯Threebody题目官方题解

robots

 

题目描述:“三体人要入侵地球了,听说他们要使出最厉害的武器”

打开图片,发现有三个重复的图形,下面有”DIFOIL”字样,再下面好像还有一串字,但看不清楚。

图片看起来很奇怪,三个图形也呼应了“ThreeBody”的题目名称。

对于图片题目常规操作,使用StegSolve查看各图层,能发现两张隐藏的图片,其他图层再没有什么可疑的东西了:

图片上能认出半个星球、一个宇航员、一只手,以及《三体》中经典的一句话“你们都是虫子”。

对三体比较熟悉的同学可能可以猜出这张图以及原始图片是三体人使用二向箔对地球进行降维打击的场景。

这里也是小小地调侃了一下选手。如果不能找到通往下一步的方法,便只能停留在这里,被三体人嘲讽为“虫子”。

让我们再回到原始图片,放大看其中的细节:

可见图片中红黄蓝绿交错,有老式电视像素点的感觉。

通过010Editor查看像素点数值:

可见相邻像素点的RGB值都差异巨大,正常情况下相邻像素点的RGB值应该差不多才对。

再仔细观察可以发现,如果以4为周期的话相邻像素的数值就差不多了,考虑正常情况下该图片的像素点应该是每4个一组。相当于原始图片是四维的,这里被“降维打击”成了三维。我们这里需要做的,便是对图片进行升维处理。

BMP格式的头部有个biBitCount字节是控制每个像素点所占的比特数,现在为24,也就是3个字节,我们将这个字段改为4个字节对应的32:

保存后重新打开图片,便可以看到正常的图形了:

再次通过StegSolve进行查看,可以发现隐藏图片:

很多人看到“Welcome to QWB”可能就放松了警惕,以为这是一张随便放的没啥用的图片,便去找其他线索了。在CTF题目中忽视作者所给的线索是大忌,其实这里是非常关键的,所以在比赛过程中我有提示“所有图片的内容都是有意义的”。

其实细心的话可以看到左上角有一些小白点,代表着那里隐藏着一些信息。使用StegSolve的Data Extract功能查看该空间:

可以看到有“Who am I?”的字样。

再以列为方式查看:

可以看到有“David”字样。

根据这张照片和“David”的提示,通过一番搜索可得知这一位是知名的数学家大卫·希尔伯特:

不过除此之外我们得不到更多的信息了。Flag在哪呢?

让我们再用010Editor查看修改后的图片:

可以看到每个像素除了有RGB三个字段外还有一个rgbReserved字段,代表图片还有另一个通道。

这个字段有些跟rgbBlue是一样的,但也有一些有细微差异。

信息会不会就隐藏在rgbReserved字段呢?

rgbReserved字段是有数值的,所以该通道肯定有对应的图形,不过刚才通过StegSolve并没有看到该通道。

这里一个方法是修改BMP的文件头,使得StegSolve把该通道识别为Alpha通道。

不过这个可能需要了解一些BMP头相关的知识。这里采用一个更为暴力的方法,通过一个Python脚本解析BMP文件结构,把rgbReserved的数值复制给rgbBlue

with open('threebody.bmp', 'rb') as f:
    d = f.read()

w = 580
h = 435
b = 4
l = bytearray(d)
off = l[10]
for i in range(h):
    for j in range(w):
        l[off+j*b+i*b*w] = l[off+j*b+i*b*w+3]

with open('threebody_new.bmp', 'wb') as f:
    f.write(l)

再通过StegSolve进行查看,可以发现另一个隐藏的图形:

可见中间是一个黑白相间的正方形,其中左上角部分比其他部分颜色要深一些。

大家肯定能想到这里的黑白便是01序列,所以这是一个二维的二进制数组。考虑将这些二进制数组逐行保存成二进制文件,无果,并且如果是逐行保存的话不应该出现左上角的区域与其他区域密度明显不同的情况。

那这个二维数组里的信息是如何储存的呢?

这又要回到刚才提到的数学家希尔伯特了。希尔伯特提出过一种希尔伯特曲线,是一个高维到低维的映射。我们现在得到的二维二进制数组,可以通过这种方式进行降维处理转化成一串一维的二进制流。

并且,希尔伯特曲线的一个特性便是如果从低维还原成高维,则低维中相邻的点在高维中也是相邻的。这就解释了为什么会出现某一块区域密度与其他区域密度不同的情况。

不过从希尔伯特想到希尔伯特曲线可能并不十分容易,希尔伯特作为一位伟大的数学家一生的成就太多了,希尔伯特曲线可能只是其中不起眼的一个成就。

为了防止大家卡在这里,我在比赛中放出了另一个提示“不要埋头做,根据已有信息合理使用搜索引擎”。

这其实是一个大家都明白的道理,做CTF题目,尤其是做Misc题目的时候,善用搜索引擎是非常关键的一步。

但如果单纯搜索“希尔伯特”的话可能需要翻阅大量的网页,这里就需要大家有一些更加跳跃性的思维了。还记得这个题目的主体是什么吗?没错,是“三体”。那三体与希尔伯特这两个看似风马牛不相及的名词,会不会有某种联系呢?事实上,如果尝试以“三体 希尔伯特”作为关键词进行搜索, 很容易搜索引发这道题的出题思路的文章:

https://mp.weixin.qq.com/s/IOSGOJnGyiGoD8J1ITQJlg

这篇文章用文字和图片介绍了三个月前B站的一期关于降维打击的视频,视频当时还小火了一把。没错,降维打击!这不正是题目里的图片所讲述的故事。如果你看了文章会发现两张隐藏的图片都能在文章中的视频截图里找到。当发现这一点之后便可以确定,这个视频肯定跟这个题目有着密切的关系。而这个视频,讲的恰恰就是希尔伯特曲线。

下面要做的就是如何利用希尔伯特曲线把这里的二维数据转化成一维数据了。

不同维度的希尔伯特曲线是这样的:

因为这里我们得到的是128128的矩阵,128=2*7,所以我们应该使用7维的希尔伯特矩阵。

然后通过希尔伯特曲线的排列方式抽取各像素点的值,视频里已经给我们展示了,类似这样:

我们可以使用脚本把二维的01矩阵降维成一维的二进制流,便可以得到隐藏的文件。我在写脚本处理图片的时候用到了 https://github.com/galtay/hilbertcurve 这个库,实现的代码为:

import numpy as np
from PIL import Image
from hilbertcurve.hilbertcurve import HilbertCurve

with Image.open('threebody_new.bmp') as img:
    arr = np.asarray(img)
arr = np.vectorize(lambda x: x&1)(arr[:,:,2])

for x1 in range(np.size(arr,0)):
    if sum(arr[x1])>0:
        break
for x2 in reversed(range(np.size(arr,0))):
    if sum(arr[x2])>0:
        break
for y1 in range(np.size(arr,1)):
    if sum(arr[:,y1])>0:
        break
for y2 in reversed(range(np.size(arr,1))):
    if sum(arr[:,y2])>0:
        break

arr = arr[x1:x2+1, y1:y2+1]

hilbert_curve = HilbertCurve(7, 2)

s = ''
for i in range(np.size(arr)):
    [x,y] = hilbert_curve.point_from_distance(i)
    s += str(arr[127-y][x])

with open('output', 'wb') as f:
    f.write(int(s,2).to_bytes(2048, 'big'))

这里的output便是最后得到的文件,打开可以发现是一个C语言程序。编译并执行这个C语言程序,发的输出结果便为该C语言程序本身。

其实这种可以打印自身的程序学名叫Quine,2015年第一届强网杯的NESTING DOLL题目便是关于Qunie的,这里也是小小地纪念一下当年打CTF的时光。

不过如果对原始代码和程序输出的代码进行仔细比对的话可以发现,两者并不是完全相同的,在output的第11行后面多出了大片的空白字符,由空格和Tab构成。

通过把空格替换成0、Tab替换成1,可得到字符串01100110011011000110000101100111011110110100010000110001011011010100010101101110001101010110100100110000011011100100000101101100010111110101000001110010001100000011011000110001011001010110110101111101

这段二进制串还原便可得到Flag:flag{D1mEn5i0nAl_Pr061em}

后记:

ThreeBody是第五届强网杯的一道 Misc 的题目。可能由于是第二天才放出的,留给大家的时间不太多,直到比赛结束也只有0x300R一支队伍做了出来。

虽然做出的人很少,但看起来大家的参与感还是很足的。看到赛后在官方群里大家日常催更三体的writeup,很高兴大家能喜欢这道题:

说到 Misc 题目,很多人的第一印象是“脑洞”。确实很多 Misc 题目都需要一些脑洞才可以解,但是单纯靠脑洞来提高题目难度会使得题目变得很没意思。在出这道题的时候,我尽量把做题所需要的引导作为线索加入到题目当中,把需要的脑洞降到最小。不过这就需要大家足够地细心,不放过题目的任何一点提示。

另一方面,Misc 是 CTF 中最为多变的题目类型,我在出这道题的时候,也希望不仅仅是考察技术本身,更希望通过题目来讲述一个故事。题目的不同部分相互穿插关联,让大家做起来更有乐趣。降维打击是近几年互联网的热门词汇,而引发这道题目出题思路的那个三个月前几百万播放量的视频,在某种程度上也算是“时事热点”。我把视频里所讲述的故事,以Misc题目的形式展示了出来,让大家在做题过程中亲自感受降维打击的过程。而正如前面所说,本题目提供的原始图片,也可以看做四维的图片被降成了三维,这可能是另一种降维打击的可视化方式。

最后放出给我出该题目启发的B站视频,让我们来一起领略降维打击的震撼:

https://www.bilibili.com/video/BV1Sf4y147J9

(完)