この大会は2021/4/4 7:00(JST)～2021/4/6 7:00(JST)に開催されました。
今回もチームで参戦。結果は1091点で297チーム中60位でした。
自分で解けた問題をWriteupとして書いておきます。
sanity (sanity)
Discordに入り、#announcementsチャネルのメッセージを見ると、フラグが書いてあった。
flag{enjoy_our_cruel_angels_thesis}
Unlucky Strike (Crypto)
サーバの処理は以下の通り。
・getTicket() ・nums: Nballs-1個のランダム2バイトの数値の配列 ・traw: "numbers:" + numsの数値の,区切りの文字列 ・IV: 16バイトランダム文字列 ・ticket: IV + 「traw + "," + JOKER」のAES-CBC暗号化 ・ticketをbase64暗号化して返す。 →表示 ・numbers: Nballs個のランダム3バイトの数値の配列 →表示 ・以下繰り返し ・t: 入力 ・redeemTicket(t) →Trueの場合、ループから抜ける ・traw: tをAES-CBC復号(unpkcs7関数でパディングチェックをしている) ・nums: trawで"numbers:"の後ろの,区切りの数値Nballs分の配列(JOKERまで) ・上記で表示されたnumbersの数値がすべて含まれていたら、フラグが表示される。
CBC Padding Oracleで攻撃すれば良さそう。
IVを含み先頭32バイトはそのまま使わないと"numbers:"が含まれないことに注意する。
import socket from Crypto.Util.strxor import strxor import base64 def recvuntil(s, tail): data = '' while True: if tail in data: return data data += s.recv(1) def pad(s): return s + (16 - len(s) % 16) * chr(16 - len(s) % 16) def is_valid(s, t): b = base64.b64encode(t) data = recvuntil(s, ':\n').rstrip() #print data s.sendall(b + '\n') data = recvuntil(s, '\n').strip() #print data if data == 'that is an invalid ticket': return False else: return True s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('chal.b01lers.com', 25003)) data = recvuntil(s, 'ticket:\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data ticket0 = base64.b64decode(data) data = recvuntil(s, 'are:\n').rstrip() print data data = recvuntil(s, '\n').rstrip() print data numbers = eval(data) pt = 'numbers:' for num in numbers: pt += str(num) pt += ',' pt += '0' pt = pad(pt) pt_blocks = [pt[i:i+16] for i in range(0, len(pt), 16)] ct_blocks = ['\x00' * 16] * (len(pt_blocks) + 1) ct_blocks[-1] = ticket0[-16:] HEAD_BLOCKS = ticket0[:32] for i in range(len(ct_blocks)-1, 0, -1): xor_block = '' for j in range(16): print '%d - %d: %s' % (i, j, xor_block.encode('hex')) for code in range(256): try_pre_block = '\x00' * (16 - j - 1) + chr(code) + strxor(xor_block, chr(j+1)*j) try_cipher = HEAD_BLOCKS + try_pre_block + ct_blocks[i] if is_valid(s, try_cipher): xor_code = (j+1) ^ code xor_block = chr(xor_code) + xor_block break ct_blocks[i - 1] = strxor(xor_block, pt_blocks[i - 1]) ticket = ''.join(ct_blocks) b64_ticket = base64.b64encode(ticket) data = recvuntil(s, ':\n').rstrip() print data s.sendall(b64_ticket + '\n') data = recvuntil(s, '\n').strip() print data
実行結果は以下の通り。
--------------------------------------------
Welcome to the 2021 B01lers Crypto Town Fair
--------------------------------------------
Due to popular demand, our Super Jackpot Lottery [TM] returns this year as well. We are
so confident in our not-entirely-fair algorithm that we are publicly releasing its source
code. Chances for winning have never been smaller! Prizes have never been bigger!!!
Here is your complimentary raffle ticket:
h2iaenpqMU0lzYJWSqgzjJH0fiOFMe4fFohNvfEJNDxoojSd9EpEf5A/FHxyVxMgoTlZenq8qr3/xv2W7umfmteksNKKFD8BnJIq5xACD6KJYaXO8fRasae2spIQ8cf7
Draw commencing... [drumroll]... and the winning numbers are:
[10917928, 3129816, 6588047, 5779531, 15913246]
4 - 0:
4 - 1: a3
4 - 2: 09a3
4 - 3: 0409a3
4 - 4: 160409a3
4 - 5: e1160409a3
4 - 6: 2ce1160409a3
4 - 7: 942ce1160409a3
4 - 8: 9a942ce1160409a3
4 - 9: 079a942ce1160409a3
4 - 10: 39079a942ce1160409a3
4 - 11: 1239079a942ce1160409a3
4 - 12: cf1239079a942ce1160409a3
4 - 13: 91cf1239079a942ce1160409a3
4 - 14: e591cf1239079a942ce1160409a3
4 - 15: e5e591cf1239079a942ce1160409a3
3 - 0:
3 - 1: db
3 - 2: 3edb
3 - 3: de3edb
3 - 4: 52de3edb
3 - 5: ec52de3edb
3 - 6: f6ec52de3edb
3 - 7: 3ef6ec52de3edb
3 - 8: 283ef6ec52de3edb
3 - 9: 70283ef6ec52de3edb
3 - 10: d970283ef6ec52de3edb
3 - 11: c3d970283ef6ec52de3edb
3 - 12: 92c3d970283ef6ec52de3edb
3 - 13: d892c3d970283ef6ec52de3edb
3 - 14: f2d892c3d970283ef6ec52de3edb
3 - 15: 2ef2d892c3d970283ef6ec52de3edb
2 - 0:
2 - 1: e4
2 - 2: 1de4
2 - 3: 6a1de4
2 - 4: 236a1de4
2 - 5: 95236a1de4
2 - 6: 3f95236a1de4
2 - 7: 7e3f95236a1de4
2 - 8: 267e3f95236a1de4
2 - 9: 09267e3f95236a1de4
2 - 10: 5f09267e3f95236a1de4
2 - 11: 0c5f09267e3f95236a1de4
2 - 12: 540c5f09267e3f95236a1de4
2 - 13: da540c5f09267e3f95236a1de4
2 - 14: 02da540c5f09267e3f95236a1de4
2 - 15: c802da540c5f09267e3f95236a1de4
1 - 0:
1 - 1: b9
1 - 2: f4b9
1 - 3: eef4b9
1 - 4: f9eef4b9
1 - 5: a2f9eef4b9
1 - 6: a5a2f9eef4b9
1 - 7: 67a5a2f9eef4b9
1 - 8: c567a5a2f9eef4b9
1 - 9: 9ec567a5a2f9eef4b9
1 - 10: 2d9ec567a5a2f9eef4b9
1 - 11: 962d9ec567a5a2f9eef4b9
1 - 12: 9b962d9ec567a5a2f9eef4b9
1 - 13: c69b962d9ec567a5a2f9eef4b9
1 - 14: 6cc69b962d9ec567a5a2f9eef4b9
1 - 15: b36cc69b962d9ec567a5a2f9eef4b9
Redeem a ticket:
**JACKPOT** -> Here is your reward: bctf{be_v4ry_of_pr0pr13t4ry_c0de_and_don7_exp3ct_f4ir_rngs..}
bctf{be_v4ry_of_pr0pr13t4ry_c0de_and_don7_exp3ct_f4ir_rngs..}
RSASSS (Crypto)
son1～son3にRSA暗号のパラメータが渡されているので、まずは復号する。
son1のRSA暗号パラメータではeが小さく、cもnに比べてかなり小さいので、Low Public Exponent Attackで復号する。
from Crypto.Util.number import * import gmpy N = 97047969232146954924046774696075865737213640317155598548487427318856539382020276352271195838803309131457220036648459752540841036128924236048549721616504194211254524734004891263525843844420125276708561088067354907535207032583787127753999797298443939923156682493665024043791390402297820623248479854569162947726288476231132227245848115115422145148336574070067423431126845531640957633685686645225126825334581913963565723039133863796718136412375397839670960352036239720850084055826265202851425314018360795995897013762969921609482109602561498180630710515820313694959690818241359973185843521836735260581693346819233041430373151 e = 3 c = 6008114574778435343952018711942729034975412246009252210018599456513617537698072592002032569492841831205939130493750693989597182551192638274353912519544475581613764788829782577570885595737170709653047941339954488766683093231757625 m = gmpy.root(c, e)[0] flag1 = long_to_bytes(m) print flag1
実行結果は以下の通り。
(1, 132156498146518935546534654)
次にson2のRSA暗号パラメータでは、eが16で、2のべき乗となっている。
pow(m, e, p) = c % p pow(m, e, q) = c % q
上記をTonelli-Shanks Algorithmを使って平方剰余を4回行い、中国人剰余定理により復号する。
#!/usr/bin/python3 from Crypto.Util.number import * from sympy.ntheory.modular import crt def legendre(a, p): return pow(a, (p - 1) // 2, p) def tonelli_shanks(a, p): if legendre(a, p) != 1: raise Exception("not a square (mod p)") q = p - 1 s = 0 while q % 2 == 0: q >>= 1 s += 1 for z in range(2, p): if legendre(z, p) == p - 1: break m = s c = pow(z, q, p) t = pow(a, q, p) r = pow(a, (q + 1) // 2, p) t2 = 0 while True: if t == 0: return 0 if t == 1: return r t2 = (t * t) % p for i in range(1, m): if t2 % p == 1: break t2 = (t2 * t2) % p b = pow(c, 1 << (m - i - 1), p) m = i c = (b * b) % p t = (t * c) % p r = (r * b) % p def is_printable(s): for c in s: if c < 32 or c > 126: return False return True p = 7237005577332262213973186563042994240829374041602535252466099000494570602917 q = 88653318322320212121171535397276679450159832009631056842709712756058489880609 e = 16 c = 128067909105216284348808993695734979917384615977985008857494038384160720721127262500602107681721675827823420594821881043967947295783995842628815275429540 cp = c % p cq = c % q rs_p = [cp] for i in range(4): tmp_rs = [] for j in range(len(rs_p)): try: m = tonelli_shanks(rs_p[j], p) if m not in tmp_rs: tmp_rs.append(m) if p - m not in tmp_rs: tmp_rs.append(p - m) except: continue rs_p = tmp_rs rs_q = [cq] for i in range(4): tmp_rs = [] for j in range(len(rs_q)): try: m = tonelli_shanks(rs_q[j], q) if m not in tmp_rs: tmp_rs.append(m) if q - m not in tmp_rs: tmp_rs.append(q - m) except: continue rs_q = tmp_rs for r_p in rs_p: for r_q in rs_q: m = int(crt([p, q], [r_p, r_q])[0]) flag2 = long_to_bytes(m) if is_printable(flag2): print(flag2)
実行結果は以下の通り。
(2, 861352498496153254961238645321268413658613864351)
son3については、factordbでnを素因数分解する。
n = 1267650600228229401496703205653 * 2535301200456458802993406410833
あとはそのまま復号する。
629294375772413445978559434482906561379546104217158827579853
この数値を文字にしてもprintableな文字にならない。そこで再度問題文を見たら、以下の文が追加されていた。
NOTE: You will need to add 541893472927304311696017462663852715895951883676838007787557872016428N to the plaintext to recover the message after decrypting.
これを考慮して復号する。
from Crypto.Util.number import * def is_printable(s): for c in s: if ord(c) < 32 or ord(c) > 126: return False return True N = 3213876088517980551083924185487283336189331657515992206038949 e = 65537 c = 2941293819923490843589362205798232424837846370982721175905966 p = 1267650600228229401496703205653 q = 2535301200456458802993406410833 phi = (p - 1) * (q - 1) d = inverse(e, phi) m = pow(c, d, N) m += 541893472927304311696017462663852715895951883676838007787557872016428 * N flag3 = long_to_bytes(m) print flag3
実行結果は以下の通り。
(3, 3145756504701717246281836139538967176547517737056)
SSSで3者の情報が最低限必要なので、2次方程式に載るはず。son1～3で復号した3つの座標が以下の形式の方程式を満たす。
y = a * x**2 + b * x + c
3元方程式になるので、これを元にcを割り出せば、それが共有する情報となる。
import sympy from Crypto.Util.number import * share1 = 132156498146518935546534654 share2 = 861352498496153254961238645321268413658613864351 share3 = 3145756504701717246281836139538967176547517737056 a = sympy.Symbol('a') b = sympy.Symbol('b') c = sympy.Symbol('c') eq1 = a + b + c - share1 eq2 = a * 4 + b * 2 + c - share2 eq3 = a * 9 + b * 3 + c - share3 ans = sympy.solve([eq1, eq2, eq3]) m = ans[c] flag = long_to_bytes(m) print flag
bctf{Mr._Ad1_5ham1r}
