この大会は2020/7/4 0:00(JST)～2020/7/6 0:00(JST)に開催されました。
今回もチームで参戦。結果は717点で815チーム中44位でした。
自分で解けた問題をWriteupとして書いておきます。
Welcome (TRIVIA, WARM-UP)
RulesのページにWelcome flagのフラグが書いてあった。
ASIS{H3llo_eVery0n3_4nd_wi5h_y0u_all_7he_fUn!}
Baby RSA (CRYPTO, WARM-UP)
暗号処理の概要は以下の通り。
p, q: 512bit素数 e, n = 65537, p*q phi = (p-1)*(q-1) d = inverse(e, phi) r: 12～19ランダム整数 d = (1 << r) * K + 1 s, t: 1～min(p, q)ランダム整数 t_p = pow(s*p + 1, (d-1)/(1 << r), n) t_q = pow(t*q + 4, (d-1)/(1 << r), n)
このコードから以下のことがわかる。
t_p % p = 1
t_p - 1 はpの倍数のため、nとの最大公約数はpになる。pを算出できれば、qも算出でき、復号できる。
from Crypto.Util.number import * with open('output.txt', 'r') as f: params = f.read().rstrip().split('\n') n = int(params[0].split(' = ')[1]) t_p = int(params[1].split(' = ')[1]) t_q = int(params[2].split(' = ')[1]) enc = int(params[3].split(' = ')[1]) e = 65537 p = GCD(t_p - 1, n) q = n // p phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(enc, d, n) flag = long_to_bytes(m) print flag
ASIS{baby___RSA___f0r_W4rM_uP}
Elliptic Curve (CRYPTO)
$ nc 76.74.178.201 9531 Please submit a printable string X, such that sha512(X)[-6:] = f07013 and len(X) = 36 AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA.5N` ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + hi! There are three integer points such that (x, y), (x+1, y), and + + (x+2, y) lies on the elliptic curve E. You are given one of them!! + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | One of such points is: P = (61271155690342622475777210240075729710621342984654171453275106768277721560730, 10304534416315078468281913128100940831515761000045990722608570805012377026464) | Send the 36783583177328169872379599156505622641753749954083930952113653353114099382996 * P :
通常の楕円曲線暗号の式はこうなっている。
y^2 = x^3 + ax + b
3点のy^2は以下の式になる。
x^3 + ax + b (x+1)^3 + a(x+1) + b (x+2)^3 + a(x+2) + b
どれもmod mでは同じになるので、差分を取ってみる。
3x^2+3x+1 + a mの倍数 6x^2+12x+8 + a*2 mの倍数
以下もそれぞれmの倍数になる。
6x^2+6x+2 + a*2 6x^2+12x+8 + a*2
再度差分をとる。
6x+6 -> mの倍数
数値の大きさを考えると、x + 1がmになる。あとは逆算して、Pがx, x+1, x+2なのか総当たりして、整合の取れるa, bを割り出す。楕円曲線を割り出せば、掛け算は簡単にできる。
#!/usr/bin/env sage import socket import re import itertools from hashlib import * from string import * def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) def check(px, py, a, b, m): left = pow(py, 2, m) for i in range(3): right =(pow(px + i, 3, m) + a * (px + i) + b) % m if left != right: return False return True def get_param(P): px, py = P[0], P[1] for i in range(3): px, py = P[0] - i, P[1] m = px + 1 a = (- (3 * pow(px, 2, m) + 3 * px + 1)) % m b = (pow(py, 2, m) - pow(px, 3, m) - a * px) % m if check(px, py, a, b, m): return a, b, m s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('76.74.178.201', 9531)) data = recvuntil(s, '\n').rstrip() print data pattern = 'that (.+)\(X\)\[-6:\] = (.+) and len\(X\) = (.+)' m = re.search(pattern, data) alg = m.group(1) h_tail = m.group(2) length = int(m.group(3)) for c in itertools.product(printable, repeat=4): X = 'A' * (length - 4) + ''.join(c) if alg == 'md5': h = md5(X).hexdigest() elif alg == 'sha1': h = sha1(X).hexdigest() elif alg == 'sha224': h = sha224(X).hexdigest() elif alg == 'sha256': h = sha256(X).hexdigest() elif alg == 'sha384': h = sha384(X).hexdigest() elif alg == 'sha512': h = sha512(X).hexdigest() if h[-6:] == h_tail: print X s.sendall(X + '\n') break data = recvuntil(s, ':\n').rstrip() print data P = eval(data.split('\n')[4].split(' = ')[1]) mul = int(data.split('\n')[5].split(' ')[3]) a, b, m = get_param(P) print '[+] a =', a print '[+] b =', b print '[+] m =', m F = FiniteField(m) E = EllipticCurve(F, [a, b]) P = E.point(P) Q = mul * P ans = '(%d, %d)' % (Q[0], Q[1]) print ans s.sendall(ans + '\n') data = recvuntil(s, '\n').rstrip() print data
実行結果は以下の通り。
Please submit a printable string X, such that sha224(X)[-6:] = 267912 and len(X) = 12
AAAAAAAA0N(L
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ hi! There are three integer points such that (x, y), (x+1, y), and +
+ (x+2, y) lies on the elliptic curve E. You are given one of them!! +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| One of such points is: P = (65066134629160492064348712349740186777271493389550937509098916844574681320586, 48248814918191461731826799414487116812840317323816727541195008776899801930943)
| Send the 820108665267417045281300596834085575361835494744709817713694502692897533236 * P :
[+] a = 65066134629160492064348712349740186777271493389550937509098916844574681320586
[+] b = 53990383394489977569370811874725037797601425434476441150827563908083881493406
[+] m = 65066134629160492064348712349740186777271493389550937509098916844574681320587
(34467009194367032598721374049670461242650808585495568505537602087481887486236, 9994827249345438784791406640639494428843057321974593620798547257160588804430)
+ Congratz! You got the flag: ASIS{4n_Ellip71c_curve_iZ_A_pl4Ne_al9ebr4iC_cUrv3}
ASIS{4n_Ellip71c_curve_iZ_A_pl4Ne_al9ebr4iC_cUrv3}
Jazzy (CRYPTO)
$ nc 76.74.178.201 31337 ------------------------------------------------------------------------ | ..:: Jazzy semantically secure cryptosystem ::.. | | Try to break this cryptosystem and find the flag! | ------------------------------------------------------------------------ | Options: | | [E]ncryption function | | [F]lag (encrypted)! | | [P]ublic key | | [D]ecryption oracle | | [Q]uit | |----------------------------------------------------------------------| E def encrypt(msg, pubkey): h = len(bin(len(bin(pubkey)[2:]))[2:]) - 1 # dirty log :/ m = bytes_to_long(msg) if len(bin(m)[2:]) % h != 0: m = '0' * (h - len(bin(m)[2:]) % h) + bin(m)[2:] else: m = bin(m)[2:] t = len(m) // h M = [m[h*i:h*i+h] for i in range(t)] r = random.randint(1, pubkey) s_0 = pow(r, 2, pubkey) C = [] for i in range(t): s_i = pow(s_0, 2, pubkey) k = bin(s_i)[2:][-h:] c = bin(int(M[i], 2) ^ int(k, 2))[2:].zfill(h) C.append(c) s_0 = s_i enc = int(''.join(C), 2) return (enc, pow(s_i, 2, pubkey)) F encrypt(flag, pubkey) = (285758784511988734996792473393119507219268400756160874488063750970012467915603914014511645886290587479644916689702765288982490530761182115010199238742235569617597696074084710949703041926451477768488923143163705793951552963523691597617034555469758028567143898017221627069705001555110077L, 11896097786012729204042896056711423330078393488205177168674589714389521254117566447810993885197638822768474361823019961382063217167203871544286134412708823199961452263320874375426857360765259524437045571031538041889334087041205316752479519452535747774811510959598049621167541077584122625837505724476433494244407626451743303338695473369869483530950286291805711592895773930535900800442181458942182852016952168916670632553498445201350945714177114220766208169020336848779278287955888503441256633459790389912147651603467159704565649410170203574852996088637779083925921241270667395841563487878790181620271210991198827612699L) P pubkey = 18040131314759667900457887678811020338614452709739086777151261886360982985518169561129314249248164816441006297459740894967672603373312703776907273574074206737224822094608881506549036557750755680495923316080676241717075216668353540054463958510613526526645837706530243811433203943369331718185791900249855413712334649759751651752486518265906541150975961029763480805875588043774798010489437893678347331269414867612772205562413709274511832250021458133791314427494532479509859686223786822752348579164492316978993634125041564682289063366281011085245142709161055404879441983281236867346195208490289706759726107124209265927453 D | send an pair of integers, like (c, x), that you want to decrypt: (285758784511988734996792473393119507219268400756160874488063750970012467915603914014511645886290587479644916689702765288982490530761182115010199238742235569617597696074084710949703041926451477768488923143163705793951552963523691597617034555469758028567143898017221627069705001555110077, 11896097786012729204042896056711423330078393488205177168674589714389521254117566447810993885197638822768474361823019961382063217167203871544286134412708823199961452263320874375426857360765259524437045571031538041889334087041205316752479519452535747774811510959598049621167541077584122625837505724476433494244407626451743303338695473369869483530950286291805711592895773930535900800442181458942182852016952168916670632553498445201350945714177114220766208169020336848779278287955888503441256633459790389912147651603467159704565649410170203574852996088637779083925921241270667395841563487878790181620271210991198827612699) | this decryption is NOT allowed :P
暗号化の処理はこうなっている。
・h = pubkeyのbit長のbinの長さ-1
・m = msgの数値
・mのbinの長さがhの倍数になるよう先頭に0パディングし、mのbinをmにセットする。
・M: hバイトブロックの配列
・r: 1～pubkeyのランダム整数
・s_0 = pow(r, 2, pubkey)
・C: 空配列
・ブロック単位に以下を実行
・s_i = pow(s_0, 2, pubkey)
・k = bin(s_i)[2:][-h:]
・c = bin(int(M[i], 2) ^ int(k, 2))[2:].zfill(h)
・C配列にcを追加
・s_0 = s_i
・enc = int(''.join(C), 2)
・(enc, pow(s_i, 2, pubkey))を返却復号の方法はあるのかもしれないが、Deryption oracleの機能があるので、これを使う。flagの後ろにhビット適当なビットを付け暗号化することを考える。encは適当なビットをhビット分つけ、2つ目の要素はpow(flagの暗号化の2つ目の要素, 2, pubkey)にすることによって、最後に1ブロック追加して復号する。その後最後のブロックを切り落とせば、フラグになる。
import socket from Crypto.Util.number import long_to_bytes def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('76.74.178.201', 31337)) data = recvuntil(s, '-|\n').rstrip() print data print 'E' s.sendall('E\n') data = recvuntil(s, '\n\n').rstrip() print data + '\n' print 'F' s.sendall('F\n') data = recvuntil(s, '\n').rstrip() print data enc = eval(data.split(' = ')[1]) print 'P' s.sendall('P\n') data = recvuntil(s, '\n').rstrip() print data pubkey = int(data.split(' = ')[1]) print 'D' s.sendall('D\n') data = recvuntil(s, '\n').rstrip() print data h = len(bin(len(bin(pubkey)[2:]))[2:]) - 1 s_i = enc[1] k = bin(s_i)[2:][-h:] c = bin(0 ^ int(k, 2))[2:].zfill(h) try_enc0 = int(bin(enc[0])[2:] + c, 2) try_enc1 = pow(enc[1], 2, pubkey) try_enc = '(%d, %d)' % (try_enc0, try_enc1) print try_enc s.sendall(try_enc + '\n') data = recvuntil(s, '\n').rstrip() print data try_dec = int(data.split(' ')[-1]) m = int(bin(try_dec)[2:-h], 2) flag = long_to_bytes(m) print '\nflag =', flag
実行結果は以下の通り。
------------------------------------------------------------------------
| ..:: Jazzy semantically secure cryptosystem ::.. |
| Try to break this cryptosystem and find the flag! |
------------------------------------------------------------------------
| Options: |
| [E]ncryption function |
| [F]lag (encrypted)! |
| [P]ublic key |
| [D]ecryption oracle |
| [Q]uit |
|----------------------------------------------------------------------|
E
def encrypt(msg, pubkey):
h = len(bin(len(bin(pubkey)[2:]))[2:]) - 1 # dirty log :/
m = bytes_to_long(msg)
if len(bin(m)[2:]) % h != 0:
m = '0' * (h - len(bin(m)[2:]) % h) + bin(m)[2:]
else:
m = bin(m)[2:]
t = len(m) // h
M = [m[h*i:h*i+h] for i in range(t)]
r = random.randint(1, pubkey)
s_0 = pow(r, 2, pubkey)
C = []
for i in range(t):
s_i = pow(s_0, 2, pubkey)
k = bin(s_i)[2:][-h:]
c = bin(int(M[i], 2) ^ int(k, 2))[2:].zfill(h)
C.append(c)
s_0 = s_i
enc = int(''.join(C), 2)
return (enc, pow(s_i, 2, pubkey))
F
encrypt(flag, pubkey) = (8940461672871239904396425210700665180657020465062541424029649906697472058250469651625821009153594478927461459532465576604445511763388192757139578270624506967716574274109099577107091212260513412997524304533801744556391690382207973669584797229092692055232614328377194044613021282005374073L, 3985029591321212142027572568617540370962282303225246496445833927207837883485559990969344567945607188130778286620710335474559434388362148061626139763513264168427324412985299050661646804654783252354484383127209126608396936040956420419446409631693594866624082051933348963212434810974998599187512068545652459182045834487418200289375258861133097864647387858644910844050199349346498764197263314983627084690252102482320177288142732354418219511888499030670861507391303887717168625280559640704029228845601132185486839340571767534227257434838551037846236558450858285808865600613762878191923064139275962090745084604141463362187L)
P
pubkey = 9971199606729552628222257386990532090096760501090853093092182992223314447514207252045974609200181096675069707649549137130420568806519428741568433539282864905090260769752010050789746214176691579274689573106767413433003319737254568194329462679338338601616884560418513288068808387192900799931032976223086150059485299659117003903212308255416372731428233125537622063104850039714453784515567794688318277809980781539402354379856503568481181430295326145146988300521030767102697111116802000019944684734704240579331396628961585375399188303320716579263836607609381854120101976947186976524148392714937486336105984234463154682213
D
| send an pair of integers, like (c, x), that you want to decrypt:
(9155032753020149662101939415757481144992788956224042418206361504458211387648480923264840713373280746421720534561244750442952204045709509383310928149119495134941772056687717966957661401354765734909464887842612986425745090951380965037654832362590916664558197072258246701683733792773503051403, 1369813811910032868431403621033793846859607333872495643113969203078728246802372650645236351677618184631495926474948943808806827706625702448780601256912555209388949999726522586529989918763637360844603360324623910588769647291649033527175764367863039743471562763773101395463886809524055943301361399914228909333960773219184289265135207953989057403689783020056819265887315346195218033640972295791693350828062346541508865734958926817700643333736331187348628551718917200317756734945549243368148740035302255079436542526202564752616545748949708812197907849817605752961146203430606092765551948821822880484277931424658334420915)
| the decrypted message is: 23885573558187132942244816671712487138942420248121706838741164907657524845957633817140643875962135979817699302378095948610723200260054545827725186829201209741258267835315040457645335063210274437739420225908272783355589184781925137083935650510066490690335507268451389132152854994628158464
flag = ((((......:::::: Great! the flag is: ASIS{BlUM_G0ldwaS53R_cryptOsySt3M_Iz_HI9hlY_vUlNEr4bl3_70_CCA!?} ::::::......))))
ASIS{BlUM_G0ldwaS53R_cryptOsySt3M_Iz_HI9hlY_vUlNEr4bl3_70_CCA!?}
