Pragyan CTF 2018 Writeup

この大会は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: ttpisnotsecure

M3の一部の平文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}