BackdoorCTF 2018 Writeup

この大会は2018/3/18 0:30(JST)~2018/3/19 0:30(JST)に開催されました。
今回もチームで参戦。結果は1400点で123チーム中12位でした。
自分で解けた問題をWriteupとして書いておきます。

AWESOME-MIX1 (crypto 75)

$ nc 51.15.73.163 8082 
Welcome to admin's music portal.
To verify that you are the owner of this service
send the public key which will verify the following signature :

Message   -> super important information for admin only

Signature -> 43d04e6f9e22904576d5b2db818dcb82d88e733fb50a000ad5183d786f8136e9e2fdf11fe44825d63f7e94b90ddeddb66725a751086357edd6a62401cdbac16c08f801153475bd73f5dfb301007ef070cbac1390df9beb66b693025f822a8851672547d09f7c16466f07712b45d0d71b6559d272adc622d6a70d138f8e63fa64

コードを見ると、以下のような感じ。
s: Signatureの10進数値
e: 65537
n: ???
m: Messageのsha1(d5a8c16ad32b7e74ce624a17a1b3b2427c263389)
pad(m): 1ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff003021300906052b0e03021a05000414d5a8c16ad32b7e74ce624a17a1b3b2427c263389

pow(s, e, n) == pad(m)
になるようn, eを指定する。

eが小さいほうが計算が早い。3を指定してみる。

import socket
import re
from Crypto.Hash import SHA

def PKCS1_pad(data):
    asn1 = '003021300906052b0e03021a05000414'
    ans = asn1 + data
    n = len(ans)
    padding = '0001' + 'f' * (1024/4 - n - 4)
    return int((padding + ans), 16)

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('51.15.73.163', 8082))

data = s.recv(1024)
print data

pattern = 'Signature -> (.+)'
m = re.search(pattern, data)
sig = int(m.group(1), 16)

e = 3

message = 'super important information for admin only'
h = SHA.new(message)
m = h.hexdigest()
pad = PKCS1_pad(m)

n = pow(sig, e) - pad
print n
s.sendall(str(n) + '\n')
print e
s.sendall(str(e) + '\n')

data = s.recv(2048)
print data

実行結果は以下の通り。

Welcome to admin's music portal.
To verify that you are the owner of this service
send the public key which will verify the following signature :

Message   -> super important information for admin only

Signature -> 9db600326a7bfb115481fe078bd12420e91e25d2f63c576253bbda1d240bace75202e5ba5f2fefe9a924258fb47075c5f09880ce0b93bb36e3bba09a69a97de1882fb839363b772e2977c79ba6ff5e67e9e1269f801d6ace9b47171428d917b9cf44e004a242465c821e1aafbeec6077a30c4c47d04ea652e12003df01aba4a0


1358351756754439312376868517955764942617308500821039660391447768219172433407484471720434149398588844051224479476097704653260474521147742197752337211618966969538754558752563625400109949008415884153605726213293179622115349501037957509039084994777112650517856558748051951763910727845519040438532345138108852221060969539008224431649734657173412735827457060186339830910314705536016907064167093349446851226543539586673303923129991164372535641355318540931749183979990122857942574477002602542887612625641000776776563335089371858750840107955118115215185306002698984648597764979075369578200879233516411633397568715792727319942793246729625042550167470345283544356104574756696443518372751117534027952587102670844179898224868761719628957044212603094793130289162603581972325228525246424445218647529216591533294284328042930489863126762952371168966851776626727260187444811963991442153194089236603252815872488778433467803642501454097130474615
3
Enter n:Enter e:

I'm an alligator,
I'm a mama-papa coming for you
I'm the space invader,
I'll be a rock-and-rolling bitch for you

Keep your mouth shut,
You're squawking like a pink monkey bird
And I'm busting up my brains for the words

Keep your 'lectric eye on me babe
Put your ray gun to my head
Press your space face close to mine, love
Freak out in a moonage daydream oh yeah!

Don't fake it baby,
Lay the real thing on me
The church of man, love
Is such a holy place to be

Make me baby,
Make me know you really care
Make me jump into the air

Keep your 'lectric eye on me babe
Put your ray gun to my head
Press your space face close to mine, love
Freak out in a moonage daydream oh yeah!

Keep your 'lectric eye on me babe
Put your ray gun to my head
Press your space face close to mine, love
Freak out in a moonage daydream oh

Keep your 'lectric eye on me babe
Put your ray gun to my head
Press your space face close to mine, love
Freak out in a moonage daydream oh yeah

Freak out, far out, in out

CTF{cryp70_5ur3_15_w13rd}
$ echo -n CTF{cryp70_5ur3_15_w13rd} | sha256sum
93b7d01e2d60c22e5cc3033a86bc9ed577208139581bbae48397b2d656f285d6  -
93b7d01e2d60c22e5cc3033a86bc9ed577208139581bbae48397b2d656f285d6

BIT-LEAKER (crypto 150)

$ nc 51.15.73.163 8083
Welcome to BACKDOORCTF17

PublicKey:

N = 132125452490525272868512719086793824829543883912463086176670664838620633007182240166809947589097680911394793693935584719583603365100626341570568318241861642033202935437181211455076573287843223083918457652758292409212221952378430472710490094002780866599756159336468032017382896815282341434169411799424271491121

e = 65537

c = 12379713349101636227902832624035022346592359493481761589607599941163359935793354396977060791877242742663032926986094100616765497355165937197518287465298505258856776800007343292387728699031072357239640226196638363477668914730912679200629657016016233437304130727476028235554577343009967662591789799781285410844

temp_c =123
 l = 8638
temp_c =456789
 l = 2082
temp_c: 入力
temp_m = pow(temp_c, key.d, key.n)

指定した暗号に対して、復号結果の情報の一部を以下の情報として表示させる。

l = str(((temp_m&5) * random.randint(1,10000))%(2*(random.randint(1,10000))))

ランダムの数値を使っているが、以下のことがわかる。

[復号数値&5] * [ランダムA] % (2 * ランダムB)
・この結果が奇数のときは必ず復号数値は奇数
・この結果が偶数のときは復号数値は偶奇どちらも可能性がある。
 ⇒10回くらい試して、すべて偶数の場合偶数と判断する。
  1回でも奇数の場合があった場合は奇数を判断する。

以上の情報から、LSB decryption oracle attackで復号する。

from fractions import Fraction
import socket
import re

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

def lsb_oracle(s, cipher):
    for i in range(10):
        data = recvuntil(s, 'temp_c =')
        print data + str(cipher)
        s.sendall(str(cipher) + '\n')
        data = recvuntil(s, '\n')
        print data

        l = int(data.split(' = ')[1])
        if l % 2 == 1:
            return 1
    return 0

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('51.15.73.163', 8083))
data = recvuntil(s, '\n').strip()
print data
data = recvuntil(s, '\n').strip()
print data
data = recvuntil(s, '\n').strip()
print data
data = recvuntil(s, '\n').strip()
print data
data = recvuntil(s, '\n').strip()
print data
N = int(data.split(' = ')[1])
data = recvuntil(s, '\n').strip()
print data
data = recvuntil(s, '\n').strip()
print data
e = int(data.split(' = ')[1])
data = recvuntil(s, '\n').strip()
print data
data = recvuntil(s, '\n').strip()
print data
c = int(data.split(' = ')[1])

bounds = [0, Fraction(N)]

i = 0
m = 0
while True:
    print 'Round %d' % (i+1)
    i += 1

    c2 = (c * pow(2, e, N)) % N
    lsb = lsb_oracle(s, 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 = ('%x' % m).decode('hex')
print flag

実行結果は以下の通り。

    :
Round 1024
temp_c =35787795981286419742136296604317346853455644236933262220366195275020097573849339965175921268712745735906219041017373711598867167379282050083120679226952404156408554223787296491985019760199325109854563160312420870232970499884525855365692632209687348163871549869814935790064329250398905518396441921378974751032
 l = 1675

0
CTF{r1v35t_5h4m1r_4dl3m4n_cr4ck1ng_15_fun_:)}
$ echo -n CTF{r1v35t_5h4m1r_4dl3m4n_cr4ck1ng_15_fun_:\)} | sha256sum
744dc1a4f946892bba87b6dd7b4bf001cc80cf5d4f1141b0274b148de87b8d2c  -
744dc1a4f946892bba87b6dd7b4bf001cc80cf5d4f1141b0274b148de87b8d2c