HCTF 2018 Writeup

この大会は2018/11/9 21:00(JST)~2018/11/11 21:00(JST)に開催されました。
今回もチームで参戦。結果は 916.6点で1466チーム中55位でした。

xor game (Crypto)

暗号化データをBase64デコードして、XOR Cracker(https://wiremask.eu/tools/xor-cracker/)にかける。

from Crypto.Util.strxor import strxor
import base64

def dec(data, key):
    key = (key * (len(data) / len(key) + 1))[:len(data)]
    return strxor(data, key)

with open('cipher.txt', 'r') as f:
    data = f.read()

b64enc = base64.b64decode(data)
with open('cipher', 'wb') as f:

## arrange ##
print dec(b64enc, 'xor_is_interesting!@#')


Life, thin and light-off time and time again
Frivolous tireless
I heard the echo, from the valleys and the heart
Open to the lonely soul of sickle harvesting
Repeat outrightly, but also repeat the well-being of
Eventually swaying in the desert oasis
I believe I am
Born as the bright summer flowers
Do not withered undefeated fiery demon rule
Heart rate and breathing to bear the load of the cumbersome
I heard the music, from the moon and carcass
Auxiliary extreme aestheticism bait to capture misty
Filling the intense life, but also filling the pure
There are always memories throughout the earth
I believe I am
Died as the quiet beauty of autumn leaves
Sheng is not chaos, smoke gesture
Even wilt also retained bone proudly Qing Feng muscle
I hear love, I believe in love
Love is a pool of struggling blue-green algae
As desolate micro-burst of wind
Bleeding through my veins
Years stationed in the belief
I believe that all can hear
Even anticipate discrete, I met the other their own
Some can not grasp the moment
Left to the East to go West, the dead must not return to nowhere
See, I wear Zan Flowers on my head, in full bloom along the way all the way
Frequently missed some, but also deeply moved by wind, frost, snow or rain
Prajna Paramita, soon as soon as
life be beautiful like summer flowers and death like autumn leaves
Also care about what has

xor?rsa (Crypto)

$ nc rsa.2018.hctf.io 10086
Welcome to flag getting system
give me your token > 2jrCI4AslZF63Or3g0BCLzKoe0rXGTYZ
now give me you answer


p = 1024ビットランダム素数
q = 1024ビットランダム素数
n = p * q
e = 5
kbits = nのビット数 // (2*e*e)
m1 = nのビット数のランダム整数
m2 = m1 ^ kbitsのランダム整数
c1 = pow(m1, e, n)
c2 = pow(m2, e, n)

m1とm2を求める問題。kbitsが上記の定義なので、m1とm2の差は小さく、Coppersmith's Short Pad Attackでそれぞれ復号できる。

# solve.sage
import socket

def recvuntil(s, tail):
    data = ''
    while True:
        if tail in data:
            return data
        data += s.recv(1)

def short_pad_attack(c1, c2, e, n):
    PRxy.<x,y> = PolynomialRing(Zmod(n))
    PRx.<xn> = PolynomialRing(Zmod(n))
    PRZZ.<xz,yz> = PolynomialRing(Zmod(n))

    g1 = x^e - c1
    g2 = (x+y)^e - c2

    q1 = g1.change_ring(PRZZ)
    q2 = g2.change_ring(PRZZ)

    h = q2.resultant(q1)
    h = h.univariate_polynomial()
    h = h.change_ring(PRx).subs(y=xn)
    h = h.monic()

    kbits = n.nbits()//(2*e*e)
    diff = h.small_roots(X=2^kbits, beta=0.5)[0]

    return diff

def related_message_attack(c1, c2, diff, e, n):
    PRx.<x> = PolynomialRing(Zmod(n))
    g1 = x^e - c1
    g2 = (x+diff)^e - c2

    def gcd(g1, g2):
        while g2:
            g1, g2 = g2, g1 % g2
        return g1.monic()

    return -gcd(g1, g2)[0]

token = '2jrCI4AslZF63Or3g0BCLzKoe0rXGTYZ'

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('rsa.2018.hctf.io', 10086))

data = recvuntil(s, '> ')
print data + token
s.sendall(token + '\n')
data = recvuntil(s, '\n').strip()
print data
n = Integer(data[2:])
e = 5
data = recvuntil(s, '\n').strip()
print data
c1 = Integer(data[3:])
data = recvuntil(s, '\n').strip()
print data
c2 = Integer(data[3:])

diff = short_pad_attack(c1, c2, e, n)
m1 = related_message_attack(c1, c2, diff, e, n)
m2 = m1 + diff

data = recvuntil(s, '\n').strip()
print data
print m1
s.sendall(str(m1) + '\n')
print m2
s.sendall(str(m2) + '\n')
data = s.recv(1024)
print data