LoginSignup
2
4

More than 3 years have passed since last update.

@taiyaki8926

SECCON Beginners CTF Writeup

Last updated at Posted at 2019-05-26

はじめに

去年大学の同期がやってるのをみてCTFに触れ始めた記憶があります. そういう意味では私の原点ともなるCTFです.

得点としてはCrypto全問(1問目はほんの少しヒントをもらいましたが)とMiscの3問目については制限時間内に答えに辿り着けました.

私自身Crypto特化型なので, 他ジャンルの問題を解いてくれるチームメイトには感謝しきれません.
いつも通り, Writeupというよりかは答えに至るまでの思考回路を重点的に記していきます.

GitHubに問題と解答を掲載しているので, これが初心者の道標になる事を願います.

So Tired(Crypto, 115pt)

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

与えられた.txtファイルを眺めてみます.

  1. パッとみた感じ/で区切られてそうなイメージを持ったので1, 冒頭のeJwUm7V25UAQBT9IgZjCJ2bmTMzMあたりをGoogle検索しますがヒットせず. なのでmd5やsha1などのハッシュ関数ではなさそうです.
  2. ファイルの最後に==が確認できるので, おそらくbase64でエンコードしたものと思われます.

  3. デコードして結果をdecryptにリダイレクトします.

    terminal
    # mac OS
# Linuxなら-Dではなく-d
$ base64 -D encrypted.txt > decrypt

  4. decryptファイルの形式をfileコマンドで確認すると以下のようになります.

    terminal
    $ file decrypt
decrypt: zlib compressed data

  5. zlibで圧縮されたファイルのようなのでPythonで解凍してみます.

    decompress.py
    import zlib

f = open('decrypt', 'rb')
_str = f.read()
zlib.decompress(_str)

    この結果も, 英数字や+, /などが使われているのを見るとどうやらまたbase64でエンコードされているようです.

(結論)
encrypt.txtに対して
・base64デコード
・zlib解凍
を(何回か)繰り返す

solve.py
import base64
import zlib

f = open('encrypted.txt', 'r')
_str = f.read()
# 何回繰り返すかは適宜調節. 正解は500
for i in range(100):
    # デコード. ここのPythonモジュールの存在だけ友達に教えてもらいました
    _str = base64.b64decode(_str)
    # 解凍
    _str = zlib.decompress(_str)
_str

ctf4b{very_l0ng_l0ng_BASE64_3nc0ding}

Party(Crypto, 223pt)

Let's 暗号パーティ

encrypt.pyを下に載せます(ところどころ省略しています).

encrypt.py

N = 512
M = 3
secret = bytes_to_long(FLAG)

# coeff = [secret, 512bitの数, 512bitの数]
coeff = [secret] + [getRandomInteger(N) for i in range(M-1)]

# party = [512bit, 512bit, 512bit]
party = [getRandomInteger(N) for i in range(M)]

# val = [f(party[0], coeff), f(party[1], coeff), f(party[2], coeff)]
val = map(lambda x: f(x, coeff), party)

# output = [(party[0], val[0]), (party[1], val[1]), (party[2], val[2])]
output = list(zip(party, val))

コメントアウトしているところを付け足しています.
さて, outputの結果がencryptファイルにそのまま入っているので, ここからpartyとvalは分かります. 次にf(x, coeff)関数を見てみます. len(coeff) == 3であることに注意すると

encrypt.py
def f(x, coeff):
    return coeff[0] + coeff[1] * x + coeff[2] * x * x

まで簡単にすることができます.

(結論)
val, partyは既知.
$coeff[0] = a, coeff[1] = b, coeff[2] = c$とすると,
・$val[0] = a + b(party[0]) + c(party[0])^2$
・$val[1] = a + b(party[1]) + c(party[1])^2$
・$val[2] = a + b(party[2]) + c(party[2])^2$
という連立方程式を解けばよい. $a$が答えになる.

wrong_solve.py
import numpy as np
A = np.array([[1, party[0], party[0] ** 2],
          [1, party[1], party[1] ** 2],
          [1, party[2], party[2] ** 2]])
val = np.array([[output[0][1]],
            [output[1][1]],
            [output[2][1]]])
np.dot(np.linalg.inv(A), val)

と, 逆行列を求める方法はうまくいきません. まずAの桁数が大きいので逆行列が求められないこと, 逆行列Aを求めるためにfloat型に変えると誤差が大きくなり正しいcoeffが求められないことから却下です2.
2.

solve.py
import sympy
from Crypto.Util.number import long_to_bytes

output = [(5100090496682565208825623434336918311864447624450952089752237720911276820495717484390023008022927770468262348522176083674815520433075299744011857887705787, ... , 340685435384242111115333109687836854530859658515630412783515558593040637299676541210584027783029893125205091269452871160681117842281189602329407745329377925190556698633612278160369887385384944667644544397208574141409261779557109115742154052888418348808295172970976981851274238712282570481976858098814974211286989340942877781878912310809143844879640698027153722820609760752132963102408740130995110184113587954553302086618746425020532522148193032252721003579780125)]

party = [output[0][0], output[1][0], output[2][0]]
val = [output[0][1], output[1][1], output[2][1]]

a = sympy.Symbol('a')
b = sympy.Symbol('b')
c = sympy.Symbol('c')

expr1 = a + b * party[0] + c * party[0] ** 2 - val[0]
expr2 = a + b * party[1] + c * party[1] ** 2 - val[1]
expr3 = a + b * party[2] + c * party[2] ** 2 - val[2]

# 連立方程式を解く
coeff = sympy.solve([expr1, expr2, expr3])
long_to_bytes(coeff[a])

ctf4b{just_d0ing_sh4mir}

(補足)
$a \equiv val[i]\ \ ({\rm mod} \ party[i])$
であり, 今回は$i$の値によらず($val[i] ％ party[i]$)が常に等しいことを利用する方が早いことがCTF終了後に判明しました.

Go RSA(Crypto, 363pt)

Nだけなくしちゃったんだよなあ……。
Server: nc 133.242.17.175 13373

これが一番苦労しました. サーバに接続すると

Encrypted flag is: 1356187131825092410532178098810309653546877503055158050100192 ... 25109536598850959441031793763901509670362951516988048967464004579550
>

と, 最初に暗号化されたflag(ここではcとします)が与えられ, 入力待ちになります.
ここに数字を入れると, それに応じて値が返ってきます(以下は2を入力した時の様子). ・・・($\ast$)

> 2
1042130814803018989082865713925741128982648540635795437008159 ... 77230601459890284518067096715909368255724895344251422199966973323724
>

この入力を3回行うか, 数字以外の文字列を打ち込むと

The D was 1279998533837526024369176016819029077688633648993166965790108 ... 44888246730427191986954552201107983661920994674819228907268622499841

と, RSAに必要な秘密鍵dが表示され終了します.

サーバに接続するたびにcやd, 2を入力した結果なども全て変わります. 唯一, 1を入力すると1が, 0を入力すると0が常に返ってきます.

  1. まず, ($\ast$)に気づかず文字列ばかり打ち込んでいたので, 異なる(c, d)の組から公開鍵Nを見つける問題だと思っていました.

  2. そもそもNが分からない問題がほとんどないので過去の類題を見つけることは不可能に近いです. ここまでで大半の時間を浪費してます.

  3. ($\ast$)に気付いてからは, 入力する数字と返ってくる結果が何を意味するのかが分かりませんでした.

  4. $d_i$を入力して, $m_i \equiv c^{d_i}$ (mod $N$)なる$m_i$を返しているとすると

    wrong.py
    import math

kN = math.gcd(pow(c, d1) - m1, pow(c, d2) - m2)

    で与えられるkNが$N$の倍数になるのですが, kN = 1となったのでこれも違います.

  5. そもそも1を入力すると必ず1が返ってくる事に整合性を持たせるには
    ・$m_i$を入力して$m_i^e$ (mod $N$)を返す
    ・$c_i$を入力して$c_i^d$ (mod $N$)を返す
    と考えるのが最有力となります(違っていれば0と1だけ例外処理をしていると考えるべきでしょう). 実はどちらで考えてもFlagを導く上では関係ないので, ここでは$x_i$を入力して$y_i \equiv x_i^a$ (mod $N$)なる$y_i$を返すとします.

  6. $a$が分からないので, ランダムな$x_1, x_2$を入力しても意味がありません. 例えば$x_1 = 2, x_2 = 4$を入力して
    $$y^2_1 \equiv (x^a_1)^2 = x^a_2 \equiv y_2 \ ({\rm mod} \ N)$$
    を用いる事で$a$に依存する事なく$y_1, y_2$から$N$に関する条件が得られます.

(結論)
・3回の入力($x_1 = 2, x_2 = 4, x_3 = 16$)とその出力($y_1, y_2, y_3$)に対して
$y_1^2 \equiv y_2$ (mod $N$)
$y_2^2 \equiv y_3$ (mod $N$)
なので$N$は$GCD(y_1^2 - y_2, y_2^2 - y_3)$の約数

solve.py
import math
from Crypto.Util.number import long_to_bytes

c = 13561871318250924105321780988103096535468775030551580501001921763773962589868796292401544079000808475039029539038545636086459800957076719588969056193255263054579818311834950526874604446363718638886916701457196699914484388159192328394379702125155654051928853016605337233542327947890424596610567462342945703117089234999836442665854316317826836766411137075529335443084083872511977849887763858695095669928937080208840324934558662583335785727638210815461682460662525528665736690270451118699545276652363026653507205939532487629992014805602912757765765424925109536598850959441031793763901509670362951516988048967464004579550
d = 13786734611251467071801810009490751039410243166768940711096284510077859160373409092792522044559173132218255384521100100142722799088047373187343505877272235941355141162208165160611021414450328596137815921894356694104309768114839441735765579918382910465971322992774945114857761326467030344646921646503941990134186212678267993062676291914755164235407043148034799429745863010392514957511396235050929079401095177287525518390188546781975319503313483764141316224251777657269796208925476218182044527455296085325230404755722996039579779568056826966624849862947520873879404581700804303220256129286810406949579200586354100910689

# x1 = 2
# x2 = 4
# x3 = 16
# y1〜y3は接続するたびに変わる
y1 = 10421308148030189890828657139257411289826485406357954370081590173438628585683831899469112628792021639600885445384769183688314819425926574693843223592233666860978876635263057477654033703960939058244402959913210865358188797538714879461471526339060461192883107925515965602950689664136183673020786355197801272508198299828810025205383456725064398895913575455346679005117163526501719330727752130458204258768217197494169551758047807399809601479721861131023608291418893318433935642290168846835181963080438338425232807691840247161611151666994025555978880796277230601459890284518067096715909368255724895344251422199966973323724
y2 = 6303723137309354918734657928492058124649612290000834685052434809326977365985580227035803211272042170487206089685815547017754464260952285321382141854628407631052054328168035840313104872519532481003577254227185335978683990165544802567010363022777639356121169034116380279279329660693145615367657335779269888538681026832552466996552326215077727287651680669475718864319271551429926537219277233237855542520843173625360285964196489573808131565550530891398876565266066066112193834903275399886024250595633575391327102375725397610827538266292775850172410671412296858400743330836971934750053336621496704544498466555429464085240
y3 = 17909044890314241404229979841732627259954681663264786405577601655564682297497863377219252522247594915515339941511786306465500496023082745502700326190513389855086951992226268900717219155748057168046839161795321552415086711365758663857714195638387450858677210567512209244426539578007672729535683631918440903806559837518387712889665512148237778097944420180629381822545394107005957576061721300156347880427848347392042454497412974917760431617827934024174568337127263615168774892015602169581898974057378567509453485489713203381031380820669275498615716144571632643399017717654555381508249822414609922801429127345824473534378

kN = math.gcd(pow(y1,2) - y2, pow(y2,2) - y3)

# (続く)

当然$N$は$y_1, y_2, y_3$よりも大きいので, kNをkで割った結果が$max(y_1,y_2,y_3)$より小さくなることはありません.

solve.py
# (続き)
k = 1
y_max = max(y1,y2,y3)
while kN // k >= y_max:
    N = kN // k
    # Nが求まれば後はcを復号するだけ
    print(long_to_bytes(pow(c, d, N)))
    k += 1

ctf4b{f1nd_7he_p4ramet3rs}

(補足)
正規のやり方は, -1を代入するとN-1を返してくることから$N$を求めるらしいです.
なお, GitHubにはsocketを使っていつ接続してもflagが出るような解答も書いています.

Bit Flip(Crypto, 393pt)

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

bitflip.py
N = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
e = 3

# FLAGを2進表記した時, その下位bit25%のいずれかを反転させる.
# 例えば2進表記して128bitであれば下位1〜32bitのいずれか
r = 1 << random.randrange(0, FLAG.bit_length() // 4)
C = pow(FLAG ^ r, e, N)

サーバに接続すると, Cだけ送られてきて接続が終了します.

  1. まずeが小さいのでCの立方根を取る事で復号できるかもしれない, ということを頭の片隅に置いておきます(1番難しいのでおそらく違うと思いつつ).

  2. ランダム要素が上のコードの$r$の部分, それも(FLAGが100bitなら25パターンしかないことからも分かるように)何百万ものバリエーションがあるとは思えません. まずはFLAGのbit数を大体把握しておきます.

    test.py
    from socket import *

ls = []
# 試しに800回接続してみる
for i in range(800):
    s = socket(AF_INET, SOCK_STREAM)
    s.connect(("133.242.17.175", 31337))
    # C(10進数)の先頭40文字で比較
    a = s.recv(40)
    if a not in ls:
        ls.append(a)
len(ls)

  3. 結果は239でした. 多少数え漏れがあると思いますが, 800回の試行で239のパターンしか得られなかったと考えると, 信頼しても良さそうです.
    つまり, 最低でもFLAGは956bitはある事になります.

  4. FLAGに単一の操作を加えたものを暗号化する, という問題は過去に類題が出ています(こちらはFLAG末尾にpaddingをつけるものでした).
    類題の方はCが1つであるということ, brute-forceしても高々$2^{16}$回の検索であるという特殊な条件であったので, 残念ながらうまくいきません.

  5. 反転するbitの候補は沢山あるといえども, 最低でも上位bit75%は一致しているわけです. なのでRSA暗号運用でやってはいけないnのことその11でわかるように, Franklin-Reiter Related Message AttackというのをまずはGoogleで調べてみます.

  6. こちらに行き着きました. 真ん中の方にSageMathを用いたコードがあるのでそのまま利用させてもらいましょう.

なお, SageMathがインストールされていない場合, SageMathCellを用いると良いでしょう. ただし, あまりoutputに時間がかかると表示してくれない(目安として1分くらい？)ので, あまり時間がかからないコーディングにしましょう.

pseudo_solve.sage
def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+y)^e - c2
    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)
    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()
    kbits = n.nbits()//(2*e*e)
    # 注意(後述)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]
    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]


n = 8221215460857625490009622648311381071797446467763746917215162437007687444517 ... 5331
e = 3

# 暗号化テキスト
c1 = ...
c2 = ...

# diff = m2 - m1
diff = short_pad_attack(c1, c2, e, n)

m1 = related_message_attack(c1, c2, diff, e, n)
print m1
print m1 + diff

さて, 2回サーバに接続して得られた数字をc1, c2に代入して実行してみましょう.
うまくいくなら問題ありませんが, 場合によっては
IndexError: list index out of range
と表示される場合があります. 上の擬似コードの# 注意と記した箇所です. この場合うまく復号できていないので違う組で試す必要があります.

(結論)
・サーバに接続してCを何パターンか取得する.
・Cのリストから任意に2つとりc1, c2に代入する. その際うまく例外処理も施しておく.
・SageaMathCellで行う場合はサーバに接続する回数が大きすぎるとタイムアウトして結果が表示されない事にも注意.

solve.sage
# Sageで実行

from socket import *

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+y)^e - c2
    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)
    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()
    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]
    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2
    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()
    return -gcd(g1, g2)[0]

n = 82212154608576254900096226483113810717974464677637469172151624370076874445177909757467220517368961706061745548693538272183076941444005809369433342423449908965735182462388415108238954782902658438063972198394192220357503336925109727386083951661191494159560430569334665763264352163167121773914831172831824145331
e = 3

ls = []
# 20回接続してCのリストを生成
# ここは〜30くらいまでなら動くと思われる
# 239個もの結果は必要ないし時間がかかる
for i in range(20):   
    s = socket(AF_INET, SOCK_STREAM)
    s.connect(("133.242.17.175", 31337))
    # Cは約309桁だが冗長性を持たせて400文字取得
    a = s.recv(400)
    # 最後の改行を取り除きint型に変換
    a = int(a[:-1])
    if a not in ls:
        ls.append(a)

for i in range(len(ls)-1):
    for j in range(i+1, len(ls)):
        c1 = ls[i]
        c2 = ls[j]
        # 例外処理
        try:
            diff = short_pad_attack(c1, c2, e, n)
        except:
            pass
        else:
            m1 = related_message_attack(c1, c2, diff, e, n)
            print "m1 = %d" % m1
            print "m2 = %d" % (m1 + diff)

後は得られたm1やm2の中から1つを選んでデコードすれば良いでしょう.

solve.py
# こちらはPython3

from Crypto.Util.number import long_to_bytes

m1 = 16260765149986038884145173876068642724013617302097779293079362876653494069932815072038851668676222848467504538570853507159925860036819304291732134150397319327193122637750054910716746167965635612837962028769149915298230040116567157454495798898178036434538204980608594381468821524975316356795783256330
long_to_bytes(a)

ctf4b{b1tfl1pp1ng_1s_r3lated_m3ss4ge}

終わりに

長くなってしまい申し訳ありません.
miscの3問目や, 問題だけダウンロードしていたrevの最初2問も気が向いたら解説します.

  1. mac OSのテキストエディタの仕様かもしれません. ↩

  2. coeff[1] = coeff[2] = 0となってしまいました. ↩

  3. サーバが閉じてしまっていたらごめんなさい. 必要な情報は与えます. ↩

2
4
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
4