Writeup

2019-googlectf-writeup-part2

l1nk [site]
想要混入安全圈的菜鸡，只会搞简单的bin

2019 googlectf writeup 下半段

2019 GoogleCTF part2

Crypto

Reverse a cellular automata

本质上为一个算法题（大雾）

题目描述

题目描述是说，当前使用了一种叫做胞元自动机cellular automata的东西（就是题目里面那个东西）的算法。这个东西解释起来有、、复杂，不过现实中很多地方都见过。胞元自动机相当于是定义了一种规则。假设我们定义了如下的3*3的方块:

1
2
3
= = =
= = =
= = =

假定如下的规则:

  • =表示活着的细胞
  • +表示死了的细胞
  • 定义一个规则：如果细胞四周（上下左右）有>=3个细胞存在，由于细胞养料不足，当前的细胞会死亡；否则，因为养料充足，细胞会重新活过来

胞元自动机是以状态为概念的。也就是说每一个细胞只考虑当前状态下周围的养料情况，不考虑下一个状态。那么根据规则，下一个状态的方块中的细胞会变成:

1
2
3
= + =
+ + +
= + =

可以注意到，此时“死去”了很多个细胞。虽然根据资源分配的话，四周的细胞死亡后，正中间的细胞本来是不必死去的，但是根据状态，它也会进入这个状态。然后再下一个状态就是:

1
2
3
= = =
= = =
= = =

恢复成最初的形状。这种就叫做胞元自动机的变化过程。
有很多的胞元自动机规则，分别就是规定了这种变化过程。题目中给出的Wolfram rule 126也是一种变化的规则:

第一排为当前状态。也就是说仅仅在当前状态以及相邻两个状态均相等的时候，当前状态转变成0，否则转变成1

题解

题目中给出了一个密文，并且给出了一个64bit下的胞元自动机生成的数字，推测出上一个状态，对应的数字作为密文的密钥即可解开答案:

1
2
3
4
Flag (base64)
U2FsdGVkX1/andRK+WVfKqJILMVdx/69xjAzW4KUqsjr98GqzFR793lfNHrw1Blc8UZHWOBrRhtLx3SM38R1MpRegLTHgHzf0EAa3oUeWcQ=
Obtained step (in hex)
66de3c1bf87fdfcf

这里观察Rule 126，可以发现一些规律。这里推荐网站https://www.wolframalpha.com/input/?i=Rule+126，里面已经帮我们总结了规律。
这种有规律，求解的问题都可以用z3来解决。这里参考https://blog.julianjm.com/Google-CTF-2019/#Automata照着写了一个:

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
from z3 import *

BITS = 64
target = 0x66de3c1bf87fdfcf

# Solver, which will help to get answer
solver = Solver()

# define the cell rule 
def cell(p, q, r):
    return Or(Xor(p,q), Xor(p,r))

#define the step for get step-answer

def step(src):
    return [cell(src[i-1], src[i], src[(i+1)%BITS]) for i in range(BITS)]


# define Bool array
src = BoolVector("src", BITS)
# and calculate the dst
dst = step(src)

# now add restriction
for i in range(BITS):
    mask = 1 << (BITS - 1 - i)
    solver.add (dst[i] == bool(target & mask))

# and calculate answer
while solver.check() == sat:
    model = solver.model()

    solbits = "".join(['1' if model.eval(src[i]) else '0' for i in range(BITS)])

    print("%x"%int(solbits, 2))

    # here we add a list into solver to tell solver that we don't need this kind of answer, so 
    # z3 will show another answer
    solver.add(Or([ model[v]!=v for v in src]))

基本上是把人家的搬运了一下。。。
这个输出非常多，可以用bash脚本之类的主动调用题目中给出的解题指令，即可得到答案。

SecureBoot

1
Your task is very simple: just boot this machine. We tried before but we always get ‘Security Violation’. For extra fancyness use socat -,raw,echo=0 tcp:$IP:$PORT'.

这个题目是一个pwn题，从名字中可以知道应该是和一个叫做Secure Boot的特性相关的一个题目。这个特性其实是关于UEFI(Unified Extensible Firmware Interface)的一个子特性。

用binwalk查看之后，发现是一个UEFI文件，然后用UEFITool查看之后发现里面内容如下:

官方给出的run.py脚本如下:

1
2
3
4
5
6
7
8
9
10
#!/usr/bin/python3
import os
import tempfile

fname = tempfile.NamedTemporaryFile().name

os.system("cp OVMF.fd %s" % (fname))
os.system("chmod u+w %s" % (fname))
os.system("qemu-system-x86_64 -monitor /dev/null -m 128M -drive if=pflash,format=raw,file=%s -drive file=fat:rw:contents,format=raw -net none -nographic 2> /dev/null" % (fname))
os.system("rm -rf %s" % (fname))

其中qemu那段启动的内容意思为:

  • -monitor /dev/null：将监视器重定向到主机的空白设备。
  • -m 128M: 设置启动时候的RAM大小为128M
  • -drive if=pflash,format=raw,file=%s: 设置一个驱动，同时可以设置相关的设备类型。这里设置的设备接口为pflash(闪存，相当于是连接了bios的那个东东)，磁盘格式为raw，意味着不需要检测格式头，然后定义了当前的OVMF.fd作为当前的操作镜像。这句话相当于是模拟了一个写有UEFI的闪存挂载到操作系统上的一个过程
  • -drive file=fat:rw:contents,format=raw： 同理，这句话设置了一个驱动，不过这里是将contents目录作为硬盘格式挂载到这上面（标注为raw之后就不需要关注是不是MBR/GPT的磁盘了）
  • -net none: 不支持网络通信
  • 2 > /dev/null: 重定向错误流

尝试运行这段内容后，程序会输出:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
UEFI Interactive Shell v2.2
EDK II
UEFI v2.70 (EDK II, 0x00010000)
Mapping table
      FS0: Alias(s):HD1a1:;BLK3:
          PciRoot(0x0)/Pci(0x1,0x1)/Ata(0x0)/HD(1,MBR,0xBE1AFDFA,0x3F,0xFBFC1)
     BLK0: Alias(s):
          PciRoot(0x0)/Pci(0x1,0x0)/Floppy(0x0)
     BLK1: Alias(s):
          PciRoot(0x0)/Pci(0x1,0x0)/Floppy(0x1)
     BLK2: Alias(s):
          PciRoot(0x0)/Pci(0x1,0x1)/Ata(0x0)
     BLK4: Alias(s):
          PciRoot(0x0)/Pci(0x1,0x1)/Ata(0x0)

If Secure Boot is enabled it will verify kernel's integrity and
return 'Security Violation' in case of inconsistency.
Booting...
Script Error Status: Security Violation (line number 5)

根据输出，我们知道当前的OVMF.fd中的UEFI开启了SecureBoot的特性，而当前内核并没有签名，导致了内核没有能够加载。

企图绕过

在UEFI加载的时候，有四个阶段

1
SEC(安全检测，完成从flat mode 到 real mode)--PEI(EFI前期初始化，初始化各个模块，CPU/IO等等)--DXE(初始化各类驱动)--BDS(初始化键鼠驱动，VGA等等)

但在这四个阶段之后，还会有一个叫做TSL(操作系统加载前期)的阶段，这个阶段中就是在最初的UEFI加载完成之后（但是还没有尝试开始运行的时候），会从主板上(CMOS处)加载关于UEFI的配置（也就是通常说的进入BIOS）。在这之后才会正式进入RT(Runtime)加载操作系统等等。
所以想到，我们可以通过手动修改BIOS的配置来关闭SecureBoot。但是该题没有告诉我们到底怎么进入BIOS，此时只能一通乱按，终于发现是在按下了f12的时候可以打开这个界面:

1
2
3
4
5
6
7
8
9
10
BdsDxe: loading Boot0000 "UiApp" from Fv(7CB8BDC9-F8EB-4F34-AAEA-3EE4AF6516A1)/FvFile(462CAA21-7614-4503-836E-8AB6F4662331)
BdsDxe: starting Boot0000 "UiApp" from Fv(7CB8BDC9-F8EB-4F34-AAEA-3EE4AF6516A1)/FvFile(462CAA21-7614-4503-836E-8AB6F4662331)
****************************
*                          *
*   Welcome to the BIOS!   *
*                          *
****************************

Password?
****

这里会发现，程序在DXE阶段加载了一个好叫做UiAPP的文件，并且要求我们输入密码。于是这里想到说，这个UiAPP可能是实现了输入密码功能的一个自定义的EFI文件。此时我们注意到7CB8BDC9-F8EB-4F34-AAEA-3EE4AF6516A1这个值，这个值我们在UEFITool的截图中看到过。

于是想到，能不能将这个文件导出来看一下。这里使用工具uefi-firmware-parser进行导出:

1
uefi-firmware-parser -ecO ./OVMF.fd

输出中可以开到如下的内容:

1
2
3
4
5
6
File 38: 462caa21-7614-4503-836e-8ab6f4662331 type 0x09, attr 0x00, state 0x07, size 0x1beae (114350 bytes), (application)
Section 0: type 0x10, size 0x1be44 (114244 bytes) (PE32 image section)
Section 1: type 0x19, size 0x34 (52 bytes) (Raw section)
Section 2: type 0x15, size 0x10 (16 bytes) (User interface name section)
Name: UiApp
Section 3: type 0x14, size 0xe (14 bytes) (Version section section)

这段就是我们需要找到的内容(目录有点深，得搜索出来才行)

1
SecureBoot\OVMF.fd_output\volume-0\file-9e21fd93-9c72-4c15-8c4b-e77f1db2d792\section0\section3\volume-ee4e5898-3914-4259-9d6e-dc7bd79403cf\file-462caa21-7614-4503-836e-8ab6f4662331

漏洞点

首先利用全局搜索找到字符串L”Password”，发现其相关函数如下:

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
60
61
62
63
64
65
66
67
68
69
__int64 checkPassword()
{
  unsigned __int16 index; // ax
  char v2; // [rsp+2Ch] [rbp-BCh]
  __int16 chr; // [rsp+2Eh] [rbp-BAh]
  char v4; // [rsp+30h] [rbp-B8h]
  char buffer[128]; // [rsp+38h] [rbp-B0h]
  __int64 v6; // [rsp+B8h] [rbp-30h]
  _QWORD *v7; // [rsp+C0h] [rbp-28h]
  __int64 v8; // [rsp+C8h] [rbp-20h]
  unsigned __int16 i; // [rsp+D6h] [rbp-12h]
  unsigned __int64 error_time; // [rsp+D8h] [rbp-10h]

  error_time = 0i64;
  v8 = 32i64;
  wputs(L"****************************\n");
  wputs(L"*                          *\n");
  wputs(L"*   Welcome to the BIOS!   *\n");
  wputs(L"*                          *\n");
  wputs(L"****************************\n\n");
  v7 = (_QWORD *)Initialize(32i64);
  while ( error_time <= 2 )
  {
    i = 0;
    wputs(L"Password?\n");
    while ( 1 )
    {
      while ( 1 )
      {
        v6 = (*(__int64 (__fastcall **)(_QWORD, char *))(*(_QWORD *)(qword_1BC68 + 48) + 8i64))(
               *(_QWORD *)(qword_1BC68 + 48),
               &v2);
        if ( v6 >= 0 )
        {
          if ( chr )
            break;
        }
        if ( v6 == 0x8000000000000006i64 )
          (*(void (__fastcall **)(__int64, __int64, char *))(qword_1BC78 + 96))(
            1i64,
            *(_QWORD *)(qword_1BC68 + 48) + 16i64,
            &v4);
      }
      if ( chr == '\r' )
        break;
      if ( i <= 139u )
      {
        index = i++;
        buffer[index] = chr;
      }
      wputs("*");
    }
    buffer[i] = 0;
    wputs(L"\n");
    sha256((__int64)buffer, i, (__int64)v7);
    if ( *v7 == 0xDEADBEEFDEADBEEFi64
      && v7[8] == 0xDEADBEEFDEADBEEFi64
      && v7[16] == 0xDEADBEEFDEADBEEFi64
      && v7[24] == 0xDEADBEEFDEADBEEFi64 )
    {
      sub_C46((__int64)v7);
      return 1i64;
    }
    wputs("W");
    ++error_time;
  }
  sub_C46((__int64)v7);
  return 0i64;
}

程序要求我们输入128个字节，然后将这128个字节进行sha256，结果要为四个DEADBEEFDEADBEEF的时候，就会返回1表示密码输入正确。
这里会发现一个很显眼的漏洞点:程序允许我们读入140字节，但是申请的空间却只有128个字节那么大。总共可以多溢出12个字节。由于这里是位于EFI程序中，此时地址并不是特别高位，所以可以粗略的认为我们此时可以修改v6和v7处的变量。

从定义上可以发现，v7是一个地址，而我们栈溢出又正好可以溢出到v7的地址处，于是一个自然的想法就是，通过爆破sha256，得到一个粗略任意地址写的一个漏洞（因为必须要将buffer进行sha256，所以这个写入也不是那么受控制，不过如果控制了v7相当于是可以往部分位置写数据了）

那么要往哪里写呢？这个倒是一个大问题，毕竟这个题目不是在通常的运行环境下，没有libc等一系列东西，所以得考虑用别的办法。不过其实考虑到，分页保护这个过程发生在操作系统