Crypto CTF 2019 Writeup - よっちんのブログ

この大会は2019/8/10 15:00(JST)～2019/8/11 15:00(JST)に開催されました。
今回もチームで参戦。結果は541点で639チーム中49位でした。
自分で解けた問題をWriteupとして書いておきます。

Welcome

問題にフラグが書いてあった。

CCTF{W3lc0m3_2_Crypt0CTF_2019}

Decode me!

問題の暗号は以下の通り。

D: mb xwhvxw mlnX 4X6AhPLAR4eupSRJ6FLt8AgE6JsLdBRxq57L8IeMyBRHp6IGsmgFIB5E :ztey xam lb lbaH

"D:"の部分はよく顔文字で使われていて、文の最後に入ることが多いため、逆にしてみる。

Habl bl max yetz: E5BIFgmsGI6pHRByMeI8L75qxRBdLsJ6EgA8tLF6JRSpue4RALPhA6X4 Xnlm wxvhwx bm :D

なんとなく最初はThis isとなりそうな感じがする。シーザー暗号で復号できそう。英大文字、小文字、数字でシフト数が異なるようだ。調整しながら復号する。この文中で真ん中あたりにBase64文字列が出てくるので、CCTF{のBase64文字列になるよう数字のシフト数を決める。

import string

def letters_decode(s):
    d = ''
    for c in s:
        if c in string.lowercase:
            index = string.lowercase.index(c)
            index += 7
            if index >= 26:
                index -= 26
            d += string.lowercase[index]
        elif c in string.uppercase:
            index = string.uppercase.index(c)
            index += 12
            if index >= 26:
                index -= 26
            d += string.uppercase[index]
        elif c in string.digits:
            index = string.digits.index(c)
            index += 5
            if index >= 10:
                index -= 10
            d += string.digits[index]
        else:
            d += c
    return d


ct = 'D: mb xwhvxw mlnX 4X6AhPLAR4eupSRJ6FLt8AgE6JsLdBRxq57L8IeMyBRHp6IGsmgFIB5E :ztey xam lb lbaH'
ct = ct[::-1]

pt = letters_decode(ct)
print pt

pt_words = pt.split(' ')
flag = pt_words[4].decode('base64')
print flag

実行結果は以下の通り。

This is the flag: Q0NURntzSU1wTDNfYlU3X20xeDNkXzV1QnM3aXR1VDEwbl9DMXBoM1J9 Just decode it :P
CCTF{sIMpL3_bU7_m1x3d_5uBs7ituT10n_C1ph3R}

CCTF{sIMpL3_bU7_m1x3d_5uBs7ituT10n_C1ph3R}

Time Capsule

lの計算がそのままだと時間がかかるので、変換する。

l = pow(2, pow(2, t), n)
  = pow(2, pow(2, t, phi(n)), n)

phiを求めるために、nを素因数分解する。

$ python -m primefac 16801166465109052984956796702219479136700692152603640001472470493600002617002298302681832215942994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287393811934457789103209090873472485865328414154574392274611574654819495894137917800304580119452390318440601827273834522783696472257727329819952363099498446006266115011271978143149347765073211516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618066568854673260978968978974409802211538011638213976732286150311971354861300195440286582255769421094876667270445809991401456443444265323573485901383
16801166465109052984956796702219479136700692152603640001472470493600002617002298302681832215942994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287393811934457789103209090873472485865328414154574392274611574654819495894137917800304580119452390318440601827273834522783696472257727329819952363099498446006266115011271978143149347765073211516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618066568854673260978968978974409802211538011638213976732286150311971354861300195440286582255769421094876667270445809991401456443444265323573485901383: 15013 899583643974479 654269804672441 1112193819715441 706144068530309 639438000563939 1070689247726159 634947980859229 583343756982313 1079289330417443 1027313536626551 721443717105973 667954470985657 654170414254271 609245815680559 612567235432583 971274523714349 841183196554507 795581973851653 864339847436159 1110918654474373 873021823131881 1111516996694389 746232585529679 635224892351513 1018452110902339 1098516592571807 942872831732189 922745965897867 951697329369323 817224718609627 1067609726096989 815694637597057 585503197547927 1059774237802229 1108654254305327 737993471695639 744872496387077 884236929660113 1017566110290559 1025985735184171 1107673252158281

あとはm = l ^ z ^ cなので、そのまま復号すればフラグになる。

from Crypto.Util.number import *

c = 30263951492003430418944035844723976843761515320480688994488846431636782360488888188067655841720110193942081554547272176290791213962513701884837856823209432209367951673301622535940395295826053396595886942990258678430777333636450042181585837395671842878310404080487115827773100028876775230121509570227303374672524063165714509957850966189605469484201028704363052317830254920108664916139026741331552127849056897534960886647382429202269846392809641322613341548025760209280611758326300214885296175538901366986310471066687700879304860668964595202268317011117634615297226602309205086105573924029744405559823548638486054634428L
n = 16801166465109052984956796702219479136700692152603640001472470493600002617002298302681832215942994746974878002533318970006820414971818787350153626339308150944829424332670924459749331062287393811934457789103209090873472485865328414154574392274611574654819495894137917800304580119452390318440601827273834522783696472257727329819952363099498446006266115011271978143149347765073211516486037823196033938908784720042927986421555211961923200006343296692217770693318701970436618066568854673260978968978974409802211538011638213976732286150311971354861300195440286582255769421094876667270445809991401456443444265323573485901383L
t = 6039738711082505929
z = 13991757597132156574040593242062545731003627107933800388678432418251474177745394167528325524552592875014173967690166427876430087295180152485599151947856471802414472083299904768768434074446565880773029215057131908495627123103779932128807797869164409662146821626628200600678966223382354752280901657213357146668056525234446747959642220954294230018094612469738051942026463767172625588865125393400027831917763819584423585903587577154729283694206436985549513217882666427997109549686825235958909428605247221998366006018410026392446064720747424287400728961283471932279824049509228058334419865822774654587977497006575152095818L

ps = [15013, 899583643974479, 654269804672441, 1112193819715441, 706144068530309, 639438000563939, 1070689247726159, 634947980859229, 583343756982313, 1079289330417443, 1027313536626551, 721443717105973, 667954470985657, 654170414254271, 609245815680559, 612567235432583, 971274523714349, 841183196554507, 795581973851653, 864339847436159, 1110918654474373, 873021823131881, 1111516996694389, 746232585529679, 635224892351513, 1018452110902339, 1098516592571807, 942872831732189, 922745965897867, 951697329369323, 817224718609627, 1067609726096989, 815694637597057, 585503197547927, 1059774237802229, 1108654254305327, 737993471695639, 744872496387077, 884236929660113, 1017566110290559, 1025985735184171, 1107673252158281]

phi = 1
for p in ps:
    phi *= p - 1

l = pow(2, pow(2, t, phi), n)
m = l ^ z ^ c
flag = long_to_bytes(m)
print flag

CCTF{_______________________________________________Happy_Birthday_LCS______________________________________________}

Aron

最初にPoWを解く必要がある。テスト的に以下のコードでh_typeとh_tailを変更して、PoWをクリアしながら、いろいろ試してみる。

import itertools
import hashlib
import string

h_type = 'sha224'
h_tail = '1ae159'

for c in itertools.product(string.letters + string.digits
    + '!#$%&()+-*=.,:+[]{}', repeat=4):
    X = ''.join(c)
    if h_type == 'md5':
        h = hashlib.md5(X).hexdigest()
    elif h_type == 'sha1':
        h = hashlib.sha1(X).hexdigest()
    elif h_type == 'sha224':
        h = hashlib.sha224(X).hexdigest()
    elif h_type == 'sha256':
        h = hashlib.sha256(X).hexdigest()
    elif h_type == 'sha384':
        h = hashlib.sha384(X).hexdigest()
    elif h_type == 'sha512':
        h = hashlib.sha512(X).hexdigest()
    if h[-6:] == h_tail:
        print X
        break

$ nc 167.71.62.250 12439
Submit a printable string X, such that sha256(X)[-6:] = f1aad2
zt#8
*********************************************************************************
| hey! I have developed an efficient pseudorandom function, PRF, but it needs   |
| deep tests for security points!! Try hard to break this PRF and get the flag! |
| In each step I will compute the f_a(n), f_a(n + 1), f_a(n + 2), f_a(n+3), and |
| f_a(n + 4) for secret verctor a, and for your given positive number 0 < n < p |
*********************************************************************************
| for n = 275375130124552092384344654968321344654, and with these PRF parameters: 
| (p, g) = (0xf98f6e918a8d287cf4145736d5fc79ed, 0x86e41987aa2ef8bdb5bf5a6ef09ecd4c) 
| the five consecutive random numbers generated by our secure PRF are: 
| f_a(n + 0) = 85628683890107630736954068519595535503
| f_a(n + 1) = 20492301712678833292060709831593766594
| f_a(n + 2) = 315273394287387390882420840867043653898
| f_a(n + 3) = 142988296692952236913896578977523244303
| f_a(n + 4) = 15997982160052493148067363504633357039 
| Options: 
|	[G]uess next number! 
|	[P]RF function 
|	[N]ew numbers
|	[Q]uit
P
def gg(tup, a, x):
	(_, p, g), n = tup, len(a)
	assert len(bin(x)[2:]) <= n
	X = bin(x)[2:].zfill(n)
	f_ax = g
	for i in range(1, n):
		f_ax *= pow(g, a[i] * int(X[i]), p)
	return f_ax % p

| Options: 
|	[G]uess next number! 
|	[P]RF function 
|	[N]ew numbers
|	[Q]uit
N
Do you want to provide desired integer as `n'? [Y]es [N]o
Y
enter your integer n: 
12
Sorry, your input integer is small :P
| Options: 
|	[G]uess next number! 
|	[P]RF function 
|	[N]ew numbers
|	[Q]uit
G
please guess and enter the next number: 
1234
Sorry, your input is not corr3ct!
| Options: 
|	[G]uess next number! 
|	[P]RF function 
|	[N]ew numbers
|	[Q]uit

どうやら、この関数を前提に、次の数値を予測する問題らしい。
...がnを指定できる。ある程度大きいnを指定して、次にn-1を指定すれば、簡単に予測できそう。

$ nc 167.71.62.250 12439
Submit a printable string X, such that sha224(X)[-6:] = 1ae159
UsIX
*********************************************************************************
| hey! I have developed an efficient pseudorandom function, PRF, but it needs   |
| deep tests for security points!! Try hard to break this PRF and get the flag! |
| In each step I will compute the f_a(n), f_a(n + 1), f_a(n + 2), f_a(n+3), and |
| f_a(n + 4) for secret verctor a, and for your given positive number 0 < n < p |
*********************************************************************************
| for n = 132552965466391004194176144496829619622, and with these PRF parameters: 
| (p, g) = (0x8f1e139d7d17174be5b10d4d221cce41, 0x7948a8c5a86a37ac047f4662babb216d) 
| the five consecutive random numbers generated by our secure PRF are: 
| f_a(n + 0) = 29800306021970074348391444895357688152
| f_a(n + 1) = 91168159348484675661422991959872493361
| f_a(n + 2) = 62153616520877495836568245956622643734
| f_a(n + 3) = 78554585804352070084705555833196060927
| f_a(n + 4) = 52184015618889528536185436865056973999 
| Options: 
|	[G]uess next number! 
|	[P]RF function 
|	[N]ew numbers
|	[Q]uit
N
Do you want to provide desired integer as `n'? [Y]es [N]o
Y
enter your integer n: 
91168159348484675661422991959872493362
| the five consecutive random numbers generated by our secure PRF are: 
| f_a(n + 0) = 32670879450088786326381592358223094486
| f_a(n + 1) = 118085043291686788180598465855490294402
| f_a(n + 2) = 78379454949324689875746607817271265989
| f_a(n + 3) = 145501408034299576523083822092287504510
| f_a(n + 4) = 22886445357077994349602606596591229733 
| Options: 
|	[G]uess next number! 
|	[P]RF function 
|	[N]ew numbers
|	[Q]uit
N
Do you want to provide desired integer as `n'? [Y]es [N]o
Y
enter your integer n: 
91168159348484675661422991959872493361
| the five consecutive random numbers generated by our secure PRF are: 
| f_a(n + 0) = 44362010168986067071588617474891520883
| f_a(n + 1) = 32670879450088786326381592358223094486
| f_a(n + 2) = 118085043291686788180598465855490294402
| f_a(n + 3) = 78379454949324689875746607817271265989
| f_a(n + 4) = 145501408034299576523083822092287504510 
| Options: 
|	[G]uess next number! 
|	[P]RF function 
|	[N]ew numbers
|	[Q]uit
G
please guess and enter the next number: 
22886445357077994349602606596591229733
Congratz! :) You got the flag: CCTF{___Naor-Reingold___p5euD0r4ndOM_fuNc710N__PRF__}

CCTF{___Naor-Reingold___p5euD0r4ndOM_fuNc710N__PRF__}

Aron II

Aronの出題ミスっぽいのが直っている問題かと思ったが、同じ解き方で解けてしまった。今度は全部をスクリプトにして解いてみた。

import socket
import itertools
import re
import string
import hashlib

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

s = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
s.connect(('167.71.62.250', 23549))

data = recvuntil(s, '\n').rstrip()
print data
pattern = 'that (.+)\(X\)\[-6\:\] = (.+)'
m = re.search(pattern, data)
h_type = m.group(1)
h_tail = m.group(2)

for c in itertools.product(string.letters + string.digits
    + '!#$%&()+-*=.,:+[]{}', repeat=4):
    X = ''.join(c)
    if h_type == 'md5':
        h = hashlib.md5(X).hexdigest()
    elif h_type == 'sha1':
        h = hashlib.sha1(X).hexdigest()
    elif h_type == 'sha224':
        h = hashlib.sha224(X).hexdigest()
    elif h_type == 'sha256':
        h = hashlib.sha256(X).hexdigest()
    elif h_type == 'sha384':
        h = hashlib.sha384(X).hexdigest()
    elif h_type == 'sha512':
        h = hashlib.sha512(X).hexdigest()
    if h[-6:] == h_tail:
        print X
        s.sendall(X + '\n')
        break

data = recvuntil(s, '[Q]uit\n').rstrip()
print data

print 'P'
s.sendall('P\n')

data = recvuntil(s, '[Q]uit\n').rstrip()
print data

print 'N'
s.sendall('N\n')

data = recvuntil(s, '[N]o\n').rstrip()
print data

print 'Y'
s.sendall('Y\n')

data = recvuntil(s, 'n: \n').rstrip()
print data

n = '99999999999999999999999999999999999999'
print n
s.sendall(n + '\n')

data = recvuntil(s, '[Q]uit\n').rstrip()
print data
pattern = 'f_a\(n \+ 4\) = (.+)'
m = re.search(pattern, data)
ans = m.group(1)

print 'N'
s.sendall('N\n')

data = recvuntil(s, '[N]o\n').rstrip()
print data

print 'Y'
s.sendall('Y\n')

data = recvuntil(s, 'n: \n').rstrip()
print data

n = '99999999999999999999999999999999999998'
print n
s.sendall(n + '\n')

data = recvuntil(s, '[Q]uit\n').rstrip()
print data

print 'G'
s.sendall('G\n')

data = recvuntil(s, 'number: \n').rstrip()
print data
print ans
s.sendall(ans + '\n')

data = recvuntil(s, '\n').rstrip()
print data

実行結果は以下の通り。

Submit a printable string X, such that sha1(X)[-6:] = 78d8f8
DH6w
*********************************************************************************
| hey! I have developed an efficient pseudorandom function, PRF, but it needs   |
| deep tests for security points!! Try hard to break this PRF and get the flag! |
| In each step I will compute the f_a(n), f_a(n + 1), f_a(n + 2), f_a(n+3), and |
| f_a(n + 4) for secret verctor a, and for your given positive number 0 < n < p |
*********************************************************************************
| for n = 103781485000134018146769038485142316585, and with these PRF parameters:
| (p, g) = (0xe305f00bb117aee29d059efddc7b51f3, 0x58fe4656a631a7305a3e0a59a81eb3e4)
| the five consecutive random numbers generated by our secure PRF are:
| f_a(n + 0) = 234991268593909305025747004754235789466
| f_a(n + 1) = 70810672983888854922198226846536814934
| f_a(n + 2) = 134191384784257335633929561544836935794
| f_a(n + 3) = 22514196187652811688216450974804710393
| f_a(n + 4) = 228105815094197968284719203000820734387
| Options:
|       [G]uess next number!
|       [P]RF function
|       [N]ew numbers
|       [Q]uit
P
def gg(tup, a, x):
        (_, p, g), n = tup, len(a)
        assert len(bin(x)[2:]) <= n
        X = bin(x)[2:].zfill(n)
        f_ax = g
        for i in range(1, n):
                f_ax *= pow(g, a[i] * int(X[i]), p)
        return f_ax % p

| Options:
|       [G]uess next number!
|       [P]RF function
|       [N]ew numbers
|       [Q]uit
N
Do you want to provide desired integer as `n'? [Y]es [N]o
Y
enter your integer n:
99999999999999999999999999999999999999
| the five consecutive random numbers generated by our secure PRF are:
| f_a(n + 0) = 54972294286928546366615261585896020335
| f_a(n + 1) = 60219524522385663072634974727945621753
| f_a(n + 2) = 197471080809930961952625018802500468012
| f_a(n + 3) = 159722355046906579114263248014594366384
| f_a(n + 4) = 243504553220838903102994924682416081526
| Options:
|       [G]uess next number!
|       [P]RF function
|       [N]ew numbers
|       [Q]uit
N
Do you want to provide desired integer as `n'? [Y]es [N]o
Y
enter your integer n:
99999999999999999999999999999999999998
| the five consecutive random numbers generated by our secure PRF are:
| f_a(n + 0) = 290969245319810346991333270784993957068
| f_a(n + 1) = 54972294286928546366615261585896020335
| f_a(n + 2) = 60219524522385663072634974727945621753
| f_a(n + 3) = 197471080809930961952625018802500468012
| f_a(n + 4) = 159722355046906579114263248014594366384
| Options:
|       [G]uess next number!
|       [P]RF function
|       [N]ew numbers
|       [Q]uit
G
please guess and enter the next number:
243504553220838903102994924682416081526
Congratz! :) You got the flag: CCTF{___Naor-Reingold___fix3d_V3r5I0n___}

CCTF{___Naor-Reingold___fix3d_V3r5I0n___}

Survey

アンケートに答えたら、フラグが表示された。

CCTF{H4ppy_Br3king_CIph3rs_H4aackers!!}