チームm1z0r3として参加(傍観)しました。開催時ちょうど出先だったので、まともに参加できず、warm-up以外はただ眺めて方針を言っただけでした。。。
帰ってからちゃんとcrypro全問とmisc一問解きました。

解けた問題

解けた問題

[warmup] So Tired[Crypto,115pts]

ちょうど電車の中なので、テザリングで問題を解いてた。

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

とやけに長い暗号文が与えられました。最後の方で5+K5v4B8HzgzA==が見えたので、とりあえずbas64でデコードしてみた。
結果をファイルに書き出しfileコマンドで見るとzlibデータということが判明。
zlib.decopress()にかましたら、またbase64っぽいやつになった。
試行錯誤の末、この二つの繰り返しだと踏んでsolverを書いて一発でflagが出ました。
↓はそのsolverです

# coding: utf-8
for i in range(100):
    print i
    dd = base64.b64decode(ct)
    if 'ctf4b' in dd:
        print dd 
        break
    dd = zlib.decompress(dd)
    if 'ctf4b' in dd:
        print dd
        break
    
    
for i in range(1000):
    print i
    dd = base64.b64decode(dd)
    if 'ctf4b' in dd:
        print dd 
        break
    dd = zlib.decompress(dd)
    if 'ctf4b' in dd:
        print dd
        break

flagctf4b{very_l0ng_l0ng_BASE64_3nc0ding}

Party[Crypto,223pts]

Let's 暗号パーティ

あと暗号化用スクリプトと暗号文が渡されました。

#暗号化スクリプト  
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)

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

単純な多項式方程式の計算でした

$$a+bx+cx^2$$

のような式が三つがありました
よって連立してsympy使って解いた。

# solver.py
import sympy
from Crypto.Util.number import long_to_bytes
exec(open('encrypted').read().strip())
a,b,c = sympy.symbols('a b c')
expr = []

for x,y in z:
    tmp = a + b*x + c*x**2-y
    expr.append(tmp)

r = sympy.solve(expr,[a,b,c])
print long_to_bytes(r[a])

flag ctf4b{just_d0ing_sh4mir}

Go RSA[Crypto,363pts]

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

問題文通りnetcatしてみたら
1. enc(flag)がくれる
2. 送りつける平文を暗号化してくれる* 3
3. 秘密鍵d
まぁ、Nがないわけですね。
最初2,3,5を送ってgcdでnを求めようと思ったが、上手くいけず
試しに-1を送ってみたらまさか通った、
eは奇数のため

$$ (-1)^e modn = -1 modn = c1 $$

Nはこれで入手できたので、あとは複合するだけです。

from gmpy import gcd,mpz
from Crypto.Util.number import long_to_bytes
from pwn import *
while True:
    ip,port = "133.242.17.175",1337
    io = remote(ip,port)
    c = io.recvline()
    c = eval(c[19:])
    io.recvuntil('> ')
    io.sendline('-1')
    c2 = eval(io.recvline().strip())
    print c2
    io.recvuntil('> ')
    io.sendline('3')
    c3 = eval(io.recvline().strip())
    io.recvuntil('> ')
    io.sendline('5')
    c5 = eval(io.recvline().strip())
    d = io.recvline()
    d = eval(d[10:])
    
    

    n = c2+1
    print n
    m = pow(c,d,n)
    print long_to_bytes(m)
    if 'ctf4b' in long_to_bytes(m):
        print long_to_bytes(m)
        break
    else:
        continue

flag ctf4b{f1nd_7he_p4ramet3rs}

Bit Flip[Crypro,396pts]

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

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)

早々にcoppersmithのFranklin-Reiter Related Message Attackと気づいて、メンバーに言ったらすぐ解いてくれたが、自分が解く時結構苦戦しました。

inaz2.hatenablog.com

ももいろさんのコードをそのままやればできるはずだが、なぜか自分は最初diffの部分をbruteforceしようと思った。

from Crypto.Util.number import long_to_bytes
#exec(open('frank').read())
ct = [33460967930651042564008329494837980959989903859210697421802306279164621522687556814718235426111472547179095329371506382390014453846091397832498600503239318321010755518869476348035475014069822783161625493689769776352756995160846240078842031192708266413703448094909589244233878164639106160103912289438284532951,
35767470795467826626462219405218933905532798348984975613284120383492541445125994872372814500011529932489701983142275580480838210299890062839431655315781938554677350092881704540017377748405584214318021791801390834437575079426825881380116885654989459718950805516298665349023074086528990085624070703653325590626,
2564767480510465230025376237485323465247347695767670175449224103561779300575591945349037051568803129039497886094466895116814508667226331922270653397257175611435834481444137923198078723295284476543076934928703086503949903527333767882768961960752424916858651191341982753280463984103242342990373600472836273483,
48435977819599167293699473693205310917010250721248336492061287216379692891690691913767776069993911112239078185069288585022377993407270013401637539048567366526297730605589951913845745872046158333042631889854531385928428660788578942630939788805433004268454651608813773788184844655098499352542867632893087089862,
70243886202594041384149567279846398108812572645105073366462606332641138118730202337380722533868511370427257637609073439393551732783916350915670572090839624554072402040626243669086780305822849504543665527511573152185251528039856817426643797216433781977178180000264280600433349179693943419348506755320080926694,
56073186874991156857455984286684500442906235298857187632607776454964999796759688131079504400025542651062833165579892099321785638532878398946777427851711272910781669617329188445433612821472292131082921802664259975670362919592393670596478369004299401092384846933003092047569839327675819547737050008092855586836,
76973946533903301664341043538088060381425103867343158161579223936021109952721928226649404602045450132057340858205331299178226892039280164374466121273289679601927740750394666755935423240638326819231534726682109186304705616758011069263053347795504543107507654422375687528839427587126700855441423639423394856915,
49654154495482283465834374278541758019608540780454081817664398472317688626329722856959095884025794014552636483510868510209039491680134524145557941720491231286814385904119640028052534147728739758655222825827641976571227089805222280335420420592070351022229307985817960062100669012614681238209307730930907097822,
43127534228950588003064862597617662349110503750643598403895078065209780109199580967321519663285345035915141004019522531717660071908459330437728550039841396677044821855383201329486465004296535288616321397257850646054096663686972817521272024268602548417965146689582261300067924995202141674341056643542839881709,
57689275579576395277674386946337672158924398165151862094706053940830821532864260543417237811918166807469715046584334237149250584727692745234746142171573175423785721026709593407664046881589413366706252864920052167228324308547218195967450249948207887341536607780400807107730207032926117718549982543342765633452,
52359266544766452482523975685608230407291002763343708814586323783536687163032519294172952791019189972735544414177241032748822987128020591624518112210653204778035127348730617786610234768247540041763186245947296196728495533871800544502941653267136708893036674478754400011664069241697039722736589615301087984767,
38844834597621755927122817069901146449872652071559225576929653719687546171913834706512962460338554916524680815254372597395506874917236317267396410010981378138718936802206799767435370326551257259787965495758168188779021198496511984668695738922224971732694952548129382773592529943971677475172616574617049917266,
65629968065768428556355481091340719361116741954090679498200327504380027400680764581274354973606760186939105604187865883111048765492587922739179675879975061207040589702673604068461675060948522167495142009134118186484638258930209624450387799273925135732923965394541431779018125927937023326149589446756683291575,
42931548833801764667442686792357953483640108421931662235100823765650887206728669527853083362065574312034401943127260307486662029021664321290485915120573764222508091524383596332156757300055325893277712136182289687677900418079735270414024337891273172139106857868598826210870661754777950107969285904122398033903]

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]  # find root < 2^kbits with factor >= n^0.5

    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

for i in range(len(ct)):
    for j in range(len(ct)-1):
        ct1 = ct[i]
        ct2 = ct[j+1]
        try:
            diff = short_pad_attack(ct1,ct2,3,N)
        except:
            continue
        m = related_message_attack(ct1,ct2,diff,3,N)
        if 'ctf4b' in long_to_bytes(m):
            print long_to_bytes(m)
            break

flag ctf4b{b1tfl1pp1ng_1s_r3lated_m3ss4ge}

Sliding Puzzle[Misc,206pts]

帰りの新幹線で解いてみました、
競技はとっくに終わったが、
一応気になった問題なので、取り込みました。

----------------
|  0 |  2 |  3 |
|  6 |  7 |  1  |
|  8 |  4 |  5 |
----------------

↑のようなpuzzleから0だけ動かして、
数字の昇順に並べ換えらせるまでの手順を遅れれば良い。なんとなく深さ優先探索(合ってる?)でできそうなので、
競プロの人は普通に解けると思います。
競プロできない自分は他の方の実装を弄って終わった。

github.com

from m1z0r3 import *
from pwn import *
...略...
   #Prints the solutions if the prnt = True
    if prnt == True:
        print solutions
        old_tmp = [flatten for inner in eval(solutions[1]) for flatten in inner]
        old_idx = old_tmp.index(0)
       
        for i in solutions[2:]:
            tmp = [flatten for inner in eval(i) for flatten in inner]
            idx = tmp.index(0)
            diff = idx - old_idx
            if diff == 3:
                ss.append('2')
            elif diff == -3:
                ss.append('0')
            elif diff == 1:
                ss.append('1')
            elif diff == -1 :
                ss.append('3')
            t = PuzzleNode(n, eval(i))
            t.__str__(i)
            print "The next step is :"
            old_idx = idx

    return ss
   #return "The frontier size, number of steps and error code are :" , steps, frontierSize, err,


ip,port = '133.242.50.201',24912
#s,f = sock(ip,port)
io = remote(ip,port)
#print recv_line(f)
n = 0
while True:
    print n
    priv = io.recvline()
    if '----------------' not in priv:
        print priv
        break 
    puzzle = []
    for _ in range(3):
        t = []
        tmp = io.recvline().strip().replace(' | ',',').replace('|','',1).replace('|','')
        for i in tmp.split(','):
            t.append(int(i))
        puzzle.append(t)
    print io.recvline()
    print io.recvline()
    print puzzle
        
    #test =  [[0,2,3],[6,7,1],[8,4,5]]
    #print solvePuzzle(3,test,heuristics[1],True)
    r = solvePuzzle(3, puzzle, heuristics[2], True)
    print r
    r = ','.join(r)
    print r
    io.sendline(r)
    n += 1
print io.recvline()

flag ctf4b{fe6f512c15daf77a2f93b6a5771af2f723422c72}

他の問題

気が向いたら

所感

去年より難しいと感じています、楽しかったです。

魚脳の池

CTF:Little Twoos

SECCON Beginners CTF 2019 write-up