KCTF2022秋季赛第二题——盗贼作乱题解

外层分析

序列号形式，先拿 ida 上手

输入部分应该就是，会先找到一个 -，所以序列号的形式是

1	xxxxxxx-xxxxxx

然后下面进行一大波判断，逐一下断点动调分析。

遇到的第一个函数，经过反复动调，确定是找表得到下标值，有点像 base62 感觉，并且传的第三个参数也很像 base62 的表

最后确定应该是 62 进制的一个转换，结果保存在第一个参数，并且保存的地址类似一个结构体，第一个 int 为长度，往后都是 int 型存储，这边把结构体定义一下，改改。

struct number
{
  int len;
  int num[8];
};

里面有一个常数，是由 IRtzloZ6iuB 字符串转换而来，把它转 10 进制发现它的值刚好是：

1	10000000000000000000

下面那个函数经过动调之后，发现只是把结构体设置了一下，所以我叫它 set_number。

最下面还有一个函数，它对我们之前转换的三个数字做了比较，并且需要返回结果都小于 0。

其实不难想到，先判断长度，大于返回 1，小于返回 -1，等于就比较后面的，很难不联想到是对数比大小，并且看上去应该是大于返回 1 小于返回 -1，等于应该会返回 0。

这样一来，就清晰了。

我们输入的序列号应该满足输入的两个数 num1<num2<num3=10000000000000000000。

分析循环体

首先看那个 >=0x200000 应该能明白了，循环不会超过 0x200000 多次。

第一个函数分析起来略微有点困难，但是输入 1-2 之后动调不难发现，每次循环结束，第一个参数的结构体的值都会对应加上我们输入的数值，看起来就有点像加法，后两个参数做加法赋值给第一个参数。

第二个函数大家应该能看到，进去之后发现会对两个数进行比较，其实这个时候需要输入大一点的数来试试，大体结果就是：大于 10000000000000000000 则减去再赋值，其实就是取模运算。

然后对两个数都这么操作一遍。

然后呢，在 if 之前那个函数，会对我们的 num11-1之后再赋值给 flag，最后和原来输入的数相等即可 k++，下面我们也能看到 k==10 才会判断正确。

那我们写一下表达式就是：

1	k*num1-1%10000000000000000000==num1

第二个数同理，只不过我们需要满足

1	k*num2+1%10000000000000000000==num2

其实根据一些数论的知识，我们显然不难发现：当 0<=k<=gcd(k,mod)时，对于任意 num，num*k%mod的结果将不相等（或者说，任意结果出现不会超过1次，若是小于n倍的gcd(k,mod)，则不会出现超过n次）。显然，0x20000是大不过那么大的模数的，因此要我们满足五次显然有点不合理。

但是我们可以注意一下，在满足条件之后，还有一个处理函数做了一些事情，因此我们直接开调这个函数去。

在这里可以发现，有个对内存 +4 的操作，不难想到，应该要触发这里的一个函数，然后这个内存可能刚好要指到 k，+4之后加上外面的 ++就是 +5，两次就是 +10，刚好凑出。

现在主要问题就是如何达成这个条件。

对上面的代码多次调试之后确定应该是外部循环变量 ==32 的时候才能触发这里的条件，因此这里的 k 可以说是确定的：k=32。

1
2
3

k*num1-1%n==num1
k*num2+1%n==num2
n=

在这里呢，可以把余式转为等式：

1
2
3

32*num1-1=k*n+num1 ===> 31*num1-1=k*n
32*num2+1=k*n+num2 ===> 31*num2+1=k*n
以上k均为任意不确定的常数，并且不保证相等

这里又需要一点点的小知识：因为 num1<n，所以在这里，s*num1=k*n 这里的任意常数 k<s 恒成立，所以对于未知数 k，我们跑不到 32 次一定能得到结果。

这里直接上 python 大法即可。

n=10000000000000000000
for i in range(33):
    if (i*n+1)%31==0:
        print(hex((i*n+1)//31))
for i in range(33):
    if (i*n-1)%31==0:
        print(hex((i*n-1)//31))
        
#0x35b870a6eb0f7bdf
#0x550eb25d9ed88421

然后就是 cyberchef 你好。

serial：

1	ZSxZerX4xb4-jyvP7x12lI7

最后感谢队友 ThTsOd神手把手教学。