この大会は2020/8/15 0:00(JST)～2020/8/16 0:00(JST)に開催されました。
今回もチームで参戦。結果は194点で552チーム中75位でした。
自分で解けた問題をWriteupとして書いておきます。
Amsterdam
添付のコードの処理概要は以下の通り。
■comb(n, k) ・k = min(k, n - k) ・u = n * (n-1) * ... * (n-k+1) ・d = 1 * 2 * ... * k ・u//d(=組合せの数)を返す。 ■encrypt(msg, n, k) ・m = ['1'] + ['0' for i in range(n - 1)] ・i = 1～nについて、comb(n - i, k)とmsgの比較の結果により計算 ・3進数として見てそれにより計算
以上の処理から逆算する。
from Crypto.Util.number import * from functools import reduce import operator def comb(n, k): if k > n : return 0 k = min(k, n - k) u = reduce(operator.mul, range(n, n - k, -1), 1) d = reduce(operator.mul, range(1, k + 1), 1) return u // d def get_m(n): z = [] r = n while True: z.insert(0, r % 3) r = r // 3 if r == 0: break m = 0 for v in z: if v == 1: m += 1 elif v == 2: m -= 1 m *= 2 return m // 2 with open('output.txt', 'r') as f: enc = int(f.read().rstrip().split(' = ')[1]) m = get_m(enc) m = list(bin(m)[2:]) n = len(m) msg = 0 k = 0 for i in range(n, 1, -1): if m[i-1] == '1': k += 1 msg += comb(n - i, k) flag = long_to_bytes(msg) print flag
実行結果は以下の通り。
..:: CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!} ::..
CCTF{With_Re3p3ct_for_Sch4lkwijk_dec3nt_Encoding!}
Gambler
$ nc 05.cr.yp.toc.tf 33371 Please submit a printable string X, such that md5(X)[-6:] = 436d29 and len(X) = 15 aaaaaaaaaaa3b c ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ + Hi, there is a strong relation between philosophy and the gambling! + + Gamble as an ancient philosopher and find the flag :) + ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ | Options: | [C]ipher flag! | [E]ncryption function! | [T]ry the encryption | [Q]uit E def encrypt(m, p, a, b): assert m < p and isPrime(p) return (m ** 3 + a * m + b) % p | Options: | [C]ipher flag! | [E]ncryption function! | [T]ry the encryption | [Q]uit C | encrypt(bytes_to_long(flag)) = 4339765736830935414327965338053684580043454821290341525216211716629855521006492403426648253523243969172076764249860030760412141126792833762698294650295993 | Options: | [C]ipher flag! | [E]ncryption function! | [T]ry the encryption | [Q]uit T | please enter your message to encrypt: 0 | encrypt(0) = 1089301495525915394959217783050238720360823156044460562942045915433765226363143224942220585780797051983913183133330187520635392023778046748500434599782334
この暗号化の処理から以下のようになることがわかる。
m=0 c = b % p = b m=1 c = (a + b + 1) % p m=2 c = (a*2 + b + 8) % p
差分を計算し、aを数回求め、正負の値が出るようにする。両方ともmod pでは同じ値を示すので、以下の式が成り立つ。
p = 正の値 - 負の値
あとはsageでmodulo p上の三次方程式を解けば、フラグが求められる。
#!/usr/bin/env sage import socket import itertools import re import string import hashlib from Crypto.Util.number import * 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(('05.cr.yp.toc.tf', 33371)) data = recvuntil(s, '\n').rstrip() print data pattern = 'that (.+)\(X\)\[-6:\] = (.+) and len\(X\) = (.+)' m = re.search(pattern, data) alg = m.group(1) h = m.group(2) l = int(m.group(3)) for c in itertools.product(string.letters + string.digits + '!#$%&()+-*=.,:+[]{}', repeat=4): X = 'a' * (l - 4) + ''.join(c) if alg == 'md5': try_h = hashlib.md5(X).hexdigest() elif alg == 'sha1': try_h = hashlib.sha1(X).hexdigest() elif alg == 'sha224': try_h = hashlib.sha224(X).hexdigest() elif alg == 'sha256': try_h = hashlib.sha256(X).hexdigest() elif alg == 'sha384': try_h = hashlib.sha384(X).hexdigest() elif alg == 'sha512': try_h = hashlib.sha512(X).hexdigest() if try_h[-6:] == h: print X s.sendall(X + '\n') break data = recvuntil(s, '[Q]uit\n').rstrip() print data print 'E' s.sendall('E\n') data = recvuntil(s, '[Q]uit\n').rstrip() print data print 'C' s.sendall('C\n') data = recvuntil(s, '[Q]uit\n').rstrip() print data flag_enc = int(data.split('\n')[0].split(' ')[-1]) encs = [] for i in range(8): print 'T' s.sendall('T\n') data = recvuntil(s, ':\n').rstrip() print data print str(i) s.sendall(str(i) + '\n') data = recvuntil(s, '[Q]uit\n').rstrip() print data enc = int(data.split('\n')[0].split(' ')[-1]) encs.append(enc) b = encs[0] a01 = [] for i in range(7): a = encs[i+1] - encs[i] - ((i+1)**3 - i**3) if a not in a01: a01.append(a) if a01[0] > 0: a = a01[0] p = a01[0] - a01[1] else: a = a01[1] p = a01[1] - a01[0] print '[+] a =', a print '[+] b =', b print '[+] p =', p PR.<x> = PolynomialRing(Zmod(p)) f = x**3 + a * x + b - flag_enc x = f.roots() for x0 in x: m = x0[0] flag = long_to_bytes(m) if flag.startswith('CCTF{'): print flag break
実行結果は以下の通り。
Please submit a printable string X, such that sha256(X)[-6:] = dcec57 and len(X) = 34
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaau4:H
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
+ Hi, there is a strong relation between philosophy and the gambling! +
+ Gamble as an ancient philosopher and find the flag :) +
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
E
def encrypt(m, p, a, b):
assert m < p and isPrime(p)
return (m ** 3 + a * m + b) % p
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
C
| encrypt(bytes_to_long(flag)) = 5859516123032408533939710338576303083349657177204288009870620113808657974777306952491312119968507733782625057335054668782484329039657233624056698649884479
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
T
| please enter your message to encrypt:
0
| encrypt(0) = 3637655651634145666149005129567650238506907370016588111100276114666277871801383820019190490265615402427492341457234915175477949683389630837892818806483316
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
T
| please enter your message to encrypt:
1
| encrypt(1) = 6684357881294328590827758239283935840508256629140296502574070083663474657706694077011405369969103934322873783266172317422303466082228788559258018890537923
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
T
| please enter your message to encrypt:
2
| encrypt(2) = 9731060110954511515506511349000221442509605888264004894047864052660671443612004334003620249672592466218255225075109719669128982481067946280623218974592536
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
T
| please enter your message to encrypt:
3
| encrypt(3) = 3044830652562186554641560518436170068234378799214462545904358445175680930299518352118531703785023105414819829718421119070044005355378749771648575733506042
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
T
| please enter your message to encrypt:
4
| encrypt(4) = 6091532882222369479320313628152455670235728058338170937378152414172877716204828609110746583488511637310201271527358521316869521754217907493013775817560685
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
T
| please enter your message to encrypt:
5
| encrypt(5) = 9138235111882552403999066737868741272237077317461879328851946383170074502110138866102961463192000169205582713336295923563695038153057065214378975901615352
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
T
| please enter your message to encrypt:
6
| encrypt(6) = 2452005653490227443134115907304689897961850228412336980708440775685083988797652884217872917304430808402147317979607322964610061027367868705404332660528930
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
T
| please enter your message to encrypt:
7
| encrypt(7) = 5498707883150410367812869017020975499963199487536045372182234744682280774702963141210087797007919340297528759788544725211435577426207026426769532744583663
| Options:
| [C]ipher flag!
| [E]ncryption function!
| [T]ry the encryption
| [Q]uit
[+] a = 3046702229660182924678753109716285602001349259123708391473793968997196785905310256992214879703488531895381441808937402246825516398839157721365200084054606
[+] b = 3637655651634145666149005129567650238506907370016588111100276114666277871801383820019190490265615402427492341457234915175477949683389630837892818806483316
[+] p = 9732931688052507885543703940280336976276576348173250739617299576482187299217796238877303425591057892698816837165626002845910493524528354230339843325141119
CCTF{__Gerolamo__Cardano_4N_itaLi4N_p0lYma7H}
CCTF{__Gerolamo__Cardano_4N_itaLi4N_p0lYma7H}
Trailing Bits
2進数コードになっているが、そのままでは文字にならない。シフトしながらデコードしてみる。
with open('output.txt', 'r') as f: enc = f.read().rstrip() for j in range(8): try_enc = enc[j:] msg = '' for i in range(0, len(try_enc), 8): msg += chr(int(try_enc[i:i+8], 2)) print '[+] shift =', j print msg
実行結果は以下の通り。
[+] shift = 0
H禄ﾚXﾈ[ﾙ・[剱ﾜ婢][ﾛ・[・ﾛﾛ\][卻[・Yﾚ]ﾛﾛ[][唸ﾘ][ﾛ慷・H麓YH\ﾈHﾜ ・X[・X]Hﾙ・喙禄曰Yﾚ]摸WHH 兔兔ﾙ[・ﾈHﾙﾚXﾘﾝ]Hﾚ]ﾛ僣ﾙ・ﾛﾈﾜﾜﾚX・H麓Y\ﾋ・\ﾙH麓Y\ﾈ\僣[ﾜﾛﾛ[[ﾛ・H兔兔ﾙ[ \ﾈZ]\・ﾜ ﾝ\・兔兔ﾙ[・][ﾛ慂ﾝ\ﾈ拑Kﾙ麓ﾙY\ﾋﾛ嵳
Wﾌﾛ・NZﾚ筆UﾝﾗﾜﾒY・ﾓLﾟB・Hﾛﾜ恙\ﾜﾛ・[俛H兢ﾙY[・\ﾙH麓Y\ﾈ[・H\ﾚXﾝ]\ﾈﾙ・H[・\・Z[卻ﾝﾜ郎ﾙHﾜ・]唸ﾙH\ﾈHX]\・ﾙ・ﾛﾛ撕[・[ﾛ・[・Y劔\兌・\ﾜﾚYﾛ婪[・ﾈX^H僣\]兌・ﾚ][・Hﾘ[YH]唸ﾙHﾜ・巍ﾜ麓K X^H僣\ﾚXﾘ[H[\[Y[・ﾚHﾛﾋ\ﾝ
[+] shift = 1
・0ｹｴｱ・ｷ4ｺ7ｳ4ｷ37ｹ6ｰｺ4ｷｷ4ｷ1ｷｶｸ:ｺ4ｷ3・ｷ224ｳｴｺ0ｶ1ｷｶｶｺｷ4ｱｰｺ4ｷｷ9・*42・0ｶｲ・ｹ ・・7ｹ:6ｰｷ:2ｰｺ・ｳ14ｷ0ｹ<・4ｳｴｺ-舒・42・4ｺ92ｸ92ｹｲｷ:9・・7ｳｴｱｰｶ9ｺ0ｺ2・ｴｺ47ｷ2・ｳ:;ｷ・7ｹｹｴｱ62・0ｶ:ｲｹ・*42ｹｲ・0ｶ:ｲｹ・ｹ2・ｷｹｺ1ｷｶｶｷｷ6<・2ｸ92ｹｲｷ:2ｲ0ｹ・ｴｺ42ｹ7ｹ・1:ｺ7ｺ42ｹ92ｸ92ｹｲｷ:0ｺ4ｷｷ9・ｺｱｴ0ｹ・9:ｲ竜0ｶ9ｲ・<ｲｹ旅7・列DI7ｹ7ｷｷｳ30ｹ2・ｷｶｶｷｷ*42・60ｳ・ｹ・｡ｪ#=ｴｺｯ匚:惷/ｵ*坎/ｺ'ｯｹ､ｳ:/ｦ卆・42・ｷｹ92ｹｸ7ｷ22ｷ1ｲ・2ｺ;ｲｲｷ:42ｹｲ・0ｶ:ｲｹ・ｷ2:42・4<ｹｴｱｰｶ9ｺ0ｺ2ｹ・ｳ:42・ｷ22ｹ6<ｴｷ3・ｺ7ｹ0ｳｲ・ｹ22ｻ4ｱｲ・ｹ・・ｰｺ:2ｹ7ｳ1ｷｷ;2ｷ:4ｷｷ0ｷ224ｳ32ｹ2ｷ:0ｹｹｴｳｷ6ｲｷ:9・ｰｼ・2・ｹｲｲ2ｻ2ｷ;ｴｺ44ｷ:42・ｰｶｲ・2ｻ4ｱｲ・ｹ897ｳｹ0ｶ・$ｺ6ｰｼ・2・4<ｹｴｱｰｶ6<・ｶｸ62ｶｲｷ:2ｲ;ｴｺ40・;ｷ婿ｺ
[+] shift = 2
basic unit of information in computing and digital communications. The name is a portmanteau of binary digit.[1] The bit represents a logical state with one of two possible values. These values are most commonly represented as either 0or1, but other representations such as true/false, yes/no, +/竏・ or on/off are common.
The flag is CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}
The correspondence between these values and the physical states of the underlying storage or device is a matter of convention, and different assignments may be used even within the same device or program. It may be physically implemented with a two-st
[+] shift = 3
@ﾄﾂ贅ﾆ@・ﾒ錙ﾞﾌ@ﾒﾜﾌﾞ蒂ﾂ靨ﾞﾜ@ﾒﾜ@ﾆﾞﾚ瑕靨ﾜﾎ@ﾂﾜﾈ@ﾈﾒﾎﾒ霙ﾘ@ﾆﾞﾚﾚ・ﾒﾆﾂ靨ﾞﾜ觸@ｨﾐﾊ@ﾜﾂﾚﾊ@ﾒ襦ﾂ@玻蒻ﾚﾂﾜ靆ﾂ鵝ﾞﾌ@ﾄﾒﾜﾂ蔗@ﾈﾒﾎﾒ鐔ｶbｺ@ｨﾐﾊ@ﾄﾒ錙萍琅ﾊ賁ﾜ韆@ﾂ@ﾘﾞﾎﾒﾆﾂﾘ@跖ﾂ靆@迤靤@ﾞﾜﾊ@ﾞﾌ@韶ﾞ@玻跏ﾒﾄﾘﾊ@・ﾘ・觸@ｨﾐﾊ賁@・ﾘ・襦ﾂ萍@ﾚﾞ跖@ﾆﾞﾚﾚﾞﾜﾘ萍琅ﾊ賁ﾜ靆ﾈ@ﾂ襦ﾊﾒ靤ﾊ隋`ﾞ臙X@ﾄ・@ﾞ靤ﾊ隋萍琅ﾊ賁ﾜ霙靨ﾞﾜ襦跛ﾆﾐ@ﾂ襦鞴・^ﾌﾂﾘ賁X@訖ﾜﾞX@V_ﾅ$X@ﾞ隋ﾞﾜ^ﾞﾌﾌ@ﾂ萍@ﾆﾞﾚﾚﾞﾜ\ｨﾐﾊ@ﾌﾘﾂﾎ@ﾒ襦・ｨ公ﾒ鑠ｾfﾜ`靡ﾐｾﾔｪjｨｾ陞ｾ謳bﾌ霎喃・ｨﾐﾊ@ﾆﾞ蒿ﾊ赳ﾞﾜﾈﾊﾜﾆﾊ@ﾄﾊ韶ﾊﾊﾜ@靤ﾊ賁@・ﾘ・襦ﾂﾜﾈ@靤ﾊ@獎ﾒﾆﾂﾘ@跖ﾂ靆襦ﾞﾌ@靤ﾊ@・ﾈﾊ蒭ﾜﾎ@跖ﾞ萃ﾎﾊ@ﾞ隋ﾈﾊ・ﾆﾊ@ﾒ襦ﾂ@ﾚﾂ韋ﾊ隋ﾞﾌ@ﾆﾞﾜ・ﾜ靨ﾞﾜX@ﾂﾜﾈ@ﾈﾒﾌﾌﾊ萍ﾜ錙ﾂ跏ﾒﾎﾜﾚﾊﾜ韆@ﾚﾂﾄﾊ@・ﾊﾈ@ﾊ・ﾜ@迤靤ﾒﾜ@靤ﾊ@貭ﾚﾊ@ﾈﾊ・ﾆﾊ@ﾞ隋琅ﾞﾎ萃ﾚ\@定@ﾚﾂﾄﾊ@獎ﾒﾆﾂﾘﾘﾒﾚ獵ﾊﾚﾊﾜ靆ﾈ@迤靤@ﾂ@韶ﾞZ跖
[+] shift = 4
♂・･戟ﾕｹ･ﾐ⊃・･ｹ區ﾉｵ・･ｽｸ▼ｸ″ｽｵﾁﾕﾑ･ｹ怐・吹則擂ﾑ・″ｽｵｵﾕｹ･劫ﾑ･ｽｹﾌｸ＿｡煤ｹ・煤･ﾌ ＞・ｽﾉﾑｵ・ﾑ腐ﾔ⊃・翁ｹ・艨則擂ﾐｹlﾅt＿｡煤翁ﾐ∨蔽ﾉ箆併ﾑﾌ＞・ｽ擂劫ｰ∀ﾑ・煤ﾝ･ﾑ⊃ｹ煤ｽ・ﾑﾝｼ・ｽﾍﾍ･桶煤ﾙ・ﾕ蔑ｸ＿｡箆煤ﾙ・ﾕ蔑≦ﾉ煤ｵｽﾍﾐ″ｽｵｵｽｹｱ艨ﾉ蔽ﾉ箆併ﾑ武≦ﾌ＆･ﾑ｡癖€ﾁｽﾈﾄｰ♂ﾕﾐ⊃ﾑ｡癖∨蔽ﾉ箆併ﾑ・･ｽｹﾌ∀ﾕ頃≦ﾌ・ﾉﾕ反刔ｱﾍ伐∝蔑ｽｹｼｰ€ｬｿ・Hｰ⊃ﾈ⊃ｸｽｽ劍≦ﾉ煤鎖Q綋ﾐﾕ|ﾍｸﾁﾔ蝪}ｩTﾕQ}ﾑ=}ﾍ ﾅ厶}4ﾍ・Q｡煤鎖ﾉﾉ箆ﾁｽｹ装ｹ鵠♂篇ﾝ封ｸ・｡箆煤ﾙ・ﾕ蔑≦ｹ吹ﾑ｡煤ﾁ｡袁･劫ｰ∀ﾑ・蔑⊃・ﾑ｡煤ﾕｹ装ﾉｱ螂ｹ怐ﾍﾑｽﾉ・煤ｽﾈ￠弁･鵠▼ﾌ＞・・ﾑ癖⊃・鎖ｹﾙ併ﾑ･ｽｸｰ≦ｹ吹則劔碧併ﾐ≦ﾍﾍ･攣ｵ併ﾑﾌ・・♂煤ﾕﾍ武＆ﾙ丙∂･ﾑ｡･ｸ・｡煤ﾍ・煤装ﾙ･鵠⊃ﾈ・ﾉｽ數・ｸ・ﾐ ・・♂煤ﾁ｡袁･劫ｱｱ艨･ｵﾁｱ雰併ﾑ武∂･ﾑ＞・ﾝｼｵﾍﾑ
[+] shift = 5
姙ｫsK｡{1Ks3{徒｣K{qKq{kΝ｣Ks9s!#K;K｣a{kkｫsK｣K{s冫｣C)sk)K・ ボ謄ks｣+ｩ{1Ks橡#K;K｡rﾙ企｣C)K｡・ン+・s｣・ c{;Ka屮｣)ｻK｣A{s){1｣ｻyボ屁Kc)ｳcｫ+冫｣C+・ｳcｫ+・・k{孱{kk{scﾉ・ン+・s｣+!・+K｣C+・ボ痩aｫ｡{｣C+・・ン+・s｣｣K{s・岫A・｣騰){3c・aﾋ+几syaYD疎{・{q{{31・{kk{qpR｣C)3c9K・｢3ﾛK｡ｪqΛﾋB炫ｩｪ｢裵z蕓A・｢仡幄R｣C){涛+寃{s#+s)+｣ｻ++q｣C+・ｳcｫ+・s!｣C)イﾋ姙a屮｣+・{1｣C)ｫs#+田ﾋKs9屮{・;){・#+ｳK)K・ k｣｣+・{1{sｳ+s｣K{qas!#K33+・s｡屁K;sk+s｣・kﾉ)ｫ・!+ｳ+qｻK｣CKq｣C)・k)#+ｳK){・ン{;・iqK｡kﾉ)イﾋ姙ccﾉKkツ+k+s｣+!ｻK｣A ｣ｻyk屮
[+] shift = 6
&6・V譌B匁f・ﾖF柳・問6WF匁r襭F没友ﾂ6ﾗV譁6F柳・・F・・ﾖR・・Fﾖ蹤VR&匁'・F没唯蟲ﾒF・&唯&W&W6V蹠2ﾆ・ﾂ7FFRv友・RGv・・6・ﾆRfﾇVW2・F・6RfﾇVW2&Rﾖ・B6ﾖﾇ・&W&W6V蹤VB2V友・"・ﾂ'WB・"&W&W6V蹤F柳・7V6・2G'VRﾇ6Rﾂ妨2ｲ(・ﾂ・fb&R6ﾖ爭F・fﾆr・45Dgｶ佑U・・S妹SUE4・gE7ﾐ･F・6・&W7FV・R&WGvVV・F・6RfﾇVW2襭F・∠6・ﾂ7FFW2F・V襷W&ﾇ末誡7F・vR・FWf・R・ﾖGFW"6fV蹤柳篦襭F貿fW&V蹌76没贍V蹠2ﾖ・&RW6VBWfV・v友・・F・6ﾖRFWf・R・&&ﾒ・唯ﾖ・&R ∠6・ﾆﾇ・儲ﾆVﾖV蹤VBv友・Gv7F
[+] shift = 7
-ﾄm縈ｮ・ﾌ・-ﾌ・・・・・m縨ｮｭﾍ,l.・腠eﾄ
・M-ﾌ.O$・・・f+､
?m,M研ﾌ-汐ｮeﾄ・$
遣ｬｭﾎ軒・・・$種螳n・ ､､l-ｬ､鍵ﾍ,l､ｧ-曻ｦｪ駒雅靖,ﾎ矩ｦo｡J・､m琮Lｮshift=2の時に復号できている。
CCTF{it5_3n0u9h_jU5T_tO_sH1ft_M3}
