Securinets CTF Quals 2018 Writeup

この大会は2018/3/25 4:00(JST)~2018/3/26 4:00(JST)に開催されました。
今回もチームで参戦。結果は5200点で216チーム中11位でした。
自分で解けた問題をWriteupとして書いておきます。

IRC (Misc 50)

IRCタグから#ctf_securinetsチャネルに入る。

Welcome to CTF Securinets Channel :D Flag{W3Lc0m3_T0_CTFSecurinets_Quals_2018}
Flag{W3Lc0m3_T0_CTFSecurinets_Quals_2018}

Easy (Reverse Engineering 100)

$ strings easy | grep Flag
Flag{This_Is_A_Hidden_Flag!!}
Flag{This_Is_A_Hidden_Flag!!}

looser (Crypto 150)

キー1文字でXORしていそう。PNGに復号することを想定して復号する。

with open('flag.png.crypt', 'rb') as f:
    c = f.read()

key = ord(c[0]) ^ 0x89

flag = ''
for i in range(len(c)):
    code = ord(c[i]) ^ key
    flag += chr(code)

with open('flag.png', 'wb') as f:
    f.write(flag)

f:id:satou-y:20180402213006p:plain

Flag{Hopefully_headers_are_constants}

The worst RSA Joke (Crypto 350)

公開鍵と暗号ファイルが与えられている。まず、公開鍵を見てみる。

$ openssl rsa -pubin -text < public.pem
Public-Key: (2049 bit)
Modulus:
    01:21:3b:05:7d:6f:de:bc:45:27:b5:b7:42:1a:c1:
    e9:3c:cf:fe:a7:6c:4f:08:74:99:1c:f3:fa:cf:0e:
    ab:9e:f6:46:a2:18:39:82:0b:4d:65:3a:91:6b:68:
    f2:58:e9:d3:f7:c2:ba:05:4e:4a:f0:5f:3e:4d:61:
    b3:de:77:2d:2a:d2:33:8b:0e:ae:6e:a0:8f:20:76:
    e4:e4:b0:8a:b2:09:20:fa:68:85:e6:c4:4d:ec:1b:
    ee:28:a8:76:53:c7:4b:cb:9e:9f:12:94:de:8a:48:
    bd:61:46:52:a3:d6:59:df:ce:7b:89:44:61:0f:25:
    bf:af:93:6e:9a:54:16:7c:4d:22:7d:16:d3:2e:65:
    ea:45:8b:69:d6:0d:ec:d7:fa:03:4c:1b:3b:d8:62:
    71:71:64:e7:78:5e:b0:6d:cc:5b:88:ba:a2:62:e4:
    31:20:e5:46:65:c0:cb:cb:3e:ad:51:b0:a0:08:19:
    b4:e9:1d:48:72:d3:fb:e7:72:4e:03:ab:71:bc:af:
    8b:b8:4c:74:de:c9:6a:ad:fc:b1:86:53:a8:f0:53:
    93:d6:66:06:99:23:bc:7b:9b:31:36:3d:6d:6d:9b:
    45:9f:46:db:5b:af:96:f8:40:4a:af:1a:83:1f:0d:
    b8:aa:d7:d9:3a:42:56:e8:15:6b:2b:70:75:7a:01:
    20:93
Exponent: 65537 (0x10001)
writing RSA key
-----BEGIN PUBLIC KEY-----
MIIBIjANBgkqhkiG9w0BAQEFAAOCAQ8AMIIBCgKCAQEBITsFfW/evEUntbdCGsHp
PM/+p2xPCHSZHPP6zw6rnvZGohg5ggtNZTqRa2jyWOnT98K6BU5K8F8+TWGz3nct
KtIziw6ubqCPIHbk5LCKsgkg+miF5sRN7BvuKKh2U8dLy56fEpTeiki9YUZSo9ZZ
3857iURhDyW/r5NumlQWfE0ifRbTLmXqRYtp1g3s1/oDTBs72GJxcWTneF6wbcxb
iLqiYuQxIOVGZcDLyz6tUbCgCBm06R1IctP753JOA6txvK+LuEx03slqrfyxhlOo
8FOT1mYGmSO8e5sxNj1tbZtFn0bbW6+W+EBKrxqDHw24qtfZOkJW6BVrK3B1egEg
kwIDAQAB
-----END PUBLIC KEY-----
n = 0x01213b057d6fdebc4527b5b7421ac1e93ccffea76c4f0874991cf3facf0eab9ef646a21839820b4d653a916b68f258e9d3f7c2ba054e4af05f3e4d61b3de772d2ad2338b0eae6ea08f2076e4e4b08ab20920fa6885e6c44dec1bee28a87653c74bcb9e9f1294de8a48bd614652a3d659dfce7b8944610f25bfaf936e9a54167c4d227d16d32e65ea458b69d60decd7fa034c1b3bd862717164e7785eb06dcc5b88baa262e43120e54665c0cbcb3ead51b0a00819b4e91d4872d3fbe7724e03ab71bcaf8bb84c74dec96aadfcb18653a8f05393d666069923bc7b9b31363d6d6d9b459f46db5baf96f8404aaf1a831f0db8aad7d93a4256e8156b2b70757a012093
  = 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611

nを素因数分解してみる。

$ python -m primefac 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611
36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611: 36511974694593690272644354864534934200522045623187752384823594729275730789191680514905027084950729514148679507005058047146031869995768765034876499069680202424692876360895377987654388335335689563844006584610187090074654410815638237841872991488680663410743679302763304922852173164820002226109196761249018548478251723505481964749218302723593776180246783117481280725673997940309717028451914887375722437833384305529884261542397905220138488012276363046571670926597766521674838665982314321651508118240682649024780239598188845543243957916954287138820155843952556411235376764737602711594439293285811102883736229645274092478611

nが素数のようだ。RSA暗号の仕組みを考える。

c = m^e % n
 ↓
c = m^e % (素数 * n)

この場合は復号結果が複数出るが、文字として読み取れるものをブルートフォースで探す。

from Crypto.PublicKey import RSA

def is_prime(d):
    if d < 2:
        return False
    if d == 2:
        return True
    if d % 2 == 0:
        return False

    a = 3
    while a ** 2 <= d:
        if d % a == 0:
            return False
        a = a + 2

    return True

def is_printable(s):
    for i in range(len(s)):
        if ord(s[i]) < 32 or ord(s[i]) > 126:
            return False

    return True

with open('RSA_Worst_Joke/public.pem', 'r') as f:
    pub_data = f.read()

pubkey = RSA.importKey(pub_data)
p = pubkey.n
e = pubkey.e

with open('RSA_Worst_Joke/flag.enc', 'r') as f:
    c = int(f.read().decode('base64').encode('hex'), 16)

for q in range(50):
    if is_prime(q):
        n = p * q

        phi = (p - 1) * (q - 1)

        x = 0
        while True:
            if (phi * x + 1) % e == 0:
                d = (phi * x + 1) / e
                break
            x = x + 1

        m = pow(c, d, n)

        hex_flag = '%x' % m
        if len(hex_flag) % 2 == 1:
            hex_flag = '0' + hex_flag
        flag = hex_flag.decode('hex')
        if is_printable(flag):
            print 'q =', q
            print flag

実行結果は以下の通り。

q = 47
The empire secret system has been exposed ! The top secret flag is : Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}
Flag{S1nGL3_PR1m3_M0duLUs_ATT4cK_TaK3d_D0wn_RSA_T0_A_Sym3tr1c_ALg0r1thm}

Improve the quality (Crypto 800)

decription.txtには以下のように記載されている。

Hello Every one,
We didn't know what to do, so we are asking for your help.

A friend of us sent us the following text:

I used an elliptic curve encrytion for the first time.
The only thing that i kown about elliptic curve is that a number K must always be hidden.
so i made multiple encryption to send some information.

Here is all the informations about the elliptic curve that i used excep the K number.

The elliptic curve is : 
y^2 = x^3 + A*x + B
A = 658974
Sorry i forget the B :/ , I just remember that it's most significant number is  6

As an order of a finite field must be a prime power, i used p = 962280654317 (FiniteField(p)).
as a starter point, i used the generator G for this elliptic curve: (518459267012 : 339109212996 : 1)
and each time i reuse it to encrypt again

let my secret message be K .
for exemple I divided my K to 2 elements k1 and k2
then Q1 is k1*G
and Q2 is k2*G

here are the Qi that i got:

[(656055339629 : 670956206845 : 1), 
(714432985374 : 30697818482 : 1), 
(519532969453 : 833497145865 : 1), 
(606806384185 : 353033449641 : 1), 
(370553209582 : 211121736115 : 1), 
(95617246846 : 666814491609 : 1), 
(474872055371 : 795112698430 : 1), 
(249845085299 : 222352033875 : 1), 
(850954431245 : 810446463695 : 1), 
(188731559428 : 877002121896 : 1), 
(168665615402 : 464872506873 : 1), 
(26722558561 : 269217869309 : 1), 
(16403346294 : 478534963882 : 1), 
(539749282946 : 332444159141 : 1), 
(932295517649 : 23439478940 : 1), 
(765194933041 : 920187938377 : 1), 
(853124087439 : 845601917928 : 1), 
(246454416048 : 212483699689 : 1), 
(312547608490 : 688107262695 : 1), 
(43261158649 : 439444472742 : 1), 
(320785434805 : 477080449838 : 1), 
(741706320740 : 672809544395 : 1), 
(361762297756 : 858805805323 : 1), 
(782235980044 : 600673464737 : 1), 
(69196762074 : 327427680437 : 1), 
(876001563166 : 573218279075 : 1), 
(117946101727 : 954797129239 : 1), 
(771781111553 : 314018907599 : 1), 
(579549799021 : 322325160055 : 1), 
(857081196493 : 464260539273 : 1), 
(852938568103 : 429083796488 : 1), 
(850954431245 : 810446463695 : 1), 
(55203632714 : 255470537391 : 1), 
(600464434215 : 605840305721 : 1), 
(620532163623 : 575613893944 : 1), 
(215810002861 : 481354983411 : 1), 
(538481263994 : 666638294130 : 1), 
(528666082457 : 895034116069 : 1), 
(296218553972 : 899557390183 : 1), 
(428618251485 : 445768511836 : 1), 
(632412058600 : 685699421425 : 1), 
(634041855232 : 495546745721 : 1), 
(570481762204 : 252944477333 : 1), 
(760959783781 : 435626456209 : 1)]
y^2 = x^3 + a*x + b mod n 
→b = y^2 - x^3 - a*x mod n

この場合は以下の文字になるので、まずはBを求める。

a -> A
b -> B
n -> p
p = 962280654317
A = 658974
G = (518459267012, 339109212996)

x = G[0]
y = G[1]
B = (pow(y, 2) - pow(x, 3) - A * x) % p
print 'B =', B
B = 618

Bの値はわかったので、Pohlig–Hellman algorithmを使って、k1から順番に求める。その値を見ながらメッセージになるようASCIIコード(10進数)として2桁ずつ読み込む。
コードは以下の通り。

# solve.sage
p = 962280654317
A = 658974
B = 618
G = (518459267012, 339109212996)
Q = [(656055339629, 670956206845), 
(714432985374, 30697818482), 
(519532969453, 833497145865), 
(606806384185, 353033449641), 
(370553209582, 211121736115), 
(95617246846, 666814491609), 
(474872055371, 795112698430), 
(249845085299, 222352033875), 
(850954431245, 810446463695), 
(188731559428, 877002121896), 
(168665615402, 464872506873), 
(26722558561, 269217869309), 
(16403346294, 478534963882), 
(539749282946, 332444159141), 
(932295517649, 23439478940), 
(765194933041, 920187938377), 
(853124087439, 845601917928), 
(246454416048, 212483699689), 
(312547608490, 688107262695), 
(43261158649, 439444472742), 
(320785434805, 477080449838), 
(741706320740, 672809544395), 
(361762297756, 858805805323), 
(782235980044, 600673464737), 
(69196762074, 327427680437), 
(876001563166, 573218279075), 
(117946101727, 954797129239), 
(771781111553, 314018907599), 
(579549799021, 322325160055), 
(857081196493, 464260539273), 
(852938568103, 429083796488), 
(850954431245, 810446463695), 
(55203632714, 255470537391), 
(600464434215, 605840305721), 
(620532163623, 575613893944), 
(215810002861, 481354983411), 
(538481263994, 666638294130), 
(528666082457, 895034116069), 
(296218553972, 899557390183), 
(428618251485, 445768511836), 
(632412058600, 685699421425), 
(634041855232, 495546745721), 
(570481762204, 252944477333), 
(760959783781, 435626456209)]

F = FiniteField(p)
E = EllipticCurve(F, [A,B])
G = E.point(G)

factors, exponents = zip(*factor(E.order()))
primes = [factors[i] ^ exponents[i] for i in range(len(factors))]

str_num = ''
for i in range(len(Q)):
    dlogs = []
    for fac in primes:
        t = int(G.order()) / int(fac)
        dlog = discrete_log(t*E.point(Q[i]), t*G, operation='+')
        dlogs += [dlog]

    k = crt(dlogs, primes)
    print k
    #print k * G == E.point(Q[i])
    str_num += str(k)

msg = ''
for i in range(0, len(str_num), 2):
    msg += chr(int(str_num[i:i+2]))

print msg

実行結果は以下の通り。

CONVERT THIS TO LOWER CASE FIRST :
THIS IMAGE CONTAINS THE FLAG, TRY TO GET IT
THE SUBMITTED FLAG MUST BE IN THIS FORMAT: 
FLAG-EC[WHAT YOU'LL FIND IN THE IMAGE]
IMAGE URL:
HTTP://CRYPTO.CTFSECURINETS.COM/1/STEG-PART.PNG

上記で大文字、小文字が関係するところは小文字にする。
http://crypto.ctfsecurinets.com/1/steg-part.pngのファイルを見たら、フラグが書いてあった。
f:id:satou-y:20180402213759p:plain

flag-ec[EC_St!e-g1(a)no]