noxCTF 2018 Writeup

この大会は2018/9/7 2:00(JST)～2018/9/9 2:00(JST)に開催されました。
今回もチームで参戦。結果は 10779点で531チーム中13位でした。
自分で解けた問題をWriteupとして書いておきます。

Discord (Welcome)

DiscordでnoxCTFのthe-flag-is-hereチャネルを見る。

noxCTF{w3lc0me_2_n0xC7F!!!!!!!!!!!!!!!!!}

Facebook (Welcome)

https://www.facebook.com/noxaleを探す。ある画像にノートPCがたくさんあるが、その中の一つのPCにフラグが表示されている。

noxCTF{SECRET_flag}

Twitter (Welcome)

https://twitter.com/teamnoxale/のトップの方にある記事のグラフ画像にフラグが書いてある。

noxCTF{follow_our_twitter_for_updates!}

Blind Date (Misc)

jpegファイルが添付されているが、画像は表示できない。4バイト単位でバイト文字が逆になっている。

with open('BlindDate.jpeg', 'rb') as f:
    data = f.read()

flag = ''
for i in range(0, len(data), 4):
    flag += data[i:i+4][::-1]

with open('flag.jpeg', 'wb') as f:
    f.write(flag)

戻してやると、jpgの末尾に以下の文字列の後、zipが含まれていることが分かる。zipはパスワードがかかっている。

Li4gICAuICAuLiAgLi4gICAuICAuLiAgLi4gICAuICAuLiAgLiAgLi4NCi4gICAgLiAgIC4gICAgICAgLiAgICAgIC4gICAgLiAgIC4gIC4gIA0KICAgIC4uICAgICAgICAgIC4uICAgICAgLiAgIC4uICAgICAgLiAgLg

$ echo Li4gICAuICAuLiAgLi4gICAuICAuLiAgLi4gICAuICAuLiAgLiAgLi4NCi4gICAgLiAgIC4gICAgICAgLiAgICAgIC4gICAgLiAgIC4gIC4gIA0KICAgIC4uICAgICAgICAgIC4uICAgICAgLiAgIC4uICAgICAgLiAgLg== | base64 -d
..   .  ..  ..   .  ..  ..   .  ..  .  ..
.    .   .       .      .    .   .  .  
    ..          ..      .   ..      .  .

点字のようだ。https://www.pharmabraille.com/braille-codes/unified-english-braille-ueb-code/を参考にデコードする。

F4C3P4LM

このパスワードで解凍できて、flag.txtが抽出できる。

$ cat flag.txt
++++++++++[>+>+++>+++++++>++++++++++<<<<-]>>>>++++++++++.+.+++++++++.<---.+++++++++++++++++.--------------.>+++.<+++++++++++++++++.<++++++++++++++++++.>>------.---------.--------.-----.++++++++++++++++++++++++++.<<.>>----.<++++++++.+++.>---------.<<+.>>++.<++.-----.+++++.<+++.>>++++++.<<-.>-----.<+.>.+++.>--------.<<---.>>++.<++.-----.+++++.<+++.>>++++++.<<-.++++++++++++.>>+++++++++.<<<++++++++++++++++++++++.
$ python3 brainfuck.py flag.txt
noxCTF{W0uld_y0u_bl1nd_d4t3_4_bl1nd_d4t3?}

noxCTF{W0uld_y0u_bl1nd_d4t3_4_bl1nd_d4t3?}

Marcode (Misc)

QRコードが次々に変わる動画。まずフレーム画像を抽出する。

import os
import cv2

movie = 'Marcode.mp4'
count = 0
cap = cv2.VideoCapture(movie)
 
while True:
    ret, frame = cap.read()
    if ret == True:
        count += 1
        cv2.imwrite('div/Marcode_' + str("{0:05d}".format(count)) +'.png', frame)
    else:
        break

それぞれQRコードになっているので、読み取ると、GoogleドライブのURLになっている。
試しにアクセスしてみると、アルファベット一文字の画像ファイルだった。つなげると文章になりそうだ。
まず順にQRコードを読み取り、GoogleドライブのURLの一覧にする。

from pyzbar.pyzbar import decode
from PIL import Image
import os

I_FILE_FORMAT = 'div/Marcode_%05d.png'

for i in range(1, 3491):
    i_filename = I_FILE_FORMAT % i
    data = decode(Image.open(i_filename))
    print data[0][0]

種類はそこまで多くないので、URLと文字の対応は一つ一つ確認する。そして、順に対応する文字をつなげる。

dic = {
'https://drive.google.com/open?id=1vHlCNodJ84iw51C8gIz4hr0UpsWNx3fm': ' ',
'https://drive.google.com/open?id=1p4m9gtvh31s2SJ9G1uNr8burIvQabm_k': '?',
'https://drive.google.com/open?id=1OqacmR-Ccc2YLVYCS2co4dWtSqfEGxIl': 'A',
'https://drive.google.com/open?id=151y0xa6hnTR9yp9G0D-dyox08bV4-JZX': 'B',
'https://drive.google.com/open?id=1GLtL-X1IS4ms6fwC2OQV4jAmXjI_6bjQ': 'C',
'https://drive.google.com/open?id=1JtDxAfX8AEC_mFzJPZofI1RyOL62MAmk': 'D',
'https://drive.google.com/open?id=1upmw0QvLjzp6b7RjCrjJGjYfRijF82-g': 'E',
'https://drive.google.com/open?id=1rHGDe2F5vLws9fA0M3L9IELX9LYaU50x': 'F',
'https://drive.google.com/open?id=1DV0ACuyKWsFm2ApXgHHDP_DSzwqmtt5M': 'G',
'https://drive.google.com/open?id=1c-go7QIZb_yqGDsRKlXG1j1Py7-wcSFG': 'H',
'https://drive.google.com/open?id=1Rw-Op049iTliLPFTTRj7p4gBXmm8IboN': 'I',
'https://drive.google.com/open?id=1uynnoN7ItBRls7MiqFa1rLE-W3o9CnY5': 'J',
'https://drive.google.com/open?id=1dtYor_A9Sf3DDTlczTLA0s9rBluVNoOX': 'K',
'https://drive.google.com/open?id=1H5DHyv0METKfLV7xdzw-SVXU_F1o1iKM': 'L',
'https://drive.google.com/open?id=1b5wz-LsIBxnA7mp5ImbNLZQY0nob94OO': 'M',
'https://drive.google.com/open?id=1cZlhiRoZcEiaNEwScBQd0IA2PXh1Z1tX': 'N',
'https://drive.google.com/open?id=1pXSHKhMzuKrUMg0x8ygZ36yTn0-9nBe8': 'O',
'https://drive.google.com/open?id=1DF2RneUWAb6wqp7YJ0vjOwDJGdENEc0Q': 'P',
'https://drive.google.com/open?id=1vPBtiNzUzYEOEKFK60vG305uPw9CDy8p': 'Q',
'https://drive.google.com/open?id=1lKeCjQFcTSuUzMGUEeEzPj4d2x1MLTJm': 'R',
'https://drive.google.com/open?id=1lSanpoEq3LeV0aaL6KEnUiJE2iGijdrt': 'S',
'https://drive.google.com/open?id=131OPuwNVggs0ZAsVie4dfA3k9zLWN-uu': 'T',
'https://drive.google.com/open?id=1hjIQq2fEcduFF0CfRs-MJ2hlCuC5lkW6': 'U',
'https://drive.google.com/open?id=1apKMrqUwZn5dOkRWfjbYgYH_RvkmPD2P': 'V',
'https://drive.google.com/open?id=1mZivmNZ8uDiUb5YUoF8sj9kZXKkh7GNO': 'W',
'https://drive.google.com/open?id=1UpU1_MTK-0XgCpcZKC4AVGsBswNpQTBO': 'X',
'https://drive.google.com/open?id=1g2I1a09lO4m0imhIzJ60LUeDPNDIdIp_': 'Y',
'https://drive.google.com/open?id=1nlp-HIwnRbG61mf5SF_BzMdlNAR7tHLt': 'Z'
}

with open('access_list.txt', 'r') as f:
    lines = f.readlines()

msg = ''
for line in lines:
    line = line.strip()
    msg += dic[line]

print msg

この結果、以下のようなメッセージになる。ただし、?はファイル名がelseになっていたので、記号などが入ることになる。

THE TWO MEN APPEARED OUT OF NOWHERE? A FEW YNARDS APART IN THE NARROW? MOONLIT LANE? FOR A SECOND THEY STOOD QUITE STOILL? WANDS DIRECTED AT EACH OTHER?S CHESTS? THEN? RECOGNIZING EACH OTHER? THEY STOWED THEIR WANDS BENEATH THEIR CLOAKS AND STARTED WALKING BRISKLY IN THE SAME DIRECTION? ?NEWS?? ASKED THE TALLEXR OF THE TWO? ?THE BEST?? REPLIED SEVERUS SNAPE? THE LANE WAS BORDERED ON THE LEFT BY WILD? LOW?GROWING BRAMBLES? ON THE RIGHT BY A HICGH? NEATLY MANICURED HEDGE? THE MEN?S LONG CLOAKS FLAPPED AROUND THEIR ANKLES AS THEY MARCHED? ?THOUGHT I MIGHTT BE LATE?? SAID YAXLEY? HIS BLUNT FEATURES SLIDING IN AND OUT OF SIGHT AS THE BRANCHES OF OVERHANGING TREES BROKE THE MOONLIGHT? ?IT WAS A LITTLE TRICKIER THAN I EXPECTEFD? BUT I HOPE HE WILL BE SATISFIED? YOU SOUND CONFIDENT THAT YOUR RECEPTION WILL BE GOOD?? SNAPE NODD?ED? BUT DID NOT ELABORATE? THEY TURNED RIGHT? INTO A WIDE DRIVAEWAY THAT LED OFF THE LANE? THE HIGH HEDGE CURVED INTO THEM? RUNNIVNG OFF INTO THE DISTANCE BEYOND THE PAIR OF IMPAOSING WROUGHT?IRON GATES BARRING THE MEN???S WAY? NEITDHER OF THEM BROKE STEP? IN SILENCE BOTH RAISED THEIR LEFT ARMS IN A KIND OF SALAUTE AND PASSED STRAIGHT THROUGH? AS THOUGH THE DARK METAL WAS SMOKE? THE YEW HEDGES MUFFLED THE SOKUND OF THE MEN???S FOOTSTEPS? THERE WAS A RUSTLE SOMEWHERE TO THEIR RIGHT? YAXLEY DREW HIS WAND AGAIN POINTING IT OVER HIS COMPANION???S HEAD? BUT THE SOURCE OF THE NOISE PROVED TO BE NOTHING MORE THAN A PURE?WHITE PEACOCK? STERUTTING MAJESTICALLY ALONG THE TOP OF THE HEDGE? ???HE ALWAYS DID HIMSELF WELL? LUCIUS? PEACOCKS?????? YAXLEY THRUST HIS WAND BADCK UNDER HIS CLOAK WITH A SNORT? A HANDSOME MANOR HOUSE GREW OUT OF THE DARKNESS AT THE END OF THE STRAIGHT DRIVE? LIGHTS GLINTING IN THE DIAMOND PANED DOWNSTAAIRS WINDOWS? SOMEWHERE IN THE DARK GARDEN BEYOND THE HEDGE A FOUNTAIN WAS PLAYING? GRAVEL CRACKLED BENEATH THEIR FEET AS SNAPE AND YAXLEY SPED TOWARD THE FRONT DOOR? WHICH SWUNG INWARD AT THEIR APPROACH? THOUGH NOBODY HAD VISIBLY OPENED VIT? THE HALLWAY WAS LARGE? DIMLY LIT? AND SUMPTUOUSLY DECORATED? WITH A MAGNIFICENT CARPET COVERING MOST OF THE STONE FLOOR? THE EYES OF THE PALE?FACED PORTRAITS ON THE WALL FOLLOWED SNAPE AND YAXLEY AS THEY STRODE PAST? THE TWO MEN HALTED AT A HEAVY WOODEN DOOR LEADING INTO THE NEXT ROOM? HESITATED FOR THE SPACE OF A HEARTBEAT? THEN SNAPE TURNED THE BRONZE HANDLE? THE DRAWING ROOM WAS FULL OF SILENT PREOPLE? SITTING AT A LONG AND ORNATE TABLE? THE ROOM???S USUAL FURNITURE HAD BEEN PUSHED CARELESSLY UP AGAINST THE WALLS? ILLUMINATION CAME FROM A ROARING FIRE BENEATH A HANDSOME MARBLE MANTELPIECE SURMOUNTED BY A GILDED MIRROR? SNAPE AND YAXLEY LINGERED FOR A MOMENT ON THE THRESHOLD? AS THEIR EYES GREW ACCUSTOMED TO THE LACK OF LIGHT? THEY WERE DRAWN UPWARD TO THE STRANGEST FEATURE OF THE SCENE? AN APPARENTLY UNCONSCIOUS HUMAN FIGURE HANGING UPSIDE DOWN OVER THE TABLE? REVOLVING SLOWLY AS IF SUSPENDED BY AAN INVISIBLE ROPE? AND REFLECTED IN THE MIRROR AND IN THE BARE? POLISHED SURFACE OF THE TABLE BELOW? NONE OF THE PEOPLE SEATED UNDERNEATH THIS SINGULAR SIGHT WERE LOOKING AT IT EXCEPT FOR A PALE YOUNG MAN SITTING ALMOST DIRECTLY BELOW IT? HE SEEMED UNABLE TO PREVENT HIMSELF FROM GLANCING UPWARD EVERY MINUTE OR SO? ???YAXLEY? SNAPE???? SAID A HIGH? CLEAR VOICE FROM THE HEAD OF THE TABLE? ???YOU ARE VERY NEARLY LATE???? THE SPEAKER WAS SEATED DIRECTLY IN FRONT OF THE FIREPLACE? SO THAT IT WAS DIFFICULT? AT FIRST? FOR THE NEW ARRIVAL?S TO MAKE OUT MORE THAN HIS SILHOUETTE?

この文章を調べるとハリーポッターのストーリーの一部であることがわかる。例えばhttps://www.lingq.com/ja/lesson/hp-7-hp-and-the-deathly-hallows-ch1-1-1166226/を参考にし、原文と照らし合わせ、加わった部分を並べる。'は???(3文字分)と表記されていることに気を付ける。

NOXCTF?AVADAKEDAVRA?

noxCTF{AVADAKEDAVRA}

Read Between The Lines (Misc)

$ file message.code 
message.code: gzip compressed data, was "message", from Unix, last modified: Fri Jul 20 21:53:57 2018
$ mv message.code message.gz
$ gzip -d message.gz

解凍したmessageの内容を確認すると、難読化したようなコードの後に、spaceやtabが含まれている。Whitespace言語のようだ。
http://www.hpcs.cs.tsukuba.ac.jp/~kanbayashi/whitespace.rb
上記を使って、実行する。

$ ruby whitespace.rb message.ws 
noxCTF{DaFuckIsWHITESPACE}whitespace.rb:470:in `sprintf': no implicit conversion from nil to integer (TypeError)
	from whitespace.rb:470:in `exec_io_out_a_char'
	from whitespace.rb:439:in `exec_io'
	from whitespace.rb:61:in `interprete'
	from whitespace.rb:28:in `main'
	from whitespace.rb:637:in `<main>'

エラーが出ているが、フラグはわかった。

noxCTF{DaFuckIsWHITESPACE}

Chop Suey (Crypto)

RSA暗号でn, eの代わりにdp, dpが分かっている場合の復号を行う。

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m

p = 8637633767257008567099653486541091171320491509433615447539162437911244175885667806398411790524083553445158113502227745206205327690939504032994699902053229
q = 12640674973996472769176047937170883420927050821480010581593137135372473880595613737337630629752577346147039284030082593490776630572584959954205336880228469
dp = 6500795702216834621109042351193261530650043841056252930930949663358625016881832840728066026150264693076109354874099841380454881716097778307268116910582929
dq = 783472263673553449019532580386470672380574033551303889137911760438881683674556098098256795673512201963002175438762767516968043599582527539160811120550041
c = 24722305403887382073567316467649080662631552905960229399079107995602154418176056335800638887527614164073530437657085079676157350205351945222989351316076486573599576041978339872265925062764318536089007310270278526159678937431903862892400747915525118983959970607934142974736675784325993445942031372107342103852

qinv = modinv(q, p)
m1 = pow(c, dp, p)
m2 = pow(c, dq, q)
h = (qinv * (m1 - m2)) % p
m = m2 + h * q

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

noxCTF{W31c0m3_70_Ch1n470wn}

Decryptor (Crypto)

$ nc chal.noxale.com 4242
Please insert your ciphertext to decrypt in hex form:
0
0
$ nc chal.noxale.com 4242
Please insert your ciphertext to decrypt in hex form:
1
1
$ nc chal.noxale.com 4242
Please insert your ciphertext to decrypt in hex form:
2
c073e0ce8e6b81d6641fb7ec8926af0c9737a18e25815c2528772315d069073b0dd6288dd8cf0d7e9ce44f776bfb3269445421180b178dd5b63e109416fbd80a3874546929fc4dfe2b82c3024bdf0716d7fdde303533f473078f265e9c7ba8e11dd5a70b28241352deea70a44c4f3f9c58a39c76abcdf138491437a480ceb178
$ nc chal.noxale.com 4242
Please insert your ciphertext to decrypt in hex form:
7b1a62cb17160448d544ff674f978876d2a4418ff9cfc32e9eda41ed566617a034c34091f19dbe650fdb11e7aa5744a48709b61a44a499c213dc19eb092fd8282e5ec69051d3adba84129571143e14e14be7f63bd8cdb42a4eedfb62570ed7eaef8002c3f6f3267079833effe836d8e10e0f01bcbd2470b2c0c10b59d1aa260a
Not gonna happen.

復号してくれるシステムだが、問題の暗号だけは復号してくれない。LSB decryption oracle attackで復号する。

from fractions import Fraction
import socket

def lsb_oracle(enc):
    s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
    s.connect(('chal.noxale.com', 4242))
    data = s.recv(1024)
    print data + enc
    s.sendall(enc + '\n')
    data = s.recv(1024)
    print data
    return int(data, 16) % 2

N = 140165355674296399459239442258630641339281917770736077969396713192714338090714726890918178888723629353043167144351074222216025145349467583141291274172356560132771690830020353668100494447956043734613525952945037667879068512918232837185005693504551982611886445611514773529698595162274883360353962852882911457919
c = 86445915530920147553767348020686132564453377048106098831426077547738998373682256014690928256854752252580894971618956714013602556152722531577337080534714463052378206442086672725486411296963581166836329721403101091377505869510101752378162287172126836920825099014089297075416142603776647872962582390687281063434
e = 65537

bounds = [0, Fraction(N)]

i = 0
m = 0
while True:
    print 'Round %d' % (i+1)
    i += 1

    c2 = (c * pow(2, e, N)) % N
    ct2 = '%x' % c2
    lsb = lsb_oracle(ct2)
    if lsb == 1:
        bounds[0] = sum(bounds)/2
    else:
        bounds[1] = sum(bounds)/2
    diff = bounds[1] - bounds[0]
    diff = diff.numerator / diff.denominator
    if diff == 0:
        m = bounds[1].numerator / bounds[1].denominator
        break
    c = c2

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

noxCTF{0u7sm4r73d}

Plot Twist (Crypto)

鍵を予測し、当たっていれば、フラグが表示される。間違っていると、鍵を教えてくれる。Mersenne Twisterの性質から鍵を予測する。

import socket
import re
import random

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def untemper(rand):
    rand ^= rand >> 18;
    rand ^= (rand << 15) & 0xefc60000;
 
    a = rand ^ ((rand << 7) & 0x9d2c5680);
    b = rand ^ ((a << 7) & 0x9d2c5680);
    c = rand ^ ((b << 7) & 0x9d2c5680);
    d = rand ^ ((c << 7) & 0x9d2c5680);
    rand = rand ^ ((d << 7) & 0x9d2c5680);
 
    rand ^= ((rand ^ (rand >> 11)) >> 11);
    return rand

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('chal.noxale.com', 5115))

N = 624
state = []
for i in range(N):
    tmp_key = '1234567890123456'
    data = recvuntil(s, '\n')
    print data + tmp_key
    s.sendall(tmp_key)
    data = recvuntil(s, '\n')
    print data
    pattern = 'The key was: (.+)'
    m = re.search(pattern, data)
    key =  int(m.group(1))
    state.append(untemper(key))

state.append(N)
random.setstate([3, tuple(state), None])

real_key = str(random.getrandbits(32)).rjust(16, '0')
data = recvuntil(s, '\n')
print data + real_key
s.sendall(real_key)
data = recvuntil(s, '\n')
print data

noxCTF{41w4ys_us3_cryp70_s3cur3d_PRNGs}

Trinity (Crypto)

RSA暗号でHastad's broadcast attackで復号する問題と推測。eは3のはず。そのままHastad's broadcast attackをしても復号できない。よく見るとN,cの値が0～4しか使われていない。5進数表記となっているとみて、Hastad's broadcast attackで復号する。

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

N1 = 331310324212000030020214312244232222400142410423413104441140203003243002104333214202031202212403400220031202142322434104143104244241214204444443323000244130122022422310201104411044030113302323014101331214303223312402430402404413033243132101010422240133122211400434023222214231402403403200012221023341333340042343122302113410210110221233241303024431330001303404020104442443120130000334110042432010203401440404010003442001223042211442001413004
c1 = 310020004234033304244200421414413320341301002123030311202340222410301423440312412440240244110200112141140201224032402232131204213012303204422003300004011434102141321223311243242010014140422411342304322201241112402132203101131221223004022003120002110230023341143201404311340311134230140231412201333333142402423134333211302102413111111424430032440123340034044314223400401224111323000242234420441240411021023100222003123214343030122032301042243

N2 = 302240000040421410144422133334143140011011044322223144412002220243001141141114123223331331304421113021231204322233120121444434210041232214144413244434424302311222143224402302432102242132244032010020113224011121043232143221203424243134044314022212024343100042342002432331144300214212414033414120004344211330224020301223033334324244031204240122301242232011303211220044222411134403012132420311110302442344021122101224411230002203344140143044114
c2 = 112200203404013430330214124004404423210041321043000303233141423344144222343401042200334033203124030011440014210112103234440312134032123400444344144233020130110134042102220302002413321102022414130443041144240310121020100310104334204234412411424420321211112232031121330310333414423433343322024400121200333330432223421433344122023012440013041401423202210124024431040013414313121123433424113113414422043330422002314144111134142044333404112240344

N3 = 332200324410041111434222123043121331442103233332422341041340412034230003314420311333101344231212130200312041044324431141033004333110021013020140020011222012300020041342040004002220210223122111314112124333211132230332124022423141214031303144444134403024420111423244424030030003340213032121303213343020401304243330001314023030121034113334404440421242240113103203013341231330004332040302440011324004130324034323430143102401440130242321424020323
c3 = 10013444120141130322433204124002242224332334011124210012440241402342100410331131441303242011002101323040403311120421304422222200324402244243322422444414043342130111111330022213203030324422101133032212042042243101434342203204121042113212104212423330331134311311114143200011240002111312122234340003403312040401043021433112031334324322123304112340014030132021432101130211241134422413442312013042141212003102211300321404043012124332013240431242

N = [int(str(N1), 5), int(str(N2), 5), int(str(N3), 5)]
C = [int(str(c1), 5), int(str(c2), 5), int(str(c3), 5)]
e = len(N)
a = chinese_remainder(N, C)
for n, c in zip(N, C):
    assert a % n == c
m = inv_pow(a, e)
flag = ('%x' % m).decode('hex')
print flag

noxCTF{D4mn_y0u_h4s74d_wh47_4_b100dy_b4s74rd!}

WTF (Crypto)

N,e,cに使われている文字を見てみる。

['A', 'B', 'E', 'g', 'l', 'O', 'S', 'b', 'T', 'Z']

10個あり、leet文字として0～9にあてはめられる。

0: O
1: l
2: Z
3: E
4: A
5: S
6: b
7: T
8: B
9: g

N,e,cを通常の数値に変換すると、eの値が大きいので、Wiener's Attackで復号する。

from fractions import Fraction

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    gcd, a, b = egcd(e, phi)
    d = a
    pt = pow(c, d, n)
    return hex(pt)[2:-1].decode('hex')

def continued_fractions(n,e):
    cf = [0]
    while e != 0:
        cf.append(int(n/e))
        N = n
        n = e
        e = N%e
    return cf

def calcKD(cf):
    kd = list()
    for i in range(1,len(cf)+1):
        tmp = Fraction(0)
        for j in cf[1:i][::-1]:
            tmp = 1/(tmp+j)
        kd.append((tmp.numerator,tmp.denominator))
    return kd

def int_sqrt(n):
    def f(prev):
        while True:
            m = (prev + n/prev)/2
            if m >= prev:
                return prev
            prev = m
    return f(n)

def calcPQ(a,b):
    if a*a < 4*b or a < 0:
        return None
    c = int_sqrt(a*a-4*b)
    p = (a + c) /2
    q = (a - c) /2
    if p + q == a and p * q == b:
        return (p,q)
    else:
        return None

def wiener(n,e):
    kd = calcKD(continued_fractions(n,e))
    for (k,d) in kd:
        if k == 0:
            continue
        if (e*d-1) % k != 0:
            continue
        phin = (e*d-1) / k
        if phin >= n:
            continue
        ans = calcPQ(n-phin+1,n)
        if ans is None:
            continue
        return (ans[0],ans[1])

def leet_to_long(s):
    d = ''
    for c in s:
        d += leets[c]
    return long(d)

N = 'lObAbAbSBlZOOEBllOEbblTlOAbOlTSBATZBbOSAEZTZEAlSOggTggbTlEgBOgSllEEOEZZOSSAOlBlAgBBBBbbOOSSTOTEOllbZgElgbZSZbbSTTOEBZZSBBEEBTgESEgAAAlAOAEbTZBZZlOZSOgBAOBgOAZEZbOBZbETEOSBZSSElSSZlbBSgbTBOTBSBBSOZOAEBEBZEZASbOgZBblbblTSbBTObAElTSTOlSTlATESEEbSTBOlBlZOlAOETAZAgTBTSAEbETZOlElBEESObbTOOlgAZbbOTBOBEgAOBAbZBObBTg'

e = 'lBlbSbTASTTSZTEASTTEBOOAEbEbOOOSBAgABTbZgSBAZAbBlBBEAZlBlEbSSSETAlSOlAgAOTbETAOTSZAZBSbOlOOZlZTETAOSSSlTZOElOOABSZBbZTSAZSlASTZlBBEbEbOEbSTAZAZgAgTlOTSEBEAlObEbbgZBlgOEBTBbbSZAZBBSSZBOTlTEAgBBSZETAbBgEBTATgOZBTllOOSSTlSSTOSSZSZAgSZATgbSOEOTgTTOAABSZEZBEAZBOOTTBSgSZTZbOTgZTTElSOATOAlbBZTBlOTgOSlETgTBOglgETbT'

c = 'SOSBOEbgOZTZBEgZAOSTTSObbbbTOObETTbBAlOSBbABggTOBSObZBbbggggZZlbBblgEABlATBESZgASBbOZbASbAAOZSSgbAOZlEgTAlgblBTbBSTAEBgEOEbgSZgSlgBlBSZOObSlgAOSbbOOgEbllAAZgBATgEAZbBEBOAAbZTggbOEZSSBOOBZZbAAlTBgBOglTSSESOTbbSlTAZATEOZbgbgOBZBBBBTBTOSBgEZlOBTBSbgbTlZBbbOBbTSbBASBTlglSEAEgTOSOblAbEgBAbOlbOETAEZblSlEllgTTbbgb'

leets = {'O': '0', 'l': '1', 'Z': '2', 'E': '3', 'A': '4',
    'S': '5', 'b': '6', 'T': '7', 'B': '8', 'g': '9'}

N = leet_to_long(N)
e = leet_to_long(e)
c = leet_to_long(c)

p, q = wiener(N, e)

flag = decrypt(p, q, e, c)
print flag

noxCTF{RSA_1337_10rd}

Java Corporation (Crypto)

CBC Padding oracle attackで復号する。

import socket

def str_xor(s1, s2):
    return ''.join(chr(ord(a) ^ ord(b)) for a, b in zip(s1, s2))

def unpad(s):
    return s[0:-ord(s[-1])]

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('chal.noxale.com', 3141))

with open('Encrypted.txt', 'rb') as f:
    ciphertext = f.read()

blocks = [ciphertext[i:i+16] for i in range(0, len(ciphertext), 16)]
print blocks


flags = []
for i in range(len(blocks)-1, 0, -1):
    pre_block = blocks[i-1]
    flag_block = ''
    for j in range(16):
        for code in range(256):
            print 'flag_block = %s(%s)' % (flag_block, flag_block.encode('hex'))
            try_iv = '\x00' * (16 - j - 1) + chr(code) + str_xor(str_xor(flag_block, chr(j+1)*j), pre_block[-j:])
            try_cipher = try_iv + blocks[i]
            send_length = str(len(try_cipher))
            print send_length
            s.sendall(send_length)
            print try_cipher
            s.sendall(try_cipher)
            data = s.recv(1)
            print data
            if data == '1':
                xor_code = (j + 1) ^ code ^ ord(pre_block[-j-1])
                flag_block = chr(xor_code) + flag_block
                print flag_block
                break
    flags.append(flag_block)

flags.reverse()
flag = unpad(''.join(flags))
print flag

noxCTF{0n3_p4d_2_f4r}