この大会は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!!!!!!!!!!!!!!!!!}
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}
$ 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}
