Google Capture The Flag 2017 (Quals) 参戦

この大会は2017/6/17 9:00(JST)～2017/6/19 9:00(JST)に開催されました。
今回もチームで参戦。結果は1002点で1977チーム中47位でした。
自分が得点した問題は1問も無く、本当に残念！

SHA2017 CTF Teaser round Writeup

この大会は2017/6/10 21:00(JST)～2017/6/11 5:00(JST)に開催されました。
今回もチームで参戦。結果は650点で462チーム中7位でした。
自分で解けた問題をWriteupとして書いておきます。

Crypto Engine (Crypto 200)

いろいろ試して出力される色のRGBの組を確認する。まずは以下の点がわかる。

・3文字で一つのセルが生成される。
・3の倍数の文字でない場合は、3で割った余りの文字数分8ビットの16進数が表記されている。

このことからフラグの文字数は38文字であることがわかる。XORで算出された結果を色で表していると推測しながら、38文字でいろいろ試す。

■abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLの場合
RGB: 83 82 82 83 54 52 53 59 95 94 94 87 50 48 49 39 67 66 66 83 54 52 53 43 79 78 116 105 12 10 49 47 75 66 120 101 | 0x00 0x0e
文字列とRGBのXOR:
[50, 48, 49, 55, 83, 82, 82, 83, 54, 52, 53, 59, 95, 94, 94, 87, 50, 48, 49, 39, 67, 66, 66, 83, 54, 52, 53, 43, 79, 78, 116, 105, 12, 10, 49, 47, 75, 66]

■ZUHadnaopwefvnsudhaaiTjaksUkladauULandの場合
RGB: 104 101 121 86 12 11 24 57 124 124 125 95 10 18 14 42 110 122 111 75 7 46 5 42 108 93 80 65 0 60 52 32 117 105 120 65 | 0x1b 0x0d
文字列とRGBのXOR:
[50, 48, 49, 55, 104, 101, 121, 86, 12, 11, 24, 57, 124, 124, 125, 95, 10, 18, 14, 42, 110, 122, 111, 75, 7, 46, 5, 42, 108, 93, 80, 65, 0, 60, 52, 32, 117, 105]

■YZabcdefghijklMNOPqrstuVWxyzhaAjadsKKKの場合
RGB: 107 106 80 85 8 14 53 51 111 102 92 89 4 10 17 23 75 90 96 101 56 46 21 51 111 86 108 73 7 55 45 35 102 83 94 104 | 0x2d 0x18
文字列とRGBのXOR:
[50, 48, 49, 55, 107, 106, 80, 85, 8, 14, 53, 51, 111, 102, 92, 89, 4, 10, 17, 23, 75, 90, 96, 101, 56, 46, 21, 51, 111, 86, 108, 73, 7, 55, 45, 35, 102, 83]

■ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklの場合
RGB: 115 114 114 115 54 52 53 59 127 126 126 119 50 48 49 39 99 98 98 115 54 52 53 43 111 110 84 73 12 10 49 47 107 98 88 69 | 0x00 0x0e
文字列とRGBのXOR:
[50, 48, 49, 55, 115, 114, 114, 115, 54, 52, 53, 59, 127, 126, 126, 119, 50, 48, 49, 39, 99, 98, 98, 115, 54, 52, 53, 43, 111, 110, 84, 73, 12, 10, 49, 47, 107, 98]

以上を見ていて以下のことに気が付いた。

・XORキーの最初の4バイトは固定：50, 48, 49, 55
・XORキーの5バイト以降はRGBの値を順に並べている。

このことから復号コードを書く。

from PIL import Image

img = Image.open('flag.png').convert('RGB')
w, h = img.size

key = [50, 48, 49, 55]
enc = []
for x in range(1, w, 40):
    r, g, b = img.getpixel((x, 1))
    key.append(r)
    key.append(g)
    key.append(b)
    enc.append(r)
    enc.append(g)
    enc.append(b)
del key[-2:]
enc.append(0x2e)
enc.append(0x29)

flag = ''
for i in range(len(enc)):
    flag += chr(key[i] ^ enc[i])

print flag

この結果フラグがゲットできた。

flag{deaf983eb34e485ce9d2aff0ae44f852}

Security Fest 2017 Writeup

この大会は2017/5/31 21:00(JST)～2017/6/2 1:00(JST)に開催されました。
今回もチームで参戦。結果は1460点で447チーム中14位でした。
自分で解けた問題をWriteupとして書いておきます。

#makeircgreatagain (Misc 10)

freenodeで#securityfest-ctfチャネルに入る。

21:01 *topic : DL server problems, WORKING ON IT! https://securityfest.ctf.rocks - SCTF{Welcome_to_SECURITYFEST_CTF_2017!} -  start: https://goo.gl/L9Ltwj

SCTF{Welcome_to_SECURITYFEST_CTF_2017!}

Empty (Misc 100)

何も書かれていない空のPDFファイルが与えられている。

$ strings empty.pdf
     :
/LastChar 25
/Widths[/Widths[83 67 84 70 123 115 116 114 52 110 103 51 95 111 98 106 51 99 116 95 99 104 114 95 49 110 95 112 108 52 49 110 95 115 49 116 51 125]
/FontDescriptor 12 0 R
     :

Widthsの値がASCIIコードの羅列に見える。文字に置き換えてみる。

codes_str = '83 67 84 70 123 115 116 114 52 110 103 51 95 111 98 106 51 99 116 95 99 104 114 95 49 110 95 112 108 52 49 110 95 115 49 116 51 125'
codes = codes_str.split(' ')

flag = ''
for code in codes:
    flag += chr(int(code))

print flag

フラグの文字列だった。

SCTF{str4ng3_obj3ct_chr_1n_pl41n_s1t3}

Qr code madness (Misc 200)

QRコードの画像が複数ある。1つの画像で1文字を読め、なんとなくBase64の文字種別になっていることがわかる。
あとはどの順番で読むかを考える。更新日付順で最後に読めたのが「=」になっていることがわかったので、その順で並び替えればよそさう。
まずはタイムスタンプをファイル名にして、QRコードをテキストにする。

import os
import time
import datetime
from PIL import Image

BLACK = 'X'
WHITE = ' '
UNKNOWN = '?'

quiet_zone_size = 12
cell_size = 3

QR_DIR = 'qrcodemadness\\'
TXT_DIR = 'qrtext\\'

files = os.listdir(QR_DIR)
for file in files:
    img = Image.open(QR_DIR + file)
    width, height = img.size

    pixels = img.load()
    output = ""
    y = quiet_zone_size + 1

    qrtxt = ''
    while y < height - quiet_zone_size:
        x = quiet_zone_size + 1
        while x < width - quiet_zone_size:
            if pixels[x, y] == 0:
                qrtxt += BLACK
            else:
                qrtxt += WHITE
            x += cell_size
        qrtxt += '\n'
        y += cell_size

    utime = datetime.datetime.fromtimestamp(os.stat(QR_DIR + file).st_mtime)
    o_filename = TXT_DIR + str(int(time.mktime(utime.timetuple()))) + '.txt'
    with open(o_filename, 'w') as f:
        f.write(qrtxt)

次にQRコードを読み取り、最初の1文字を除いて、Base64デコードする。

import os
import subprocess

TXT_DIR = 'qrtext\\'
CMD_FORMAT = 'python sqrd.py qrtext\\%s'

files = os.listdir(TXT_DIR)

b64str = ''
for file in files:
    cmd = CMD_FORMAT % file
    ret = subprocess.check_output( cmd.split(" ") )
    ret = ret.replace('\r\n', '')
    ret = ret.replace('\r', '')
    ret = ret.replace('\n', '')
    b64str += ret

print b64str[1:].decode('base64')

SCTF{Th3s3_d4mn_QR_c0d3_k33p_p0p1ng_up}

I heart cats (Misc 50)

空白やタブが目立つHTMLが与えられている。
空白8バイトを0、タブを1として、2進数のコードにして読込む。

with open('index.html', 'r') as f:
    data = f.read()

data = data.replace('        ', ' ')

bin_code = ''
for i in range(len(data)):
    if data[i] == ' ':
        bin_code += '0'
    elif data[i] == '\t':
        bin_code += '1'

flag = ''
for i in range(0, len(bin_code), 8):
    flag += chr(int(bin_code[i:i+8], 2))

print flag

SCTF{Wh1735p4c35_4r3_84d_4u!}

Fair play! (Crypto 50)

問題のタイトルからもPlayfair暗号と推測。オンラインのツールなどで復号してみたが、うまくいかない。CryptoCrackを使って、ブルートフォースで復号する。
この結果、キーはCOKBVQARNDXYEPWSHMZILFTGU。復号結果は以下の通り。

THEFLAGISTHENEXTFORTYONECHARACTERSPLAYFAIRISAFUNCIPHERTOCRACKDONTYOUTHINKSOIHOPEYOUENIOYEDTHECHALXLENGESPORTSMANSHIPISANASPIRATIONORETHOSTHATASPORTORACTIVITYWILLBEXENIOYEDFORITSOWNSAKEWITHPROPERCONSIDERATIONFORFAIRNESXSETHICSRESPECTANDASENSEOFXFELXLOWSHIPWITHONESCOMPETITORSASORELOSERREFERSTOONEWHODOESNOTXTAKEDEFEATWELXLWHEREASAGOXODSPORTMEANSBEINGAGOODWINXNERASWELLASBEINGAGOXODLOSERSOMEONEWHOSHOWSCOURTESYTOWARDSANOTHERINASPORTSGAMESPORTSMANSHIPCANBECONCEPTUALIZEDASANENDURINGANDRELATIVELYSTABLECHARACTERISTICORDISPOSITIONSUCHTHATINDIVIDUALSDIFXFERINTHEWAYTHEYAREGENERALXLYEXPECTEDTOBEHAVEINSPORTSITUATIONSINGENERALSPORTSMANSHIPREFERSTOVIRTUESSUCHASFAIRNESXSXSELFCONTROLCOURAGEANDPERSISTENCEANDHASBEENASSOCIATEDWITHINTERPERSONALCONCEPTSOFTREATINGOTHERSANDBEINGTREATEDFAIRLYMAINTAININGSELFCONTROLIFDEALINGWITHOTHERSANDRESPECTFORBOTHAUTHORITYANDOPPONENTSXSPORTSMANSHIPISALSOLOXOKEDATASBEINGTHEWAYONEREACTSTOASPORTGAMEPLAYERTHEFOURELEMENTSOFSPORTSMANSHIPAREOFTENSHOWNBEINGGOODFORMTHEWILLTOWINEQUITYANDFAIRNESSALXLFOURELEMENTSARECRITICALANDABALANCEMUSTBEFOUNDAMONGALXLFOURFORTRUESPORTSMANSHIPTOBEILXLUSTRATEDTHESEELEMENTSMAYALSOCAUSECONFLICTASAPERSONMAYDESIRETOWINMORETHANPLAYINEQUITYANDFAIRNESXSANDTHUSRESULTINGINACLASHWITHINTHEASPECTSOFSPORTSMANSHIPTHISWILXLCAUSEPROBLEMSASTHEPERSONBELIEVESTHEYAREBEINGAGOODSPORTSMANBUTTHEYAREDEFEATINGTHEPURPOSEOFTHISIDEAASTHEYAREIGNORINGTWOKEYCOMPONENTSOFBEINGSPORTSMANLIKEWHENATHLETESBECOMETOXOSELFCENTREDTHEIDEAOFSPORTSMANSHIPISDISMISSEDTODAYSXSPORTINGCULTUREINPARTICULARTHEBASEOFELITESPORTPLACESGREATIMPORTANCEONTHEIDEAOFCOMPETITIONANDWINXNINGANDTHUSXSPORTSMANSHIPTAKESABACKSEATASARESULTINMOSTIFNOTALXLSPORTSXSPORTSMENATXTHEXELITELEVELMAKETHESTANDARDSONSPORTSMANSHIPANDNOMATXTERWHETHERTHEYLIKEITORNOTXTHEYARESEXENASLEADERSANDROLEMODELSINSOCIETYSINCEEVERYSPORTISRULEDRIVENTHEMOSTCOMMONOFXFENCEOFBADSPORTSMANSHIPISTHEACTOFCHEATINGORBREAKINGTHERULESTOGAINANUNFAIRADVANTAGEACOMPETITORWHOEXHIBITSPOORSPORTSMANSHIPAFTERLOSINGAGAMEORCONTESTISOFTENCALLEDASORELOSERTHOSEWHOSHOWPOXORSPORTSMANSHIPAFTERWINXNINGARETYPICALLYCALXLEDBADCHAMPSSORELOSERBEHAVIOURINCLUDESBLAMINGOTHERSFORTHELOSSNOTACCEPTINGRESPONSIBILITYFORPERSONALACTIONSTHATCONTRIBUTEDTOTHEDEFEATREACTINGTOTHELOSXSINANIMXMATUREORIMPROPERFASHIONMAKINGEXCUSESFORTHEDEFEATANDCITINGUNFAVOURABLECONDITIONSOROTHERPETXTYISSUESASREASONSFORTHEDEFEATABADWINNERACTSINASHALLOWFASHIONAFTERHISORHERVICTORYSUCHASBYGLOATINGABOUTHISORHERWINRUBXBINGTHEWININTHEFACESOFTHEOPXPONENTSANDLOWERINGTHEOPXPONENTSXSXSELFESTEEMBYCONSTANTLYREMINDINGTHEOPPONENTSOFPOXORPERFORMANCEINCOMPARISONEVENIFTHEOPPONENTSCOMPETEDWELLNOTSHOWINGRESPECTTOTHEOTHERTEAMISCONSIDEREDTOBEINGABADSPORTSMANANDCOULDLEADTODEMORALISINGEFFECTSASLESLIEHOWEDESCRIBESIFAPITCHERINBASEBALXLDECIDESTOPITCHNOTTOHISMAXIMUMABILITYSUGGESTTHATTHEBATTERISNOTATANADEQUATELEVELANDCOULDLEADTOTHEBATXTERTOHAVELOWSELFCONFIDENCEORWORTHTHEREARESIXDIFXFERENTCATEGORIESRELATINGTOSPORTSMANSHIPTHEELEMENTSOFSPORTSTHEXELEMENTSOFSPORTSMANSHIPCLARIFICATIONSCONFLICTSBALANCEANDIRREDUCIBILITYALLSIXOFTHESECHARACTERIZEAPERSONWITHGOODSPORTSMANSHIPEVENTHOUGHTHEREISSOMEAFFINITYBETWEXENSOMEOFTHECATEGORIESTHEYAREDISTINCTELEMENTSINESSENCEPLAYHASFORITSDIRECTEDANDIMXMEDIATEXENDIOYPLEASUREANDXDELIGHTSANDWHICHISDOMINATEDBYASPIRITOFMODERATIONANDGENEROSITYATHLETICSONTHEOTHERHANDISESSENTIALXLYACOMPETITIVEACTIVITYWHICHXHASFORITSENDVICTORYINTHECONTESTANDWHICHISCHARACTERIZEDOFDEDICATIONSACRIFICEANDINTENSITYFEXELEZZPPHENCETHEVIRTUESOFAPLAYERARERADICALXLYDIFXFERENTFROMTHEVIRTUESOFANATHLETEFEXELEZZPPWHENTALKINGABOUTMISUNDERSTANDINGSPORTSMANSHIPRUDXDANDSTOLLPROVIDEANEXAMPLEFROMAUSHIGHSCHOOLATHLETICLEAGUEBANXNEDTHEPOSTGAMEHANDSHAKETHATWASAPARTOFSPORTSXSUCHASFOOTBALXLANDBASKETBALXLTHEHANDSHAKINGWASBANXNEDBECAUSEOFFIGHTSTHATWEREENSUINGAFTERTHEHANDSHAKEPXPMOSTPLAYERSAREINFLUENCEDBYTHELEADERSAROUNDTHEMSUCHASCOACHESANDOLDERPLAYERSIFTHEREARECOACHESANDADMINISTRATORSWHODONTUNDERSTANDSPORTSMANSHIPTHENWHATABOUTTHEPLAYERS

スペースを入れて読みやすくすると、先頭部分にはこう書いてある。

THE FLAG IS THE NEXT FORTYONE CHARACTERS

次の41文字がフラグ。

PLAYFAIRISAFUNCIPHERTOCRACKDONTYOUTHINKSO

WhiteHat Contest 13 Writeup

この大会は2017/5/27 11:00(JST)～2017/5/28 11:00(JST)に開催されました。
今回もチームで参戦。結果は1800点で108チーム中8位でした。
自分で解けた問題をWriteupとして書いておきます。

Da Nang (Cryptography 200)

makefile.pycファイルとn, c1～c4の値が与えられている。
EasyPythonDecompilerでmakefile.pycをデコンパイルすると、以下のようなコードで暗号化していることがわかる。

# Embedded file name: /root/Desktop/ctf-2017/rade/makefile.py
from FLAG import *
from Crypto.Util.number import *
p = getPrime(1024)
q = getPrime(1024)
n = p * q
e1 = 17
e2 = 23
m1 = pow(flag, e1, n)
m2 = pow(flag, e2, n)
c1 = pow(m1 + 12345, e1, n)
c2 = pow(m1 + 56789, e1, n)
c3 = pow(m2 + 12345, e2, n)
c4 = pow(m2 + 56789, e2, n)

まず、Franklin-Reiter Related Message Attackでm1とm2を求める。

# related_message_attack.sage
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 = 23992456508721632904544057999056395984840598682551527471151904763246778638836805311058576074076544471814362118450963752614808101805018226501728749753154687251596663180454809994272928278066817153483685668132338944992849111855590973474678454159123639456555256485147196164078477717189520027988101925788303558976065942012105491523422884349644306896086216721825961334666043695121350988761613913914655313225263251356627080558127266206207253980892813908459449433940028268804981985006285644508736389967109173883994849116220035021283230523958640143355551140077459561176550844398278642511471910168765368624465988996082307992457
c1 = 20373828497176435167633953604896280749084861536083536617122139289929021045377176745113967394233342868062933415554192920963948057887324013008257380015103546511196207444982065505097904316167335975881412955740451727799394577357107415462104942067847048630173382510001061068806873459709567970640047451719077689284250663779574472232440594570502056709748603086893912068708152949459839465110567129133452824619222918019880393381073202052633467737917229789195417254877277542398992729106705037414050409175283815504552780234997208287185820010853470529752628470226853313501197054312938111140137899570545855875031148908922559079288
c2 = 4360293477491071631082413589399984151934700148049881396354060511784164719699104502640364063839372357371432182276578283932647249629707984639755245731994004982047010862474568253438883825981211552726455647610616600152683140602219777227764342827766552684058977170125324805316413550680703753463380261978903747369677517090549750490497714726106808405188795507741435252228742048791254891796083781713724953974101730953449734214103419451007355326070889428042830527374106171411884042865409718813225704924308910578917985370161732700040769553579304781551439507813917217693054553136139858632877393572913681604198562756394542739717
c3 = 4345261358659519189634881349240932351623603440440060460588285817392306152201826610576491755629698765088135761317793967803519010356869269204503397215039512744495117601932620637450095192646479479541571697381615227131485964855439316795397514445542660502760126364064850197352955455820341422106740318181122113707487426652989875585231637716536188004952356846847687782788196021954904944243050038759261831381697585862182084930662578928342538660648403902072793943235882313263403348511364765676275877687747514403142706712995406077875195587485333137738286810493929324782535392363155178660765334428891921464976278013274433592459
c4 = 11163192691864487842504791707572292045010440994593022973064948393324184598662086767886111478358067883324039072186651857397731078118781186686459647088206129240315423019956385054334592265029781917246602461962626683725203283354094411740566113019140776580459728655850754495232498348144806199874330892136766891492831287879346899778473534258469040357585649045269842028785546606058644151580331160754603828262995696611984149905299109630697269974668616156412842759609194334129212734919638779629261074770920807952993453659743525451175541328430753432209789806184520128139906770561431423993324872179142853918272022140840732281811
e1 = 17
e2 = 23

diff = 56789 - 12345
m1 = related_message_attack(c1, c2, diff, e1, n) - 12345
print 'm1 =', m1
m2 = related_message_attack(c3, c4, diff, e2, n) - 12345
print 'm2 =', m2

以下の通り、m1とm2を算出することができた。

m1 = 19940708887759698510138918424450978321561069230659682994645881255326771243148984534641521276833375122703596885707253454427683279897828170878752612038114916127076079372073980486084679133895997151796999085785875836411210710632349923692939803228793799180641695640367708674225359974103741571982122048082035653192117956305119783207139142492158377892592169456609523577779421428356103367766774789680587969032302667151786683889761811812272622064633882550675704607685899902862193827181388950179113885788804816791465827265522578945146174815051717419478773041589332193216487854230882177980058898250512045181287339603392316697829
m2 = 2970132540488149339645289732236094260249062136537890152544022014880742014613667308336012839589875906076626365709335806489861391924524036985675821291443068706330596605582227620510725657401246096937011593605357908632053035718719770934145713092502591072370696481368118792860212738265793148704385419081990887592837829524490105986239282282260211257709359015566779069639346641105169115995195678357307965665965863966691547051261296196880300064216255207531200236387931460445195365540532178913046683294419159294042199243485508880751463979557947263693533936834072139357019316229736030987782295309538167642041408183532003721823

次にCommon Modules Attackでflagを求める。

import gmpy

def commom_modules_attack(c1, c2, e1, e2, n):
    gcd, s1, s2 = gmpy.gcdext(e1, e2)
    if s1 < 0:
        s1 = -s1
        c1 = gmpy.invert(c1, n)
    elif s2 < 0:
        s2 = -s2
        c2 = gmpy.invert(c2, n)
 
    v = pow(c1, s1, n)
    w = pow(c2, s2, n)
    x = (v*w) % n
    return x

n = 23992456508721632904544057999056395984840598682551527471151904763246778638836805311058576074076544471814362118450963752614808101805018226501728749753154687251596663180454809994272928278066817153483685668132338944992849111855590973474678454159123639456555256485147196164078477717189520027988101925788303558976065942012105491523422884349644306896086216721825961334666043695121350988761613913914655313225263251356627080558127266206207253980892813908459449433940028268804981985006285644508736389967109173883994849116220035021283230523958640143355551140077459561176550844398278642511471910168765368624465988996082307992457
e1 = 17
e2 = 23
m1 = 19940708887759698510138918424450978321561069230659682994645881255326771243148984534641521276833375122703596885707253454427683279897828170878752612038114916127076079372073980486084679133895997151796999085785875836411210710632349923692939803228793799180641695640367708674225359974103741571982122048082035653192117956305119783207139142492158377892592169456609523577779421428356103367766774789680587969032302667151786683889761811812272622064633882550675704607685899902862193827181388950179113885788804816791465827265522578945146174815051717419478773041589332193216487854230882177980058898250512045181287339603392316697829
m2 = 2970132540488149339645289732236094260249062136537890152544022014880742014613667308336012839589875906076626365709335806489861391924524036985675821291443068706330596605582227620510725657401246096937011593605357908632053035718719770934145713092502591072370696481368118792860212738265793148704385419081990887592837829524490105986239282282260211257709359015566779069639346641105169115995195678357307965665965863966691547051261296196880300064216255207531200236387931460445195365540532178913046683294419159294042199243485508880751463979557947263693533936834072139357019316229736030987782295309538167642041408183532003721823

flag = commom_modules_attack(m1, m2, e1, e2, n)
flag_str = ('%x' % flag).decode('hex')
print flag_str

この結果は以下の通り。

common_modulus_and_franklin_reiter_related_message

$ echo -n common_modulus_and_franklin_reiter_related_message | sha1sum
4111c011bc640806ef98a32a5caaf9d169a960a0  -

WhiteHat{4111c011bc640806ef98a32a5caaf9d169a960a0}

Ha Long bay (Cryptography 250)

以下のコードと、n, e, C1～C3の値が与えられている。

from Crypto.Util import number

from secret import M, flag

p = number.getPrime(512)
q = number.getPrime(512)
n = p * q
e = 3

assert (len(flag) < 18),"Fail!"

fsplit = len(flag)/3

m1 = M + chr(number.getRandomRange(32, 128)) + flag[:fsplit]
m2 = M + chr(number.getRandomRange(32, 128)) +  flag[fsplit:2*fsplit]
m3 = M + chr(number.getRandomRange(32, 128)) +  flag[2*fsplit:]

m1 = int(m1.encode('hex'),16)
m2 = int(m2.encode('hex'),16)
m3 = int(m3.encode('hex'),16)

C1 = pow(m1, e, n)
C2 = pow(m2, e, n)
C3 = pow(m3, e, n)

Coppersmith's Short Pad Attackで平文の差を求めながら、Franklin-Reiter Related Message Attackでm1～m3を求める。

# coppersmiths_short_pad-and-related_message_attack.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]  # 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 = 103812409689464886276475047044770609297885893720146571798654593885477457188425375786047017735691464865799751262776976174291152757506033948402223696021505470811665108707476725788296289255777914656800454451779117367605227364391483323666809650532860469176398816220707851639905500304208833022438234033264200398959
e = 3

C1 = 9317106922634505445328279149755295612464875825943780841886193649700131610057100771444165757592479299555845021862440454968502065319770337331674061960123779876709748994547507057835826773522733671492329400557540100987018908395372213360970889608191940631081957498661950679566048064234326337242245437800870328713
C2 = 9314352234311777268152500810432217195086739647228997430466360767070638972017377674642639833356580951663634114522574738957708645348438979256455824440476178459296267056062724307782801856615506577790281367843133061096735566462588088807072141910079117362448136849082448630141871675817981866725491776400151339928
C3 = 102298788718908831383454512674839558060033746080468660252243145800572734468521296602058538109452538907204027081338987796558296639830757629468491322438048912956916198524821066676689795698612028521062296901313097979278633376983280108123961097977187251599033620058543603046291262367128490175209233898073639549204

diff = short_pad_attack(C1, C2, e, n)
m1 = related_message_attack(C1, C2, diff, e, n)
msg1 = ('%x' % m1).decode('hex')
m2 = m1 + diff
msg2 = ('%x' % m2).decode('hex')

diff = short_pad_attack(C2, C3, e, n)
m3 = m2 + diff
msg3 = ('%x' % m3).decode('hex')
print msg1
print msg2
print msg3

この結果は以下の通り。

ab688786fce01806bea4f1812740c15703837b12_part of flag is !uozt_
ab688786fce01806bea4f1812740c15703837b12_part of flag is \ficm_
ab688786fce01806bea4f1812740c15703837b12_part of flag is l41t0r

このことから以下のことがわかる。

flag = 'uozt_ficm_41t0r'

$ echo -n uozt_ficm_41t0r | sha1sum
a1ac8b83a8c8495b94007c2745596206d431748f  -

WhiteHat{a1ac8b83a8c8495b94007c2745596206d431748f}

RCTF 2017 Writeup

この大会は2017/5/20 9:00(JST)～2017/5/22 9:00(JST)に開催されました。
今回もチームで参戦。結果は574点で620チーム中102位でした。
自分で解けた問題をWriteupとして書いておきます。

Sign In (Misc)

freenodeで#rctf2017チャネルに入る。

09:03 *topic : RCTF{Welcome_To_RCTF_2017}

RCTF{Welcome_To_RCTF_2017}

RSA_sign1 (Crypto)

メッセージと対応するシグネチャがあっていればフラグが表示できそう。
何でもよいので、先にシグネチャを決める。それからメッセージを求め、メッセージから順に指定する。

#!/usr/bin/env python
import socket
import rsa

with open('public.pem') as f:
    pub_pem = f.read()

pub_key = rsa.PublicKey.load_pkcs1(pub_pem)
sig = 'hogehoge'

blocksize = rsa.common.byte_size(pub_key.n)
encrypted = rsa.transform.bytes2int(sig)
decrypted = rsa.core.decrypt_int(encrypted, pub_key.e, pub_key.n)
clearsig = rsa.transform.int2bytes(decrypted, blocksize)
sep_idx = clearsig.index('\x00', 2)
msg = clearsig[sep_idx+1:]

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('rsasign1.2017.teamrois.cn', 3000))

data = s.recv(256)
print data
print msg
s.sendall(msg + '\n')
data = s.recv(256)
print data
print sig.encode('hex')
s.sendall(sig.encode('hex') + '\n')
data = s.recv(256)
print data

このコードを実行したらフラグを得られた。

RCTF{your_fir5t_sig_test}

UIUCTF 2017 Writeup

この大会は2017/4/29 9:00(JST)～2017/4/30 21:00(JST)に開催されました。
今回もチームで参戦。結果は600点で163チーム中57位でした。
自分で解けた問題をWriteupとして書いておきます。

babyrsa (crypto 200)

RSA暗号。nが大きく、eが小さいため、cのe乗根により復号する。

import gmpy

e = 5
c = 199037898049081148054548566008626493558290050160287889209057083223407180156125399899465196611255722303390874101982934954388936179424024104549780651688160499201410108321518752502957346260593418668796624999582838387982430520095732090601546001755571395014548912727418182188910950322763678024849076083148030838828924108260083080562081253547377722180347372948445614953503124471116393560745613311509380885545728947236076476736881439654048388176520444109172092029548244462475513941506675855751026925250160078913809995564374674278235553349778352067191820570404315381746499936539482369231372882062307188454140330786512148310245052484671692280269741146507675933518321695623680547732771867757371698350343979932499637752314262246864787150534170586075473209768119198889190503283212208200005176410488476529948013610803040328568552414972234514746292014601094331465138374210925373263573292609023829742634966280579621843784216908520325876171463017051928049668240295956697023793952538148945070686999838223927548227156965116574566365108818752174755077045394837234760506722554542515056441166987424547451245495248956829984641868331576895415337336145024631773347254905002735757

m = gmpy.root(c, e)[0]
flag = ('%x' % m).decode('hex')
print flag

実行結果は次の通り。

welcome to uiuctf!
your super secret flag is: flag{c4n_w3_get_s0m3b0dy_t0_sm1th_some_c0pper_pls}

flag{c4n_w3_get_s0m3b0dy_t0_sm1th_some_c0pper_pls}

WhiteHat Challenge 03 Writeup

この大会は2017/4/27 11:00(JST)～2017/4/27 19:00(JST)に開催されました。
今回は仕事の合間に個人で参戦。結果は70点で101チーム中42位でした。
自分で解けた問題をWriteupとして書いておきます。

Crypto001 (Cryptography 25)

単語ごとに反転して、11シフトする。

import string

al_U = string.uppercase

e = 'HJXAJY GPHTPR HPL P CPBDG APGTCTV SCP CPXRXIXADE DWL LTGWIGTKD TWI CPBDG RXAQJETG SCP STWHXAQPIHT TWI TAJG UD TWI HGDGTEBT. GPHTPR STHJ TWI HBTAQDGE SCP HEXWHSGPW UD TWI SDXGTE DI TIPTGR HXW CLD TBTGEJH APRXIXADE SCP NGPIXAXB GTLDE. VPAU HX TWI GPTN IPWI GPHPTR HPL CGDQ. CPBDG GDGTEBT HJXAJY GPHTPR HX STSGPVTG HP TCD UD TWI IHDB AJUGTLDE SCP AJUHHTRRJH HGTSPTA CX TWI NGDIHXW UD TWI SAGDL. HXW TUXA SCP HXW ICTADXK WIPTS TKPW CTTQ NATSXL STIPGQTATR CX TGJIPGTIXA SCP BAXU.'

words = e.split(' ')

m = ''
for i in range(len(words)):
    if words[i][-1:] == '.':
        word = words[i][::-1][1:] + '.'
    else:
        word = words[i][::-1]
    #print word
    for j in range(len(word)):
        if word[j] in al_U:
            index = al_U.index(word[j]) + 11
            if index > 25:
                index = index - 26
            m += al_U[index]
        else:
            m += word[j]

    if i != len(words) - 1:
        m += ' '

print m

実行結果は次の通り。

JULIUS CAESAR WAS A ROMAN GENERAL AND POLITICIAN WHO OVERTHREW THE ROMAN REPUBLIC AND ESTABLISHED THE RULE OF THE EMPERORS. CAESAR USED THE PROBLEMS AND HARDSHIPS OF THE PERIOD TO CREATE HIS OWN SUPREME POLITICAL AND MILITARY POWER. FLAG IS THE YEAR THAT CEASAR WAS BORN. ROMAN EMPEROR JULIUS CAESAR IS REGARDED AS ONE OF THE MOST POWERFUL AND SUCCESSFUL LEADERS IN THE HISTORY OF THE WORLD. HIS LIFE AND HIS VIOLENT DEATH HAVE BEEN WIDELY CELEBRATED IN LITERATURE AND FILM.

フラグはCeaserが生まれた年なので、紀元前100年。

$ echo -n 100 | sha1sum
310b86e0b62b828562fc91c7be5380a992b2786a  -

WhiteHat{310b86e0b62b828562fc91c7be5380a992b2786a}

Crypto002 (Cryptography 10)

n, p, q, e, cが与えられているので、そのままRSA暗号の復号を行う。

n = 132584825018166892036247821308754740533575984294912859418971244776769293548107490233355297115861255963076622070127865142205107181207673702587393494860613316425336008819081169031194442020498569601888048767385032364436395644961861833287918315793817245497784496450110641025476274978672298849300106831336352152221
p = 12476682960795779723419989287306239606331347310604553825605263028855086418051086300006278888049896375754096827163121306696417314531666670662341673511789487
q = 10626608485185909739187126602183513204215955466032868268570782358820047751795982373252873333276843831383542360202874683262678664975380865415068554992090483
e = 65537
c = 126028558760741438230925566962334702896791270808414391828894437291120207835997354509410869568173448979784329516392078311028442458946906210498176026685581176779209904039179175088984829699783861789249260322822491502790157863487861171337660785254139478229397872969136220001367017765809130698515063339265165085655

a = (p - 1) * (q - 1)

x = 0
while True:
    if (a * x + 1) % e == 0:
        d = (a * x + 1) / e
        break
    x = x + 1

m = pow(c, d, n)

flag = ('%x' % m).decode('hex')
print flag

復号結果は simple_rsa_decryption

$ echo -n simple_rsa_decryption | sha1sum
100be37579e0f27c314efcb68a773b31537b5118  -

WhiteHat{100be37579e0f27c314efcb68a773b31537b5118}

Web001 (Web Security 20)

ソースに次のように書いてある。

<!--test/test-->

testアカウントでログインすると、You are not admin.と表示される。クッキーのuserの値がtestになっているので、adminに書き換え、ページを更新するとフラグが表示される。

Flag: don't_believe_cookies_at_all

$ echo -n "don't_believe_cookies_at_all" | sha1sum
92b2bc2f657574ab3481ebcb6705c36079b3e6d7  -

WhiteHat{92b2bc2f657574ab3481ebcb6705c36079b3e6d7}

For002 (Forensics 15)

POST /accounts/login/ の箇所が数か所ある。No.505に対して302 Foundで返ってきている。No.505で投入しているパスワードは"@Bkav123#$challange3"

$ echo -n "@Bkav123#\$challange3" | sha1sum
0d712cbea97819fa1e1c0a605283b1b912bcf350  -

WhiteHat{0d712cbea97819fa1e1c0a605283b1b912bcf350}