この大会は2022/3/19 19:30(JST)～2022/3/21 19:30(JST)に開催されました。
今回もチームで参戦。結果は484点で665チーム中55位でした。
自分で解けた問題をWriteupとして書いておきます。
Welcome (Misc)
問題にフラグが書いてあった。
LINECTF{welcome_to_LINECTF2022}
X Factor (Crypto, Warmup)
RSA署名でnとeはわかっている。平文とその対応するシグネチャのペアが7つ提示されている。0x686178656c696f6eのシグネチャを算出する問題。
素因数分解してみる。
>>> 0x686178656c696f6e
7521425229691318126L
G = 7521425229691318126 = 2 * 197 * 947 * 2098711 * 9605087
>>> 0x945d86b04b2e7c7
668178073886320583L
>>> 0x5de2
24034
>>> 0xa16b201cdd42ad70da249
12196433909207788967273033L
>>> 0x6d993121ed46b
1928075547694187L
>>> 0x726fa7a7
1919920039
>>> 0x31e828d97a0874cff
57538707471611677951L
>>> 0x904a515
151299349
E1 = 668178073886320583 = 811 * 947^3 * 970111
E2 = 24034 = 2 * 61 * 197
E3 = 12196433909207788967273033 = 970111 * 2098711^2 * 2854343
E4 = 1928075547694187 = 947 * 970111 * 2098711
E5 = 1919920039 = 61 * 197^2 * 811
E6 = 57538707471611677951 = 2098711 * 2854343 * 9605087
E7 = 151299349 = 197 * 811 * 947
2 61 197 811 947 970111 2098711 2854343 9605087
G 1 0 1 0 1 0 1 0 1
E1 0 0 0 1 3 1 0 0 0
E2 1 1 1 0 0 0 0 0 0
E3 0 0 0 0 0 1 2 1 0
E4 0 0 0 0 1 1 1 0 0
E5 0 1 2 1 0 0 0 0 0
E6 0 0 0 0 0 0 1 1 1
E7 0 0 1 1 1 0 0 0 0方程式にして各値の積の組み合わせの等式を作る。実行結果から以下が成り立つ。
G * E1 * E3 * E5 = E2 * E4 * E4 * E6 * E7 * E7
これは署名でも同様に成り立つため、目的のシグネチャを算出することができる。
#!/usr/bin/env python3 from sympy import * n = 0xa9e7da28ebecf1f88efe012b8502122d70b167bdcfa11fd24429c23f27f55ee2cc3dcd7f337d0e630985152e114830423bfaf83f4f15d2d05826bf511c343c1b13bef744ff2232fb91416484be4e130a007a9b432225c5ead5a1faf02fa1b1b53d1adc6e62236c798f76695bb59f737d2701fe42f1fbf57385c29de12e79c5b3 signs = [ 0x17bb21949d5a0f590c6126e26dc830b51d52b8d0eb4f2b69494a9f9a637edb1061bec153f0c1d9dd55b1ad0fd4d58c46e2df51d293cdaaf1f74d5eb2f230568304eebb327e30879163790f3f860ca2da53ee0c60c5e1b2c3964dbcf194c27697a830a88d53b6e0ae29c616e4f9826ec91f7d390fb42409593e1815dbe48f7ed4, 0x3ea73715787028b52796061fb887a7d36fb1ba1f9734e9fd6cb6188e087da5bfc26c4bfe1b4f0cbfa0d693d4ac0494efa58888e8415964c124f7ef293a8ee2bc403cad6e9a201cdd442c102b30009a3b63fa61cdd7b31ce9da03507901b49a654e4bb2b03979aea0fab3731d4e564c3c30c75aa1d079594723b60248d9bdde50, 0x9444e3fc71056d25489e5ce78c6c986c029f12b61f4f4b5cbd4a0ce6b999919d12c8872b8f2a8a7e91bd0f263a4ead8f2aa4f7e9fdb9096c2ea11f693f6aa73d6b9d5e351617d6f95849f9c73edabd6a6fde6cc2e4559e67b0e4a2ea8d6897b32675be6fc72a6172fd42a8a8e96adfc2b899015b73ff80d09c35909be0a6e13a, 0x2b7a1c4a1a9e9f9179ab7b05dd9e0089695f895864b52c73bfbc37af3008e5c187518b56b9e819cc2f9dfdffdfb86b7cc44222b66d3ea49db72c72eb50377c8e6eb6f6cbf62efab760e4a697cbfdcdc47d1adc183cc790d2e86490da0705717e5908ad1af85c58c9429e15ea7c83ccf7d86048571d50bd721e5b3a0912bed7c, 0xa7d5548d5e4339176a54ae1b3832d328e7c512be5252dabd05afa28cd92c7932b7d1c582dc26a0ce4f06b1e96814ee362ed475ddaf30dd37af0022441b36f08ec8c7c4135d6174167a43fa34f587abf806a4820e4f74708624518044f272e3e1215404e65b0219d42a706e5c295b9bf0ee8b7b7f9b6a75d76be64cf7c27dfaeb, 0x67832c41a913bcc79631780088784e46402a0a0820826e648d84f9cc14ac99f7d8c10cf48a6774388daabcc0546d4e1e8e345ee7fc60b249d95d953ad4d923ca3ac96492ba71c9085d40753cab256948d61aeee96e0fe6c9a0134b807734a32f26430b325df7b6c9f8ba445e7152c2bf86b4dfd4293a53a8d6f003bf8cf5dffd, 0x927a6ecd74bb7c7829741d290bc4a1fd844fa384ae3503b487ed51dbf9f79308bb11238f2ac389f8290e5bcebb0a4b9e09eda084f27add7b1995eeda57eb043deee72bfef97c3f90171b7b91785c2629ac9c31cbdcb25d081b8a1abc4d98c4a1fd9f074b583b5298b2b6cc38ca0832c2174c96f2c629afe74949d97918cbee4a ] x1 = symbols('x1') x2 = symbols('x2') x3 = symbols('x3') x4 = symbols('x4') x5 = symbols('x5') x6 = symbols('x6') x7 = symbols('x7') eq1 = Eq(x2, 1) eq2 = Eq(x2 + x5, 0) eq3 = Eq(x2 + x5 * 2 + x7, 1) eq4 = Eq(x1 + x5 + x7, 0) eq5 = Eq(x1 * 3 + x4 + x7, 1) eq6 = Eq(x1 + x3 + x4, 0) eq7 = Eq(x3 * 2 + x4 + x6, 1) eq8 = Eq(x3 + x6, 0) eq9 = Eq(x6, 1) sol = solve([eq1, eq2, eq3, eq4, eq5, eq6, eq7, eq8, eq9], [x1, x2, x3, x4, x5, x6, x7]) xs = [] for xi in sol: xs.append(int(sol[xi])) sign = 1 for i in range(len(xs)): sign *= pow(signs[i], xs[i], n) sign %= n flag = 'LINECTF{%s}' % hex(sign)[-32:] print(flag)
LINECTF{a049347a7db8226d496eb55c15b1d840}
ss-puzzle (Crypto)
以下のようにフラグを分割して、xorをしてデータを作成している。
S[0] = FLAG[0:8] S[1] = FLAG[8:16] S[2] = FLAG[16:24] S[3] = FLAG[24:32] R[0] = FLAG[32:40] R[1] = FLAG[40:48] R[2] = FLAG[48:56] R[3] = FLAG[56:64] Share[0] = R[0] + xor(R[1], S[3]) + xor(R[2], S[2]) + xor(R[3],S[1]) Share[1] = xor(R[0], S[0]) + R[1] + xor(R[2], S[3]) + xor(R[3],S[2]) Share[2] = xor(R[0], S[1]) + xor(R[1], S[0]) + R[2] + xor(R[3],S[3]) Share[3] = xor(R[0], S[2]) + xor(R[1], S[1]) + xor(R[2], S[0]) + R[3] Share[4] = xor(R[0], S[3]) + xor(R[1], S[2]) + xor(R[2], S[1]) + xor(R[3],S[0])
また以下のようにして一部データ(9～16バイト目)が壊れた状態になっている。
Share[1] = Share[1][0:8] + b'\x00'*8 + Share[1][16:24] + Share[1][24:32]
フラグ形式から以下がわかる。
S[0] = b'LINECTF{'順に割り出していく。
S[0] -> R[0] (Share1) S[0] -> R[3] (Share4) R[0] -> S[3] (Share4) R[3] -> S[2] (Share1) S[3] -> R[2] (Share1) S[2] -> R[1] (Share4) R[2] -> S[1] (Share4)
あとは連結すればフラグになる。
#!/usr/bin/env python3 def xor(a:bytes, b:bytes) -> bytes: return bytes(i^j for i, j in zip(a, b)) with open('Share1', 'rb') as f: Share1 = f.read() with open('Share4', 'rb') as f: Share4 = f.read() S = [None]*4 R = [None]*4 S[0] = b'LINECTF{' R[0] = xor(Share1[:8], S[0]) R[3] = xor(Share4[24:], S[0]) S[3] = xor(Share4[:8], R[0]) S[2] = xor(Share1[24:], R[3]) R[2] = xor(Share1[16:24], S[3]) R[1] = xor(Share4[8:16], S[2]) S[1] = xor(Share4[16:24], R[2]) flag = (b''.join(S) + b''.join(R)).decode() print(flag)
LINECTF{Yeah_known_plaintext_is_important_in_xor_based_puzzle!!}
Baby crypto revisited (Crypto)
ECDSAの問題。r, s, kの上位64bit、hashの組が100組あり、dを求める必要がある。https://blog.y011d4.com/20210321-line-ctf-writeup/を参考にLLLを使って解く。
#!/usr/bin/env sage # secp160r1 parameters p = 0xffffffffffffffffffffffffffffffff7fffffff K = GF(p) a = K(0xffffffffffffffffffffffffffffffff7ffffffc) b = K(0x1c97befc54bd7a8b65acf89f81d4d4adc565fa45) E = EllipticCurve(K, (a, b)) G = E(0x4a96b5688ef573284664698968c38bb913cbfc82, 0x23a628553168947d59dcc912042351377ac5fb32) E.set_order(0x0100000000000000000001f4c8f927aed3ca752257 * 0x01) n = int(E.order()) with open('Babycrypto_revisited_b1f108dea290b83253b80443260b12c3cadc0ed7.txt', 'r') as f: lines = f.read().splitlines() N = len(lines) r = [0] * N s = [0] * N k = [0] * N h = [0] * N for i in range(N): params = lines[i].split() r[i] = int(params[0], 16) s[i] = int(params[1], 16) k[i] = int(params[2], 16) h[i] = int(params[3], 16) t = [r[i] * inverse_mod(s[i], n) % n for i in range(N)] u = [(h[i] * inverse_mod(-s[i], n) % n) % n for i in range(N)] nonce_max = 2**128 B = matrix(QQ, N + 2, N + 2) B.set_block(0, 0, matrix.identity(N) * n) B.set_block(N, 0, matrix(QQ, 1, N, t)) B.set_block(N+1, 0, matrix(QQ, 1, N, u)) B[N,N] = nonce_max / n B[N+1,N+1] = nonce_max L = B.LLL() for row in list(L): k1 = int(abs(row[0])) if k1 != 0 and k1 != nonce_max and k1 < nonce_max: x = (k1*s[0] - h[0]) * inverse_mod(r[0], n) % n kk = (k1 >> 64) << 64 assert kk in k flag = 'LINECTF{0x%x}' % x print(flag) break
LINECTF{0xd77d10fec685cbe16f64cba090db24d23b92f824}
Forward-or (Crypto)
暗号処理の概要は以下の通り。
・key: '0'～'3'で構成された20バイト文字列 ・cipher = CTFMode(key) ・self.cipher = DoubleRoundReducedPresent(key) ・self.block_size = 8 ・self.key_length = 160 ・self.round = 16 ・self.cipher0 = Present(key[0:10], self.round) ・self.rounds = 16 ・self.roundkeys = generateRoundkeys80(byte2number(key[0:10]),self.rounds) ・self.cipher1 = Present(key[10:20], self.round) ・self.rounds = 16 ・self.roundkeys = generateRoundkeys80(byte2number(key[10:20],self.rounds) ・self.nonce = os.urandom(4) ・ciphertext = cipher.encrypt(plain) ・self.XorStream(plain) ・plain、8バイトごとに以下を処理する。 ・keystream = self.cipher.encrypt(self.nonce+counter.to_bytes(self.cipher.block_size//2, 'big')) nonce+counterの暗号化 ・ciphertext = self.cipher0.encrypt(nonce+counter) ・ciphertext = self.cipher1.encrypt(ciphertext) ・keystreamとplainの8バイトのXOR ・counter: +1 ・暗号化結果、nonceを表示
Presentの内容はあまり気にする必要はない。フラグの先頭はLINECTF{であることから、最初のブロックの平文と暗号の組み合わせがわかる。異なる10バイトのキーで2回暗号化しているので、平文のkey[0:10]で暗号化したものと暗号文のkey[10:20]で復号したものが一致するものを探す。
#!/usr/bin/env python3 from present import Present from Crypto.Util.strxor import strxor import itertools class CTRMode(): def __init__(self, key, nonce=None): self.key = key # 20bytes self.cipher = DoubleRoundReducedPresent(key) if None==nonce: nonce = os.urandom(self.cipher.block_size//2) self.nonce = nonce # 4bytes def XorStream(self, data): output = b"" counter = 0 for i in range(0, len(data), self.cipher.block_size): keystream = self.cipher.encrypt(self.nonce+counter.to_bytes(self.cipher.block_size//2, 'big')) if b""==keystream: exit(1) if len(data)<i+self.cipher.block_size: block = data[i:len(data)] block = data[i:i+self.cipher.block_size] block = strxor(keystream[:len(block)], block) output+=block counter+=1 return output def encrypt(self, plaintext): return self.XorStream(plaintext) def decrypt(self, ciphertext): return self.XorStream(ciphertext) class DoubleRoundReducedPresent(): def __init__(self, key): self.block_size = 8 self.key_length = 160 # bits self.round = 16 self.cipher0 = Present(key[0:10], self.round) self.cipher1 = Present(key[10:20], self.round) def encrypt(self, plaintext): if len(plaintext)>self.block_size: print("Error: Plaintext must be less than %d bytes per block" % self.block_size) return b"" return self.cipher1.encrypt(self.cipher0.encrypt(plaintext)) def decrypt(self, ciphertext): if len(ciphertext)>self.block_size: print("Error: Ciphertext must be less than %d bytes per block" % self.block_size) return b"" return self.cipher0.decrypt(self.cipher1.decrypt(ciphertext)) def base10_to_4(X): if (int(X // 4)): return base10_to_4(int(X // 4)) + str(X % 4) return str(X % 4) ciphertext_hex = '3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0' nonce_hex = '32e10325' ciphertext = bytes.fromhex(ciphertext_hex) nonce = bytes.fromhex(nonce_hex) flag0 = 'LINECTF{'.encode('ascii') counter = 0 nonce_ctr = nonce + counter.to_bytes(4, 'big') xor0 = strxor(flag0, ciphertext[:8]) cts = [] pts = [] for c in itertools.product('0123', repeat=10): key0 = ''.join(c).encode('ascii') key1 = ''.join(c).encode('ascii') cipher0 = Present(key0, 16) cipher1 = Present(key1, 16) ct = cipher0.encrypt(nonce_ctr) pt = cipher1.decrypt(xor0) cts.append(ct) pts.append(pt) ct_set = set(cts) pt_set = set(pts) ct = list(ct_set & pt_set)[0] index1 = cts.index(ct) index2 = pts.index(ct) key0 = base10_to_4(index1).encode('ascii') key1 = base10_to_4(index2).encode('ascii') key = key0 + key1 print('[+] key:', key.decode()) cipher = CTRMode(key, nonce) flag = cipher.decrypt(ciphertext).decode() print('[*] flag:', flag)
実行結果は以下の通り。
[+] key: 32013230202123003302
[*] flag: LINECTF{|->TH3Y_m3t_UP_1n_th3_m1ddl3<-|}
LINECTF{|->TH3Y_m3t_UP_1n_th3_m1ddl3<-|}
