OverTheWire Advent Bonanza 2019 Writeup

この大会は2019/12/1 21:00(JST)～2019/12/26 21:00(JST)に開催されました。
今回もチームで参戦。結果は428点で948チーム中136位でした。
自分で解けた問題をWriteupとして書いておきます。

Santaty flag (misc)

Discordに入って#advent-2019チャネルを見ると、トピックにフラグが書いてあった。

General CTF Discussion - bridged with #advent on OverTheWire.org IRC -- Santaty Flag: AOTW{Testing123}

AOTW{Testing123}

7110 (keylogger, programming)

ガラケーキーパッドのログがついているので、復元する問題。101はDelete、102は左、103は右に移動する。時間が1000開いている場合は次の文字入力になっていると判断すると、入力文字を復元することができる。

KEY_ZERO  = ' 0'
KEY_ONE   = '.,\'?!"1-()@/:'
KEY_TWO   = 'abc2'
KEY_THREE = 'def3'
KEY_FOUR  = 'ghi4'
KEY_FIVE  = 'jkl5'
KEY_SIX   = 'mno6'
KEY_SEVEN = 'pqrs7'
KEY_EIGHT = 'tuv8'
KEY_NINE  = 'wxyz9'
KEY_STAR  = '@/:_;+&%*[]{}'

def get_chr(key, count):
    if key == '0':
        return KEY_ZERO[(count-1)%len(KEY_ZERO)]
    elif key == '1':
        return KEY_ONE[(count-1)%len(KEY_ONE)]
    elif key == '2':
        return KEY_TWO[(count-1)%len(KEY_TWO)]
    elif key == '3':
        return KEY_THREE[(count-1)%len(KEY_THREE)]
    elif key == '4':
        return KEY_FOUR[(count-1)%len(KEY_FOUR)]
    elif key == '5':
        return KEY_FIVE[(count-1)%len(KEY_FIVE)]
    elif key == '6':
        return KEY_SIX[(count-1)%len(KEY_SIX)]
    elif key == '7':
        return KEY_SEVEN[(count-1)%len(KEY_SEVEN)]
    elif key == '8':
        return KEY_EIGHT[(count-1)%len(KEY_EIGHT)]
    elif key == '9':
        return KEY_NINE[(count-1)%len(KEY_NINE)]
    elif key == '10':
        return KEY_STAR[(count-1)%len(KEY_STAR)]

with open('sms4.csv', 'r') as f:
    lines = f.readlines()[6:-17]

pre_time = 0
msg = [''] * 1024
cur_key = '11'
cur_count = 1
index = 0

for line in lines:
    csv = line.rstrip()
    cur_time = int(csv.split(',')[0])
    key = csv.split(',')[1]
    if int(key) <= 10:
        if cur_key == '11':
            cur_key = key
            cur_count = 1
        elif key != cur_key:
            if int(cur_key) <= 10:
                char = get_chr(cur_key, cur_count)
                msg.insert(index, char)
                index += 1
            elif cur_key == '101':
                del msg[index]
            elif cur_key == '102':
                index -= 0
            elif cur_key == '103':
                index += 2
            cur_key = key
            cur_count = 1
        elif cur_time - pre_time > 1000:
            char = get_chr(cur_key, cur_count)
            msg.insert(index, char)
            index += 1
            cur_key = key
            cur_count = 1
        else:
            cur_count += 1
    else:
        if int(cur_key) <= 10:
            char = get_chr(cur_key, cur_count)
            msg.insert(index, char)
        else:
            if cur_key == '101':
                del msg[index]
                index -= 1
            elif cur_key == '102':
                index -= 1
            elif cur_key == '103':
                index += 1
        cur_count = 1
        cur_key = key

    pre_time = cur_time

char = get_chr(cur_key, cur_count)
msg.insert(index, char)
msg = ''.join(msg)
print msg

実行結果は以下の通り。

alright pal heres ye flag good luck entering it with those hooves lol its aotw{l3ts_dr1nk_s0m3_eggn0g_y0u_cr4zy_d33r}

AOTW{l3ts_dr1nk_s0m3_eggn0g_y0u_cr4zy_d33r}

Sudo Sudoku (misc, sudoku)

Sudokuのルールなど条件を指定して、z3で解く。フラグは左上から時計回りに外周の数字を並べて、フラグの形式にしたもの。

from z3 import *

#### Rules of Sudoku ####
def betweenOneToNine(val, s):
    for i in range(n):
        for j in range(n):
            s.add(1 <= val[i][j], val[i][j] <= n)

def distinctRow(val, s):
    for i in range(n):
        tmpList = []
        for j in range(n):
            tmpList.append(val[i][j])
        s.add(Distinct(tmpList))

def distinctColumn(val, s):
    for i in range(n):
        tmpList = []
        for j in range(n):
            tmpList.append(val[j][i])
        s.add(Distinct(tmpList))

def distinctBlock(val, s):
    for k in range(3):
        for l in range(3):
            tmpList = []
            for i in range(3):
                for j in range(3):
                    tmpList.append(val[3*k+i][3*l+j])
            s.add(Distinct(tmpList))

#### Set known numbers ####
def setNum(val,s,x,y,num):
    s.add(val[x-1][y-1] == num)

def condition1(val, s):
    setNum(val, s, 1, 9, 1)
    setNum(val, s, 2, 2, 1)
    setNum(val, s, 2, 3, 2)
    setNum(val, s, 3, 7, 2)
    setNum(val, s, 4, 9, 2)
    setNum(val, s, 5, 2, 2)
    setNum(val, s, 7, 7, 1)
    setNum(val, s, 8, 1, 1)
    setNum(val, s, 8, 6, 2)
    setNum(val, s, 9, 4, 1)


#### Add other conditions ####
def condition2(val, s):
    s.add(val[1][8] + val[1][7] + val[2][0] + val[7][3] + val[7][3] == 23)
    s.add(val[0][4] + val[3][6] + val[8][4] + val[6][7] + val[1][2] + val[0][4] == 19)
    s.add(val[8][1] + val[8][2] + val[5][1] + val[4][8] == 15)
    s.add(val[8][6] + val[7][7] + val[2][1] + val[3][8] == 26)
    s.add(val[8][5] + val[0][4] + val[8][2] + val[1][7] + val[2][2] == 20)
    s.add(val[8][6] + val[3][8] + val[1][5] + val[0][7] + val[0][2] + val[2][3] == 27)
    s.add(val[2][6] + val[7][8] + val[8][6] + val[1][1] + val[7][7] + val[6][2] == 31)
    s.add(val[3][2] + val[8][7] + val[0][3] + val[8][5] == 27)
    s.add(val[5][4] + val[1][7] + val[5][7] + val[8][6] + val[5][0] == 33)
    s.add(val[0][1] + val[0][7] + val[3][6] + val[4][3] == 21)
    s.add(val[2][0] + val[8][3] + val[2][1] + val[8][0] + val[0][3] == 20)
    s.add(val[5][7] + val[2][0] + val[5][5] + val[3][2] + val[1][5] == 25)

#### n * n values ####
n = 9
val = [[Int("val[%d,%d]" % (i,j)) for j in range(n)] for i in range(n)]
s = Solver()

#### add conditions ####
betweenOneToNine(val, s)
distinctRow(val, s)
distinctColumn(val, s)
distinctBlock(val, s)
condition1(val, s)
condition2(val, s)

#### solve ####
r = s.check()
if r == sat:
    m = s.model()
    for i in range(n):
        for j in range(n):
            print('%d' % m[val[i][j]].as_long()),
        print
else:
    print(r)

#### print flag ####
flag = ''
i = 0
j = 0
while j < n - 1:
     flag += str(m[val[i][j]].as_long())
     j += 1
while i < n - 1:
     flag += str(m[val[i][j]].as_long())
     i += 1
while j > 0:
     flag += str(m[val[i][j]].as_long())
     j -= 1
while i > 0:
     flag += str(m[val[i][j]].as_long())
     i -= 1

flag = 'AOTW{%s}' % flag
print flag

実行結果は以下の通り。

8 6 4 7 2 9 5 3 1
9 1 2 4 5 3 7 6 8
3 7 5 6 1 8 2 4 9
6 4 9 8 7 5 3 1 2
7 2 1 9 3 6 8 5 4
5 3 8 2 4 1 6 9 7
4 8 6 5 9 7 1 2 3
1 9 7 3 6 2 4 8 5
2 5 3 1 8 4 9 7 6
AOTW{86472953189247356794813521457639}

AOTW{86472953189247356794813521457639}

Easter Egg 2 (fun)

問題が増えるとき(?)に出現するっぽい画像(以下のURL)にアクセスする。

https://advent2019.overthewire.org/static/img/transparent-santa-gif-flying.gif

レスポンスヘッダに以下が設定されている。

X-EasterEgg2: ==QftRHdz8VZydmZuNzXhJ3MxcGMltnSHJkT

base64文字列が反転されているので、反転してデコードする。

$ echo ==QftRHdz8VZydmZuNzXhJ3MxcGMltnSHJkT | rev | base64 -d
NBGJ{e0g13ra_3nfgre_3ttm}

さらにROT13のデコードをする。

$ echo ==QftRHdz8VZydmZuNzXhJ3MxcGMltnSHJkT | rev | base64 -d | tr '[A-Za-z]' '[N-ZA-Mn-za-m]'
AOTW{r0t13en_3aster_3ggz}

AOTW{r0t13en_3aster_3ggz}

Santa's Signature (crypto)

$ nc 3.93.128.89 1219
Dear Santa,
Last christmas you gave me your public key,
to confirm it really is you please sign three
different messages with your private key.

Here is the public key you gave me:
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAu1jb39GZlWh9XPpOHmaa
ZEYrbNqa6KMf4E211NYklZytuRBQy71zOI8V9O7i12C4hjhoAzj8JnXkpFur7w3z
PLimVB/B+KfQq3fo5YqWzVhi06LuuCvyGwkWSO3K2sMyH3ISKlPKlyVzhr/9qeHR
2gbFXK6so8rHXpZGgSJk5TimuY4yb+TNjpfi4srQIyepVPCjECs4n+Ii941c+7KW
2wScAUk7MuMExuKuNvvKeTZdhQeq/ZCd0otascBXk9GmsBx0eVBzG8/94Hm+9egl
eQu1DqLn/HZovaAcyIbqjunuB/KoM76DISjhmcaRyipafEJm+u9/jPHAG+8dLUuc
Wr+04D9iAFBEt5XBA2u3WaaL4/eP7hR5mR9QOxH8YilpttfQJY/78AXo+GJtECTF
LJ7zRyP1Jq89qdySJVumxwZmKP3sE7mojTb2030TDF/27v+vMVVtczyAQdybDHzj
8ainHn2SP3yTTOnjNTuGWvIcs3Qa4bv78ezTmLofpsZLoRbcx5FV2YXuiao8ezD/
WBuIOlDZhqRiods3LN8x7gNQo8zDmwY0Z54oac2dPgIUr1AvnDbEGdqyCyJRIrnW
kLFMXdy2GJLSFMk+rswORKEtojCmqQIydW7+5M4J4FhVNyVtNuPcLfUjF+e5+V5E
+piEcAsCnQ1k9QHGZAuVxX8CAwEAAQ==
-----END PUBLIC KEY-----
Message 1 you signed (hex encoded):12
Signature 1:1
Looks like you aren't Santa after all!

RSA署名で暗号と平文の組を3パターン答えればよいだけ。

import socket
from Crypto.PublicKey import RSA

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

sc = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
sc.connect(('3.93.128.89', 1219))

data = recvuntil(sc, 'END PUBLIC KEY-----\n').rstrip()
print data

pub_pem = '\n'.join(data.split('\n')[6:])
pub_key = RSA.importKey(pub_pem)
n = pub_key.n
e = pub_key.e

for i in range(1, 4):
    m = hex(pow(i, e, n))[2:].rstrip('L')
    s = i
    data = recvuntil(sc, '(hex encoded):')
    print data + str(m)
    sc.sendall(str(m) + '\n')
    data = recvuntil(sc, ':')
    print data + str(s)
    sc.sendall(str(s) + '\n')

data = recvuntil(sc, '\n').rstrip()
print data
data = recvuntil(sc, '\n').rstrip()
print data

実行結果は以下の通り。

Dear Santa,
Last christmas you gave me your public key,
to confirm it really is you please sign three
different messages with your private key.

Here is the public key you gave me:
-----BEGIN PUBLIC KEY-----
MIICIjANBgkqhkiG9w0BAQEFAAOCAg8AMIICCgKCAgEAu1jb39GZlWh9XPpOHmaa
ZEYrbNqa6KMf4E211NYklZytuRBQy71zOI8V9O7i12C4hjhoAzj8JnXkpFur7w3z
PLimVB/B+KfQq3fo5YqWzVhi06LuuCvyGwkWSO3K2sMyH3ISKlPKlyVzhr/9qeHR
2gbFXK6so8rHXpZGgSJk5TimuY4yb+TNjpfi4srQIyepVPCjECs4n+Ii941c+7KW
2wScAUk7MuMExuKuNvvKeTZdhQeq/ZCd0otascBXk9GmsBx0eVBzG8/94Hm+9egl
eQu1DqLn/HZovaAcyIbqjunuB/KoM76DISjhmcaRyipafEJm+u9/jPHAG+8dLUuc
Wr+04D9iAFBEt5XBA2u3WaaL4/eP7hR5mR9QOxH8YilpttfQJY/78AXo+GJtECTF
LJ7zRyP1Jq89qdySJVumxwZmKP3sE7mojTb2030TDF/27v+vMVVtczyAQdybDHzj
8ainHn2SP3yTTOnjNTuGWvIcs3Qa4bv78ezTmLofpsZLoRbcx5FV2YXuiao8ezD/
WBuIOlDZhqRiods3LN8x7gNQo8zDmwY0Z54oac2dPgIUr1AvnDbEGdqyCyJRIrnW
kLFMXdy2GJLSFMk+rswORKEtojCmqQIydW7+5M4J4FhVNyVtNuPcLfUjF+e5+V5E
+piEcAsCnQ1k9QHGZAuVxX8CAwEAAQ==
-----END PUBLIC KEY-----
Message 1 you signed (hex encoded):1
Signature 1:1
Message 2 you signed (hex encoded):5bf10144e9e96f26774f5750df1083d68ee461e4e4932291b0a511c5f2f8860db89470008ed3971b92d91a8b6ec8bc122f1ca5f3beb7533b014604f633da5b83ebed3d8f092f0636b50e62a492a407c35357b30815b78c55a5dcf40ce5b94cf8b6aebc67a596e56ea171f938e27671a4dae3d2dc9ae3f79624579123a166e5745c24799f490e5d8e2d00709445366c9278ed65aff3930daa5aeeab58ea566b636e7f72973ab9ed7b0af698fb3dc9ea5c2d4ebc330a7ef06fa457ff27f6f697fb047b8046f2e801b97e7d753ef8c07089082ff1e1f8bea9ff1c8023f054f0640f109c5aa055e96743cb09d07651334c483ebdebe8482e7a723ee308d6f7398fa792461badea070b2cf2c850ad20dd236f7ed6832702c27896c408ff34716215e0d9e9907e0b9ce9fb08f8c0b81619255eff9d046ca1d665b355e948e3e6cf5a377ac3e09f73c008a07975e20ed164458deee1cd019d6a9eb64e1472fa40388fec77c16ed57147cbc193477923eb5d6ac352d65e0934f815c5915608855959b5e28b425f9b1fbd42348c6128efe1307c9bc1fd8df8b2ac6911f3905be0d6bbdc11c8a7b50c800879f4665a7cd241230805173e9a88b90d95246fd7d1056c7bcdb66f6f096321c07a978720ba8a38114331e2539fd54fe484c093becdcbe38f16120f356b330de703835efc5421e39124ccb4d289e94cfc9fb5f0d846b8cd94a577
Signature 2:2
Message 3 you signed (hex encoded):4ae2bad4c417894d61336509fd5bbed5d698d2dd666dd4b3e022f022a99ca96963b22a582227634b328b7a209ebaaa8dfc026193f542706cce3b517df79314c0cfd2932d8a342361e902717145c66965d289b3dc175a26546a7860bb0f6c7894ae741a6c8793c796d267f67680c8a19375cfbad66346327def10a499ee9b70ba1eb8a74c52ddd70dae2e7f3bbedaa1f24d497d7382dbca8ba2f091f054bcfd6edb69f1ba0f43195c23edf288bf0694980d38f3df75c5eaafc2e3ca21a92b8d896b2e20e9ddc7e64817dbc6c92b856cd3184468093e2cab9bb004ffcd376e8bd08261673e9a9fd70e003f255cf76628d446cc343ae8d2b5f2396266e8845087e31e046039363b90aba5cb63dbb84eac5bdd0016e72ed3e32c06b1fe82f317f5bfe629a989b8b3df614f501305055a4806fdbc1a37dedbd1cba85205f1391be9bcfdfd9d4947568ed3d0f9cfb09443f8bc757addb2da4d9e6e6f0fd152d3c82c0771a379236d94aabe9ad9309b2486dd5927c2a5fcc4ace15217cae3bd7842e6eaaf3b82869c0caf5c2415ab5f66488607d21ca520a5818b262274997d44dfd27dbc7e9ce27445f57f8dcb8164fec46842e19eb686682446f1ed2c36218794e9447133ff0e883e91e874f9597704d6776aa686cd328080343014423963ae23ba4884d9df62f5694a3aeb1c7ccef01465ebef2db366fd70fb6a7cd260cef9c46797
Signature 3:3
Hello Santa, here is your flag:
AOTW{RSA_3dg3_c4s3s_ftw}

AOTW{RSA_3dg3_c4s3s_ftw}

Survey (misc)

アンケートに答えたら、フラグが表示された。

AOTW{Surv3y5_5h0w_7h4t_5urv3ys_n3v3r_l13}