不一样的flag

info
题目来源
不一样的flag.

解题过程

首先查找一下，没发现程序有壳，那便直接使用反编译工具直接获得程序的代码．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59

int __cdecl main(int argc, const char **argv, const char **envp)
{
  char v3; // [esp+17h] [ebp-35h]
  int v4; // [esp+30h] [ebp-1Ch]
  int v5; // [esp+34h] [ebp-18h]
  signed int v6; // [esp+38h] [ebp-14h]
  int i; // [esp+3Ch] [ebp-10h]
  int v8; // [esp+40h] [ebp-Ch]

  __main();
  v4 = 0;
  v5 = 0;
  qmemcpy(&v3, _data_start__, 0x19u);
  while ( 1 )
  {
    puts("you can choose one action to execute");
    puts("1 up");
    puts("2 down");
    puts("3 left");
    printf("4 right\n:");
    scanf("%d", &v6);
    if ( v6 == 2 )
    {
      ++v4;
    }
    else if ( v6 > 2 )
    {
      if ( v6 == 3 )
      {
        --v5;
      }
      else
      {
        if ( v6 != 4 )
LABEL_13:
          exit(1);
        ++v5;
      }
    }
    else
    {
      if ( v6 != 1 )
        goto LABEL_13;
      --v4;
    }
    for ( i = 0; i <= 1; ++i )
    {
      if ( *(&v4 + i) < 0 || *(&v4 + i) > 4 )
        exit(1);
    }
    if ( *((_BYTE *)&v8 + 5 * v4 + v5 - 41) == 49 )
      exit(1);
    if ( *((_BYTE *)&v8 + 5 * v4 + v5 - 41) == 35 )
    {
      puts("\nok, the order you enter is the flag!");
      exit(0);
    }
  }
}

注意到第 13 行 qmemcpy(&v3, _data_start__, 0x19u); 不必多想，直接得出结论，程序将 _data_start__ 复制到了 v3 的位置．查看 _data_start__ 存放的内容为：*11110100001010000101111# 含有 0x19 个字符（不计算 \0）．
不必担心 char v3; 无法存储 _data_start__ 导致程序错误的问题，_data_start__

可以看到 v3 与 v4 间留有巨大的空隙，从 v3 到 v4 的空间恰好能存储整个字符串（除了 \0）．

剩下的一切就不是那么的困难了，仔细看代码会发现输入的值（即v6）只能为 1、2、3、4，其余的值均会导致程序执行 exit(1); （即 exit(EXIT_FAILURE);）．继续看代码可发现一个对应关系

可发现，这正对应着一个「以竖直向下为 x 轴正方向、以水平向右为 y 轴正方向」的平面直角坐标系，即有 ：「v4 代表 x 轴坐标 ，v5 代表 y 轴坐标」．

考察第 51 行、第 53 行代码，会发现 49=='1' 并且 35=='#' ．然后分析看 *((_BYTE *)&v8 + 5 * v4 + v5 - 41) ，_BYTE 表示 1 byte 也就是 char 类型，那也就是 *((char *)&v8 + 5 * v4 + v5 - 41) ，看 v8 的地址是 esp+40h，那么 (char *)&v8 - 41 就是 esp + 40h - 41 == esp + 17h，也就是 &v3．那么就得到了最终的结论，*((_BYTE *)&v8 + 5 * v4 + v5 - 41) 就是 v3[5 * v4 + v5]．

刚才说过，「v4 代表 x 轴坐标 ，v5 代表 y 轴坐标」．还记得 *11110100001010000101111# 含有 0x19 个字符（不计算 \0）吗？

以 0 作为坐标原点建立「以竖直向下为 x 轴正方向、以水平向右为 y 轴正方向」，「v4 代表 x 轴坐标 ，v5 代表 y 轴坐标」就会发现 5 * v4 + v5 的值正是上标中格子的序号．而 5 * v4 + v5 正是 v3 的索引值．

这说明 v3 存储的实际上是一个被压扁地图，也就是下表中的模样．

分析第 53 行代码，if ( *((_BYTE *)&v8 + 5 * v4 + v5 - 41) == 35 )在刚才的分析中已经明白其等价于 if (v3[5 * v4 + v5] == '#') ，只有满足该条件才会执行 exit(0);（即 exit(EXIT_SUCCESS);）．那么本题的分析就全部结束了，只需要寻找按照全为 0 的路径移动即可到达 # 的位置．那么就可以轻松的得到 flag 为 222441144222．当然也还需要用 flag{} 包上，得到最终答案 flag{222441144222}．

Random

解压题目提供的压缩包，得到了出题人给出的 Python 脚本．其中使用写打开 Random.txt 文件并在其中填充由 Python 的 Random 模块生成的随机数据．

众所周知，在编程中通常使用的是伪随机数， Python 的 Random 模块生成的伪随机数可通过一定方式进行预测或重现．

info
INFO

将随机数的性质分为以下三类：[1]

• 随机性——不存在统计学偏差，是完全杂乱的数列．
• 不可预测性——不能从过去的数列推测出下一个出现的数．
• 不可重现性——除非将数列本身保存下来，否则不能重复相同的数列．

当时笔者想到了两种思路：

• 根据文件创建时间推测作为 Random 模块默认种子的系统时间的大致范围，并将其可能的取值区间进行遍历．试图找出其使用的随机数种子，并重现其生成的伪随机数．
• 根据已有输出预测新的随机数．

很明显这两条思路分别利用了不可重现性和不可预测性这两个真随机数应当具有的性质，或者说 Python 的 Random 模块生成的伪随机数具有的缺陷．

由于笔者查找了很久也没弄明白作为默认种子的时间格式，于是尝试思路 2．

通过查找发现 RandCrack 能通过读取前 624 次 random.getrandbits(32) 的结果来预测下一次 random.getrandbits(32) 的结果．

可以看到，出题人给出的脚本中进行 104 次循环，每次循环生成 一个 32 bits 随机数，一个 64 bits 随机数，一个 96 bits 的随机数．如果「1 个 64 bits 的随机数」可以拆成 「2 个 32 bits 的随机数」、「1 个 96 bits 的随机数」可以拆成 「3 个 32 bits 的随机数」．如果假设成立，一个循环也就是生成 6 个 32 bits 的随机数，那么 104 次循环也就是生成 624 个随机数．完美符合 RandCrack 的需求．

完美的像是出题人仿佛为此工具定制的题目一样．这样的巧合，让笔者觉得这绝非偶然，便尝试进行验证．

首先考虑如何拆分数字：
那么最方便的方式就是将字符串转换为 int 后，做位运算进行进行拆分．
笔者以 96 bits 的随机数拆分成低 32 bits 的随机数、中 32 bits 的随机数、高 32 bits 的随机数为例说明：
取 96 bits 的低 32 bits 仅需：

1

n & 0xffffffff

取 96 bits 的中 32 bits 仅需：

1

(n >> 32) & 0xffffffff

取 96 bits 的高 32 bits 仅需：

1

n >> 64

笔者在做题时，写出这段代码远没有此时写 WriteUp 这般自信．因为在 C 语言中，若对 整形变量 n 执行左移或右移操作，如果操作数大于等于 sizeof(n) * 8，那么便会对操作数取 sizeof(n) * 8 的模．

虽然笔者是在用 Python 解题，但 Python 是否允许对一个 int 右移 32 / 64 位，笔者并不确定．
当然最终的测试说明笔者的担心是多余的．

尝试时，会遇到新的问题：
64 bits 的随机数拆成 2 个 32 bits 的随机数，那么自然是高 32 bits 作为一个随机数、低 32 bits 作为另一个随机数．但 RandCrack 每次只能提交一个 32 bits 的随机数，该先提交高 32 bits 的随机数，还是低 32 bits 的随机数？ 当然，96 bits 的随机数也同理．

这确实令人感到困惑．

但好在只有两种可能性．尝试后发现需要先提交低 32 bits 的随机数．

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

from randcrack import RandCrack
import io
from hashlib import md5


rc = RandCrack()
file = io.open('random.txt', 'r')


def conversion(x: str):
    return int(x[:-1])


def getNumber():
    n1 = file.readline()
    rc.submit(conversion(n1))
    n2 = file.readline()
    n2 = conversion(n2)
    rc.submit(n2 & 0xffffffff)
    rc.submit(n2 >> 32)
    n3 = file.readline()
    n3 = conversion(n3)
    rc.submit(n3 & 0xffffffff)
    rc.submit((n3 >> 32) & 0xffffffff)
    rc.submit(n3 >> 64)
    return


for i in range(104):
    getNumber()

value = rc.predict_randrange(0, 4294967295)
value = str(value)
flag = md5(value.encode()).hexdigest()
print(flag)

参考资料

¹. 结成浩.图解密码技术[M].第3版.周自恒,译.北京:人民邮电出版社. ↩