HackCon 2017 Writeup

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

Rotate it (Bacche 2)

シーザー暗号。ROT13で復号できた。

d4rk{wh0_give$_ca3sar_in_CTF???}c0de

High Bass (Bacche 3)

Base64デコードする。

$ echo VGhpcyB3YXMgaW4gYmFzZS02NDogZDRya3t0aGF0XyRpbXBsXzNuMHVnaDRfVX1jMGRl | base64 -d
This was in base-64: d4rk{that_$impl_3n0ugh4_U}c0de
d4rk{that_$impl_3n0ugh4_U}c0de

File (Bacche 3)

実行するだけ。

$ ./one
d4rk{s1mpl_linux_execUt4ble}c0de
d4rk{s1mpl_linux_execUt4ble}c0de

Needle (Bacche 3)

テキストファイルをd4rkで検索

d4rk{n33dle_in_a_h4ystck}c0de

ALL CAPS (Bacche 5)

換字式暗号。quipqiupで復号する。

IN CRYPTOGRAPHY, A S??STIT?TION CIPHER IS A METHOD OF ENCODING ?Y WHICH ?NITS OF PLAINTEXT ARE REPLACED WITH CIPHERTEXT, ACCORDING TO A FIXED SYSTEM; THE "?NITS" MAY ?E SINGLE LETTERS (THE MOST COMMON), PAIRS OF LETTERS, TRIPLETS OF LETTERS, MIXT?RES OF THE A?O?E, AND SO FORTH. THE RECEI?ER DECIPHERS THE TEXT ?Y PERFORMING THE IN?ERSE S??STIT?TION. THAN?S FOR READING THAT, HERE'S YO?R FLAG: D4R?{TRY_FACCH3_IFTHIS_TOO_SIMPEL}C0DE
D4RK{TRY_FACCH3_IFTHIS_TOO_SIMPEL}C0DE

RSA - 1 (Bacche 10)

p, q がわかっているので、そのまま復号する。

p = 152571978722786084351886931023496370376798999987339944199021200531651275691099103449347349897964635706112525455731825020638894818859922778593149300143162720366876072994268633705232631614015865065113917174134807989294330527442191261958994565247945255072784239755770729665527959042883079517088277506164871850439

q = 147521976719041268733467288485176351894757998182920217874425681969830447338980333917821370916051260709883910633752027981630326988193070984505456700948150616796672915601007075205372397177359025857236701866904448906965019938049507857761886750656621746762474747080300831166523844026738913325930146507823506104359

c = 8511718779884002348933302329129034304748857434273552143349006561412761982574325566387289878631104742338583716487885551483795770878333568637517519439482152832740954108568568151340772337201643636336669393323584931481091714361927928549187423697803637825181374486997812604036706926194198296656150267412049091252088273904913718189248082391969963422192111264078757219427099935562601838047817410081362261577538573299114227343694888309834727224639741066786960337752762092049561527128427933146887521537659100047835461395832978920369260824158334744269055059394177455075510916989043073375102773439498560915413630238758363023648

e = 65537

n = p * q

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

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

m = pow(c, d, n)

flag = ('%x' % m).decode('hex')
print flag
d4rk{s1mpl3_rsa_n0t_th1s_34sy_next_time}c0de

RSA - 2 (Crypto 50)

eが非常に大きいため、Wiener's attackで復号する。

from fractions import Fraction

def egcd(a, b):
    x,y, u,v = 0,1, 1,0
    while a != 0:
        q, r = b//a, b%a
        m, n = x-u*q, y-v*q
        b,a, x,y, u,v = a,r, u,v, m,n
        gcd = b
    return gcd, x, y

def decrypt(p, q, e, c):
    n = p * q
    phi = (p - 1) * (q - 1)
    gcd, a, b = egcd(e, phi)
    d = a
    pt = pow(c, d, n)
    return hex(pt)[2:-1].decode('hex')

def continued_fractions(n,e):
    cf = [0]
    while e != 0:
        cf.append(int(n/e))
        N = n
        n = e
        e = N%e
    return cf

def calcKD(cf):
    kd = list()
    for i in range(1,len(cf)+1):
        tmp = Fraction(0)
        for j in cf[1:i][::-1]:
            tmp = 1/(tmp+j)
        kd.append((tmp.numerator,tmp.denominator))
    return kd

def int_sqrt(n):
    def f(prev):
        while True:
            m = (prev + n/prev)/2
            if m >= prev:
                return prev
            prev = m
    return f(n)

def calcPQ(a,b):
    if a*a < 4*b or a < 0:
        return None
    c = int_sqrt(a*a-4*b)
    p = (a + c) /2
    q = (a - c) /2
    if p + q == a and p * q == b:
        return (p,q)
    else:
        return None

def wiener(n,e):
    kd = calcKD(continued_fractions(n,e))
    for (k,d) in kd:
        if k == 0:
            continue
        if (e*d-1) % k != 0:
            continue
        phin = (e*d-1) / k
        if phin >= n:
            continue
        ans = calcPQ(n-phin+1,n)
        if ans is None:
            continue
        return (ans[0],ans[1])

n = 109676931776753394141394564514720734236796584022842820507613945978304098920529412415619708851314423671483225500317195833435789174491417871864260375066278885574232653256425434296113773973874542733322600365156233965235292281146938652303374751525426102732530711430473466903656428846184387282528950095967567885381

e = 49446678600051379228760906286031155509742239832659705731559249988210578539211813543612425990507831160407165259046991194935262200565953842567148786053040450198919753834397378188932524599840027093290217612285214105791999673535556558448523448336314401414644879827127064929878383237432895170442176211946286617205

c = 103280644092615059984518332609100925251130437801342718478803923990158474621180283788652329522078935869010936203566024336697568861166241737937884153980866061431062015970439320809653170936674539901900312536610219900459284854811622720209705994060764318380465515920139663572083312965314519159261624303103692125635

p, q = wiener(n, e)

flag = decrypt(p, q, e, c)
print flag
d4rk{1_70ld_y0u_th15_would_8e_more_difficult}c0de

VizHash (Crypto 100)

暗号化の概要は以下の通り。

・flagをBase64エンコードする。
・flagのBase64文字列分、以下の処理を行い、結合する。
 ・先頭1文字をencode(逆にしてASCIIコードで4つプラス)
 ・先頭2文字をencode
    :
 ・全文字をencode
・結合したものを1文字ずつmd5を取る。
・md5の文字について以下のような処理で色にして画像にする。

R (128 + ord('0')) ^ ord('x')
G 128 + ord('x') ^ ord(2番目)
B 128 + ord(2番目) ^ ord(3番目)

R (128 + ord(3番目)) ^ ord(4番目)
G 128 + ord(4番目) ^ ord(5番目)
B 128 + ord(5番目) ^ ord(6番目)

:

R (128 + ord(30番目)) ^ ord(31番目)
G 128 + ord(31番目) ^ ord(32番目)
B 128 + ord(32番目) ^ ord(33番目)

一つ一つ逆算していけば元に戻せそう。

import hashlib
from PIL import Image

BODY_DATA_NUM = 12936

def decode(s):
        return (''.join([ chr(ord(c)-4) for c in s[::-1] ]))

hash_dict = {}
for i in range(32, 127):
    h = hashlib.md5(chr(i)).hexdigest()
    hash_dict[h] = chr(i)

img = Image.open('digest.png').convert('RGB')
pixel_list = img.getdata()

md5_list = []
for i in range(BODY_DATA_NUM / 11):
    h = []
    for j in range(11):
        if j != 0:
            h.append(pixel_list[i*11+j][0] ^ (h[-1] + 128))
            h.append((pixel_list[i*11+j][1] - 128) ^ h[-1])
        else:
            h.append((pixel_list[i*11+j][1] - 128) ^ ord('x'))
        h.append((pixel_list[i*11+j][2] - 128) ^ h[-1])
    md5str = ''
    for i in range(32):
        md5str += chr(h[i])
    if md5str[-1:] == 'L':
        md5str = '0' + md5str[:-1]
    md5_list.append(md5str)

encrypted_flag = ''
for md5_val in md5_list:
    encrypted_flag += hash_dict[md5_val]

len_b64 = 0
while True:
    if len_b64 * (len_b64 + 1) == len(encrypted_flag) * 2:
        break
    len_b64 += 1

b64_flag = decode(encrypted_flag[-len_b64:])
flag = b64_flag.decode('base64')
print flag
d4rk{no00000oo_not0x_myfaUltXXX}c0de

White (Steg 50)

PNGファイルが添付されているが、PNGフォーマットの後にBase64の文字列が入っている。Base64の文字列をデコードすると、またPNGフォーマットとその後にBase64文字列のデータが入っている。繰り返し処理してPNGファイルを取り出す。

def div_png_and_b64dec(data):
    PNG_TAIL = '\x49\x45\x4e\x44\xae\x42\x60\x82'
    index = data.find(PNG_TAIL)
    enc = data[index+8:]
    if enc == '':
        return True, data, ''
    else:
        final = False
        dec = enc.decode('base64')
        return final, data[:index+8], dec

with open('final.png', 'rb') as f:
    data = f.read()

i = 1
while True:
    print 'Round %d' % i
    final, png, data = div_png_and_b64dec(data)
    file = 'png\\%02d.png' % i
    if final:
        with open(file, 'wb') as f:
            f.write(png)
        break
    else:
        with open(file, 'wb') as f:
            f.write(png)
    i += 1

取り出した画像の中にフラグの断片が入っているので、結合する。

$ convert +append 01.png 02.png 03.png 04.png 05.png 06.png flag01.png
$ convert +append 07.png 08.png 09.png 10.png 11.png 12.png flag02.png
$ convert +append 13.png 14.png 15.png 16.png 17.png 18.png flag03.png
$ convert +append 19.png 20.png 21.png 22.png 23.png 24.png flag04.png
$ convert +append 25.png 26.png 27.png 28.png 29.png 30.png flag05.png
$ convert -append flag*.png flag.png

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

d4rk{1mag3_m4n1pul4t10n_F7W}c0d3