I participated in LINE CTF 2022 as a member of Wani Hackase, and solved four crypto challenges.

ss-puzzle

Just play an XOR puzzle using the fact S[0] == b"LINECTF{". Some values are still unknown but predictable from the restored flag.

 1def xor(a, b):
 2    return bytes(i ^ j for i, j in zip(a, b))
 3
 4with open("Share1", "rb") as f:
 5    s1 = f.read()
 6with open("Share4", "rb") as f:
 7    s4 = f.read()
 8
 9r0_s0 = s1[0:8]
10r2_s3 = s1[16:24]
11r3_s2 = s1[24:32]
12
13r0_s3 = s4[0:8]
14r1_s2 = s4[8:16]
15r2_s1 = s4[16:24]
16r3_s0 = s4[24:32]
17
18s0 = b"LINECTF{"
19r0 = xor(s0, r0_s0)
20s3 = xor(r0, r0_s3)
21r2 = xor(s3, r2_s3)
22s1 = xor(r2, r2_s1)
23r3 = xor(s0, r3_s0)
24s2 = b"wn_plain"
25r1 = xor(s2, r1_s2)
26print(s0 + s1 + s2 + s3 + r0 + r1 + r2 + r3)

Flag: LINECTF{Yeah_known_plaintext_is_important_in_xor_based_puzzle!!}

X Factor

We have seven message and signature pairs $(m_i, s_i)$.
I noticed that $f(m) \equiv m^d \mod n$ is homomorphic, and each $m_i$ contains prime factors of the target value $\hat{m} $ = 0x686178656C696F6E = 7521425229691318126.

Consider a vector $(c_0, c_1, \cdots, c_6)$ that satisfies

$$ \hat{m} \equiv m_0^{c_0} m_1^{c_1} \cdots m_6^{c_6} \mod n. $$

Once we found this vector, the signature of $\hat{m}$ is

$$ \begin{aligned} \hat{m}^d &\equiv (m_0^{c_0} m_1^{c_1} \cdots m_6^{c_6})^d &\mod n \\ &\equiv (m_0^d)^{c_0} (m_1^d)^{c_1} \cdots (m_6^d)^{c_6} &\mod n \\ &\equiv s_0^{c_0} s_1^{c_1} \cdots s_6^{c_6} &\mod n \\ \end{aligned} $$

This can be done by solving linear equations. Check out my solver for more details.

 1from sage.all import *
 2
 3e = 0x10001
 4n = 0xA9E7DA28EBECF1F88EFE012B8502122D70B167BDCFA11FD24429C23F27F55EE2CC3DCD7F337D0E630985152E114830423BFAF83F4F15D2D05826BF511C343C1B13BEF744FF2232FB91416484BE4E130A007A9B432225C5EAD5A1FAF02FA1B1B53D1ADC6E62236C798F76695BB59F737D2701FE42F1FBF57385C29DE12E79C5B3
 5
 6
 7M = [0x945D86B04B2E7C7, 0x5DE2, 0xA16B201CDD42AD70DA249, 0x6D993121ED46B, 0x726FA7A7, 0x31E828D97A0874CFF, 0x904A515]
 8
 9S = [
10    0x17BB21949D5A0F590C6126E26DC830B51D52B8D0EB4F2B69494A9F9A637EDB1061BEC153F0C1D9DD55B1AD0FD4D58C46E2DF51D293CDAAF1F74D5EB2F230568304EEBB327E30879163790F3F860CA2DA53EE0C60C5E1B2C3964DBCF194C27697A830A88D53B6E0AE29C616E4F9826EC91F7D390FB42409593E1815DBE48F7ED4,
11    0x3EA73715787028B52796061FB887A7D36FB1BA1F9734E9FD6CB6188E087DA5BFC26C4BFE1B4F0CBFA0D693D4AC0494EFA58888E8415964C124F7EF293A8EE2BC403CAD6E9A201CDD442C102B30009A3B63FA61CDD7B31CE9DA03507901B49A654E4BB2B03979AEA0FAB3731D4E564C3C30C75AA1D079594723B60248D9BDDE50,
12    0x9444E3FC71056D25489E5CE78C6C986C029F12B61F4F4B5CBD4A0CE6B999919D12C8872B8F2A8A7E91BD0F263A4EAD8F2AA4F7E9FDB9096C2EA11F693F6AA73D6B9D5E351617D6F95849F9C73EDABD6A6FDE6CC2E4559E67B0E4A2EA8D6897B32675BE6FC72A6172FD42A8A8E96ADFC2B899015B73FF80D09C35909BE0A6E13A,
13    0x2B7A1C4A1A9E9F9179AB7B05DD9E0089695F895864B52C73BFBC37AF3008E5C187518B56B9E819CC2F9DFDFFDFB86B7CC44222B66D3EA49DB72C72EB50377C8E6EB6F6CBF62EFAB760E4A697CBFDCDC47D1ADC183CC790D2E86490DA0705717E5908AD1AF85C58C9429E15EA7C83CCF7D86048571D50BD721E5B3A0912BED7C,
14    0xA7D5548D5E4339176A54AE1B3832D328E7C512BE5252DABD05AFA28CD92C7932B7D1C582DC26A0CE4F06B1E96814EE362ED475DDAF30DD37AF0022441B36F08EC8C7C4135D6174167A43FA34F587ABF806A4820E4F74708624518044F272E3E1215404E65B0219D42A706E5C295B9BF0EE8B7B7F9B6A75D76BE64CF7C27DFAEB,
15    0x67832C41A913BCC79631780088784E46402A0A0820826E648D84F9CC14AC99F7D8C10CF48A6774388DAABCC0546D4E1E8E345EE7FC60B249D95D953AD4D923CA3AC96492BA71C9085D40753CAB256948D61AEEE96E0FE6C9A0134B807734A32F26430B325DF7B6C9F8BA445E7152C2BF86B4DFD4293A53A8D6F003BF8CF5DFFD,
16    0x927A6ECD74BB7C7829741D290BC4A1FD844FA384AE3503B487ED51DBF9F79308BB11238F2AC389F8290E5BCEBB0A4B9E09EDA084F27ADD7B1995EEDA57EB043DEEE72BFEF97C3F90171B7B91785C2629AC9C31CBDCB25D081B8A1ABC4D98C4A1FD9F074B583B5298B2B6CC38CA0832C2174C96F2C629AFE74949D97918CBEE4A,
17]
18
19
20mm = 0x686178656C696F6E
21
22
23factors = {m: factor(m) for m in M}
24factor_set = set()
25for F in factors.values():
26    factor_set |= set(p for p, e in F)
27factor_set = sorted(factor_set)
28
29
30A = [[dict(F).get(p, 0) for p in factor_set] for F in factors.values()]
31A = matrix(A)
32
33b = [dict(factor(mm)).get(p, 0) for p in factor_set]
34b = matrix(b)
35
36X = A.solve_left(b)[0]
37
38ans = 1
39for s, exp in zip(S, X):
40    ans *= int(pow(s, exp, n))
41    ans %= n
42
43assert pow(ans, e, n) == mm
44ans = f"{ans:x}"
45ans = f"LINECTF{{{ans[-32:]}}}"
46print(ans)

Flag: LINECTF{a049347a7db8226d496eb55c15b1d840}

Baby crypto revisited

One hundred equations for ECDSA are given and some values are missing. Let the original value of missing $k$ be $\hat{k}_i := k_i + x_i$. Given parameters satisfy

$$ \begin{aligned} s_i &\equiv \hat{k}_i^{-1}(h_i + r_id) \mod n . \end{aligned} $$

Because the missing values $x_i$ are relatively small(64bit), I soon realized that $x_i$ can be recovered using lattice reduction.

$$ \begin{pmatrix} \ell_0 \\ \ell_1 \\ \vdots \\ \ell_{99} \\ d \\ 1 \\ \end{pmatrix} ^T \begin{pmatrix} n & 0& \cdots & 0 & 0 & 0 \\ 0 & n & \cdots & 0 & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & \cdots & n & 0 & 0 \\ r_0s_0^{-1} & r_1s_1^{-1} & \cdots & r_{99}s_{99}^{-1} & c_1 & 0 \\ h_0s_0^{-1} - k_0 & h_1s_1^{-1} - k_1 & \cdots & h_{99}s_{99}^{-1} - k_{99} & 0 & c_2 \\ \end{pmatrix}= \begin{pmatrix} x_0 \\ x_1 \\ \vdots \\ x_{99} \\ c_1d \\ c_2 \\ \end{pmatrix} ^T $$

I chose $c_1, c_2$ have the same bit as $x_i$(=64bit).

 1from sage.all import *
 2
 3with open("output.txt") as f:
 4    parse = lambda x: int(x, 0)
 5    params = [list(map(parse, line.split())) for line in f.readlines()]
 6
 7
 8# secp160r1
 9n = 0x0100000000000000000001F4C8F927AED3CA752257
10
11m = len(params)
12A = [[0 for _ in range(m + 2)] for _ in range(m + 2)]
13
14
15c1 = pow(2, 64 - 160)
16c2 = 1 << 64
17
18
19for i, (r, s, k, h) in enumerate(params):
20    inv_s = inverse_mod(s, n)
21    A[i][i] = n
22    A[m][i] = r * inv_s % n
23    A[m + 1][i] = (h * inv_s - k) % n
24A[m][m] = c1
25A[m + 1][m + 1] = c2
26
27A = matrix(A)
28
29for line in A.LLL():
30    if line[-1] == 1 << 64:
31        r, s, k, h = params[0]
32        x = int(line[0])
33        d = ((k + x) * s - h) * inverse_mod(r, n) % n
34        flag = f"LINECTF{{{int(d):#x}}}"
35        print(flag)
36        break

Flag: LINECTF{0xd77d10fec685cbe16f64cba090db24d23b92f824}

Forward-or

Since a first block of the plaintext is b"LINECTF{", we can easily get XOR(cipher1.decrypt(ciphertext), b"LINECTF{"). Furthermore, cipher0.encrypt(nonce || counter(=0)) can also be calculated.

Using these information, a key of CTRMode can be recovered by performing meet-in-the-middle(MITM) attack. That is, the key that satisfies a condition cipher1.decrypt(ciphertext) == cipher0.encrypt(nonce || counter(=0)) can be found by brute force.

For a $k$-byte key, a greedy method requires $O(4^k)$ trials, but can be reduced into $O(4^{k/2}) = O(2^k)$ by MITM.

  1import os
  2from multiprocessing import Pool
  3
  4from Crypto.Util.strxor import strxor
  5
  6from present import Present
  7
  8ciphertext = bytes.fromhex("3201339d0fcffbd152f169ddcb8349647d8bc36a73abc4d981d3206f4b1d98468995b9b1c15dc0f0")
  9nonce = bytes.fromhex("32e10325")
 10
 11
 12class CTRMode:
 13    def __init__(self, key, nonce=None):
 14        self.key = key  # 20bytes
 15        self.cipher = DoubleRoundReducedPresent(key)
 16        if None == nonce:
 17            nonce = os.urandom(self.cipher.block_size // 2)
 18        self.nonce = nonce  # 4bytes
 19
 20    def XorStream(self, data):
 21        output = b""
 22        counter = 0
 23        for i in range(0, len(data), self.cipher.block_size):
 24            keystream = self.cipher.encrypt(self.nonce + counter.to_bytes(self.cipher.block_size // 2, "big"))
 25            if b"" == keystream:
 26                exit(1)
 27
 28            if len(data) < i + self.cipher.block_size:
 29                block = data[i : len(data)]
 30            block = data[i : i + self.cipher.block_size]
 31            block = strxor(keystream[: len(block)], block)
 32
 33            output += block
 34            counter += 1
 35        return output
 36
 37    def encrypt(self, plaintext):
 38        return self.XorStream(plaintext)
 39
 40    def decrypt(self, ciphertext):
 41        return self.XorStream(ciphertext)
 42
 43
 44class DoubleRoundReducedPresent:
 45    def __init__(self, key):
 46        self.block_size = 8
 47        self.key_length = 160  # bits
 48        self.round = 16
 49        self.cipher0 = Present(key[0:10], self.round)
 50        self.cipher1 = Present(key[10:20], self.round)
 51
 52    def encrypt(self, plaintext):
 53        if len(plaintext) > self.block_size:
 54            print("Error: Plaintext must be less than %d bytes per block" % self.block_size)
 55            return b""
 56        return self.cipher1.encrypt(self.cipher0.encrypt(plaintext))
 57
 58    def decrypt(self, ciphertext):
 59        if len(ciphertext) > self.block_size:
 60            print("Error: Ciphertext must be less than %d bytes per block" % self.block_size)
 61            return b""
 62        return self.cipher1.decrypt(self.cipher0.decrypt(ciphertext))
 63
 64
 65def quad(x):
 66    s = ""
 67    while x > 0:
 68        x, t = divmod(x, 4)
 69        s += str(t)
 70    return s[::-1].zfill(10).encode()
 71
 72
 73def __store_key(args):
 74    pn, start, end, nonce, ciphertext = args
 75    ck = {}
 76    p0 = nonce + (0).to_bytes(4, "big")
 77    for i, key in enumerate(range(start, end)):
 78        if i % 10000 == 0:
 79            print(f"{pn}: {i / (end-start):.1%}")
 80        key = quad(key)
 81        cipher = Present(key, 16)
 82        c_ = cipher.encrypt(p0)
 83        ck[c_] = key
 84
 85    return ck
 86
 87
 88def __find_key(args):
 89    pn, start, end, ck = args
 90    c0 = strxor(ciphertext[0:8], b"LINECTF{")
 91    for i, key in enumerate(range(start, end)):
 92        if i % 10000 == 0:
 93            print(f"{pn}: {i / (end-start):.1%}")
 94        key = quad(key)
 95        cipher = Present(key, 16)
 96        c_ = cipher.decrypt(c0)
 97        if c_ in ck:
 98            print("[+] Found")
 99            print(f"[+] key = {ck[c_].hex()}{key.hex()}")
100            key = ck[c_] + key
101            return key
102
103    return None
104
105
106def find_key(nonce, ciphertext, lb=0, ub=4 ** 10, process_num=4):
107    assert ub % process_num == 0
108    print("[*] Creating a key table...")
109    with Pool(processes=process_num) as p:
110        results = p.imap_unordered(
111            func=__store_key,
112            iterable=[[i, ub // process_num * i, ub // process_num * (i + 1), nonce, ciphertext] for i in range(process_num)],
113        )
114        cks = {}
115        for result in results:
116            cks |= result or {}
117
118    print("[*] Finding a key from the table...")
119    with Pool(processes=process_num) as p:
120        results = p.imap_unordered(
121            func=__find_key,
122            iterable=[[i, ub // process_num * i, ub // process_num * (i + 1), cks] for i in range(process_num)],
123        )
124        for result in results:
125            if result:
126                return result
127
128
129def solve(key=None):
130    key = key if key else find_key(nonce, ciphertext, process_num=8)
131    cipher = CTRMode(key, nonce=nonce)
132    plaintext = cipher.decrypt(ciphertext)
133    print(plaintext)
134
135
136solve()

Flag: LINECTF{|->TH3Y_m3t_UP_1n_th3_m1ddl3<-|}