この大会は2018/3/2 16:30(JST)～2018/3/4 16:30(JST)に開催されました。
今回もチームで参戦。結果は2800点で606チーム中11位でした。
自分で解けた問題をWriteupとして書いておきます。
Improper encryption (Crypto 100)
M1に対する平文の中の sAldnJfpUGlciN の位置、アルファベットだけでXOR暗号の復号できる場所を探す。
import string M1 = '2d142303073d05392c3d3e273c2a1a211f082b280d2d0e332025380301352a122a151c3a342e362d2723171904011c0c0c292b3d0122063e2e1e2a08102a2d3d0b2e102123141c280f0c373d2b380d3d0301301f2d281935233239330f3a102b123b0d2a' M2 = '29190f1b18390707093a290b2d0b113f37332533333a0c3d1a29160a2f100a1d0034323b1b2e1225252500182531391d13260c21211019242d0a0a123b362d232d3a3a0a083c0e363c183a032b332d252c5637252d047b522a1e462a2a2909081705033d' M3 = '15350a23053f04272a2f12113a2137202a3022081616090c32162b0b32333413161725072508391f3c36192e1e1e37030b361a2a26163337130628020b34352d1a2e143d3f0a1b1d13012a19223c2b1f0c172b3406033808061d1a2306133011080e1839' m1 = M1.decode('hex') m2 = M2.decode('hex') m3 = M3.decode('hex') pw = 'sAldnJfpUGlciN' def isAlp(s): for c in s: if c not in string.letters: return False return True def decrypt(s, key): dec = '' for i in range(len(s)): code = ord(s[i]) ^ ord(key[i%len(key)]) dec += chr(code) return dec keys = [] for i in range(len(m1) - len(pw) + 1): key = '' shift = i % len(pw) for j in range(len(pw)): code = ord(m1[i+j]) ^ ord(pw[j]) key += chr(code) if isAlp(key): if shift == 0: keys.append(key) else: keys.append(key[-shift:] + key[:len(pw)-shift]) for key in keys: r1 = decrypt(m1, key) r2 = decrypt(m2, key) r3 = decrypt(m3, key) idx = r1.find(pw) if idx % 14 == 0: print '*** %s ***' % key print r1 print r2 print r3
実行すると、ある71-84バイト部分が復号できる。
*** oichYwMHXzobYQ ***
B}@k^JHqtGQEe{uH|`r_@eVIOGaRn\IzsbQrlTYO~rxpgiE{AasGn@_oAwI`I]`uSTCzEsAldnJfpUGlciNBAz]zEt{W@IKjbC
FplsANJOQ@FitZ~VT[|D~rTGuKO[@yiuYCsCT}G|toqFY`j^nT[Nr@uBcizbA`ku@UhQma__pctf{u_C4ntBm:sibrSfjNTlT3
z\iK\HIorU}scpXIIX{[^Qv]trZ]ZW{O`hO}rV}egvG}vntF~BPItjf|oKjRCxeBT{_f[ttpisnotsecureij[`_jWk^i_sQ_wP
71-84バイト部分はそれぞれ以下のようになっている。
M1: sAldnJfpUGlciN
M2: a__pctf{u_C4nt
M3: ttpisnotsecureM3の一部の平文14バイトは繰り返すことを考慮する。
85-98バイト部分もM3の復号が ttpisnotsecure になるようM2も復号する。
import string M1 = '2d142303073d05392c3d3e273c2a1a211f082b280d2d0e332025380301352a122a151c3a342e362d2723171904011c0c0c292b3d0122063e2e1e2a08102a2d3d0b2e102123141c280f0c373d2b380d3d0301301f2d281935233239330f3a102b123b0d2a' M2 = '29190f1b18390707093a290b2d0b113f37332533333a0c3d1a29160a2f100a1d0034323b1b2e1225252500182531391d13260c21211019242d0a0a123b362d232d3a3a0a083c0e363c183a032b332d252c5637252d047b522a1e462a2a2909081705033d' M3 = '15350a23053f04272a2f12113a2137202a3022081616090c32162b0b32333413161725072508391f3c36192e1e1e37030b361a2a26163337130628020b34352d1a2e143d3f0a1b1d13012a19223c2b1f0c172b3406033808061d1a2306133011080e1839' m1 = M1.decode('hex') m2 = M2.decode('hex') m3 = M3.decode('hex') r3_parts = 'ttpisnotsecure' def xor_str(s1, s2): key = '' for i in range(len(s1)): code = ord(s1[i]) ^ ord(s2[i]) key += chr(code) return key key1 = xor_str(r3_parts, m3[70:84]) key2 = xor_str(r3_parts, m3[84:98]) m_part1 = [m1[70:84], m2[70:84], m3[70:84]] r_part1 = [] for i in range(3): r_part1.append(xor_str(m_part1[i], key1)) m_part2 = [m1[84:98], m2[84:98], m3[84:98]] r_part2 = [] for i in range(3): r_part2.append(xor_str(m_part2[i], key2)) for i in range(3): print r_part1[i] + r_part2[i]
実行結果は以下の通り。
：
sAldnJfpUGlciN__QTVALdzLCOhP
a__pctf{u_C4nt_s33_m3}__Zlmn
ttpisnotsecurettpisnotsecure
pctf{u_C4nt_s33_m3}
Quite an EC task (Crypto 200)
楕円曲線暗号なので、以下が成り立つ。
>
y^2 = x^3 + a*x + b mod n
→b = y^2 - x^3 - a*x mod n
この場合は以下の文字になるので、まずはBを求める。
a -> A b -> B n -> M
M = 93556643250795678718734474880013829509320385402690660619699653921022012489089 A = 66001598144012865876674115570268990806314506711104521036747533612798434904785 P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926) x = P[0] y = P[1] B = (pow(y, 2) - pow(x, 3) - A * x) % M print 'B =', B
実行すると、Bの値がわかる。
B = 25255205054024371783896605039267101837972419055969636393425590261926131199030
Bの値はわかったので、Pohlig–Hellman algorithmを使って、nを求める。
# solve.sage M = 93556643250795678718734474880013829509320385402690660619699653921022012489089 A = 66001598144012865876674115570268990806314506711104521036747533612798434904785 B = 25255205054024371783896605039267101837972419055969636393425590261926131199030 P = (56027910981442853390816693056740903416379421186644480759538594137486160388926, 65533262933617146434438829354623658858649726233622196512439589744498050226926) Q = (61124499720410964164289905006830679547191538609778446060514645905829507254103, 2595146854028317060979753545310334521407008629091560515441729386088057610440) F = FiniteField(M) E = EllipticCurve(F, [A,B]) P = E.point(P) Q = E.point(Q) factors, exponents = zip(*factor(E.order())) primes = [factors[i] ^ exponents[i] for i in range(len(factors))][:-2] dlogs = [] for fac in primes: t = int(P.order()) / int(fac) dlog = discrete_log(t*Q, t*P, operation='+') dlogs += [dlog] n = crt(dlogs,primes) print 'n =', n
実行した結果、nがわかった。
152977126447386808276536247114
Rivest, Shamir and Aldeman’s quest (Crypto 200)
$ nc 128.199.224.175 34000 Enter encrypted message (in HEX) :- 10 Decrypted message :- In HEX :- 5954815972c69c0428f17ae1aeb74c32f2c23d075b9958718cf5169ab359fedd1c9af4fbdf73fe52155bcdca461db65a2685628f079c55d96f6cd13e9ccb87e87f9183ca8a032fe4b0bfe4d120d7f5824bba874da9a31df1a638124bbd10b7e7a543ca547a0af84c6a78fc3c77da25a16e37a957d2c2c211610adb75033b00b7 In ASCII :- The decrypted message is not a valid ASCII text. $ nc 128.199.224.175 34000 Enter encrypted message (in HEX) :- 1000 Decrypted message :- In HEX :- 5954815972c69c0428f17ae1aeb74c32f2c23d075b9958718cf5169ab359fedd1c9af4fbdf73fe52155bcdca461db65a2685628f079c55d96f6cd13e9ccb87e87f9183ca8a032fe4b0bfe4d120d7f5824bba874da9a31df1a638124bbd10b7e7a543ca547a0af84c6a78fc3c77da25a16e37a957d2c2c211610adb75033b00b7 In ASCII :- The decrypted message is not a valid ASCII text.
面倒なことに入力、出力のHEXコードはリトルエンディアン。このことに注意しながら、LSB decryption oracle attackで復号する。
from fractions import Fraction import socket import re def i2hex(i): h = '%0256x' % i h = h[::-1] rev_i = '' for j in range(0, len(h), 2): s = h[j+1] + h[j] rev_i += s return rev_i def hex2i(h): h = h[::-1] rev_i = '' for j in range(0, len(h), 2): s = h[j+1] + h[j] rev_i += s return int(rev_i, 16) def lsb_oracle(cipher): cipher = i2hex(cipher) s = socket.socket(socket.AF_INET, socket.SOCK_STREAM) s.connect(('128.199.224.175', 34000)) data = s.recv(512) #print data + cipher s.sendall(cipher + '\n') data = s.recv(512) #print data pattern = 'In HEX :- \n(.+)\n\nIn' m = re.search(pattern, data, re.DOTALL) p = hex2i(m.group(1).strip()) return p % 2 c = hex2i('a0b75ef5dfd9ab0de9aa8c36a9c5aa28a924128a62826740ac3986efac69e2b85fc0df803e80da04c5f803726689e5f3134178de3cb203f6aebca22b376f7205d93a7224aca82cbbdc382200a1749fee095dfebe2aaabf99b622e4343bf5423cf6527433e26273e67d576157bf65a9258f613be9ad88d7b50350a89e676ae462') n = 0x00b961cd4db6cca2c5ec44d1e669e52b850574a5575c093aa740d223a7b42a48ed3d478ac3e910c793d29fda13f23cecd00bd0acbdcdb70ab1f6d5e9821b85153f3981f207cf5fa20fcdf5e4e432b1d3fbb3b012d7d270400d5c67c99abaeb2ff3c08e5b29c807b1243a297387ff06443c0977dbf2f284a948d45c1696eba459bf e = 65537 bounds = [0, Fraction(n)] i = 0 m = 0 while True: print i i += 1 c2 = (c * pow(2, e, n)) % n lsb = lsb_oracle(c2) if lsb == 1: bounds[0] = sum(bounds)/2 else: bounds[1] = sum(bounds)/2 diff = bounds[1] - bounds[0] diff = diff.numerator / diff.denominator print diff if diff == 0: m = bounds[1].numerator / bounds[1].denominator break c = c2 flag = i2hex(m).decode('hex') print flag
pctf{13xtb0Ok^Rs4+is`vUln3r4b1e,p4D~i1}
