SECCON Beginners CTF 2019 Write-up

はじめに
成績
Misc
Reversing
- Seccompare [warmup, 407solves, 57pts]
Web
- Ramen [warmup, 280solves, 77pts]
- katsudon [214solves, 102pts]
Crypto
まとめ

はじめに

2019/05/25 ~ 2019/05/26に開催されたSECCON Beginners CTFに個人で参加しました．
自分にとっての初CTFが去年のSECCON Beginners CTFだったので個人的に思い入れがあるCTFです．
去年はwarmupしか解けず，絶望してしまったので今年は時間を十分に確保して参加しました(バイトを休ませてもらった)．

成績

54位(666チーム中)でした．

f:id:satto1237:20190526151446p:plain f:id:satto1237:20190526151459p:plain

Misc

Welcome [warmup, 593solves, 51pts]

SECCON Beginners CTFのIRCチャンネルで会いましょう。

IRC: freenode.net #seccon-beginners-ctf

アプローチ：IRCに入る

f:id:satto1237:20190526144417p:plain

ctf4b{welcome_to_seccon_beginners_ctf}

containers [302solves, 71pts]

Let's extract files from the container.
file

> file e35860e49ca3fa367e456207ebc9ff2f_containers
e35860e49ca3fa367e456207ebc9ff2f_containers: data

アプローチ：foremost

とりあえずbinwalkをかけるとPNGが大量に埋め込まれていることが分かります．

> binwalk e35860e49ca3fa367e456207ebc9ff2f_containers

DECIMAL       HEXADECIMAL     DESCRIPTION
--------------------------------------------------------------------------------
16            0x10            PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
107           0x6B            Zlib compressed data, compressed
738           0x2E2           PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
829           0x33D           Zlib compressed data, compressed
1334          0x536           PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
1425          0x591           Zlib compressed data, compressed
1914          0x77A           PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
2005          0x7D5           Zlib compressed data, compressed
2856          0xB28           PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
2947          0xB83           Zlib compressed data, compressed
3666          0xE52           PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
3757          0xEAD           Zlib compressed data, compressed
4354          0x1102          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
4445          0x115D          Zlib compressed data, compressed
5156          0x1424          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
5247          0x147F          Zlib compressed data, compressed
5846          0x16D6          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
5937          0x1731          Zlib compressed data, compressed
6722          0x1A42          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
6813          0x1A9D          Zlib compressed data, compressed
7757          0x1E4D          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
7848          0x1EA8          Zlib compressed data, compressed
8338          0x2092          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
8429          0x20ED          Zlib compressed data, compressed
9243          0x241B          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
9334          0x2476          Zlib compressed data, compressed
10319         0x284F          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
10410         0x28AA          Zlib compressed data, compressed
11042         0x2B22          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
11133         0x2B7D          Zlib compressed data, compressed
12118         0x2F56          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
12209         0x2FB1          Zlib compressed data, compressed
12809         0x3209          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
12900         0x3264          Zlib compressed data, compressed
13845         0x3615          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
13936         0x3670          Zlib compressed data, compressed
14592         0x3900          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
14683         0x395B          Zlib compressed data, compressed
15535         0x3CAF          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
15626         0x3D0A          Zlib compressed data, compressed
16440         0x4038          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
16531         0x4093          Zlib compressed data, compressed
17313         0x43A1          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
17404         0x43FC          Zlib compressed data, compressed
18218         0x472A          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
18309         0x4785          Zlib compressed data, compressed
19123         0x4AB3          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
19214         0x4B0E          Zlib compressed data, compressed
19926         0x4DD6          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
20017         0x4E31          Zlib compressed data, compressed
20869         0x5185          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
20960         0x51E0          Zlib compressed data, compressed
21742         0x54EE          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
21833         0x5549          Zlib compressed data, compressed
22465         0x57C1          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
22556         0x581C          Zlib compressed data, compressed
23408         0x5B70          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
23499         0x5BCB          Zlib compressed data, compressed
23989         0x5DB5          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
24080         0x5E10          Zlib compressed data, compressed
24810         0x60EA          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
24901         0x6145          Zlib compressed data, compressed
25753         0x6499          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
25844         0x64F4          Zlib compressed data, compressed
26788         0x68A4          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
26879         0x68FF          Zlib compressed data, compressed
27599         0x6BCF          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
27690         0x6C2A          Zlib compressed data, compressed
28504         0x6F58          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
28595         0x6FB3          Zlib compressed data, compressed
29085         0x719D          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
29176         0x71F8          Zlib compressed data, compressed
29808         0x7470          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
29899         0x74CB          Zlib compressed data, compressed
30844         0x787C          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
30935         0x78D7          Zlib compressed data, compressed
31524         0x7B24          PNG image, 128 x 128, 8-bit/color RGBA, non-interlaced
31615         0x7B7F          Zlib compressed data, compressed

foremostで抽出します．

> foremost e35860e49ca3fa367e456207ebc9ff2f_containers

PNGイメージとflagが1対1で対応しているみたいです．

f:id:satto1237:20190526145231p:plain

ctf4b{e52df60c058746a66e4ac4f34db6fc81}

Dump [163solves, 138pts]

Analyze dump and extract the flag!!

file

> file fc23f13bcf6562e540ed81d1f47710af_dump
fc23f13bcf6562e540ed81d1f47710af_dump: tcpdump capture file (little-endian) - version 2.4 (Ethernet, capture length 262144)

アプローチ：Oct to Bytes

tcpdump capture fileであることがわかったのでWiresharkで覗いてみます．

f:id:satto1237:20190526150626p:plain

f:id:satto1237:20190526150638p:plain

GET /webshell.php?cmd=ls -l /home/ctf4b/flag HTTP/1.1

GET /webshell.php?cmd=hexdump -e '16/1 "%02.3o " "\n"' /home/ctf4b/flag

flagをhexdumpしているっぽいのでdumpされたOctを集めてflagを復元します．

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

with open('./message.txt') as f:
    messages = [s.strip() for s in f.readlines()]

output = bytearray()

for line in messages:
    m = line.split(' ')
    for x in m:
        if len(x) == 3:
            output.append(int(x,8))

with open('dump', 'wb') as f:
    f.write(output)

> file dump
dump: gzip compressed data, last modified: Sun Apr  7 10:46:34 2019, from Unix, original size 798720

復元結果がgzipになっているので解凍してあげます．

f:id:satto1237:20190526151338j:plain

ctf4b{hexdump_is_very_useful}

Sliding puzzle [106solves, 206pts]

スライドパズルを解いてください。すべてのパズルを解き終わったとき FLAG が表示されます。

nc 133.242.50.201 24912

0 はブランクで動かすことが可能です。操作方法は以下のとおりです。
0 : 上
1 : 右
2 : 下
3 : 左

操作手順は以下の形式で送信してください。

1,3,2,0, ... ,2

> nc 133.242.50.201 24912
----------------
| 03 | 04 | 01 |
| 08 | 02 | 05 |
| 06 | 00 | 07 |
----------------

アプローチ：拾ってきたソルバ(A-star)をよしなに書き換える

ソルバをググると以下のコードがヒットします．

github.com

これを今回の問題の形式に対応させると以下のようなソルバになります．

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import numpy as np
from solver import Solver
from socket import *

def A_star(init_state, goal_state, max_iter, heuristic):
    command = ''
    solver = Solver(init_state, goal_state, heuristic, max_iter)
    path = solver.solve_a_star()

    if len(path) == 0:
        exit(1)

    init_idx = init_state.flatten().tolist().index(0)
    init_i, init_j = init_idx // goal_state.shape[0], init_idx % goal_state.shape[0]

    for node in reversed(path):
        cur_idx = node.get_state().index(0)
        cur_i, cur_j = cur_idx // goal_state.shape[0], cur_idx % goal_state.shape[0]

        new_i, new_j = cur_i - init_i, cur_j - init_j
        if new_j == 0 and new_i == -1:
            command += '0,'
            print('Moved UP    from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j)))
        elif new_j == 0 and new_i == 1:
            command += '2,'
            print('Moved DOWN  from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j)))
        elif new_i == 0 and new_j == 1:
            command += '1,'
            print('Moved RIGHT from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j)))
        else:
            command += '3,'
            print('Moved LEFT  from ' + str((init_i, init_j)) + ' --> ' + str((cur_i, cur_j)))

        init_i, init_j = cur_i, cur_j

    return command

def parseRow(rec):
    row = [int(x) for x in rec.split(' ') if len(x) > 1]
    return row

def main():
    max_iter = 5000
    heuristic = "manhattan"
    algorithm = "a_star"
    n = 3

    goal_state = np.array([[0, 1, 2],[3, 4, 5],[6, 7, 8]])

    s = socket(AF_INET, SOCK_STREAM)
    s.connect(('133.242.50.201',24912))

    while True:
        rec = s.recv(1024).decode('utf-8')
        print(rec)
        rec = rec.split('\n')
        row1 = parseRow(rec[1])
        row2 = parseRow(rec[2])
        row3 = parseRow(rec[3])
        init_state = np.array([row1, row2, row3])

        command =  A_star(init_state, goal_state, max_iter, heuristic)
        s.send(command[:-1].encode('utf-8') + b'\n')

if __name__ == '__main__':
    main()

----------------
| 04 | 06 | 02 |
| 01 | 05 | 00 |
| 07 | 03 | 08 |
----------------


Moved LEFT  from (1, 2) --> (1, 1)
Moved UP    from (1, 1) --> (0, 1)
Moved LEFT  from (0, 1) --> (0, 0)
Moved DOWN  from (0, 0) --> (1, 0)
Moved RIGHT from (1, 0) --> (1, 1)
Moved DOWN  from (1, 1) --> (2, 1)
Moved LEFT  from (2, 1) --> (2, 0)
Moved UP    from (2, 0) --> (1, 0)
Moved RIGHT from (1, 0) --> (1, 1)
Moved UP    from (1, 1) --> (0, 1)
Moved LEFT  from (0, 1) --> (0, 0)

[snip]
----------------
| 03 | 00 | 02 |
| 04 | 01 | 05 |
| 06 | 07 | 08 |
----------------


Moved DOWN  from (0, 1) --> (1, 1)
Moved LEFT  from (1, 1) --> (1, 0)
Moved UP    from (1, 0) --> (0, 0)
[+] Congratulations! ctf4b{fe6f512c15daf77a2f93b6a5771af2f723422c72}

100問解いたらflagが落ちてきました．

ctf4b{fe6f512c15daf77a2f93b6a5771af2f723422c72}

Reversing

Seccompare [warmup, 407solves, 57pts]

file

> file seccompare
seccompare: ELF 64-bit LSB executable, x86-64, version 1 (SYSV), dynamically linked, interpreter /lib64/ld-linux-x86-64.so.2, for GNU/Linux 3.2.0, BuildID[sha1]=4a607c82ea263205071c80295afe633412cda6f7, not stripped

アプローチ：ltrace

問題名にcompareが入っているのでstrcmpで愚直に比較してる読みltraceをします．

> ltrace ./seccompare hoge
strcmp("ctf4b{5tr1ngs_1s_n0t_en0ugh}", "hoge")   = -5
puts("wrong"wrong
)                                    = 6
+++ exited (status 0) +++

ctf4b{5tr1ngs_1s_n0t_en0ugh}

Web

Ramen [warmup, 280solves, 77pts]

ラーメン https://ramen.quals.beginners.seccon.jp

f:id:satto1237:20190526141556p:plain

アプローチ：UNION Query Injection

SQLiできそうな見た目をしているのでいつものやつ(' or 1 = 1 -- )を投げてみます．

f:id:satto1237:20190526141843p:plain

攻撃自体は成功していますがこのテーブルにはflagはないようです．

そのため，UNION句を使ってdbのテーブル名とカラム名一覧を取得します．
' UNION SELECT table_name, GROUP_CONCAT(column_name) FROM INFORMATION_SCHEMA.COLUMNS GROUP BY table_name --

f:id:satto1237:20190526142430p:plain

flagテーブルにflagカラムがあることがわかったので表示してあげます．

' UNION SELECT null,flag FROM flag --

f:id:satto1237:20190526142742p:plain

ctf4b{a_simple_sql_injection_with_union_select}

katsudon [214solves, 102pts]

Rails 5.2.1で作られたサイトです｡

https://katsudon.quals.beginners.seccon.jp

クーポンコードを復号するコードは以下の通りですが､まだ実装されてないようです｡

フラグは以下にあります｡ https://katsudon.quals.beginners.seccon.jp/flag

f:id:satto1237:20190526143434p:plain

アプローチ：Base64

各店舗のシリアルコード(Base64 + 謎ハッシュ値)が表示されているのでBase64の方だけデコードしてみます．

> echo 'BAhJIhByZWl3YWhhbnRlbgY6BkVU' | base64 -D
I"reiwahanten:ET%

> echo 'BAhJIhNoZWlzZWlzaG9rdWRvdQY6BkVU' | base64 -D
I"heiseishokudou:ET%

> echo 'BAhJIhRyZXN0YXVyYW50c2hvd2EGOgZFVA==' | base64 -D
I"restaurantshowa:ET%

意味のある文字列だったのでflagページの方のBase64もデコードしてみます．

> echo 'BAhJIiVjdGY0YntLMzNQX1kwVVJfNTNDUjM3X0szWV9CNDUzfQY6BkVU' | base64 -D
I"%ctf4b{K33P_Y0UR_53CR37_K3Y_B453}:ET%

ctf4b{K33P_Y0UR_53CR37_K3Y_B453}

一応flagは取れたのですがRails 5.2.1と全く関係ない方法で取れてしまったので正直よくわかりませんでした．

Crypto

So Tired [warmup, 192solves, 115pts]

最強の暗号を作りました。暗号よくわからないけどきっと大丈夫！

file

> file encrypted.txt
encrypted.txt: ASCII text, with very long lines, with no line terminators

eJwUm7V25UAQBT9IgZj[snip]4+xY8VKB7Iqh9I+5+K5v4B8HzgzA==

アプローチ：Base64 + zlib

encrypted.txtはBase64だったのでとりあえずデコードしてみると

import base64
import zlib

with open('./encrypted.txt') as f:
    text = f.read().encode()

output = base64.b64decode(text)

with open('output_file', 'wb') as f:
    f.write(output)

> file output_file
output_file: zlib compressed data

zlib compressed dataであることが分かります．

次にzlibをdecompressしてあげるとまたBase64テキストになることが分かりました．

めんどくさくなったので自動化します．

import base64
import zlib

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

count = 1

while True:
    print(count)
    if data[:2] == b'x\x9c':
        dc = zlib.decompress(data)
        data = base64.b64decode(dc)
        count += 1
    else:
        break

500回目でflagになります．

ctf4b{very_l0ng_l0ng_BASE64_3nc0ding}

Party [96solves, 223pts]

Let's 暗号パーティ

file

encrypt.py

from flag import FLAG
from Crypto.Util.number import bytes_to_long, getRandomInteger, getPrime


def f(x, coeff):
    y = 0
    for i in range(len(coeff)):
        y += coeff[i] * pow(x, i)
    return y


N = 512
M = 3
secret = bytes_to_long(FLAG)
assert(secret < 2**N)

coeff = [secret] + [getRandomInteger(N) for i in range(M-1)]
party = [getRandomInteger(N) for i in range(M)]

val = map(lambda x: f(x, coeff), party)
output = list(zip(party, val))
print(output)

encrypted

[(5100090496682565208825623434336918311864447624450952089752237720911276820495717484390023008022927770468262348522176083674815520433075299744011857887705787, 222638290427721156440609599834544835128160823091076225790070665084076715023297095195684276322931921148857141465170916344422315100980924624012693522150607074944043048564215929798729234427365374901697953272928546220688006218875942373216634654077464666167179276898397564097622636986101121187280281132230947805911792158826522348799847505076755936308255744454313483999276893076685632006604872057110505842966189961880510223366337320981324768295629831215770023881406933), (3084167692493508694370768656017593556897608397019882419874114526720613431299295063010916541874875224502547262257703456540809557381959085686435851695644473, 81417930808196073362113286771400172654343924897160732604367319504584434535742174505598230276807701733034198071146409460616109362911964089058325415946974601249986915787912876210507003930105868259455525880086344632637548921395439909280293255987594999511137797363950241518786018566983048842381134109258365351677883243296407495683472736151029476826049882308535335861496696382332499282956993259186298172080816198388461095039401628146034873832017491510944472269823075), (6308915880693983347537927034524726131444757600419531883747894372607630008404089949147423643207810234587371577335307857430456574490695233644960831655305379, 340685435384242111115333109687836854530859658515630412783515558593040637299676541210584027783029893125205091269452871160681117842281189602329407745329377925190556698633612278160369887385384944667644544397208574141409261779557109115742154052888418348808295172970976981851274238712282570481976858098814974211286989340942877781878912310809143844879640698027153722820609760752132963102408740130995110184113587954553302086618746425020532522148193032252721003579780125)]

アプローチ：ラグランジュ補間

どうみてもSecret Sharingなのでラグランジュ係数の演算誤差に注意しながらラグランジュ補間をします．

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from Crypto.Util.number import long_to_bytes

output = [(5100090496682565208825623434336918311864447624450952089752237720911276820495717484390023008022927770468262348522176083674815520433075299744011857887705787, 222638290427721156440609599834544835128160823091076225790070665084076715023297095195684276322931921148857141465170916344422315100980924624012693522150607074944043048564215929798729234427365374901697953272928546220688006218875942373216634654077464666167179276898397564097622636986101121187280281132230947805911792158826522348799847505076755936308255744454313483999276893076685632006604872057110505842966189961880510223366337320981324768295629831215770023881406933), (3084167692493508694370768656017593556897608397019882419874114526720613431299295063010916541874875224502547262257703456540809557381959085686435851695644473, 81417930808196073362113286771400172654343924897160732604367319504584434535742174505598230276807701733034198071146409460616109362911964089058325415946974601249986915787912876210507003930105868259455525880086344632637548921395439909280293255987594999511137797363950241518786018566983048842381134109258365351677883243296407495683472736151029476826049882308535335861496696382332499282956993259186298172080816198388461095039401628146034873832017491510944472269823075), (6308915880693983347537927034524726131444757600419531883747894372607630008404089949147423643207810234587371577335307857430456574490695233644960831655305379, 340685435384242111115333109687836854530859658515630412783515558593040637299676541210584027783029893125205091269452871160681117842281189602329407745329377925190556698633612278160369887385384944667644544397208574141409261779557109115742154052888418348808295172970976981851274238712282570481976858098814974211286989340942877781878912310809143844879640698027153722820609760752132963102408740130995110184113587954553302086618746425020532522148193032252721003579780125)]

lag0 = (output[0][1] * output[1][0] * output[2][0]) // ((output[0][0]-output[1][0]) * (output[0][0]-output[2][0]))
lag1 = (output[1][1] * output[0][0] * output[2][0]) // ((output[1][0]-output[0][0]) * (output[1][0]-output[2][0]))
lag2 = (output[2][1] * output[1][0] * output[0][0]) // ((output[2][0]-output[1][0]) * (output[2][0]-output[0][0]))
secret = lag0 + lag1 + lag2
print(long_to_bytes(secret))

ctf4b{just_d0ing_sh4mir}

Secret Sharingは通常であれば $\bmod P$ (素数)上で行うはずなのですが今回の問題はちょっと違いましたね(getPrimeをimportしてるので草案ではそうだったのかもしれない)

Go RSA [37solves, 363pts]

Nだけなくしちゃったんだよなあ……。

Server: nc 133.242.17.175 1337

> nc 133.242.17.175 1337
Encrypted flag is: 4725892326131640511938836467356380640397395755148515442238144307716268382252628227752706337031081867656763601262225583418303010193239356145844773869421583928956830475001659989802417519525376977915742938040734455026586792580629138505932764823343548099242875945669696790179649220582806677338952996620085062222609753771468773503312464080667581802039545168540557775175910139783773568895672923857876387792456057914870803099574255916087021356112254136797301781099631817901879990750639939793954026851169923804748143896554243498372979547574635377196600744448195794904851780679885454328745360685620374662405322841325901266342
> 11
7637811207979739219669490743378336650776535942943752504812029481377761911058098069129370129891186065700013565658425623145096181174940284569170173845864097024499447436745302222316078164333521436075178658111338798129491626771375186572329383908383189341163934643713551924178771397720534193926131973485274138576551879941437401429052365352919721199518788548926065434907685968560503200611173822384479590055822627949819328899143710503731634878295102670058980960754156195359495395859997444231704641045830011633563005247272318388623636227814230719956741962610601123833306215246334889580406317875472898523048605130307312142405
> 27
9083236756510502667672149597920937345609065952381103744458773609677349181137664898132336299978787391428145194106398285831203807691539715388732580593315467304747140152910340572357534656173881218457206571537060957819436232216333145441782251558467372248774534265689018805410968856154304032189923153055338920877482978347723674178822530503588597019097743749899880561404545399165006564054140566630136178882852665776958989723666213308348480085079148320569989618818179565755270024216590124150820307469348296537784213056635374932270363584956103955814113622691900216592869655412483832137357451499594296512566943069908225210734
> 100
7026445835542647141907783190328483047682576235769713858426579438967936914699835557760650020607977551407452309826139518542937401053779667154528749498335633652039979184783915183555701404386624160304188959930900255234658247046723155024892615238236151937654211279613994878056685883680731033253494552504451907528560837434514304089104648323475985198621962943979282704998385067331133496621660306924791131855783998482073799172052170009672789638003863302229835592540595367819302032212643072356316510889051286933794282881878035554552646333541242222793357920058043907289691535546821516658857953954016748437167985559279211706133
The D was 11458711755035670464038023339470449045516641995506883118289541007057383750687501319340094124932721557270059748633889547682404537144455516634669377475861767368934592310210016407301606085157477328662317671491707721936501722619798842708958774830172877965800990263700253906048588526355356847729377612163313112308312564511078609962986973393588081618659656723726978199229317195649278770467451124046419253881031382495199996086694246635234831202278493431951587700512798998873022490223975989484868695392247040865016421693345721234250068247064936395381184432538492079017858523226444063058574726651206459901461956681780685609953

アプローチ：GCD

CとDが既知なのであとはNが分かればmを求めることができます．
しかし，問題文にもある通りNが公開されていなのでmとCの対応関係を使ってNを求める必要があります．

RSAでは $C$ は以下のように計算します．

$C \equiv m^{e} \bmod N$

そのため， $m^{e}$ は次のように表すことができます．

$m_1^{e} = k_1 N + C_1$

$m_2^{e} = k_2 N + C_2$

$m_3^{e} = k_3 N + C_3$

したがって， $k_i N = m_i^{e} - C_i$ により $k_i N$ が取得可能になります．

あとは $k_i N$ 同士のGCDを計算すれば $N$ が求められます．
$k_i$ の値によっては上手くいかない場合がありますが上手くいくまで $m$ をガチャれば大丈夫です（は？

以下ソルバです．

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from Crypto.Util.number import *

e = 0x10001
c = 4725892326131640511938836467356380640397395755148515442238144307716268382252628227752706337031081867656763601262225583418303010193239356145844773869421583928956830475001659989802417519525376977915742938040734455026586792580629138505932764823343548099242875945669696790179649220582806677338952996620085062222609753771468773503312464080667581802039545168540557775175910139783773568895672923857876387792456057914870803099574255916087021356112254136797301781099631817901879990750639939793954026851169923804748143896554243498372979547574635377196600744448195794904851780679885454328745360685620374662405322841325901266342
d = 11458711755035670464038023339470449045516641995506883118289541007057383750687501319340094124932721557270059748633889547682404537144455516634669377475861767368934592310210016407301606085157477328662317671491707721936501722619798842708958774830172877965800990263700253906048588526355356847729377612163313112308312564511078609962986973393588081618659656723726978199229317195649278770467451124046419253881031382495199996086694246635234831202278493431951587700512798998873022490223975989484868695392247040865016421693345721234250068247064936395381184432538492079017858523226444063058574726651206459901461956681780685609953

m1 = 11
c1 = 7637811207979739219669490743378336650776535942943752504812029481377761911058098069129370129891186065700013565658425623145096181174940284569170173845864097024499447436745302222316078164333521436075178658111338798129491626771375186572329383908383189341163934643713551924178771397720534193926131973485274138576551879941437401429052365352919721199518788548926065434907685968560503200611173822384479590055822627949819328899143710503731634878295102670058980960754156195359495395859997444231704641045830011633563005247272318388623636227814230719956741962610601123833306215246334889580406317875472898523048605130307312142405

m2 = 27
c2 = 9083236756510502667672149597920937345609065952381103744458773609677349181137664898132336299978787391428145194106398285831203807691539715388732580593315467304747140152910340572357534656173881218457206571537060957819436232216333145441782251558467372248774534265689018805410968856154304032189923153055338920877482978347723674178822530503588597019097743749899880561404545399165006564054140566630136178882852665776958989723666213308348480085079148320569989618818179565755270024216590124150820307469348296537784213056635374932270363584956103955814113622691900216592869655412483832137357451499594296512566943069908225210734

m3 =100
c3 =  7026445835542647141907783190328483047682576235769713858426579438967936914699835557760650020607977551407452309826139518542937401053779667154528749498335633652039979184783915183555701404386624160304188959930900255234658247046723155024892615238236151937654211279613994878056685883680731033253494552504451907528560837434514304089104648323475985198621962943979282704998385067331133496621660306924791131855783998482073799172052170009672789638003863302229835592540595367819302032212643072356316510889051286933794282881878035554552646333541242222793357920058043907289691535546821516658857953954016748437167985559279211706133

k1_n = pow(m1,e) - c1
k2_n = pow(m2,e) - c2
k3_n = pow(m3,e) - c3

n = GCD(k1_n, GCD(k2_n, k3_n))
print(long_to_bytes(pow(c, d, n)))

ctf4b{f1nd_7he_p4ramet3rs}

$e$ も公開されていませんがエスパーで0x10001を使いました．

Bit Flip [28solves, 393pts]

平文を1ビットランダムで反転させる能力を手に入れた！

Server: nc 133.242.17.175 31337

bitflip.py

from Crypto.Util.number import bytes_to_long
import random

N = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
e = 3
FLAG = bytes_to_long(open('flag', 'rb').read())

r = 1 << random.randrange(0, FLAG.bit_length() // 4)
C = pow(FLAG ^ r, e, N)

print(C)

> nc 133.242.17.175 31337
34495772845776138053860574863082807629902875416466919427415045743727265142914336137794413529141543617083815519863768748750221150257700972178855168455330281760754772707935321008538904121600699189837041293041987846498541772956761968152857045790864281449660662376827310046502947581341524518919435263611890512450

> nc 133.242.17.175 31337
22847704804485272897240201332364615448076265560473081494130345961236707114724029595074930665254174643883050394417095822457682230300066684688366644862329503747236653245028193028050352131020229282412626915605242797100427600649337929655211677780729739319416990174820944195984397134699611486337684117580918892985

> nc 133.242.17.175 31337
43035312703842017954042292254907266700617316162695453879829757160086337037615079359132390226750471117197542576308742513788463886773570509421068480648480633408018559488856706451532969717573877686330681208899968785429205284758238175636453962046579776676915523262861472762948841759403707556065773671701666530758

アプローチ：Related Message Attack

ぱっと見eが3なのでLow Public Exponent Attackが使えるのでは？と思ったのですがncして返ってくる暗号文を見ても分かる通りメッセージがパディングされており，そう簡単にはいきませんでした．

気を取り直して平文における1bit反転について考えてみます．
暗号化の際にflagとXORをとっているので一見複雑そうに見えますが，数式に落とすと次のように簡単化されます．

${(m - 2^{x})^{e}} \bmod N$
または
${(m + 2^{x})^{e}} \bmod N$

そのため，2つの暗号文 $C_1$ , $C_2$ は次のように表されます．

$C_1 \equiv m_1^{3} \bmod N$
$m_1 \equiv m_2 + b \bmod N$

$C_1 \equiv (m_2 + b) ^ 3 \bmod N$
$C_2 \equiv m_2^{3} \bmod N$

ここからゴリゴリ計算すると $m_2$ は以下のようになります．

$m_2 \equiv \frac{b(C_1 + 2C_2 - b^{3})}{C_1 - C_2 + 2b^{3}} \bmod N$

詳しくはpaper

以下ソルバです.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-

from Crypto.Util.number import *

def getMessage(b, c1, c2, n, e):
    b3 = pow(b, e, n)
    part1 = b * (c1 + 2 * c2 - b3) % n
    part2 = (c1 - c2 + 2 * b3) % n
    part2 = inverse(part2, n)
    return (part1 * part2) % n

def main():
    N = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
    e = 3
    c1 = 48435977819599167293699473693205310917010250721248336492061287216379692891690691913767776069993911112239078185069288585022377993407270013401637539048567366526297730605589951913845745872046158333042631889854531385928428660788578942630939788805433004268454651608813773788184844655098499352542867632893087089862
    c2 = 32832657981817352905083775530972899460590019159991145524259682040379084401983824033739329107366301756520684118701358144664961003685650874802305450356329470616987673919308922191127619492477891253202306385458337433034756100386997791550557924840412386588071364098074412967888671978045411920247972161545432892891


    b1_list = []
    b2_lsit = []

    for i in range(200):
        x = 1 << i
        b1_list.append(x)
        b1_list.append(-x)
        b2_lsit.append(x)
        b2_lsit.append(-x)

    for b1 in b1_list:
        for b2 in b2_lsit:
            if b1 == b2:
                continue
            else:
                b = b1 - b2
                message = getMessage(b, c1, c2, N, e) - b2
                flag = long_to_bytes(message)
                if b'ctf4b' in flag:
                    print(flag)
                    return

if __name__ == '__main__':
    main()

> python solve.py
b'ctf4b{b1tfl1pp1ng_1s_r3lated_m3ss4ge} DUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMYDUMMY\n'

ctf4b{b1tfl1pp1ng_1s_r3lated_m3ss4ge}

$m$ のベースがずれているのでbは予め想定値を生成しておくことで差分を全探索しています.

まとめ

CTFを始めた1年前(warmupしか解けなかった)と比較すると少しは成長できたのではないかと思う
Crypto全完できたのでやっとCrypto Beginnerになれた（は？
Web, Rev, Pwn 何も分からないので勉強します(低レイヤも高レイヤも何も分からないのはまずい)
Pwnに至ってはwarmupすら解けなかったので本当に悲しくなった

f:id:satto1237:20190526173956p:plain

s4tt01237’s diary

ラーメンとかCTFとかセキュリティとか