HCTF 2018 Writeup

この大会は2018/11/9 21:00(JST)～2018/11/11 21:00(JST)に開催されました。
今回もチームで参戦。結果は 916.6点で1466チーム中55位でした。
自分で解けた問題をWriteupとして書いておきます。

xor game (Crypto)

xorの鍵が不明で、その鍵を突き止める問題。
暗号化データを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:
    f.write(b64enc)

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

これを実行すると、きちんと復号できていることが分かる。

Life, thin and light-off time and time again
Frivolous tireless
one
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
Bored
Two
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
Occult
Three
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
Four
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
Five
Prajna Paramita, soon as soon as
life be beautiful like summer flowers and death like autumn leaves
Also care about what has

hctf{xor_is_interesting!@#}

xor?rsa (Crypto)

$ nc rsa.2018.hctf.io 10086
Welcome to flag getting system
give me your token > 2jrCI4AslZF63Or3g0BCLzKoe0rXGTYZ
n=25275261816080723577383625252321605813293020177515415346273626867915569138289688717413356558193996845476305528125832070604557462428746989292112808118629779995853500422163753237317584703994425361069816700082487715542167171713699666726887235382197073068733120714572524136047731843566904816054447149749558432678912765881098765528412138624603442724195067422316458776382746088522690538448161527517375561342031327658770828995835520042246472144202767031798115768655362628916139166585435054566298105440647015024307766333320215539234184515515996807842360812897141090870808136031078799184603768964924810402365848053621310874371
c1=11165085713561189003280953910551795650069641727697255665204270392356119682302194809551085381412459067137708791048033212887178854783178521082866084322294736924387003502539404006446446960913768668751546334339464672969536040183161881553997971542237143014930493145940738807334373127733697348176468962798526646137597541643569114699950367076718329916819155968155932149333397328469867074678751467552042630972042728542318490144115620371495906795551552788089985932610796897659179997445268713553678805380667254387708279651188394366215609009582176348204515365158369592961753687386325076074438007962972262423575684012468736502784
c2=3692619448894086202620380631082268435018623838407343923441472120868415709925497517010788618542797329154197746377107382855787882364201552243204454392390226061058770734934557129438642712750088115325177185876919748092262061559995643597615670605259279309223337082989077402836087239826642767218219888576126501421187433421552115165902886235999884421474474839807257919154091416829866712451600989516801908414284252064861856712338940516499148321453909303775761944595561080379704862572754567977567513085826683733515940571450314778688781004557900332788704156673505934867551765430160894036472529704734924702982507494191016739987
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

hctf{c81d20647f1ff3d55fc25626cd29ec4d95a3d66977973569a5a7a1b2487a1e9a}