AliyunCTF2023 NanoCatPlanet 出题笔记

Misc, 400 points, 3 solves。

出题思路

一切的起源，还是来自 ByteCTF2021 Final 出了一道 Arnold’s cat map 水印题。傻傻的我以为加密参数没给，就去爆破参数，然后解出来了，然后看到预期解是去某个偏僻的地方找藏起来的参数……

藏参数坏文明！所以！大家一起来爆破参数解 Arnold’s cat map 吧！

题解

题目附件是一个 11500x11500 的卫星图片，其他什么都没有。

虽然做过猫图题的选手看题目背景和水印大体上都能猜到这张图片使用了 Arnold’s cat map 加密，但为了新手考虑，我还是藏了一些附加信息。

通过查看文件二进制信息可以发现存在一个 tEXt 段，里面的信息是 Software=CatWatermark。这一个 block 的 CRC 有误，所以如果用 PIL 读取图片的话也会有提醒。

通过在 GitHub 搜索确定加密工具是 https://github.com/Konano/CatWatermark，里面自带了一个 encode 和 decode。

通过 README 可以知道，要 decode 这个加密过的卫星图需要原图和私钥，而私钥又分为三部分：x 轴偏移、y 轴偏移和迭代次数。原图其实不难找，这里略过（我也忘了在哪里找的）。

然后我们把目光转向 encode.py，发现这个代码实现了一个 $O(n^3)$ 的 Arnold’s cat map 算法。尝试下你会发现这代码巨慢无比，跑个 1000x1000 的图都已经特别慢了，更何况 11500x11500 的图，而且还要爆破三个参数，此时爆破复杂度为 $O(n^6)$，约为 $2313060765625000000000000$。

通过分析代码可以发现 Arnold’s cat map 的实现有问题。如下代码所示，new_image 在操作后并没有更新给 image，导致无论循环多少次，返回的 new_image 一直都是迭代 1 次的结果。此时爆破复杂度降到了 $O(n^4)$，约为 $17490062500000000$。

def arnold_cat_map(image, key=(1, 2, 1)):
    """
    Implements Arnold's cat map transformation on an image.
    """
    height, width, *_ = image.shape
    offset_x, offset_y, iterations = key

    new_image = np.zeros(image.shape, dtype=np.uint8)
    for i in range(iterations):
        for x in range(height):
            for y in range(width):
                _x, _y = x, y
                _y = (_y + offset_x * _x) % width
                _x = (_x + offset_y * _y) % height
                new_image[_x, _y] = image[x, y]
    return new_image

def arnold_cat_map_rev(image, key=(1, 2, 1)):
    """
    Implements Arnold's cat map transformation on an image (reverse).
    """
    height, width, *_ = image.shape
    offset_x, offset_y, iterations = key

    new_image = np.zeros(image.shape, dtype=np.uint8)
    for i in range(iterations):
        for x in range(height):
            for y in range(width):
                _x, _y = x, y
                _x = (_x - offset_y * _y) % height
                _y = (_y - offset_x * _x) % width
                new_image[_x, _y] = image[x, y]
    return new_image

继续观察代码。在添加水印的代码实现中，水印的位置是图片的正中央，所以如果水印的大小比原图的大小还小的话，那么恢复后的水印像素是不可能在图像边缘的。实际上，我们后续的解法就是利用这个特点来加速爆破。

首先我们观测到，在迭代次数为 1 的情况下，Arnold’s cat map 逆过程相当于先将矩阵每一列循环偏移打乱，再将每一行循环偏移打乱，而在打乱行的时候，第 1 行的像素是不会发生位置偏移的。通过观察第 1 行的元素，也可以发现水印图片的大小是要小于原图图片的。

同时，由代码可知，第 2 行的偏移量为 offset_x，也就是其中一个需要爆破的私钥参数。通过比较前两行的水印像素，我们可以直接算出 offset_x 为 $5809$。当你将第 2 行的水印像素循环偏移 $5809$ 格时，你能看到前两行的水印像素重合度非常高，证明我们的思路是对的。此时需要爆破的参数值也就只有 offset_y 了，爆破复杂度降到了 $O(n^3)$，约为 $1520875000000$。

对于 offset_y，我们可以假设水印图片的高也小于原图的高，将此作为剪枝条件，在爆破 offset_y 时，如果发现有的水印像素在还原后跑到了图片边缘处，我们就可以直接判断该 offset_y 不合法。经过爆破可以得到 offset_y 的值为 $2901$。

本题最后得到的水印如下：

实际上，题目描述中「这次猫咪们又将他们抓来的 flag 藏在了喵星球上，你们能找到吗？」以及「请注意：猫咪们 还尚未掌握航天科技。」也在二次提示选手，猫猫们只会把水印放在星球范围内！它们不会飞！！

以及原代码写的 Arnold’s cat map 算法实在是太慢啦~，其实也是故意写成这样的，给选手留点优化的空间。大家也可以尝试优化一下代码，让其跑得更快！所以最后复杂度能降到多少纯靠各位的代码优化能力了！

为了让大家动手复现和多思考，这里也不放 exp 了，不过复现过程中如果遇到什么困难也可以来跟我交流！

最后，敬请期待下一道难度加强版猫图题！喵 (=´ω｀=)