WPICTF 2020 Writeup

この大会は2020/4/18 6:00(JST)～2020/4/20 6:00(JST)に開催されました。
今回もチームで参戦。結果は1676点で905チーム中40位でした。
自分で解けた問題をWriteupとして書いておきます。

Can you Read? (misc 1)

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

WPI{Yes_I_c4N_R3ad}

Suckmore Shell 2.0 (linux 200)

$ ssh smsh@smsh.wpictf.xyz
The authenticity of host 'smsh.wpictf.xyz (172.105.150.220)' can't be established.
ED25519 key fingerprint is SHA256:GqFuIm5erH/zteuldHoJPiNP6ZI1MHeUa2LL8H1BU7U.
Are you sure you want to continue connecting (yes/no)? yes
Warning: Permanently added 'smsh.wpictf.xyz,172.105.150.220' (ED25519) to the list of known hosts.
Password:
> ls -la
total 24
drwx------ 1 ctf  ctf  4096 Apr 14 01:56 .
drwxr-xr-x 1 root root 4096 Apr 14 01:55 ..
-rw-r--r-- 1 ctf  ctf    21 Feb 13 19:41 .bash_logout
-rw-r--r-- 1 ctf  ctf    57 Feb 13 19:41 .bash_profile
-rw-r--r-- 1 ctf  ctf   141 Feb 13 19:41 .bashrc
-r--r--r-- 1 ctf  ctf    48 Apr 14 01:56 flag
> cat flag
>

tacコマンドやheadコマンドなど、いろいろコマンドを実行したけどうまくいかない。調べたらfoldというコマンドがあったので、試してみる。

> fold -w 48 flag
echo "WPI{SUckmoreSoftwareN33dz2G3TitTogeTHER}"

WPI{SUckmoreSoftwareN33dz2G3TitTogeTHER}

Illuminati Confirmed (crypto 250)

同じメッセージの暗号化で、n, cが3つずつわかっている。Hastad's broadcast attackで復号する。その際復号した数値をそのまま文字列にしても可読文字にならない。数値を眺めていたら、3つずつの数値にしてASCIIコードとして文字になると推測できた。最終的なコードは以下の通り。

import functools

def chinese_remainder(n, a):
    sum = 0
    prod = functools.reduce(lambda a, b: a*b, n)
    for n_i, a_i in zip(n, a):
        p = prod // n_i
        sum += a_i * mul_inv(p, n_i) * p
    return sum % prod
 
def mul_inv(a, b):
    b0 = b
    x0, x1 = 0, 1
    if b == 1: return 1
    while a > 1:
        q = a // b
        a, b = b, a%b
        x0, x1 = x1 - q * x0, x0
    if x1 < 0: x1 += b0
    return x1

def inv_pow(c, e):
    low = -1
    high = c+1
    while low + 1 < high:
        m = (low + high) // 2
        p = pow(m, e)
        if p < c:
            low = m
        else:
            high = m
    m = high
    assert pow(m, e) == c
    return m

c1 = 515274042976912179894435774656907420040599503456517078488056218986662017260212389975972477279505310799399071383390618892499008790928347543017765027618590150794317674792875250152206518326158674718404382617692169589911938548819188733852354294583496715425255584973283840789780326402769751705164900106921523637157271605500111846563844641773661723255718653040958019618435501230171699432186518803652675691180548548982155426472648502704469425298466513665043628724497448475714424482446137414939511691724839553567514050622159418495196773388690852258256550787962177196383253952227153557220272199293397879908308572668952866439
c2 = 10512934566887371506285681495672139256544177416158977932082410009242386741198073874632763611137937701329570263046854521709347241390006612379393018933295475369159148328248445221357906382527678877429535168220389698475391828837227453358681276167720605617228338487308750653165147019400915842904872988789759529121710032871148507314874152494680057046977274373381326003405301191489108322498519602528688873942243307708631394538177629868515911161222795303220989599519719169300455717641863368473309673489958952173445661451265442004625237606054046962062434813126456494957846077185121041599277143211160596207640833275850170891378
c3 = 4122591425712279559823043898131225014447235394996958162806737555257607173149332839353292933732548212376056402900761362427837044396517072345683265668973735260384169928448531246071624967168190024583028639591981238222340513125989229227761894026521238496145716707176637113415430809586007230597253976748507442809040629281971868442704017013258355403718545489677897799000961350863824810217217745918503635905775610161826572608564207497464646323778407843991683950506484189720225535503643332574132841288909783555334280205740975729691459011043954137669831817945210956835398278009161994675851980163314376477384045294293755909874
n1 = 21939147590581954242131893557689750173730181114330873782062274456630281986233643990882568426690149971468987847436717513764939861105600249325682418749886588739440853385485272501856860578476795830603738468829294920737586209822299603185425324611481798231193950636987017718955070420091525231666894903436050998112803225822333684113551754209802262129292376015861410644289380376439390552627189657966103965089679163295591136464541998227543058082734503570960156783196006833967361311083486266118899788620317372054292861892020849652213277431575285275801196626852675579752895079650118836892859390462805733596279690076656763624249
n2 = 26325215018784165663958487526715385161171636566916698114816183716597566424675870012796860473421390775180027083457908584461525282815469520282303059318923930531826588673345113634118988713179894971211405380241575065877886390347877768297280022387015195069836149198306647472534681286406136303674462323742151285361538383784282113898065157278366533587767199303585208673225974716800760227497569577072903884939422787710986913747191378087554442395968729847569180921093186599977266346501947184849099856506537976370069200813758143237937721729073822639191799709052936074831322440705620902220824412476988222346922869104007199777561
n3 = 23013589835547680503802140462487647716102548445081685245087901486321520435018899614072711065158868927754813316329675676910885474767916372370942795565358071859270832973837949423193707764788999822539648518439967218163608118921979697363190728350735745938069012584523314223346479156208977445194408267152808800890485882602068876756801123087623323707553203656108124651989136578687688847505350883163751096338640206246619001851586459510648241545637475283654557530338836698680934504086346810521919864048046078444168117563048636886066060497385368685340990757248020960409380316695810483273153565980791846594355984630591111120973
e = 3
 
N = [n1, n2, n3]
C = [c1, c2, c3]
a = chinese_remainder(N, C)
for n, c in zip(N, C):
    assert a % n == c
m = inv_pow(a, e)
msg_enc = str(m)

msg = ''
for i in range(0, len(msg_enc), 3):
    msg += chr(int(msg_enc[i:i+3]))

print msg

実行結果は以下の通り。

hello,Thenextmeetingisat100InstituteRdonWednesdayMay13,2020.5pm.DontbelateWPI{Ch1n3s3_R3M@ind3R_Th30r3m_!_}.

WPI{Ch1n3s3_R3M@ind3R_Th30r3m_!_}