Teaser CONFidence CTF 2019 Writeup

この大会は2019/3/16 20:00(JST)~2018/3/17 20:00(JST)に開催されました。
今回もチームで参戦。結果は 330点で546チーム中56位でした。
自分で解けた問題をWriteupとして書いておきます。

Sanity check (warmup)

freenodeで#p4teamチャネルに接続する。

20:01 *topic : Teaser lasts from March 16th 11:00UTC to March 17th 11:00UTC | https://confidence2019.p4.team | p4{thanks_for_playing_:)}
p4{thanks_for_playing_:)}

Count me in! (crypto, warmup)

AESのCTRもどき。各ブロックごとに並列で暗号化するが、カウンターを共有しており、61ブロックを32本の同時並行処理だと同じカウンターを使う確率が高い。フラグの部分以外は平文と暗号文が分かっている。
各ブロックの平文と暗号文のXORのどれかがフラグの各ブロックの平文と暗号文のXORになっていると推測し、復号する。

def chunk(input_data, size):
    return [input_data[i:i + size] for i in range(0, len(input_data), size)]

def xor(*t):
    from functools import reduce
    from operator import xor
    return [reduce(xor, x, 0) for x in zip(*t)]

def xor_string(t1, t2):
    t1 = map(ord, t1)
    t2 = map(ord, t2)
    return "".join(map(chr, xor(t1, t2)))

def is_printable(s):
    for c in s:
        if ord(c) < 32 or ord(c) > 126:
            return False
    return True

def unpad(s):
    return s[:-ord(s[-1])]

pt_head = """The Song of the Count

You know that I am called the Count
Because I really love to count
I could sit and count all day
Sometimes I get carried away
I count slowly, slowly, slowly getting faster
Once I've started counting it's really hard to stop
Faster, faster. It is so exciting!
I could count forever, count until I drop
1! 2! 3! 4!
1-2-3-4, 1-2-3-4,
1-2, i love couning whatever the ammount haha!
1-2-3-4, heyyayayay heyayayay that's the sound of the count
I count the spiders on the wall...
I count the cobwebs in the hall...
I count the candles on the shelf...
When I'm alone, I count myself!
I count slowly, slowly, slowly getting faster
Once I've started counting it's really hard to stop
Faster, faster. It is so exciting!
I could count forever, count until I drop
1! 2! 3! 4!
1-2-3-4, 1-2-3-4, 1,
2 I love counting whatever the
ammount! 1-2-3-4 heyayayay heayayay 1-2-3-4
That's the song of the Count!
"""

with open('output.txt', 'r') as f:
    enc = f.read().decode('hex')

enc_list = chunk(enc, 16)
pt_head_list = chunk(pt_head, 16)

flag = ''
for i in range(4):
    enc_flag_parts = enc_list[i - 4]
    for j in range(len(enc_list) - 4):
        key = xor_string(enc_list[j], pt_head_list[j])
        dec_flag_parts = xor_string(enc_flag_parts, key)
        if i == 3:
            dec_flag_parts = unpad(dec_flag_parts)
        if is_printable(dec_flag_parts):
            flag += dec_flag_parts

print flag
p4{at_the_end_of_the_day_you_can_only_count_on_yourself}

Bro, do you even lift? (crypto)

p(=35671)の1乗からpの100乗までmodulusを段階的に増やし、元のデータに近づいていくような方式でフラグを求める。

from Crypto.Util.number import *

p = 35671

a1 = 12172655049735206766902704703038559858384636896299329359049381021748
a2 = 11349632906292428218038992315252727065628405382223597973250830870345
a3 = 9188725924715231519926481580171897766710554662167067944757835186451
a4 = 8640134917502441100824547249422817926745071806483482930174015978801
a5 = 170423096151399242531943631075016082117474571389010646663163733960337669863762406085472678450206495375341400002076986312777537466715254543510453341546006440265217992449199424909061809647640636052570307868161063402607743165324091856116789213643943407874991700761651741114881108492638404942954408505222152223605412516092742190317989684590782541294253512675164049148557663016927886803673382663921583479090048005883115303905133335418178354255826423404513286728

pre_base = [0]
for i in range(1, 101):
    tmp_a1 = a1 % (p**i)
    tmp_a2 = a2 % (p**i)
    tmp_a3 = a3 % (p**i)
    tmp_a4 = a4 % (p**i)
    tmp_a5 = a5 % (p**i)

    base = []
    for b in pre_base:
        for x in range(p):
            y = b + x * (p**(i-1))
            f = (tmp_a1 * y**4 + tmp_a2 * y**3 + tmp_a3 * y**2 
                + tmp_a4 * y + tmp_a5) % (p**i)
            if f == 0:
                base.append(y)
    pre_base = base
    print '%03d' % i, pre_base

for b in pre_base:
    flag = long_to_bytes(b)
    if flag.startswith('p4{'):
        print flag
p4{Th4t5_50m3_h34vy_l1ft1n9}

UTCTF Writeup

この大会は2019/3/9 10:00(JST)~2018/3/11 10:00(JST)に開催されました。
今回もチームで参戦。結果は 6350点で581チーム中25位でした。
自分で解けた問題をWriteupとして書いておきます。

[basics] re (Reverse Engineering 100)

$ strings calculator | grep utflag
utflag{str1ng5_15_4_h4ndy_t00l}
utflag{str1ng5_15_4_h4ndy_t00l}

[basics] forensics (Forensics 100)

$ cat secret.jpg 
utflag{d0nt_tru5t_f1l3_3xt3ns10n5}
utflag{d0nt_tru5t_f1l3_3xt3ns10n5}

Regular Zips (Forensics 600)

パスワード付きZIPとproblem.txt(2回目の解凍以降はhint.txt)がある。problem.txt(2回目の解凍以降はhint.txt)には正規表現が書いてあり、パスワードが満たす条件になっている。解凍すると、パスワード付きZIPとhint.txtが展開されるということを繰り返す。

import zipfile
import exrex
import os

DIR = './archives/'

def unzip_with_pwd(filename, path=DIR, pwd=''):
    with zipfile.ZipFile(filename, 'r') as zip_file:
        try:
            zip_file.extractall(path=path, pwd=pwd)
            return True
        except:
            return False

filename = 'RegularZips.zip'
exp_file = 'problem.txt'

i = 1
finish = False
while True:
    print 'Round %d' % i
    with open(exp_file, 'r') as f:
        exp = f.read()

    for pwd in list(exrex.generate(exp)):
        if unzip_with_pwd(filename, pwd=pwd):
            print 'Found!! password =', pwd
            filename = 'archive.zip'
            exp_file = 'hint.txt'
            if os.path.exists(filename):
                os.remove(filename)
            if os.path.exists(exp_file):
                os.remove(exp_file)
            if os.path.exists(DIR + filename):
                os.rename(DIR + filename, filename)
                os.rename(DIR + exp_file, exp_file)
            else:
                finish = True
            break
    i += 1

    if finish:
        break

1000回解凍すると、flag.txtが展開されて、フラグが書いてあった。

utflag{bean_pure_omission_production_rally}

[basics] crypto (Cryptography 200)

2進数を文字にすると、途中からBase64文字列になっている。Base64デコードすると、途中からシーザー暗号などになっているので、復号する。

import string

def caesar(s, key):
    d = ''
    for c in s:
        code = ord(c)
        if c in string.uppercase:
            code = code - key
            if code < ord('A'):
                code += 26
        elif c in string.lowercase:
            code = code - key
            if code < ord('a'):
                code += 26
        d += chr(code)
    return d

with open('binary.txt', 'r') as f:
    data = f.read().strip()

codes = data.split(' ')
msg = ''
for code in codes:
    msg += chr(int(code, 2))

msg1 = msg.split('\n')[0]
msg2 = msg.split('\n')[1].decode('base64')

msg21 = msg2.split('\n')[0]
msg22 = caesar(msg2.split('\n')[1], 10)
msg23 = msg2.split('\n')[2]

print msg1
print msg21
print msg22
print msg23

ここまでの復号結果は以下の通り。

Uh-oh, looks like we have another block of text, with some sort of special encoding. Can you figure out what this encoding is? (hint: if you look carefully, you'll notice that there only characters present are A-Z, a-z, 0-9, and sometimes / and +. See if you can find an encoding that looks like this one.)
New challenge! Can you figure out what's going on here? It looks like the letters are shifted by some constant. (hint: you might want to start looking up Roman people).
alright, you're almost there! Now for the final (and maybe the hardest...) part: a substitution cipher. In the following text, I've taken my message and replaced every alphabetic character with a correspondence to a different character - known as a substitution cipher. Can you find the final flag? hint: We know that the flag is going to be of the format utflag{...} - which means that if you see that pattern, you know what the correspondences for u, t, f, l a, and g are. You can probably work out the remaining characters by replacing them and inferring common words in the English language. Another great method is to use frequency analysis: we know that 'e' shows up most often in the alphabet, so that's probably the most common character in the text, followed by 't', and so on. Once you know a few characters, you can infer the rest of the words based on common words that show up in the English language.
rghnxsdfysdtghu! qgf isak cthtuike dik zknthhkx rxqldgnxsliq risyykhnk. ikxk tu s cysn cgx syy qgfx isxe kccgxdu: fdcysn{3hrxqld10h_15_r00y}. qgf vtyy cthe disd s ygd gc rxqldgnxsliq tu pfud zftyethn gcc ditu ugxd gc zsutr bhgvykenk, she td xksyyq tu hgd ug zse scdkx syy. iglk qgf khpgqke dik risyykhnk!

最終行をquipqiupで復号する。(f=u p=j)

congratulations! you have finished the beginner cryptography challenge. here is a flag for all your hard efforts: utflag{3ncrypt10n_15_c00l}. you will find that a lot of cryptography is just building off this sort of basic knowledge, and it really is not so bad after all. hope you enjoyed the challenge!
utflag{3ncrypt10n_15_c00l}

Jacobi's Chance Encryption (Cryptography 750)

flag.encには0が多く存在する。このことからencrypt関数のyがnの倍数と考えられる。つまり、暗号化して0になっている箇所はbitが1で、そうでない場合はbitが0となる。このことから元のデータを割り出す。

with open('flag.enc', 'r') as f:
    enc = f.read()

b_data = ''
for num in enc.split(',')[:-1]:
    if num == '0':
        b_data += '1'
    else:
        b_data += '0'

flag = ''
for i in range(0, len(b_data), 8):
    code = int(b_data[i:i+8], 2)
    flag += chr(code)

print flag
utflag{did_u_pay_attention_in_number_theory}

Pragyan CTF 2019 Writeup

この大会は2019/3/8 21:30(JST)~2018/3/10 21:30(JST)に開催されました。
今回もチームで参戦。結果は2525点で499チーム中26位でした。
自分で解けた問題をWriteupとして書いておきます。

Cookie Monster (Web 100)

Cookieのflagはmd5の値がセットされている。ページを更新すると、その値は変わっていく。md5逆変換すると、2文字になるようだ。これを前提にmd5の元の文字をつなげていく。

import requests
import hashlib
import itertools
import string

url = 'http://159.89.166.12:13500/'

h_list = {}
for c in itertools.product(string.printable, repeat=2):
    text = ''.join(c)
    h = hashlib.md5(text).hexdigest()
    h_list[h] = text

s = requests.session()

flag = ''
for i in range(24):
    r = s.get(url)
    flag_val = s.cookies.get('flag')
    flag += h_list[flag_val]

print flag
pctf{c0oki3s_@re_yUm_bUt_tHEy_@ls0_r3vEaL_@_l0t}

Welcome (Forensics 50)

jpgの後ろにzipが入っている。解凍すると、d.zipが展開される。さらに解凍すると、a.zipとsecret.bmpが展開される。a.zipはパスワード付きzip。secret.bmpbmpではなく、末尾の方にBase64文字列がある。

$ echo dGhlIHBhc3N3b3JkIGlzOiBoMzExMF90aDNyMyE= | base64 -d
the password is: h3110_th3r3!

このパスワードでa.zipを解凍すると、a.pngが展開される。これをStegsolveで開き、Blue plane 1を見ると、フラグが書いてある。
f:id:satou-y:20190313220953p:plain

pctf{st3gs0lv3_1s_u53ful}

Magic PNGs (Forensics 100)

pngのヘッダが壊れているので、以下のような修正をする。

5バイト目:2E -> 0D
7バイト目:2E ->1A
チャンク名が小文字になっているのを修正:idat→IDAT
各チャンク:CRCを修正

これでpngファイルが見れる。
f:id:satou-y:20190313221253p:plain
上下反転すると、文字が読める。

h4CK3RM4n

またtEXtチャンクにmd5_MEf89jf4h9と書いてある。

$ echo -n h4CK3RM4n | md5sum
2c919f82ee2ed6985d5c5e275d67e4f8  -

このmd5の値でtryme.zipを解凍すると、flag.txtが展開されフラグが書いてある。

pctf{y0u_s33_m33_n0w!}

Slow Realization (Forensics 200)

jpgの後ろにmp3があるので、Audacityで開いてみると。モールス信号があるのがわかる。

.--. .- - .. . -. -.-. . .. ... - .... . -.- . -.-- .--. -.-. - ..-. -. ----- - .... ...-- .-. ...--

デコードする。

PATIENCEISTHEKEYPCTFN0TH3R3

mp3をサポートしているステガノツールをいろいろ試したがうまくいかない。mp3側を確認するのをあきらめ、もう一方のpdfを攻めることにする。パスワードがかかっていたので、クラックできないか試してみる。

>pdfcrack --wordlist=rockyou.txt flag.pdf
PDF version 1.4
Security Handler: Standard
V: 2
R: 3
P: -1028
Length: 128
Encrypted Metadata: True
FileID: 936f22840118a542401db0b9716930c8
U: c6417694dd485620f1629c6ae47a795700000000000000000000000000000000
O: ed2fd42c99e91c38c42eff249cacb3f968f3605be0ee9dc8586d5d38ab06c7f5
found user-password: 'congratulations'

このパスワードでpdfを開くと、フラグが書いてあった。

pctf{y0u_h34rd_m3_r1ght}

Spoiler (Cryptography 50)

pdfの%%EOFの後ろにデータが入っている。これから0を削除し、デコードしたものが鍵。PDFに書かれているhexデータのデコードとXORをとる。

enc_key = '0000006a0000006f0000006e000000730000006e0000006f000000770000006900000073000000640000007200000061000000670000006f0000006e00000062000000790000006200000069000000720000007400000068'

key = enc_key.replace('0', '').decode('hex')
print key

enc = '3a2c3a35152538272c2d213e332e3c25383030373a15'.decode('hex')

flag = ''
for i in range(len(enc)):
    code = ord(enc[i]) ^ ord(key[i])
    flag += chr(code)

print flag
PCTF{JON_IS_TARGARYEN}

Add them Sneaky Polynomials (Cryptography 100)

xのn乗のnがビットの位置を表していると推測して、p,q,rのxorをとる。

def poly_to_str(p):
    pt = p.rstrip().replace('+ x +', '+ x^1 +').replace('+ 1', '+ x^0')
    pt = map(int, pt.replace('x^', '').split(' + '))

    bin_list_p = ['0'] * 408
    for p in pt:
        bin_list_p[p] = '1'
    bin_list_p.reverse()
    bin_str = ''.join(bin_list_p)

    s = ''
    for i in range(0, len(bin_str), 8):
        s += chr(int(bin_str[i:i+8], 2))
    return s

def str_xor(s1, s2):
    return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2))

p = 'x^406 + x^405 + x^402 + x^399 + x^397 + x^391 + x^390 + x^387 + x^386 + x^378 + x^374 + x^372 + x^371 + x^369 + x^367 + x^364 + x^360 + x^358 + x^357 + x^352 + x^350 + x^345 + x^344 + x^341 + x^336 + x^335 + x^334 + x^333 + x^331 + x^330 + x^329 + x^328 + x^327 + x^324 + x^322 + x^320 + x^314 + x^311 + x^308 + x^307 + x^303 + x^300 + x^299 + x^296 + x^295 + x^290 + x^289 + x^287 + x^279 + x^271 + x^266 + x^264 + x^262 + x^260 + x^257 + x^256 + x^252 + x^249 + x^248 + x^246 + x^243 + x^239 + x^238 + x^236 + x^233 + x^230 + x^227 + x^225 + x^223 + x^222 + x^220 + x^218 + x^216 + x^215 + x^209 + x^208 + x^207 + x^204 + x^202 + x^199 + x^190 + x^189 + x^185 + x^184 + x^180 + x^177 + x^176 + x^175 + x^172 + x^167 + x^166 + x^162 + x^160 + x^159 + x^155 + x^154 + x^149 + x^147 + x^143 + x^137 + x^135 + x^131 + x^129 + x^126 + x^124 + x^122 + x^116 + x^110 + x^108 + x^105 + x^104 + x^100 + x^99 + x^97 + x^94 + x^93 + x^90 + x^88 + x^87 + x^86 + x^85 + x^83 + x^75 + x^73 + x^69 + x^63 + x^62 + x^57 + x^54 + x^51 + x^44 + x^41 + x^38 + x^37 + x^36 + x^34 + x^29 + x^28 + x^26 + x^25 + x^21 + x^20 + x^19 + x^16 + x^15 + x^14 + x^13 + x^6 + x^5 + x^2 '
q = 'x^399 + x^398 + x^396 + x^393 + x^392 + x^391 + x^388 + x^386 + x^384 + x^381 + x^377 + x^376 + x^368 + x^364 + x^360 + x^355 + x^354 + x^353 + x^352 + x^348 + x^346 + x^345 + x^344 + x^343 + x^335 + x^334 + x^329 + x^326 + x^325 + x^321 + x^318 + x^317 + x^315 + x^314 + x^311 + x^307 + x^306 + x^304 + x^300 + x^296 + x^293 + x^291 + x^282 + x^277 + x^270 + x^263 + x^261 + x^260 + x^256 + x^254 + x^253 + x^252 + x^251 + x^248 + x^245 + x^242 + x^241 + x^239 + x^238 + x^236 + x^232 + x^226 + x^225 + x^222 + x^220 + x^219 + x^214 + x^209 + x^208 + x^207 + x^206 + x^202 + x^200 + x^196 + x^191 + x^190 + x^186 + x^181 + x^180 + x^178 + x^177 + x^169 + x^168 + x^165 + x^164 + x^163 + x^162 + x^161 + x^159 + x^157 + x^156 + x^151 + x^149 + x^148 + x^147 + x^146 + x^144 + x^141 + x^140 + x^138 + x^137 + x^136 + x^134 + x^133 + x^132 + x^130 + x^129 + x^128 + x^126 + x^123 + x^121 + x^113 + x^109 + x^103 + x^101 + x^100 + x^95 + x^93 + x^91 + x^85 + x^84 + x^81 + x^74 + x^73 + x^71 + x^68 + x^67 + x^54 + x^52 + x^51 + x^50 + x^48 + x^46 + x^45 + x^43 + x^39 + x^35 + x^32 + x^31 + x^30 + x^29 + x^21 + x^15 + x^14 + x^9 + x^8 + x^5 + x^4 + x^2 + 1 '
r = 'x^404 + x^402 + x^396 + x^389 + x^387 + x^386 + x^384 + x^382 + x^376 + x^373 + x^367 + x^366 + x^365 + x^362 + x^361 + x^358 + x^356 + x^355 + x^354 + x^353 + x^352 + x^349 + x^348 + x^347 + x^345 + x^343 + x^340 + x^334 + x^332 + x^331 + x^328 + x^327 + x^326 + x^322 + x^317 + x^316 + x^314 + x^313 + x^312 + x^310 + x^309 + x^308 + x^305 + x^304 + x^303 + x^301 + x^300 + x^299 + x^296 + x^295 + x^292 + x^291 + x^290 + x^288 + x^287 + x^286 + x^285 + x^283 + x^279 + x^278 + x^274 + x^271 + x^269 + x^268 + x^266 + x^265 + x^263 + x^261 + x^260 + x^259 + x^258 + x^256 + x^254 + x^252 + x^251 + x^250 + x^249 + x^244 + x^243 + x^242 + x^237 + x^236 + x^228 + x^225 + x^224 + x^223 + x^222 + x^221 + x^215 + x^214 + x^213 + x^212 + x^205 + x^201 + x^200 + x^199 + x^197 + x^193 + x^192 + x^191 + x^190 + x^189 + x^188 + x^187 + x^182 + x^180 + x^175 + x^174 + x^173 + x^167 + x^166 + x^163 + x^158 + x^156 + x^155 + x^153 + x^151 + x^150 + x^149 + x^143 + x^142 + x^140 + x^139 + x^136 + x^135 + x^133 + x^129 + x^126 + x^125 + x^123 + x^121 + x^118 + x^117 + x^116 + x^115 + x^113 + x^110 + x^106 + x^105 + x^104 + x^103 + x^102 + x^98 + x^95 + x^92 + x^89 + x^87 + x^85 + x^81 + x^80 + x^77 + x^76 + x^75 + x^74 + x^71 + x^70 + x^67 + x^66 + x^64 + x^63 + x^60 + x^59 + x^58 + x^56 + x^54 + x^53 + x^48 + x^44 + x^41 + x^39 + x^38 + x^35 + x^34 + x^31 + x^29 + x^28 + x^27 + x^22 + x^21 + x^20 + x^17 + x^14 + x^12 + x^11 + x^10 + x^9 + x^6 + x^4 + x^3 + x + 1 '

msg1 = poly_to_str(p)
msg2 = poly_to_str(q)
msg3 = poly_to_str(r)

flag = str_xor(str_xor(msg1, msg2), msg3)
print flag
pctf{f1n1t3_f13lds_4r3_m0r3_us3ful_th4n_y0u_th1nk}

The Order of the Phoenix (Cryptography 100)

10人分のQRコードがあるので、QRコードを読み取る。

Bill
a-424b493442128adbeef5ce33f18c6c5996cdd97e4922644a4479bb4e05f8846f

Charlie
8-1268bf4430c0b1a4c568a302da92421bc672aceb57fef3401f2434cfc3bf740b

Fleur
9-b52781fd38b0185bd1a8a92a92dbf01c99eddbb50b86f65a882ad8a7fa313e9d

George
6-7c61f3ee00ab759a6853f041e74ae2378144a96b662230888d6ba6412c646190

Ginny
7-d01f29e42de0ab1fb183a35d06a2ac6117acaad2b3017671846c7b380e83d6bb

Harry
1-d301da5536a5d8b8e2be50a7584127eb3704025f048cf72335f1b301b852b30a

Hermione
2-e1af01e2f7887b63c068823cbcd812f91899678656456db71dfa9ab1fbb1bd26

Luna
4-510c9c8f6aaacebf16bb5fd9e2cd8c0845ec483bd49bf57fa4151e5b672c73b0

Neville
3-dc60d55a411ccfd4a44e6a9799774dd6207dffdfcab4b442075ead165fa7ecb

Ron
5-bd4f58a846bb9e47a7402e22df13002aef3bf3048011674269eaff39154c62bf

Shamir's Secret Sharingの問題のようだ。Pythonのライブラリを使って簡単に秘密情報を取得できる。

from secretsharing import PlaintextToHexSecretSharer

shares = [
    '1-d301da5536a5d8b8e2be50a7584127eb3704025f048cf72335f1b301b852b30a',
    '2-e1af01e2f7887b63c068823cbcd812f91899678656456db71dfa9ab1fbb1bd26',
    '3-dc60d55a411ccfd4a44e6a9799774dd6207dffdfcab4b442075ead165fa7ecb',
    '4-510c9c8f6aaacebf16bb5fd9e2cd8c0845ec483bd49bf57fa4151e5b672c73b0',
    '5-bd4f58a846bb9e47a7402e22df13002aef3bf3048011674269eaff39154c62bf',
    '6-7c61f3ee00ab759a6853f041e74ae2378144a96b662230888d6ba6412c646190',
    '7-d01f29e42de0ab1fb183a35d06a2ac6117acaad2b3017671846c7b380e83d6bb',
    '8-1268bf4430c0b1a4c568a302da92421bc672aceb57fef3401f2434cfc3bf740b',
    '9-b52781fd38b0185bd1a8a92a92dbf01c99eddbb50b86f65a882ad8a7fa313e9d',
    'a-424b493442128adbeef5ce33f18c6c5996cdd97e4922644a4479bb4e05f8846f'
]
flag = PlaintextToHexSecretSharer.recover_secret(shares)
print flag
pctf{sh4m1r3_w4s_4_gr34t_m4n}

Help Rabin (Cryptography 150)

公開鍵を見ると、eは1だが、encrypt.pyを見ると実質e=2のRabin暗号。また、pとqは近い素数なので、Fermat法で素因数分解できる。あとはRabin暗号の復号方法で復号する。

from Crypto.PublicKey import RSA
from Crypto.Util.number import *

def isqrt(n):
    x = n
    y = (x + n // x) // 2
    while y < x:
        x = y
        y = (x + n // x) // 2
    return x

def fermat(n):
    x = isqrt(n) + 1
    y = isqrt(x * x - n)
    while True:
        w = x * x - n - y * y
        if w == 0:
            break
        elif w > 0:
            y += 1
        else:
            x += 1
    return x - y, x + y

def egcd(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, y, x = egcd(b % a, a)
        return gcd, x - (b // a) * y, y

def is_printable(s):
    for c in s:
        if ord(c) != 10 and (ord(c) < 32 or ord(c) > 126):
            return False
    return True

with open('publickey.pem', 'r') as f:
    pub_data = f.read()

pubkey = RSA.importKey(pub_data)
n = pubkey.n

p, q = fermat(n)

with open('ciphertext.txt', 'r') as f:
    ct = bytes_to_long(f.read().decode('hex'))

r = pow(ct, long((p+1)/4), long(p))
s = pow(ct, long((q+1)/4), long(q))

gcd, c, d = egcd(p, q)
x = (r * d * q + s * c * p) % n
y = (r * d * q - s * c * p) % n
plains = [x, n - x, y, n - y]

for plain in plains:
    flag = long_to_bytes(plain)
    if is_printable(flag):
        print flag
        break

復号結果は以下の通り。

Hey Rabin, would you like to be the front end to my back end? Here is your flag: pctf{R4b1n_1s_th3_cut3st}
pctf{R4b1n_1s_th3_cut3st}

Easy RSA (Cryptography 150)

eが非常に大きいので、Wiener's Attackで復号する。

from fractions import Fraction

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    gcd, a, b = egcd(e, phi)
    d = a
    pt = pow(c, d, n)
    return hex(pt)[2:-1].decode('hex')

def continued_fractions(n,e):
    cf = [0]
    while e != 0:
        cf.append(int(n/e))
        N = n
        n = e
        e = N%e
    return cf

def calcKD(cf):
    kd = list()
    for i in range(1,len(cf)+1):
        tmp = Fraction(0)
        for j in cf[1:i][::-1]:
            tmp = 1/(tmp+j)
        kd.append((tmp.numerator,tmp.denominator))
    return kd

def int_sqrt(n):
    def f(prev):
        while True:
            m = (prev + n/prev)/2
            if m >= prev:
                return prev
            prev = m
    return f(n)

def calcPQ(a,b):
    if a*a < 4*b or a < 0:
        return None
    c = int_sqrt(a*a-4*b)
    p = (a + c) /2
    q = (a - c) /2
    if p + q == a and p * q == b:
        return (p,q)
    else:
        return None

def wiener(n,e):
    kd = calcKD(continued_fractions(n,e))
    for (k,d) in kd:
        if k == 0:
            continue
        if (e*d-1) % k != 0:
            continue
        phin = (e*d-1) / k
        if phin >= n:
            continue
        ans = calcPQ(n-phin+1,n)
        if ans is None:
            continue
        return (ans[0],ans[1])

e = 217356749319385698521929657544628507680950813122965981036139317973675569442588326220293299168756490163223201593446006249622787212268918299733683908813777695992195006830244088685311059537057855442978678020950265617092637544349098729925492477391076560770615398034890984685084288600014953201593750327846808762513
n = 413514550275673527863957027545525175432824699510881864021105557583918890022061739148026915990124447164572528944722263717357237476264481036272236727160588284145055425035045871562541038353702292714978768468806464985590036061328334595717970895975121788928626837881214128786266719801269965024179019247618967408217
c = 337907824405966440030495671003069758278111764297629248609638912154235544001123799434176915113308593275372838266739188034566867280295804636556069233774555055521212823481663542294565892061947925909547184805760988117713501561339405677394457210062631040728412334490054091265643226842490973415231820626551757008360

p, q = wiener(n, e)

flag = decrypt(p, q, e, c)
print flag

復号結果は以下の通り。

Here is your flag, pctf{Sup3r_st4nd4rd_W31n3r_4tt4ck}
pctf{Sup3r_st4nd4rd_W31n3r_4tt4ck}

Decode This (Cryptography 200)

行列で以下のような計算になる。

key[0][0] key[0][1]   'p' 't'     c1  c3
                    *         =
key[1][0] key[1][1]   'c' 'f'     c2  c4
key = c * inv(m)
m = inv(key) * c

pctfが含まれているだけという条件しかわからないので、上記の条件をもとに、ブルートフォースで復号し、英文として意味の通るものを探す。

# solve.sage
ct = 'vuqxyugfyzfjgoccjkxlqvguczymjhpmjkyzoilsxlwtmccclwizqbetwthkkvilkruufwuu'

n = 26

for j in range(len(ct) - 4):
    print '**** %d ****' % j
    ct_parts = ct[j:j+4]

    cipher = matrix(Zmod(n), [[ord(ct_parts[0]) - 97, ord(ct_parts[2]) - 97],
        [ord(ct_parts[1]) - 97, ord(ct_parts[3]) - 97]])
    plain = matrix(Zmod(n), [[ord('p') - 97, ord('t') - 97],
        [ord('c') - 97, ord('f') - 97]])
    key = cipher * plain.inverse()

    flag = ''
    for i in range(0, len(ct), 4):
        c = matrix(Zmod(n), [[ord(ct[i]) - 97, ord(ct[i+2]) - 97],
            [ord(ct[i+1]) - 97, ord(ct[i+3]) - 97]])
        try:
            m = key.inverse() * c
            flag += chr(int(m[0][0]) + 97)
            flag += chr(int(m[1][0]) + 97)
            flag += chr(int(m[0][1]) + 97)
            flag += chr(int(m[1][1]) + 97)
        except:
            break

    print flag

実行結果は以下の通り。

    :
**** 38 ****
ramhasalittlesecretforyourighthereitispctfilikeclimbinghillswhataboutyou
    :
pctf{ilikeclimbinghillswhataboutyou}

EXORcism (Miscellaneous 300)

10000行あり、0か1になっている。100×100に並べると、QRコードが浮かぶ。
strong-qr-decoderで読めるよう少し整形する。

with open('encoded.txt', 'r') as f:
    lines = f.readlines()

qr = ''
i = 0
for line in lines:
    val = line.strip()
    qr += val
    if i % 100 == 99:
        qr += '\n'
    i += 1

qr_lines = qr.split('\n')
qr_lines = qr_lines[13:-14]
qr_array = []
for line in qr_lines:
    qr_array.append(line[13:-13])

qr = ''
for y in range(37):
    for x in range(37):
        qr += qr_array[y*2][x*2]
    qr += '\n'

qr = qr.replace('0', 'X')
qr = qr.replace('1', '_')

with open('qr.txt', 'w') as f:
    f.write(qr)
$ cat qr.txt
XXXXXXX___XX_X_X_X___X__X_X___XXXXXXX
X_____X__X_XXX_XXX_XX_X_X_X_X_X_____X
X_XXX_X__X_____XXXX_XX_XXXX_X_X_XXX_X
X_XXX_X__XXX_____X__X_X_XX__X_X_XXX_X
X_XXX_X_X_X_XXXX_XXXXXX_XX_X__X_XXX_X
X_____X___XX____X_XXX__X__X_X_X_____X
XXXXXXX_X_X_X_X_X_X_X_X_X_X_X_XXXXXXX
________X__X_X__X_X_XX_XXXX__________
__XX__XXXX_X__XX___XX__XXXX_XXX_X____
XX_XXX_____XX__X__X__XX_X__X___X_X_X_
XX_XXXXX_X__X__X___XXX____X_X__XXXXX_
X___X__X____X_X______X___XX_X_X___XX_
_X_XX_X_XXX___XX____X__XXX_XX_XXX_X_X
X_X_X____XXXX__XX_X_XXX_X__X__X_X__XX
XX_XX_XXXX_XXX__X________XX_XX___XXX_
_______XX__XXXX_XXX_XXXXX_X_XXXX_X_XX
_XXX_XX________XX_____X_XXX_XX_X_XXX_
____X___X_X_X____X_X__X__XXXXXXX__XXX
XX_XX_X_X_X__X____XX_X___X_XX_XX_XX_X
_XXXXX_____XX_XX_X__XX__X__X__X____X_
XXXXX_X_X___X___X__XXX_X_______XXX__X
X_X__X___XX_____XXXX_X__X_X__X_X_X_X_
X_XXX_XXX_____X__XX__XX_X_X_X___XXXX_
X__XXX_X____X__XX__X__X__XX__X_X__XX_
XX__XXX_XXXXX_XXXXXX_______X__XXX_X_X
__XXXX___XX____XX_X_XXXX___XX_X_XX__X
_X____X__XXX__XX_XXX____XX_______XX__
X__XXX__XXXXX__X_X__X_X_X_XX_XX_XX_XX
__X___XXXXX____XX___X__XXX__XXXXXXX__
________X__X__XXX_X__XXX____X___XXXXX
XXXXXXX_XXX_X_XXXX__XX__X___X_X_XXX_X
X_____X__XX__XXX_XXX_X__X__XX___X__X_
X_XXX_X__XXX_X_XXXXX_X______XXXXXX_X_
X_XXX_X_XXXXXX___XX___X___X___XXXX___
X_XXX_X_XXX_X_XX_X__X_X____X__X_X__X_
X_____X_____X__XXXX_XX_XXXXX___X__X__
XXXXXXX___X_XXX_XXX_XX_X_X_X_X__X_XXX
$ ./sqrd.py qr.txt 
160f15011d1b095339595138535f135613595e1a

問題タイトルからもXORが関係していそう。pctfが先頭につくことからXOR鍵を推測して復号する。

enc = '160f15011d1b095339595138535f135613595e1a'.decode('hex')

pre_flag = 'pctf{'

key = ''
for i in range(len(pre_flag)):
    code = ord(enc[i]) ^ ord(pre_flag[i])
    key += chr(code)
print 'key =', key

key = key[:4]

flag = ''
for i in range(len(enc)):
    code = ord(enc[i]) ^ ord(key[i%len(key)])
    flag += chr(code)

print flag
pctf{wh4_50_53r1u5?}

Aero CTF 2019 Writeup

この大会は2019/3/8 18:00(JST)~2018/3/9 18:00(JST)に開催されました。
今回もチームで参戦。結果は1473点で241チーム中34位でした。
自分で解けた問題をWriteupとして書いておきます。

crypto_warmup (Warmup)

5種類のワードがたくさん出てくる。5進数で1行1文字になるのかもしれない。Aeroで始まることを前提に数字を割り当てる。

kappa_pride -> 2
pepe -> 3
kappa -> 0
look_at_this_dude -> 4
trollface -> 1
with open('meme_or_not', 'r') as f:
    lines = f.readlines()

nums = {'kappa': '0', 'trollface': '1', 'kappa_pride': '2',
    'pepe': '3', 'look_at_this_dude': '4'}

flag = ''
for line in lines:
    words = line.strip().split(' ')
    base5 = ''
    for word in words:
        base5 += nums[word]
    code = int(base5, 5)
    flag += chr(code)
    print code

print flag
Aero{7a911ccfb18c2fafe2960b6ee2cbc9c7}

gocryptor (Crypto)

go言語で暗号処理が書かれているが、16バイトのキーのXOR暗号であることがわかる。
繰り返す16バイトのデータを参考に鍵を予測する。jpgとわかるので、調整しながら復号する。

with open('example_drawing.enc', 'rb') as f:
    enc = f.read()

key = '\x72\xb5\x39\xC7\xA3\xe2\x39\x15\x37\x44\x5b\x2b\x87\x6e\x23\x20'

dec = ''
for i in range(len(enc)):
    code = ord(enc[i]) ^ ord(key[i%len(key)])
    dec += chr(code)

with open('example_drawing.jpg', 'wb') as f:
    f.write(dec)

f:id:satou-y:20190311200302j:plain
画像の右下に小さくフラグが書いてある。

Aero{9e57f6b3509283933c1be3fedda555b6}

damaged ticket (Code)

画像を縦切りにしたファイルが600個。ファイル名は0~599のmd5と推測。順に結合していく。

from PIL import Image
import hashlib

DIR = './parts/'

OUTPUT_WIDTH = 600
OUTPUT_HEIGHT = 267

output_img = Image.new('RGB', (OUTPUT_WIDTH, OUTPUT_HEIGHT), (255, 255, 255))

for x in range(600):
    num = '%d' % x
    file = DIR + hashlib.md5(num).hexdigest() + '.png'
    input_img = Image.open(file)
    output_img.paste(input_img, (x, 0))

output_img.save('flag.png')

f:id:satou-y:20190311200452p:plain
画像にフラグが書いてある。

Aero{2c5afcd62a5851f744fd6adb60ae2345}

BSidesSF 2019 CTF Writeup

この大会は2019/3/4 2:00(JST)~2018/3/5 10:00(JST)に開催されました。
今回もチームで参戦。結果は763点で1092チーム中21位でした。
自分で解けた問題をWriteupとして書いておきます。

futurella (Web 1)

Webページにはalien cipherの文字で書かれているが、ソースを見るとフラグがわかった。フォントでそのように操作されていたようだ。

CTF{bring_it_back}

Trivia 1 (101 2)

問題は「My voice is my ________. Verify me.」。穴埋め問題。インターネットで調べるとすぐわかる。

passport

kookie (101, Web 10)

cookie / monsterでログインすると、Cookieのusernameにcookieがセットされている。adminに変更すると、フラグが表示された。

CTF{kookie_cookies}

zippy (Forensics 50)

TCP Streamを見ると、以下のコマンドが実行されていることがわかる。

nc -l -p 4445 > flag.zip
unzip -P supercomplexpassword flag.zip
Archive:  flag.zip
  inflating: flag.txt

No.9のパケットにflag.zipのデータがあるので、エクスポートする。それから上記と同じようにコマンドを実施する。

$ unzip -P supercomplexpassword flag.zip
Archive:  flag.zip
  inflating: flag.txt                
$ cat flag.txt
CTF{this_flag_is_your_flag}
CTF{this_flag_is_your_flag}

table-tennis (Forensics 50)

ICMPパケットが流れている。問題タイトルからもこのデータにフラグが隠されていそう。各パケットからデータ部分を抜き出す。

e0p1c3RB
UzBuZ0Fi
MHV0UDFu
Z1Awbmd9

全部結合して、Base64デコードしてみる。

$ echo e0p1c3RBUzBuZ0FiMHV0UDFuZ1Awbmd9 | base64 -d
{JustAS0ngAb0utP1ngP0ng}
CTF{JustAS0ngAb0utP1ngP0ng}

decrypto (Crypto, Web 300)

何もしないと以下のように表示される。

Welcome to the mainframe!
...
It looks like you want to access the flag!
Please present user object
...
...
...
...scanning
...
...scanning
...
Scanning user object...
...your UID value is set to 56
...
...
...your NAME value is set to baseuser
...your SKILLS value is set to n/a
...
ERROR: ACCESS DENIED
...
...
UID MUST BE '0'

クッキーの状態は以下の通りで、リセットするとパラメータが変わるようだ。

signature
809f6357940b81340fc147830f56f344fe1999316d4b34d8908d784a170869b6

user
e79b54a46aae832c6cb5e9c5cf3903d18046172a49d243198560272d397af792ab7d683425445e75666f3a6b2086d83c7197c9cff3a5c1f9df64c28714fb3a4d

rack.session
BAh7CEkiD3Nlc3Npb25faWQGOgZFVEkiRWYyZWVlMzljZDBjMjg2ZDE2MWFm%0AZDI2OTdiODkwOTE2M2RkYmJlOTVkYjU5YzgzNmY5NDcwOWEyZGZlMmU5OGYG%0AOwBGSSILc2VjcmV0BjsARiINJmUAQX1%2BsONJIghrZXkGOwBGIiUFvW1HPcr3%0AaB%2ByY2RPWz%2BprqfdSaqNNT%2BfZCfk1obFOQ%3D%3D%0A--1bc34de559dc8cfd69cf2d8a117e1c7f6bec6eaf

UIDを0にする必要があるが、文章に書かれている内容から、signatureについてはHash Length Extension Attackで何とかなりそう。
問題はuserだが、文字列長からAESの暗号と思われる。rack.sessionの%0Aの前までをBase64デコードしてみると、最後の32バイトが鍵だと推測できる。それを鍵として、復号してみる。

from Crypto.Cipher import AES

def unpad(s):
    return s[:-ord(s[-1])]

enc = 'e79b54a46aae832c6cb5e9c5cf3903d18046172a49d243198560272d397af792ab7d683425445e75666f3a6b2086d83c7197c9cff3a5c1f9df64c28714fb3a4d'.decode('hex')

with open('session', 'rb') as f:
    data = f.read()
key = data[-32:]

iv = enc[:16]
enc = enc[16:]
aes = AES.new(key, AES.MODE_CBC, iv)
dec = unpad(aes.decrypt(enc))
print dec

実行した結果は以下のとおり。

UID 56
NAME baseuser
SKILLS n/a

このデータ形式でHash Length Extension Attackを行い、得られたデータで暗号化したものをクッキーのuserに設定すればよい。

from Crypto.Cipher import AES
import hashpumpy

def pad(s):
    n = 16 - len(s) % 16
    return s + chr(n) * n

def encrypt(key, s):
    iv = '0123456789abcdef'
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc = aes.encrypt(pad(s))
    return (iv + enc).encode('hex')

sign = '809f6357940b81340fc147830f56f344fe1999316d4b34d8908d784a170869b6'
base = 'UID 56\nNAME baseuser\nSKILLS n/a\n'

h, d = hashpumpy.hashpump(sign, base, '\nUID 0\n', 8)
print 'signature:', h

with open('session', 'rb') as f:
    data = f.read()
key = data[-32:]

user = encrypt(key, d)
print 'user :', user

実行結果は以下の通り。

signature: d94e43b063c5e9e4334e2080f7207986792276cf34a260d8ec0c40eff4e03dc0
user : 303132333435363738396162636465661da120fecc4dfcd79b5fe6efb58b8a43054dac681fb99dfe53abd775bf2d1bcede42992c655039ef77071b396fede73ff33b551a9226ac4949b19860e253a23f

それぞれクッキーに設定して画面を更新すると、以下の通りフラグが表示された。

Welcome to the mainframe!
It looks like you want to access the flag!
...
Please present user object
...
...scanning
...
...scanning
...
...
...
...
Scanning user object...
...your UID value is set to 0
...your NAME value is set to baseuser
...
...
...
...your SKILLS value is set to n/a
...your ����������������������@ value is set to 
FLAG VALUE: CTF{parse_order_matters}

CTF{parse_order_matters}

TAMUctf 19 Writeup

この大会は2019/2/23 9:00(JST)~2018/3/4 9:00(JST)に開催されました。
今回もチームで参戦。結果は19178点で1866チーム中13位でした。
自分で解けた問題をWriteupとして書いておきます。

Howdy! (Misc)

問題にフラグが書いてある。

gigem{H0wdy!}

Who am I? (Misc)

tamuctf.comのAレコードを答える問題。

$ dig tamuctf.com

; <<>> DiG 9.10.3-P4-Ubuntu <<>> tamuctf.com
;; global options: +cmd
;; Got answer:
;; ->>HEADER<<- opcode: QUERY, status: NOERROR, id: 49250
;; flags: qr rd ra; QUERY: 1, ANSWER: 1, AUTHORITY: 0, ADDITIONAL: 1

;; OPT PSEUDOSECTION:
; EDNS: version: 0, flags:; MBZ: 0005 , udp: 512
;; QUESTION SECTION:
;tamuctf.com.			IN	A

;; ANSWER SECTION:
tamuctf.com.		5	IN	A	52.33.57.247

;; Query time: 151 msec
;; SERVER: 127.0.1.1#53(127.0.1.1)
;; WHEN: Sat Feb 23 09:31:59 JST 2019
;; MSG SIZE  rcvd: 56
52.33.57.247

Who do I trust? (Misc)

tamuctf.comの証明書の発行者を答える問題。証明書を確認する。

Let's Encrypt Authority X3

0_Network_Enumeration (ReadingRainbow)

1つ目の問題はプライベートWebサーバのIPアドレスを答える問題。
2つ目の問題はそのWebサーバにアクセスしているホストの数を答える問題。
WebサーバのIPアドレスはhttpアクセスしているパケットを見ていけば、192.168.11.4であることがわかる。
さらにNetworkMinerで開き、Hostsタブで192.168.11.4にアクセスしているホストの数を確認すると、13個であることがわかる。
f:id:satou-y:20190306221448p:plain

192.168.11.4
13

-.- (Crypto)

モールス信号を復号すると16進数になる。それをASCIIコードとして文字にする。

morse = {
    'di-dah': 'A',
    'dah-di-di-dit': 'B',
    'dah-di-dah-dit': 'C',
    'dah-di-dit': 'D',
    'dit': 'E',
    'di-di-dah-dit': 'F',
    'dah-dah-dit': 'G',
    'di-di-di-dit': 'H',
    'di-dit': 'I',
    'di-dah-dah-dah': 'J',
    'dah-di-dah': 'K',
    'di-dah-di-dit': 'L',
    'dah-dah': 'M',
    'dah-dit': 'N',
    'dah-dah-dah': 'O',
    'di-dah-dah-dit': 'P',
    'dah-dah-di-dah': 'Q',
    'di-dah-dit': 'R',
    'di-di-dit': 'S',
    'dah': 'T',
    'di-di-dah': 'U',
    'di-di-di-dah': 'V',
    'di-dah-dah': 'W',
    'dah-di-di-dah':'X',
    'dah-di-dah-dah': 'Y',
    'dah-dah-di-dit': 'Z',
    'di-dah-dah-dah-dah': '1',
    'di-di-dah-dah-dah': '2',
    'di-di-di-dah-dah': '3',
    'di-di-di-di-dah': '4',
    'di-di-di-di-dit': '5',
    'dah-di-di-di-dit': '6',
    'dah-dah-di-di-dit': '7',
    'dah-dah-dah-di-dit': '8',
    'dah-dah-dah-dah-dit': '9',
    'dah-dah-dah-dah-dah': '0'
}

with open('flag.txt', 'r') as f:
    data = f.read()

codes = data.split(' ')
dec = ''
for code in codes:
    dec += morse[code]
print dec.lower()
print

msg =  dec[2:].decode('hex')
print msg

実行結果は以下の通り。

0x57702a6c58744751386538716e6d4d59552a737646486b6a49742a5251264a705a766a6d2125254b446b6670235e4e39666b346455346c423372546f5430505a516d4351454b5942345a4d762a21466b386c25626a716c504d6649476d612525467a4720676967656d7b433169634b5f636c31434b2d7930755f683476335f6d3449317d20757634767a4b5a7434796f6d694453684c6d385145466e5574774a404e754f59665826387540476e213125547176305663527a56216a217675757038426a644e49714535772324255634555a4f595a327a37543235743726784c40574f373431305149

Wp*lXtGQ8e8qnmMYU*svFHkjIt*RQ&JpZvjm!%%KDkfp#^N9fk4dU4lB3rToT0PZQmCQEKYB4ZMv*!Fk8l%bjqlPMfIGma%%FzG gigem{C1icK_cl1CK-y0u_h4v3_m4I1} uv4vzKZt4yomiDShLm8QEFnUtwJ@NuOYfX&8u@Gn!1%Tqv0VcRzV!j!vuup8BjdNIqE5w#$%V4UZOYZ2z7T25t7&xL@WO7410QI

デコードした文字列にフラグが含まれている。

gigem{C1icK_cl1CK-y0u_h4v3_m4I1}

RSAaaay (Crypto)

nを素因数分解する。

2531257 = 509 * 4973

あとはそのまま復号していき、復号した数値を1つか2つのASCIIコードの連結とみて、文字にする。

from Crypto.Util.number import inverse

def n_to_str(n):
    str_n = str(n)
    s = ''
    tmp = ''
    for i in range(len(str_n)):
        tmp += str_n[i]
        if int(tmp) > 31 and int(tmp) < 127:
            s += chr(int(tmp))
            tmp = ''
    return s

n = 2531257
p = 509
q = 4973
e = 43
list_c = map(int, '906851 991083 1780304 2380434 438490 356019 921472 822283 817856 556932 2102538 2501908 2211404 991083 1562919 38268'.split(' '))

phi = (p - 1) * (q - 1)
d = inverse(e, phi)

flag = ''
for c in list_c:
    m = pow(c, d, n)
    flag += n_to_str(m)

print flag
gigem{Savage_Six_Flying_Tigers}

Mike's Marvelous Mystery Curves (Crypto)

通信パケットのNo.4と11に-----BEGIN CERTIFICATE-----で始まるデータがある。エクスポートして、中身を見ようとしたが、見れない。BASE64デコードしてみると、テキストで以下のような内容だった。

[No.4]
Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            b9:59:da:c4:d7:3f:bc:31
    Signature Algorithm: base64
        Issuer: C = US, ST = Texas, L = College Station, O = Texas A&M University, OU = tamuCTF, CN = Alice, emailAddress = alice@tamuctf.edu
        Validity
            Not Before: Oct  9 13:08:12 2018 GMT
            Not After : Nov  8 13:08:12 2018 GMT
        Subject: C = US, ST = Texas, L = College Station, O = Texas A&M University, OU = tamuCTF, CN = Alice, emailAddress = alice@tamuctf.edu
        Subject Public Key Info:
            Public Key Algorithm: id-ecPublicKey
                Public-Key:
                    61801292647
                    228288385004
                ASN1 OID: badPrime96v4
                CURVE: JustNo
                    Field Type: prime-field
                    Prime:
                        412220184797
                    A:   
                        10717230661382162362098424417014722231813
                    B:   
                        22043581253918959176184702399480186312
                    Generator:
                        56797798272
                        349018778637
        X509v3 extensions:
            X509v3 Subject Key Identifier: 
                F0:4E:BF:87:92:16:9B:D6:53:DA:CC:6D:AB:22:0E:40:25:41:C5:CC
            X509v3 Authority Key Identifier: 
                keyid:F0:4E:BF:87:92:16:9B:D6:53:DA:CC:6D:AB:22:0E:40:25:41:C5:CC

            X509v3 Basic Constraints: critical
                CA:TRUE
    Signature Algorithm: ecdsa-with-SHA256
         30:46:02:21:00:cc:3c:84:eb:19:73:e1:62:7f:81:78:99:c6:
         26:b8:86:9e:61:7e:82:87:f1:85:5c:75:e1:2d:60:37:55:b6:
         09:02:21:00:85:33:af:dc:34:0f:e5:13:8e:26:88:06:a3:13:
         d1:a2:ed:d5:04:cb:9c:50:d1:c4:a4:4d:42:92:bd:69:56:1a

[No.11]
Certificate:
    Data:
        Version: 3 (0x2)
        Serial Number:
            a8:49:ac:8c:84:0f:84:ce
    Signature Algorithm: ecdsa-with-SHA256
        Issuer: C = US, ST = Texas, L = College Station, O = Texas A&M University, OU = tamuCTF, CN = Bob, emailAddress = bob@tamuctf.edu
        Validity
            Not Before: Oct  9 13:15:35 2018 GMT
            Not After : Nov  8 13:15:35 2018 GMT
        Subject: C = US, ST = Texas, L = College Station, O = Texas A&M University, OU = tamuCTF, CN = Bob, emailAddress = bob@tamuctf.edu
        Subject Public Key Info:
            Public Key Algorithm: id-ecPublicKey
                Public-Key:
                    196393473219
                    35161195210
                ASN1 OID: badPrime96v4
                CURVE: JustNo
                    Field Type: prime-field
                    Prime:
                        412220184797
                    A:   
                        10717230661382162362098424417014722231813
                    B:   
                        22043581253918959176184702399480186312
                    Generator:
                        56797798272
                        349018778637
        X509v3 extensions:
            X509v3 Subject Key Identifier: 
                84:25:43:45:2C:0C:7E:1C:85:BC:E9:AF:44:BE:42:A1:84:D6:D2:27
            X509v3 Authority Key Identifier: 
                keyid:84:25:43:45:2C:0C:7E:1C:85:BC:E9:AF:44:BE:42:A1:84:D6:D2:27

            X509v3 Basic Constraints: critical
                CA:TRUE
    Signature Algorithm: ecdsa-with-SHA256
         30:46:02:21:00:d4:45:84:18:e3:06:8d:bb:3b:e9:4d:68:a9:
         56:f4:af:e0:28:23:26:7d:4d:1e:84:2b:e8:c4:d3:ac:85:a9:
         c8:02:21:00:e9:ef:bc:0d:fa:3a:85:c4:39:1a:16:3b:6a:c0:
         6a:3f:ac:f2:7a:5f:49:ea:86:e4:18:5e:ac:91:75:31:b3:5b

ここからパラメータを読み取ると、全体的に数値が小さい。離散対数問題で使うコードでECDHによる共通鍵を算出してみる。

# solve.sage
p = 412220184797
A = 10717230661382162362098424417014722231813
B = 22043581253918959176184702399480186312
G = (56797798272, 349018778637)

F = FiniteField(p)
E = EllipticCurve(F, [A,B])
G = E.point(G)

pub_A = (61801292647, 228288385004)
pub_A = E.point(pub_A)
pub_B = (196393473219, 35161195210)
pub_B = E.point(pub_B)

factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]
dlogs = []
for fac in primes:
    t = int(G.order()) / int(fac)
    dlog = discrete_log(t*pub_A, t*G, operation='+')
    dlogs += [dlog]

n_A = crt(dlogs,primes)

key = pub_B * n_A
key = str(key[0]) + str(key[1])
print key

共通鍵は以下であることがわかった。

130222573707242246159397

あとはTCP Streamから暗号データを抽出して、復号するだけ。AES-CBCなのでIVが必要だが、よく暗号データの先頭16バイトがIVになっているので、それを使う。

from Crypto.Cipher import AES

with open('msg.enc', 'rb') as f:
    data = f.read()

iv = data[:16]
enc = data[16:]

key = '130222573707242246159397'
aes = AES.new(key, AES.MODE_CBC, iv)

dec = aes.decrypt(enc)
print dec

復号結果は以下の通り。

 study was a total mess, like the results  of  an
explosion  in  a  public  library.  The  old  man frowned as they
stepped in.

"Terribly unfortunate," he said, "a diode  blew  in  one  of  the
life-support  computers.  When  we  tried  to revive our cleaning
staff we discovered they'd been dead for nearly  thirty  thousand
years.  Who's  going to clear away the bodies, that's what I want
to know. Look why don't you sit yourself down over there and  let
me plug you in?"

He gestured Arthur towards a chair which looked as if it had been
made out of the rib cage of a stegosaurus.

"It was made out of the rib cage of a stegosaurus," explained the
old  man as he pottered about fishing bits of wire out from under
tottering piles of paper  and  drawing  instruments.  "Here,"  he
said,  "hold  these," and passed a couple of stripped wire end to
Arthur.

The instant he took hold of them a  bird  flew  straight  through
him.

He was suspended in mid-air and  totally  invisible  to  himself.
Beneath him was a pretty treelined city square, and all around it
as far as the eye could see were white concrete buildings of airy
spacious  design  but  somewhat  the  worse  for wear - many were
cracked and stained with rain. Today however the sun was shining,
a  fresh  breeze  danced lightly through the trees, and the odd
sensation that all the buildings were quietly humming was
probably caused by the fact that the square and all the streets
around it were thronged with cheerful excited people. Somewhere a
band  was playing, brightly coloured flags were fluttering in the
breeze and the spirit of carnival was in the air.

Arthur felt extraordinarily lonely stuck up in the air  above  it
all without so much as a body to his name, but before he had time
to reflect on this a voice rang out across the square and  called
for everyone's attention.

A man standing on a brightly dressed  dais  before  the  building
which  clearly dominated the square was addressing the crowd over
a Tannoy.

"O people waiting in the Shadow of Deep Thought!" he  cried  out.
"Honoured Descendants of Vroomfondel and Majikthise, the Greatest
and Most Truly Interesting Pundits the Universe  has  ever  known
... The Time of Waiting is over!"

Wild cheers broke out amongst the  crowd.  Flags,  streamers  and
wolf whistles sailed through the air. The narrower streets looked
rather like centipedes rolled over on their backs and frantically
waving their legs in the air.

"Seven and a half million years our  race  has  waited  for  this
Great  and  Hopefully  Enlightening Day!" cried the cheer leader.
"The Day of the Answer!"

Hurrahs burst from the ecstatic crowd.

"Never again," cried the man, "never again will we wake up in the
morning  and  think Who am I? What is my purpose in life? Does it
really, cosmically speaking, matter if I don't get up and  go  to
work?  For today we will finally learn once and for all the plain
and simple answer to all these nagging little problems  of  Life,
the Universe and Everything!"

As the crowd erupted once again,  Arthur  found  himself  gliding
through the air and down towards one of the large stately windows
on the first floor of the building behind the dais from which the
speaker was addressing the crowd.

He experienced a moment's panic as  he  sailed  straight  through
towards  the  window,  which  passed when a second or so later he
found  he  had  gone  right  through  the  solid  glass   without
apparently touching it.

No one in the room remarked on his  peculiar  arrival,  which  is
hardly  surprising  as  he wasn't there. He began to realize that
the whole experience  was  merely  a  recorded  projection  which
knocked six-track seventy-millimetre into a cocked hat.

The room was much as Slartibartfast had described  it.  In  seven
and  a  half  million  years  it  had  been well looked after and
cleaned regularly every century or so. The ultramahagony desk was
worn  at  the edges, the carpet a little faded now, but the large
computer terminal sat in sparkling glory on  the  desk's  leather
top, as bright as if it had been constructed yesterday.
Two severely dressed men sat respectfully before the terminal and
waited.

"The time is nearly upon us," said one, and Arthur was  surprised
to  see a word suddenly materialize in thin air just by the man's
neck. The word was Loonquawl, and it flashed a  couple  of  times
and  the  disappeared again. Before Arthur was able to assimilate
this the other man spoke and the word  Phouchg  appeared  by  his
neck.

"Seventy-five thousand generations ago, our  ancestors  set  this
program in motion," the second man said, "and in all that time we
will be the first to hear the computer speak."

"An awesome prospect, Phouchg," agreed the first man, and  Arthur
suddenly   realized   that  he  was  watching  a  recording  with
subtitles.

"We are the ones who will hear," said Phouchg, "the answer to the
great question of Life ...!"

"The Universe ...!" said Loonquawl.

"And Everything ...!"

"Shhh," said Loonquawl with  a  slight  gesture,  "I  think  Deep
Thought is preparing to speak!"

There was a moment's expectant pause whilst panels slowly came to
life  on  the  front  of  the  console. Lights flashed on and off
experimentally and settled down into a  businesslike  pattern.  A
soft low hum came from the communication channel.

"Good morning," said Deep Thought at last.

"Er ... Good morning, O Deep Thought," said Loonquawl  nervously,
"do you have ... er, that is ..."

"An answer for you?" interrupted Deep Thought majestically. "Yes.
I have."

The two men shivered with expectancy. Their waiting had not  been
in vain.

"There really is one?" breathed Phouchg.

"There really is one," confirmed Deep Thought.

"To Everything? To the great Question of Life, the  Universe  and
Everything?"

"Yes."

Both of the men had been trained for this moment, their lives had
been  a  preparation  for  it, they had been selected at birth as
those who would witness  the  answer,  but  even  so  they  found
themselves gasping and squirming like excited children.

"And you're ready to give it to us?" urged Loonquawl.
"I am."

"Now?"

"Now," said Deep Thought.

They both licked their dry lips.

"Though I don't think," added Deep Thought, "that you're going to
like it."

"Doesn't matter!" said Phouchg. "We must know it! Now!"

"Now?" inquired Deep Thought.

"Yes! Now ..."

"Alright," said the computer and settled into silence again.  The
two men fidgeted. The tension was unbearable.

"You're really not going to like it," observed Deep Thought.

"Tell us!"

"Alright," said Deep Thought. "The Answer to the  Great  Question
..."

"Yes ...!"

"Of Life, the Universe and Everything ..." said Deep Thought.

"Yes ...!"

"Is ..." said Deep Thought, and paused.

"Yes ...!"

"Is ..."

"Yes ...!!!...?"

gigem{Forty-two_said_Deep_Thought}, with infinite majesty and calm.




It was a long time before anyone spoke.

Out of the corner of his eye Phouchg could see the sea  of  tense
expectant faces down in the square outside.

"We're going to get lynched aren't we?" he whispered.

"It was a tough assignment," said Deep Thought mildly.

"Forty-two!" yelled Loonquawl. "Is that all you've  got  to  show
for seven and a half million years' work?"
"I checked it very thoroughly,"  said  the  computer,  "and  that
quite  definitely is the answer. I think the problem, to be quite
honest with you, is that you've never  actually  known  what  the
question is."

"But it was the Great Question! The Ultimate  Question  of  Life,
the Universe and Everything!" howled Loonquawl.

"Yes," said Deep Thought with the air of one  who  suffers  fools
gladly, "but what actually is it?"

A slow stupefied silence crept over the men as they stared at the
computer and then at each other.

"Well, you know, it's just Everything ... Everything ..." offered
Phouchg weakly.

"Exactly!" said Deep Thought. "So  once  you  do  know  what  the
question actually is, you'll know what the answer means."

"Oh terrific," muttered Phouchg flinging aside his  notebook  and
wiping away a tiny tear.

"Look, alright, alright," said Loonquawl, "can  you  just  please
tell us the Question?"

"The Ultimate Question?"

"Yes!"

"Of Life, the Universe, and Everything?"

"Yes!"

Deep Thought pondered this for a moment.

"Tricky," he said.

"But can you do it?" cried Loonquawl.

Deep Thought pondered this for another long moment.

Finally: "No," he said firmly.

Both men collapsed on to their chairs in despair.

"But I'll tell you who can," said Deep Thought.

They both looked up sharply.

"Who?" "Tell us!"

Suddenly Arthur began to feel his apparently  non-existent  scalp
begin  to  crawl as he found himself moving slowly but inexorably
forward towards the console, but it was only a dramatic  zoom  on
the part of whoever had made the recording he assumed.

"I speak of none other than the computer that is  to  come  after
me,"  intoned  Deep  Thought,  his voice regaining its accustomed
declamatory  tones.  "A   computer   whose   merest   operational
parameters  I  am not worthy to calculate - and yet I will design
it for you. A computer which can calculate the  Question  to  the
Ultimate   Answer,   a  computer  of  such  infinite  and  subtle
complexity that organic  life  itself  shall  form  part  of  its
operational  matrix.  And  you yourselves shall take on new forms
and go down into the computer to  navigate  its  ten-million-year
program!  Yes!  I shall design this computer for you. And I shall
name it also unto you. And it shall be called ... The Earth."

Phouchg gaped at Deep Thought.

"What a dull name," he said and great incisions appeared down the
length  of  his  body.  Loonquawl too suddenly sustained horrific
gashed from nowhere. The Computer console blotched  and  cracked,
the  walls  flickered  and  crumbled and the room crashed upwards
into its own ceiling ...

Slartibartfast was standing in front of Arthur  holding  the  two
wires.

"End of the tape," he explained.

途中、フラグが含まれていた。

gigem{Forty-two_said_Deep_Thought}

STEM CTF: Cyber Challenge 2019 Writeup

この大会は2019/2/23 4:00(JST)~2018/2/24 4:00(JST)に開催されました。
今回もチームで参戦。結果は 2050点でProfessionalの433チーム中8位でした。
自分で解けた問題をWriteupとして書いておきます。

Warm Up (Crypto 50)

まず秘密鍵をインポートする。

$ gpg --import mitre-ctf-2019-private.asc 
gpg: 鍵CB374E23: 秘密鍵をインポートしました
gpg: /home/yoshinori/.gnupg/trustdb.gpg: 信用データベースができました
gpg: 鍵CB374E23: 公開鍵"CTF Competitor (This is private key for a 2019 MITRE CTF Competitor and should not be trusted!) <fake@fake>"をインポートしました
gpg: 処理数の合計: 1
gpg:               インポート: 1  (RSA: 1)
gpg:       秘密鍵の読み込み: 1
gpg:   秘密鍵のインポート: 1

そしてpassphrase.txt の中を見てみる。

$ cat passphrase.txt 
just use ctfd

次にkey.encを復号してみる。パスフレーズはjust use ctfd。

$ gpg key.enc

次のユーザの秘密鍵のロックを解除するには
パスフレーズがいります:"CTF Competitor (This is private key for a 2019 MITRE CTF Competitor and should not be trusted!) <fake@fake>"
2048ビットRSA鍵, ID 87BA2B5E作成日付は2018-12-03 (主鍵ID CB374E23)

gpg: 2048-ビットRSA鍵, ID 87BA2B5E, 日付2018-12-03に暗号化されました
      "CTF Competitor (This is private key for a 2019 MITRE CTF Competitor and should not be trusted!) <fake@fake>"
gpg: key.enc: 未知の拡張子
新しいファイル名を入力してください [key]: 
gpg: 20181204074809秒 JSTにRSA鍵ID F2FFFCB4で施された署名
gpg: 署名を検査できません: 公開鍵が見つかりません

aes-256-cbcで鍵にkeyを指定して、flag.html.encを復号する。

$ openssl aes-256-cbc -d -in flag.html.enc -out flag.html -pass file:./key
$ cat flag.html
<!DOCTYPE html>
<html>
<head>
  <title>MITRE CTF 2019 Homepage.</title>
</head>
<body>
<h1>This is an HTML Page</h1>
<br>
<p>Test Flag please ignore:</p>
<p>MCA{0p3n55l_c0mm4nd_l1ne_ch4ll3ng3_fl4g}</p>
<p style="display:none;">MCA{66b2f50cd2d6b9622c6be902ee2b0976badb4684}</p>
</body>
</html>
MCA{66b2f50cd2d6b9622c6be902ee2b0976badb4684}

Super Secret Hidden Service (Web 50)

サーバ証明書が無効になっているので、見てみると、サブジェクト代替名が以下のようになっている。

DNS Name=138.247.13.115.xip.io

https://138.247.13.115.xip.io/にアクセスすると、フラグが表示された。

Flag is: MCA{shuHeimoowaiF5a}
MCA{shuHeimoowaiF5a}

Turing Test (Web 50)

Alan Turingについて調べる。https://en.wikipedia.org/wiki/Alan_Turingを参考にする。

Mother's Maiden Name: Stoney
First School Attended: St. Michael's
Favorite Primary School Subject: Science
Favorite Olympic Event: Marathon
2 + 2 - 3 = ?: 1

上記を入力し、チェックボックスすべてをONにして、Submitすると、フラグが表示された。

MCA{sms_2fa_is_bad_also}