PBCTF 2nd place, Super Guesser (apparently Super Guessers)

Solved : Goodhash, Yet Another RSA, Yet Another PRNG, Seed Me

 

Goodhash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#!/usr/bin/env python3
 
from Crypto.Cipher import AES
from Crypto.Util.number import *
from flag import flag
import json
import os
import string
 
ACCEPTABLE = string.ascii_letters + string.digits + string.punctuation + " "
 
 
class GoodHash:
    def __init__(self, v=b""):
        self.key = b"goodhashGOODHASH"
        self.buf = v
 
    def update(self, v):
        self.buf += v
 
    def digest(self):
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.buf)
        enc, tag = cipher.encrypt_and_digest(b"\0" * 32)
        return enc + tag
 
    def hexdigest(self):
        return self.digest().hex()
 
 
if __name__ == "__main__":
    token = json.dumps({"token": os.urandom(16).hex(), "admin"False})
    token_hash = GoodHash(token.encode()).hexdigest()
    print(f"Body: {token}")
    print(f"Hash: {token_hash}")
 
    inp = input("> ")
    if len(inp) > 64 or any(v not in ACCEPTABLE for v in inp):
        print("Invalid input :(")
        exit(0)
 
    inp_hash = GoodHash(inp.encode()).hexdigest()
 
    if token_hash == inp_hash:
        try:
            token = json.loads(inp)
            if token["admin"== True:
                print("Wow, how did you find a collision?")
                print(f"Here's the flag: {flag}")
            else:
                print("Nice try.")
                print("Now you need to set the admin value to True")
        except:
            print("Invalid input :(")
    else:
        print("Invalid input :(")
 
cs

 

This is a hash collision challenge. We read the code to find the following two facts.

  • The hash function is computed by sending the input as the nonce, and encrypting 32 zero bytes with AES-GCM with a known key. 
  • Our collision needs to be in a JSON format, with "admin" being set to True.

Usually, in AES-GCM, the nonce is 12 bytes. However, we may send a bytearray with larger length, which suggests that there will be some logic that compresses our bytearray to be 12 bytes. With this in mind, we look at the pycryptodome library code.

 

https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/Cipher/_mode_gcm.py

 

The important part begins at line 229. If the length of the input nonce is not 12, we compute the GHASH of $$ \text{pad}(m) || 0^{64} || \text{len}(m)$$ where $\text{pad}(m)$ is $m$ padded to be a bytearray of length multiple of 16 by appending zero bytes appropriately.

To compute the GHASH, we use the finite field $GF(2^{128})$ and denote $$H = \text{Enc}_{key}(0^{128})$$ and apply $$\text{GHASH}(X_1 || X_2 || \cdots || X_n) = X_1 H^n + X_2 H^{n-1} + \cdots + X_n$$ Since we already know $H$, we can control the GHASH of a bytearray even if we select all but one block arbitrarily. In other words, we can choose $n-1$ blocks in any way we want, and we can fully control the GHASH by carefully selecting the value of the remaining one block. 

 

Solution 1

 

The above fact gives us one immediate idea. We can attempt to construct a bytearray that 

  • Has length 61, which is the length of the original JSON, which is there to force same GHASH for the actual final block
  • Can be converted into a JSON structure, with "admin" being set to true 
  • Has the same GHASH after being padded to 64 bytes (i.e. 4 blocks) as the original JSON 

To do so, we can fix 2 out of the 4 blocks of the bytearray for it to be a JSON with "admin" set to true, arbitrarily select one of remaining blocks, then compute the final block so that it matches the GHASH, hoping that all four blocks only contain the allowed characters. For example, we can make the bytearray start with {"admin":true,"a and end with ":"abcdefgh"}\x00\x00\x00 since length 61 means \x00\x00\x00 will be padded at the end. Now we can randomly select some 16 byte string using allowed characters and set it as the second block, then compute the third block by matching GHASH to be equal, hoping that the third block also consists of allowed characters and do not interfere with the whole JSON business. While this works, and some people definitely have used this solution to solve, this idea is not very efficient. This is because the probability of success is quite low, and each trial does require some computation. 

 

Solution 2 

 

In my opinion, the cleaner way to solve this challenge is to view the GHASH equation not as a linear equation of blocks, but a linear equation of bits that make up those blocks. Indeed, due to the linear nature of the GHASH, we can actually consider the bytearray as a bit vector, and the GHASH function still keeps its linearity. Therefore, the GHASH equation is just a system of linear equations over $GF(2)$, where the variables are the 512 (64 bytes) bits of the padded bytearray. Let's keep a track of the equations that we have. 

  • Since the equation is over $GF(2^{128})$ we can convert this into 128 linear equations over $GF(2)$.
  • We can fix some characters - I made my padded JSON start with {"admin": true, "a": " and end with "}\x00\x00\x00.
  • This is a total of 27 characters, which is equivalent to 216 fixed bits over $GF(2)$.

Since we have 512 bits of freedom, we can definitely solve this. However, the issue of allowed characters is still there.

To make our random trial work with less trial and error, we add an extra idea - make every character's ASCII value between 64 and 95.

This can be done by forcing the 7th bit to be 0, 6th bit to be 1, and 5th bit to be 0.

  • Since we have 37 characters remaining, this gives us an additional 111 fixed bits over $GF(2)$.

Now $128 + 216 + 111$ is still well below $512$, so now we can just solve this matrix equation, try some random solutions using its kernel basis, and keep going on until we find a good collision for us to solve the challenge. Very fun challenge to work on :)

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
pclass GoodHash:
    def __init__(self, v=b""):
        self.key = b"goodhashGOODHASH"
        self.buf = v
 
    def update(self, v):
        self.buf += v
 
    def digest(self):
        cipher = AES.new(self.key, AES.MODE_GCM, nonce=self.buf)
        enc, tag = cipher.encrypt_and_digest(b"\0" * 32)
        return enc + tag
 
    def hexdigest(self):
        return self.digest().hex()
 
POL = PolynomialRing(GF(2), 'a')
= POL.gen()
= GF(2 ** 128, name = 'a', modulus = a ** 128 + a ** 7 + a ** 2 + a + 1)
 
def aes_enc(p, k):
    cipher = AES.new(key = k, mode = AES.MODE_ECB)
    return cipher.encrypt(p)
 
def int_to_finite(v):
    bin_block = bin(v)[2:].zfill(128)
    res = 0
    for i in range(128):
        res += (a ** i) * int(bin_block[i])
    return F(res)
 
def bytes_to_finite(v):
    v = bytes_to_long(v)
    return int_to_finite(v)
 
def finite_to_int(v):
    v = POL(v)
    res = v.coefficients(sparse = False)
    ret = 0
    for i in range(len(res)):
        ret += int(res[i]) * (1 << (127 - i))
    return ret
 
def finite_to_bytes(v):
    cc = finite_to_int(v)
    return long_to_bytes(cc, blocksize = 16)
 
def hasher(v):
    H = aes_enc(b"\x00" * 16, b"goodhashGOODHASH")
    H_f = bytes_to_finite(H)
    ret = F(0)
    res = bytes_to_long(v)
    bin_block = bin(res)[2:].zfill(512)
    bas = []
    for i in range(512):
        cc = F(a ** int(i % 128)) * F(H_f ** (3 - i // 128)) 
        bas.append(finite_to_int(cc))
        ret += F(a ** int(i % 128)) * F(H_f ** (3 - i // 128)) * int(bin_block[i])
    return bas, finite_to_int(ret)
 
ACCEPTABLE = string.ascii_letters + string.digits + string.punctuation + " "
print(ACCEPTABLE)
 
conn = remote('good-hash.chal.perfect.blue'1337)
body = conn.recvline()[6:-1]
print(body)
print(len(body))
print(conn.recvline())
 
bases, target = hasher(body + b"\x00\x00\x00")
 
starter = b'{"admin": true, "a": "'
finisher = b'"}\x00\x00\x00'
print(len(starter) + len(finisher))
 
print("[+] Building Matrix")
 
SZ = 128 + 37 * 3 + 27 * 8
= Matrix(GF(2), SZ, 512)
vv = []
 
for i in range(128):
    for j in range(512):
        M[i, j] = (bases[j] >> i) & 1
    vv.append((target >> i) & 1)
 
for i in range(37):
    M[3 * i + 1288 * (22 + i)] = 1
    vv.append(0# 128
    M[3 * i + 128 + 18 * (22 + i) + 1= 1
    vv.append(1# 64
    M[3 * i + 128 + 28 * (22 + i) + 2= 1
    vv.append(0# 32
 
for i in range(22):
    for j in range(8):
        M[8 * i + j + 37 * 3 + 1288 * i + j] = 1
        vv.append((int(starter[i]) >> (7 - j)) & 1)
for i in range(5):
    for j in range(8):
        M[8 * i + j + 37 * 3 + 22 * 8 + 1288 * (59 + i) + j] = 1
        vv.append((int(finisher[i]) >> (7 - j)) & 1)
 
vv = vector(GF(2), vv)
val = M.solve_right(vv)
kernels = M.right_kernel().basis()
 
print("[+] Finished Solving Matrix, Finding Collision Now...")
 
attempts = 0
 
while True:
    attempts += 1
    print(attempts)
    cur = val 
    for i in range(len(kernels)):
        cur += (kernels[i] * GF(2)(rand.randint(01)))
    fins = 0
    for i in range(512):
        fins = 2 * fins + int(cur[i])
    fins = long_to_bytes(fins)
    print(fins)
    fins = fins[:61]
    print(fins, len(fins))
    try:
        if len(fins) == 61 and (any(v not in ACCEPTABLE for v in fins.decode()) == False):
            token = json.loads(fins)
            bases2, finresult = hasher(fins + b"\x00\x00\x00")
            print(GoodHash(body + b"\x00\x00\x00").hexdigest())
            print(GoodHash(fins + b"\x00\x00\x00").hexdigest())
            print(target)
            print(finresult)
            print(token)
            if token["admin"== True:
                conn.sendline(fins)
                print(conn.recvline())
                print(conn.recvline())
                break
    except:
        pass
cs

 

 

Yet Another RSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#!/usr/bin/env python3
 
from Crypto.Util.number import *
import random
 
 
def genPrime():
    while True:
        a = random.getrandbits(256)
        b = random.getrandbits(256)
 
        if b % 3 == 0:
            continue
 
        p = a ** 2 + 3 * b ** 2
        if p.bit_length() == 512 and p % 3 == 1 and isPrime(p):
            return p
 
 
def add(P, Q, mod):
    m, n = P
    p, q = Q
 
    if p is None:
        return P
    if m is None:
        return Q
 
    if n is None and q is None:
        x = m * p % mod
        y = (m + p) % mod
        return (x, y)
 
    if n is None and q is not None:
        m, n, p, q = p, q, m, n
 
    if q is None:
        if (n + p) % mod != 0:
            x = (m * p + 2* inverse(n + p, mod) % mod
            y = (m + n * p) * inverse(n + p, mod) % mod
            return (x, y)
        elif (m - n ** 2) % mod != 0:
            x = (m * p + 2* inverse(m - n ** 2, mod) % mod
            return (x, None)
        else:
            return (NoneNone)
    else:
        if (m + p + n * q) % mod != 0:
            x = (m * p + (n + q) * 2* inverse(m + p + n * q, mod) % mod
            y = (n * p + m * q + 2* inverse(m + p + n * q, mod) % mod
            return (x, y)
        elif (n * p + m * q + 2) % mod != 0:
            x = (m * p + (n + q) * 2* inverse(n * p + m * q + r, mod) % mod
            return (x, None)
        else:
            return (NoneNone)
 
 
def power(P, a, mod):
    res = (NoneNone)
    t = P
    while a > 0:
        if a % 2:
            res = add(res, t, mod)
        t = add(t, t, mod)
        a >>= 1
    return res
 
 
def random_pad(msg, ln):
    pad = bytes([random.getrandbits(8for _ in range(ln - len(msg))])
    return msg + pad
 
 
p, q = genPrime(), genPrime()
= p * q
phi = (p ** 2 + p + 1* (q ** 2 + q + 1)
 
print(f"N: {N}")
 
= getPrime(400)
= inverse(d, phi)
= (e * d - 1// phi
 
print(f"e: {e}")
 
to_enc = input("> ").encode()
ln = len(to_enc)
 
print(f"Length: {ln}")
 
pt1, pt2 = random_pad(to_enc[: ln // 2], 127), random_pad(to_enc[ln // 2 :], 127)
 
= (bytes_to_long(pt1), bytes_to_long(pt2))
= power(M, e, N)
 
print(f"E: {E}")
 
cs

 

The obvious weird part in the script, excluding the whole mysterious group, is that $d$ is very small. 

This leads to some ideas like Wiener's attack or Boneh-Durfee's attack. Since we cannot compute $\phi$ with a very high precision, Wiener's attack does not work well. To be honest, I forgot about Boneh-Durfee and just started googling "Wiener's attack modulo $(p^2+p+1)(q^2+q+1)$". It gave me the paper https://eprint.iacr.org/2021/1160.pdf which had all the ideas and the solution for the problem as well. It also explains where the group comes from. I'll explain this part later. 

 

Since the paper explains the choice of polynomials to use LLL on very well, I implemented them directly and used https://github.com/mimoo/RSA-and-LLL-attacks/blob/master/boneh_durfee.sage instead of defund's black-box (?) script. 

 

The Group

 

I figured this part out before I searched for the paper, but it really doesn't help with solving the challenge.

I started by thinking this was some sort of a curve, but I couldn't really think about the formula. I tried to find the curve formula by taking various monomials of coordinates of each points in the group and using the kernel of the matrix, but it failed as well. (For example, see the "Bonus" from hellman's writeup on CONFidence 2020 Finals https://nbviewer.org/gist/hellman/be17ac7b2363dd0cf6cca89c6a9e69bf)

This meant that this curve might not really be a curve. Now what do we do?

 

Then I looked at the $(m+p+nq)$ part. What could make that sort of a term? After some thought, I found $$(x^2+nx+m)(x^2+qx+p) = x^4 + (n + q)x^3 + (m + p + nq)x^2 + (np + mq)x + mp$$ which looked really suspicious. If we focused on the case where nothing was "None" and $m + p + nq$ is nonzero, we divide $m + p + nq$ to get our final values of $x, y$. This meant that something was done to make things monic. Also, that $2$ and $2(n+q)$ is very suspicious - and now we see that we can divide out by $x^3 - 2$. This gives us $$(m + p + nq)x^2 + (np + mq + 2) x + (mp + 2 (n + q))$$ and making this monic and taking coefficients gives us the $x,  y$ we have from the code. The "None" parts correspond to the cases where the polynomials are not quadratic - they are linear or even a constant. For example, the case where $n, q$ are "None" is equivalent to $(x+m)(x+p) = x^2 + (m+p)x + mp$. The other cases are similar and are left as exercises for the reader.

 

Now we can even compute the group order. If $x^3 - 2$ is irreducible over $GF(p)$, then this is just $GF(p^3)$, but with monic polynomials.

This means that the group size will be $$ \frac{p^3 - 1}{p - 1} = p^2 + p +1$$ which matches the $\phi$ description of the challenge source code.

 

Is $x^3 - 2$ irreducible? It turns out, yes. When $p \equiv 1 \pmod{3}$, results on cubic reciprocity state that $p$ can be uniquely expressed as $p = a^2 + 3b^2$, and $2$ is a cubic reciprocity of $p$ if and only if $b \equiv 0 \pmod{3}$. Check https://en.wikipedia.org/wiki/Cubic_reciprocity. Now we see that our prime generation completely blocks this, which means that $x^3 - 2$ has no solutions over $GF(p)$, hence irreducible. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
import time
 
############################################
# Config
##########################################
 
"""
Setting debug to true will display more informations
about the lattice, the bounds, the vectors...
"""
debug = True
 
"""
Setting strict to true will stop the algorithm (and
return (-1, -1)) if we don't have a correct 
upperbound on the determinant. Note that this 
doesn't necesseraly mean that no solutions 
will be found since the theoretical upperbound is
usualy far away from actual results. That is why
you should probably use `strict = False`
"""
strict = False
 
"""
This is experimental, but has provided remarkable results
so far. It tries to reduce the lattice as much as it can
while keeping its efficiency. I see no reason not to use
this option, but if things don't work, you should try
disabling it
"""
helpful_only = True
dimension_min = 7 # stop removing if lattice reaches that dimension
 
############################################
# Functions
##########################################
 
# display stats on helpful vectors
def helpful_vectors(BB, modulus):
    nothelpful = 0
    for ii in range(BB.dimensions()[0]):
        if BB[ii,ii] >= modulus:
            nothelpful += 1
 
    print(nothelpful, "/", BB.dimensions()[0], " vectors are not helpful")
 
# display matrix picture with 0 and X
def matrix_overview(BB, bound):
    for ii in range(BB.dimensions()[0]):
        a = ('%02d ' % ii)
        for jj in range(BB.dimensions()[1]):
            a += '0' if BB[ii,jj] == 0 else 'X'
            if BB.dimensions()[0< 60:
                a += ' '
        if BB[ii, ii] >= bound:
            a += '~'
        print(a)
 
# tries to remove unhelpful vectors
# we start at current = n-1 (last vector)
def remove_unhelpful(BB, monomials, bound, current):
    # end of our recursive function
    if current == -1 or BB.dimensions()[0<= dimension_min:
        return BB
 
    # we start by checking from the end
    for ii in range(current, -1-1):
        # if it is unhelpful:
        if BB[ii, ii] >= bound:
            affected_vectors = 0
            affected_vector_index = 0
            # let's check if it affects other vectors
            for jj in range(ii + 1, BB.dimensions()[0]):
                # if another vector is affected:
                # we increase the count
                if BB[jj, ii] != 0:
                    affected_vectors += 1
                    affected_vector_index = jj
 
            # level:0
            # if no other vectors end up affected
            # we remove it
            if affected_vectors == 0:
                print("* removing unhelpful vector", ii)
                BB = BB.delete_columns([ii])
                BB = BB.delete_rows([ii])
                monomials.pop(ii)
                BB = remove_unhelpful(BB, monomials, bound, ii-1)
                return BB
 
            # level:1
            # if just one was affected we check
            # if it is affecting someone else
            elif affected_vectors == 1:
                affected_deeper = True
                for kk in range(affected_vector_index + 1, BB.dimensions()[0]):
                    # if it is affecting even one vector
                    # we give up on this one
                    if BB[kk, affected_vector_index] != 0:
                        affected_deeper = False
                # remove both it if no other vector was affected and
                # this helpful vector is not helpful enough
                # compared to our unhelpful one
                if affected_deeper and abs(bound - BB[affected_vector_index, affected_vector_index]) < abs(bound - BB[ii, ii]):
                    print("* removing unhelpful vectors", ii, "and", affected_vector_index)
                    BB = BB.delete_columns([affected_vector_index, ii])
                    BB = BB.delete_rows([affected_vector_index, ii])
                    monomials.pop(affected_vector_index)
                    monomials.pop(ii)
                    BB = remove_unhelpful(BB, monomials, bound, ii-1)
                    return BB
    # nothing happened
    return BB
 
 
def attack(N, e, m, t, X, Y):
    modulus = e
 
    PR.<x, y> = PolynomialRing(ZZ)
    a = N + 1
    b = N * N - N + 1
    f = x * (y * y + a * y + b) + 1
 
    gg = []
    for k in range(0, m+1):
        for i in range(k, m+1):
            for j in range(2 * k, 2 * k + 2):
                gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k))
    for k in range(0, m+1):
        for i in range(k, k+1):
            for j in range(2*k+22*i+t+1):
                gg.append(x^(i-k) * y^(j-2*k) * f^k * e^(m - k))
 
    def order_gg(idx, gg, monomials):
        if idx == len(gg):
            return gg, monomials
 
        for i in range(idx, len(gg)):
            polynomial = gg[i]
            non = []
            for monomial in polynomial.monomials():
                if monomial not in monomials:
                    non.append(monomial)
            
            if len(non) == 1:
                new_gg = gg[:]
                new_gg[i], new_gg[idx] = new_gg[idx], new_gg[i]
 
                return order_gg(idx + 1, new_gg, monomials + non)    
 
    gg, monomials = order_gg(0, gg, [])
 
    # construct lattice B
    nn = len(monomials)
    BB = Matrix(ZZ, nn)
    for ii in range(nn):
        BB[ii, 0= gg[ii](00)
        for jj in range(1, nn):
            if monomials[jj] in gg[ii].monomials():
                BB[ii, jj] = gg[ii].monomial_coefficient(monomials[jj]) * monomials[jj](X, Y)
 
    # Prototype to reduce the lattice
    if helpful_only:
        # automatically remove
        BB = remove_unhelpful(BB, monomials, modulus^m, nn-1)
        # reset dimension
        nn = BB.dimensions()[0]
        if nn == 0:
            print("failure")
            return 0,0
 
    # check if vectors are helpful
    if debug:
        helpful_vectors(BB, modulus^m)
    
    # check if determinant is correctly bounded
    det = BB.det()
    bound = modulus^(m*nn)
    if det >= bound:
        print("We do not have det < bound. Solutions might not be found.")
        print("Try with highers m and t.")
        if debug:
            diff = (log(det) - log(bound)) / log(2)
            print("size det(L) - size e^(m*n) = ", floor(diff))
        if strict:
            return -1-1
    else:
        print("det(L) < e^(m*n) (good! If a solution exists < N^delta, it will be found)")
 
    # display the lattice basis
    if debug:
        matrix_overview(BB, modulus^m)
 
    # LLL
    if debug:
        print("optimizing basis of the lattice via LLL, this can take a long time")
 
    BB = BB.LLL()
 
    if debug:
        print("LLL is done!")
 
    # transform vector i & j -> polynomials 1 & 2
    if debug:
        print("looking for independent vectors in the lattice")
    found_polynomials = False
    
    for pol1_idx in range(nn - 1):
        for pol2_idx in range(pol1_idx + 1, nn):
            # for i and j, create the two polynomials
            PR.<a, b> = PolynomialRing(ZZ)
            pol1 = pol2 = 0
            for jj in range(nn):
                pol1 += monomials[jj](a,b) * BB[pol1_idx, jj] / monomials[jj](X, Y)
                pol2 += monomials[jj](a,b) * BB[pol2_idx, jj] / monomials[jj](X, Y)
 
            # resultant
            PR.<q> = PolynomialRing(ZZ)
            rr = pol1.resultant(pol2)
 
            # are these good polynomials?
            if rr.is_zero() or rr.monomials() == [1]:
                continue
            else:
                print("found them, using vectors", pol1_idx, "and", pol2_idx)
                found_polynomials = True
                break
        if found_polynomials:
            break
 
    if not found_polynomials:
        print("no independant vectors could be found. This should very rarely happen...")
        return 00
    
    rr = rr(q, q)
 
    # solutions
    soly = rr.roots()
 
    if len(soly) == 0:
        print("Your prediction (delta) is too small")
        return 00
 
    soly = soly[0][0]
    ss = pol1(q, soly)
    solx = ss.roots()[0][0]
 
    return solx, soly
 
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
 
= 144256630216944187431924086433849812983170198570608223980477643981288411926131676443308287340096924135462056948517281752227869929565308903867074862500573343002983355175153511114217974621808611898769986483079574834711126000758573854535492719555861644441486111787481991437034260519794550956436261351981910433997
= 3707368479220744733571726540750753259445405727899482801808488969163282955043784626015661045208791445735104324971078077159704483273669299425140997283764223932182226369662807288034870448194924788578324330400316512624353654098480234449948104235411615925382583281250119023549314211844514770152528313431629816760072652712779256593182979385499602121142246388146708842518881888087812525877628088241817693653010042696818501996803568328076434256134092327939489753162277188254738521227525878768762350427661065365503303990620895441197813594863830379759714354078526269966835756517333300191015795169546996325254857519128137848289
= 1 << 400
= 2 * inthroot(Integer(2 * N), 2)
 
res = attack(N, e, 42, X, Y)
print(res) # gives k and p + q, the rest is easy
cs

 

 

Yet Another PRNG

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#!/usr/bin/env python3
 
from Crypto.Util.number import *
import random
import os
from flag import flag
 
def urand(b):
    return int.from_bytes(os.urandom(b), byteorder='big')
 
class PRNG:
    def __init__(self):
        self.m1 = 2 ** 32 - 107
        self.m2 = 2 ** 32 - 5
        self.m3 = 2 ** 32 - 209
        self.M = 2 ** 64 - 59
 
        rnd = random.Random(b'rbtree')
 
        self.a1 = [rnd.getrandbits(20for _ in range(3)]
        self.a2 = [rnd.getrandbits(20for _ in range(3)]
        self.a3 = [rnd.getrandbits(20for _ in range(3)]
 
        self.x = [urand(4for _ in range(3)]
        self.y = [urand(4for _ in range(3)]
        self.z = [urand(4for _ in range(3)]
 
    def out(self):
        o = (2 * self.m1 * self.x[0- self.m3 * self.y[0- self.m2 * self.z[0]) % self.M
 
        self.x = self.x[1:] + [sum(x * y for x, y in zip(self.x, self.a1)) % self.m1]
        self.y = self.y[1:] + [sum(x * y for x, y in zip(self.y, self.a2)) % self.m2]
        self.z = self.z[1:] + [sum(x * y for x, y in zip(self.z, self.a3)) % self.m3]
 
        return o.to_bytes(8, byteorder='big')
 
if __name__ == "__main__":
    prng = PRNG()
 
    hint = b''
    for i in range(12):
        hint += prng.out()
    
    print(hint.hex())
 
    assert len(flag) % 8 == 0
    stream = b''
    for i in range(len(flag) // 8):
        stream += prng.out()
    
    out = bytes([x ^ y for x, y in zip(flag, stream)])
    print(out.hex())
    
 
cs

 

It turns out that taking the equations and shoving them to CVP repository works. 

https://github.com/rkm0959/Inequality_Solving_with_CVP is very strong :O :O :O 

I've been procrastinating with updating and writing about that repository, very sorry about that....

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
def urand(b):
    return int.from_bytes(os.urandom(b), byteorder='big')
 
class PRNGFinisher:
    def __init__(self, X, Y, Z):
        self.m1 = 2 ** 32 - 107
        self.m2 = 2 ** 32 - 5
        self.m3 = 2 ** 32 - 209
        self.M = 2 ** 64 - 59
 
        rnd = rand.Random(b'rbtree')
 
        self.a1 = [rnd.getrandbits(20for _ in range(3)]
        self.a2 = [rnd.getrandbits(20for _ in range(3)]
        self.a3 = [rnd.getrandbits(20for _ in range(3)]
 
        self.x = X
        self.y = Y
        self.z = Z
 
    def out(self):
        o = (2 * self.m1 * self.x[0- self.m3 * self.y[0- self.m2 * self.z[0]) % self.M
 
        self.x = self.x[1:] + [sum(x * y for x, y in zip(self.x, self.a1)) % self.m1]
        self.y = self.y[1:] + [sum(x * y for x, y in zip(self.y, self.a2)) % self.m2]
        self.z = self.z[1:] + [sum(x * y for x, y in zip(self.z, self.a3)) % self.m3]
 
        return o.to_bytes(8, byteorder='big')
 
class PRNG:
    def __init__(self):
        self.m1 = 2 ** 32 - 107
        self.m2 = 2 ** 32 - 5
        self.m3 = 2 ** 32 - 209
        self.M = 2 ** 64 - 59
 
        rnd = rand.Random(b'rbtree')
 
        self.a1 = [rnd.getrandbits(20for _ in range(3)]
        self.a2 = [rnd.getrandbits(20for _ in range(3)]
        self.a3 = [rnd.getrandbits(20for _ in range(3)]
 
        self.x = [urand(4for _ in range(3)]
        self.y = [urand(4for _ in range(3)]
        self.z = [urand(4for _ in range(3)]
 
    def out(self):
        ret = b''
        xs = []
        ys = []
        zs = []
        for _ in range(12):
            xs.append(self.x[0])
            ys.append(self.y[0])
            zs.append(self.z[0])
            o = (2 * self.m1 * self.x[0- self.m3 * self.y[0- self.m2 * self.z[0]) % self.M
            self.x = self.x[1:] + [sum(x * y for x, y in zip(self.x, self.a1)) % self.m1]
            self.y = self.y[1:] + [sum(x * y for x, y in zip(self.y, self.a2)) % self.m2]
            self.z = self.z[1:] + [sum(x * y for x, y in zip(self.z, self.a3)) % self.m3]
            ret += o.to_bytes(8, byteorder='big')
        return ret, xs, ys, zs
 
 
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = mat.BKZ(block_size = 35)
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
    # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
    
    # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
def get_idx(name, v):
    if name == 'x':
        return v - 1
    if name == 'y':
        return v + 11
    if name == 'z':
        return v + 23
 
test = False
 
if test:
    prng = PRNG()
    hint, ERRX, ERRZ, XS, YS, ZS = prng.out()
    print("XS", XS)
    print("YS", YS)
    print("ZS", ZS)
 
    vec_sol = []
    for i in range(12):
        vec_sol.append(XS[i])
    for i in range(12):
        vec_sol.append(YS[i])
    for i in range(12):
        vec_sol.append(ZS[i])
else:
    prng = PRNG()
    hint = '67f19d3da8af1480f39ac04f7e9134b2dc4ad094475b696224389c9ef29b8a2aff8933bd3fefa6e0d03827ab2816ba0fd9c0e2d73e01aa6f184acd9c58122616f9621fb8313a62efb27fb3d3aa385b89435630d0704f0dceec00fef703d54fca'
    output = '153ed807c00d585860b843a03871b11f60baf11fe72d2619283ec5b4d931435ac378e21abe67c47f7923fcde101f4f0c65b5ee48950820f9b26e33acf57868d5f0cbc2377a39a81918f8c20f61c71047c8e82b1c965fa01b58ad0569ce7521c7'
    hint = bytes.fromhex(hint)
    output = bytes.fromhex(output)
 
print(len(hint))
= Matrix(ZZ, 7575)
 
cnt = 0
tot_base = 36
 
lb = []
ub = []
 
# x
for i in range(9):
    M[get_idx('x', i + 4), cnt] = 1
    M[get_idx('x', i + 1), cnt] = -prng.a1[0]
    M[get_idx('x', i + 2), cnt] = -prng.a1[1]
    M[get_idx('x', i + 3), cnt] = -prng.a1[2]
    M[tot_base, cnt] = prng.m1
    cnt += 1
    tot_base += 1
    lb.append(0)
    ub.append(0)
 
# y 
for i in range(9):
    M[get_idx('y', i + 4), cnt] = 1
    M[get_idx('y', i + 1), cnt] = -prng.a2[0]
    M[get_idx('y', i + 2), cnt] = -prng.a2[1]
    M[get_idx('y', i + 3), cnt] = -prng.a2[2]
    M[tot_base, cnt] = prng.m2
    cnt += 1
    tot_base += 1
    lb.append(0)
    ub.append(0)
 
# z
for i in range(9):
    M[get_idx('z', i + 4), cnt] = 1
    M[get_idx('z', i + 1), cnt] = -prng.a3[0]
    M[get_idx('z', i + 2), cnt] = -prng.a3[1]
    M[get_idx('z', i + 3), cnt] = -prng.a3[2]
    M[tot_base, cnt] = prng.m3
    cnt += 1
    tot_base += 1
    lb.append(0)
    ub.append(0)
 
for i in range(12):
    M[get_idx('x', i + 1), cnt] = 1
    cnt += 1
    lb.append(0)
    ub.append(1 << 32)
 
for i in range(12):
    M[get_idx('y', i + 1), cnt] = 1
    cnt += 1
    lb.append(0)
    ub.append(1 << 32)
 
for i in range(12):
    M[get_idx('z', i + 1), cnt] = 1
    cnt += 1
    lb.append(0)
    ub.append(1 << 32)
 
for i in range(12):
    M[get_idx('x', i + 1), cnt] = (2 * prng.m1)
    M[get_idx('y', i + 1), cnt] = -prng.m3
    M[get_idx('z', i + 1), cnt] = -prng.m2
    M[tot_base, cnt] = prng.M
    cnt += 1
    tot_base += 1
    val = bytes_to_long(hint[8 * i : 8 * i + 8])
    lb.append(val)
    ub.append(val)
 
print(cnt)
print(tot_base)
 
result, applied_weights, fin = solve(M, lb, ub)
 
INIT_X = [int(fin[get_idx('x', i + 1)]) for i in range(3)]
INIT_Y = [int(fin[get_idx('y', i + 1)]) for i in range(3)]
INIT_Z = [int(fin[get_idx('z', i + 1)]) for i in range(3)]
 
print(fin)
print(INIT_X)
print(INIT_Y)
print(INIT_Z)
 
actual_prng = PRNGFinisher(INIT_X, INIT_Y, INIT_Z)
 
hint_check = b''
for i in range(12):
    hint_check += actual_prng.out()
 
sdaf = [hint_check[i] == hint[i] for i in range(96)]
print(sdaf)
 
if test == False:
    flag = b''
    for i in range(len(output) // 8):
        res = bytes_to_long(actual_prng.out())
        res = res ^ bytes_to_long(output[8 * i : 8 * i + 8])
        flag += long_to_bytes(res)
    print(flag)
cs

 

 

Seed Me

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import java.nio.file.Files;
import java.nio.file.Path;
import java.io.IOException;
import java.util.Random;
import java.util.Scanner;
 
class Main {
 
    private static void printFlag() {
        try {
            System.out.println(Files.readString(Path.of("flag.txt")));
        }
        catch(IOException e) {
            System.out.println("Flag file is missing, please contact admins");
        }
    }
 
    public static void main(String[] args) {
        int unlucky = 03777;
        int success = 0;
        int correct = 16;
 
        System.out.println(unlucky);
 
        System.out.println("Welcome to the 'Lucky Crystal Game'!");
        System.out.println("Please provide a lucky seed:");
        Scanner scr = new Scanner(System.in);
        long seed = scr.nextLong();
        Random rng = new Random(seed);
 
        for(int i=0; i<correct; i++) {
            /* Throw away the unlucky numbers */
            for(int j=0; j<unlucky; j++) {
                rng.nextFloat();
            }
 
            /* Do you feel lucky? */
            if (rng.nextFloat() >= (7.331f*.1337f)) {
                success++;
            }
        }
 
        if (success == correct) {
            printFlag();
        }
        else {
            System.out.println("Unlucky!");
        }
    }
}
 
cs

 

Java's RNG is truncated LCG, but to be honest it's not even truncated as it is pretty much LCG result divided by $2^{48}$. 

This is ultimately a hidden number problem, so it must be lattices - and CVP repository should work.

However, naively plugging in the lower bound / upper bound vectors gives some results that are off. 

To solve this problem, we manually change the lower bound / upper bound by hand to "persuade" our CVP algorithm to make the results more appropriate for our liking. For example, if one result is 0.97, smaller than we need, then we can make the lower bound a bit larger. If one result is 0.01, which means that we overshot the value, we can reduce the upper bound so that the value can land between 0.98 and 1.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
# conn = remote('seedme.chal.perfect.blue', 1337)
# conn.interactive()
 
def getv(seed):
    seed = (seed * 0x5DEECE66D + 0xB& ((1 << 48- 1)
    return seed, (seed >> 24/ (1 << 24)
 
curm = [1]
curb = [0]
 
= Matrix(ZZ, 1717)
lb = [0* 17
ub = [0* 17
 
for i in range(16 * 2048):
    curm.append((0x5DEECE66D * curm[i]) % (1 << 48))
    curb.append((0x5DEECE66D * curb[i] + 0xB) % (1 << 48))
 
for i in range(016):
    m, b = curm[2048 * i + 2048], curb[2048 * i + 2048]
    M[0, i] = m
    M[i + 1, i] = 1 << 48
    lb[i] = int(0.9803 * (1 << 48)) - b 
    ub[i] = int((1 << 48)) - 1 - b
 
# post-fix manually
lb[0= int(0.985 * (1 << 48)) - curb[2048]
ub[15= int(0.995 * (1 << 48)) - curb[2048 * 16]
 
M[016= 1
lb[16= 0
ub[16= 1 << 48
 
result, applied_weights, fin = solve(M, lb, ub)
 
res = (int(fin[0]) + (1 << 48)) % (1 << 48)
 
init_seed = 0x5DEECE66D ^ res 
 
print(init_seed)
 
seeds = init_seed
seeds = (seeds ^ 0x5DEECE66D& ((1 << 48- 1)
 
curm = [1]
curb = [0]
 
for i in range(16 * 2048):
    curm.append((0x5DEECE66D * curm[i]) % (1 << 48))
    curb.append((0x5DEECE66D * curb[i] + 0xB) % (1 << 48))
 
for i in range(016):
    m, b = curm[2048 * i + 2048], curb[2048 * i + 2048]
    res = (seeds * m + b) % (1 << 48)
    print(res / (1 << 48>= 0.7331 * 1.337)
cs

 

 

'수학 > 암호론 및 CTF' 카테고리의 다른 글

PBCTF 2021 Writeups  (0) 2021.10.13
TSGCTF 2021 Writeups  (0) 2021.10.03
DUCTF 2021 Writeups  (0) 2021.09.26
ACSC Crypto Writeups  (0) 2021.09.26
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05
Lattice Attacks Introductory Survey  (0) 2021.07.22

5 Crypto + 2 PPC = 7 solves. Favorite Challenges = This is DSA, Lumberjack Against Nature.

 

Beginner's Crypto

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
from secret import e
from Crypto.Util.number import getStrongPrime, isPrime
 
= getStrongPrime(1024)
= getStrongPrime(1024)
= p * q
phi = (p - 1* (q - 1)
 
with open('flag.txt''rb'as f:
    flag = int.from_bytes(f.read(), 'big')
 
assert(isPrime(e))
assert(isPrime(e + 2))
assert(isPrime(e + 4))
 
e1 = pow(e, 0x10001, phi)
e2 = pow(e + 20x10001, phi)
e3 = pow(e + 40x10001, phi)
 
c1 = pow(flag, e1, N)
c2 = pow(flag, e2, N)
c3 = pow(flag, e3, N)
 
print(f'p = {p}')
print(f'q = {q}')
print(f'c1 = {c1}')
print(f'c2 = {c2}')
print(f'c3 = {c3}')
 
cs

 

As it will be soon mentioned in the flag of this challenge, we will solve this without $p, q$. 

Since $e, e+2, e+4$ is all prime and at least one of them has to be a multiple of $3$, we see $e=3$. 

Now we can see that $c_1, c_2, c_3$ can be computed as $$c_1 \equiv m^{3^{65537}} \pmod{n}, \quad c_2 \equiv m^{5^{65537}} \pmod{n}, \quad c_3 \equiv m^{7^{65537}} \pmod{n}$$ Since $\gcd(3^{65537}, 5^{65537}) = 1$, we can use extended Euclidean algorithm on the exponents to find $m$. 

 

Since $3^{65537}$ and $5^{65537}$ are large numbers, it is recommended to use GMPY or Sagemath's integers.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
= 167710954518007348037383082265231465648795974011761905177264545864288011527333715495850532989338171489309608848431113452814709692343039027970312735521415071265608660628968391884287240987858607818275329135585153511665148279408708087727501421558738163577629329044315775019460018956186674179846621352371150072281
= 130354329753344570838569091064852072757046774566775609047544069941246798511317343102715733555464772099991834579660053860799207243561908291522943696711982657846373844514551117658179060004064010647453939332217996817580433587341521331941287365948919907797478197717562721233289937471168288241937022054501586986443
c1 = 2560344169447809042170685026483682125499025654554670516499742981486615082413150123244985585751880264831112089324011804397189638172356179296987581738515619297036118472798499254785110885662931526277474101787493114656242031264678448394380651657330967744585361662315313462698221954777506355498445242300193032704972074020068699180111637362566860530694807230108024167631423062629721393506643291591971626450262144814424411172618188943774725105690851574922374544865628890948773274109561622040022136970632948166009941425683576381155722191980954262373394704682297682490061906408535261437100820855976015526295573831744458528440
c2 = 9041231631916227099296501948589424780380702196870972231114747229225732542137483840187783630590878594711315671224997985975031038623195921968945234067183003568830416719957054703139219879265482072634572699299971785171441858501409377942183918216246312330291820452436486171483461790388518159980027140392750222843449604265528929311978655519463562520038992870162220913137870017065557254099767583925177889051326144499369420594398043223307161794788085369471538477803421726790780799629276012701406231535048423554314287152404245482928538931953627397633165453319078105028671410039195670727134471011040601278722143504641171853743
c3 = 3193069356811106774640161554961405075257002069448498144279061282023129342916422283816661697787316681475161942522570615456264481238277711114193792510286127129056376618422336477707825009085263623755329815306483253646072909132096678270667136193038337386976289222105363398033633185639402128949635525665502328717781718263894690234837016959581149138917064108193064639981137359869717065147934752707676203651598070046066514316196771853484143158367616177332902152347890310640338106015356361617700741042461419248117687350565094928451141103632305400493998164788411031832078388030194992306440474662871408938796429927990102583837
= p * q
 
# using n only
 
e1 = pow(Integer(3), 0x10001)
e2 = pow(Integer(5), 0x10001)
 
g1 = inverse_mod(e1, e2)
g2 = Integer((e1 * g1 - 1// e2)
 
flag = (pow(c1, g1, n) * inverse_mod(Integer(pow(c2, g2, n)), n)) % n 
 
print(long_to_bytes(int(flag)))
cs

 

Minimalist's Private

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
from Crypto.Util.number import isPrime
from random import randrange
from secret import p, q, L, e, d
 
class RSA:
    def __init__(self, p, q, L, e, d):
        assert(isPrime(p) and isPrime(q))
        self.N = p * q
        self.L = L
        self.e = e
        self.d = d
 
        # these are the normal RSA conditions
        for _ in range(100):
            assert(pow(randrange(1self.N), self.L, self.N) == 1)
        assert(self.e * self.d % self.L == 1)
 
        # minimal is the best
        assert(self.L * self.L <= 10000 * self.N)
 
    def gen_private_key(self):
        return (self.N, self.d)
 
    def gen_public_key(self):
        return (self.N, self.e)
 
    def encrypt(self, msg):
        return pow(msg, self.e, self.N)
 
    def decrypt(self, c):
        return pow(c, self.d, self.N)
 
flag = open('flag.txt''rb').read()
msg = int.from_bytes(flag, byteorder='big')
assert(msg < p * q)
 
rsa = RSA(p, q, L, e, d)
encrypted = rsa.encrypt(msg)
assert(rsa.decrypt(encrypted) == msg)
 
print(f'N, e = {rsa.gen_public_key()}')
print(f'c = {encrypted}')
 
cs

 

We see that $L \ge \text{lcm}(p-1, q-1)$. If we let $G = \gcd(p-1, q-1)$ and $p-1 = Ga$, $q-1 = Gb$, we have $$(Gab)^2 \le L^2 \le 10^4 n = 10^4(Ga + 1)(Gb + 1)$$ which shows us that $$ab \le 10^4 \left(1 + \frac{1}{Ga} \right) \left(1 + \frac{1}{Gb} \right) \le 4 \cdot 10^4$$ There are not a lot of pairs $(a, b)$ with $ab \le 4 \cdot 10^4$, in fact, the number of pairs $(a, b)$ with $ab \le n$ is around $\mathcal{O}(n \log n)$, so we can brute force all such $(a, b)$ and try to solve for $G$ with the quadratic equation $$n = (Ga+1)(Gb+1)$$

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def inthroot(a, nn):
    return a.nth_root(nn, truncate_mode=True)[0]
 
n, e = (110810384837032261825023623509673754738102610876330251649981605143280121681368156837531959563893256283529225677601694957397273288158620952782439302742812596459937884534715440963387843686842290530079941383864568643035248453476130518593895658961288946324650893599430144357678145290466607212246583158515615165537)
= 254705401581808316199469430068831357413481187288921393400711004895837418302514065107811330660948313420965140464021505716810909691650540609799307500282957438243553742714371028405100267860418626513481187170770328765524251710154676478766892336610743824131087888798846367363259860051983889314134196889300426
 
for i in tqdm(range(15000)):
    for j in range(15000 // i + 5):
        aa = i * j 
        bb = i + j 
        cc = 1 - n 
        try:
            tt = (-bb + inthroot(Integer(bb * bb - 4 * aa * cc), 2)) // (2 * aa)
            p = i * tt + 1
            q = j * tt + 1 
            if p * q == n:
                print("HEY")
                print(p, q)
                phi = LCM(p - 1, q - 1)
                d = inverse(e, phi)
                print(d)
                print(long_to_bytes(pow(c, d, n)))
                exit()
        except:
            pass
 
 
cs

 

Baba is Flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
require 'openssl'
require 'digest'
 
STDOUT.sync = true
 
class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end
 
class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end
 
  def inv(x)
    x.pow(@n - 2, @n)
  end
 
  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    x, y = (@G * k).xy
 
    # We all like hacks, ain't we?
    # s = (z + x * @d) * inv(k) % @n
    s = (z + @d) * inv(k) % @n
 
    return x, s
  end
 
  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex
 
    # ditto
    # x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
    x2, y2 = (@G * (z * inv(s)) + @Q * inv(s)).xy
 
    return x == x2
  end
end
 
ecdsa = ECDSA.new
 
5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS
 
  print 'choice? '
 
  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i
 
    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end
 
puts 'You is defeat.'
 
cs

 

Here, we want to forge $(x, s)$ such that $$s \cdot \text{lift_x}(x) = Q + z \cdot G$$ where $z$ is the hash of the message and $\text{lift_x}(x)$ is the point with $x$-coordinate equal to $x$. By asking for the signature of 'Baba', we get a pair $(x, s)$ that corresponds to the hash of 'Baba'. Since $x, s, z, G$ are all known, we can recover the value of $Q$. 

 

Now we can simply take $s = 1$ and $x$ to be the $x$-coordinate of $Q + z \cdot G$, where $z$ is the hash of 'Flag' to make a valid signature.

This solves the problem, and this vuln is of course from the missing $x$ in the signature formula.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
= remote('34.146.212.53'65434)
 
= (1 << 256- (1 << 32- (1 << 9- (1 << 8- (1 << 7- (1 << 6- (1 << 4- 1
 
= EllipticCurve(GF(p), [07])
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
 
= E(Gx, Gy)
= E.order()
print(isPrime(n))
 
h1 = bytes_to_long(hashlib.sha256(b'Baba').digest())
h2 = bytes_to_long(hashlib.sha256(b'Flag').digest())
 
for i in range(3):
    r.recvline()
r.sendline(b"1")
r.recvline()
X1 = int(r.recvline().split()[-1])
S1 = int(r.recvline().split()[-1])
 
print(X1)
print(S1)
 
 
target1 = S1 * E.lift_x(GF(p)(X1))
 
target2 = target1 + (h2 - h1) * G
for i in range(3):
    r.recvline()
r.sendline(b"2")
r.sendline("Flag")
r.sendline(str(int(target2.xy()[0])))
r.sendline(b"1")
print(r.recvline())
print(r.recvline())
cs

 

This is DSA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# See also https://github.com/tsg-ut/pycryptodome
from Crypto.PublicKey import DSA
from Crypto.Signature import DSS
from Crypto.Hash import SHA256
from Crypto.Util.number import getPrime
from Crypto.Random.random import randrange
from base64 import b64decode
from signal import alarm
import os
 
alarm(15)
 
= getPrime(256)
print(f'q = {q}')
 
= int(input('p? '))
= int(input('h? '))
 
= pow(h, (p - 1// q, p)
= randrange(q)
= pow(g, x, p)
 
print(f'g = {g}')
print(f'y = {y}')
 
dsa = DSA.construct((y, g, p, q, x))
dss = DSS.new(dsa, 'fips-186-3')
 
print('Thank you for helping me with DSA! Now give me the base64-encoded signature of sha256("flag")')
sign = b64decode(input('sign? '))
 
dss.verify(SHA256.new(b'flag'), sign)
print(f"Awesome! {os.environ.get('FLAG')}")
cs

 

I took ridiculously long to solve this challenge, for several reasons. Here's my story. 

 

Step 1 : removing all "irrational" ideas

In standard DSA, we are forced to solve a discrete logarithm in a subgroup of $\mathbb{F}_p^{\star}$ with order $q$. 

Since $q$ is 256 bits, this is very hard to do, and there are no tricks that I know of to make a nice $p$ that makes it possible. 

Therefore, directly attacking this problem is not possible. We have to go around it. 

 

The first thing that caught my eye was that there was no check that $(y, g, p, q, x)$ was valid DSA tuple. 

If I could do send some nasty values on $p, h$, then maybe this problem would be very easy to solve. 

 

At this point, about 10 minutes have passed. I decided to look at pycryptodome's code for DSA construction.

Then https://github.com/Legrandin/pycryptodome/blob/master/lib/Crypto/PublicKey/DSA.py#L489 happened. 

It turns out that pycryptodome does check everything automatically, even when not specified. 20 minutes have passed.

 

Step 2 : actually knowing what the challenge is

After wasting an additional 40 minutes, I found that the library was patched. 

https://github.com/tsg-ut/pycryptodome/commit/22388c5fec4607e8e255926c3e95724a2f070e76  

 

So it doesn't check $p \equiv 1 \pmod{q}$ anymore! This is good stuff. However, one thing still bugged me. 

After sending $h$, the server computes $g \equiv h^{\lfloor (p-1)/q \rfloor} \pmod{p}$. It then checks

  • $g \not\equiv 1 \pmod{p}$
  • $g^q \equiv 1 \pmod{p}$

If $p$ was a prime, then such $g$ can only exist if $p \equiv 1 \pmod{q}$. This forces $p$ to not be prime.

 

However, the pycryptodome library mentions that it checks for the primality of $p$, and there were no patches on that.

 

So I looked at the primality test function used in the repository. It consisted of a few Miller-Rabin tests and one Lucas test. 

If there was no Lucas test, it was not very hard to bypass this with some very large semiprimes. Because the number of Miller-Rabin iterations in the repository did not consider adversarial attacks, if we send a very large "carmichael like" semiprime, then we would only do one round of Miller-Rabin, and have good probability of passing the Miller-Rabin part of the primality test. Of course, the downside is 

  • We actually need $p$ to be exactly 2048 bits, but I didn't know that at the time 
  • We also need to pass Lucas test, and adversarial examples passing both Miller-Rabin and Lucas is not known, I think?

 

After deciding that finding a composite $p$ that passes the primality check is as hard as writing a conference paper, I looked back.

 

1
2
fmt_error = test_probable_prime(p) == COMPOSITE
fmt_error = test_probable_prime(q) == COMPOSITE
cs

 

That second line had to be OR'ed, not substituted, yet it was substituted. This was also in the original repository.

This meant that the primality check of $p$ is completely ignored, which means I didn't need to think about Miller-Rabin and stuff.

 

Step 3 : the finish

Since $p$ doesn't have to be prime, we will use the variable $n$ to avoid confusion.

OK, so I want to solve a discrete logarithm in a subgroup of $\mathbb{Z}_{n}^\star$ with a group order of $q$. 

This is a classical one - we can always take $n$ to be a power of $q$ and use Binomial Theorem. To be exact, we take $n = q^8$ and $h = 1 + q^7$.

 

Now $$g \equiv h^{q^7 - 1} \equiv 1 - q^7 \pmod{q^8}$$ and we see that $$y \equiv g^x \equiv 1 - x q^7 \pmod{q^8}$$ which means we can recover $0 \le x < q$ easily from $y$. Check out Paillier Cryptosystem.

  

Since $n$ needs to be exactly $2048$ bits, $n = q^8$ may fail. You can either reconnect until successful, or try to multiply $2$ until $n$ is exactly $2048$ bits. In this case, you also need to patch $h$ a bit as well. This is left as an exercise.

 

This was an astounding problem (thanks to the author!), as one of the main vulns was in the original repository as well. 

I briefly thought about whether this unpatched vuln is enough to create some issues, but I don't think so. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
 
 
= remote('34.146.212.53'61234)
 
= r.recvline()
= int(s.split()[-1])
 
= q ** 8
while p.bit_length() < 2048:
    p = 2 * p 
 
= 1 + 16 * q ** 7
r.sendline(str(p))
r.sendline(str(h))
 
= int(r.recvline().split()[-1])
= int(r.recvline().split()[-1])
 
print(2 <= g < p)
print(pow(g, q, p) == 1)
 
gs = ((g - 1// (q ** 7)) % q
ys = ((y - 1// (q ** 7)) % q
 
= (ys * inverse(gs, q)) % q 
 
res = bytes_to_long(hashlib.sha256(b'flag').digest())
 
= 1
rr = g % q
ss = (res + x * rr) % q
 
print(r.recvline())
 
 
res = long_to_bytes(rr, 32+ long_to_bytes(ss, 32)
 
r.sendline(b64encode(res))
 
print(r.recvline())
print(r.recvline())
cs

 

Flag is Win

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
require 'openssl'
require 'digest'
 
STDOUT.sync = true
 
class OpenSSL::PKey::EC::Point
  def xy
    n = to_bn(:uncompressed).to_i
    mask = (1 << group.degree) - 1
    return (n >> group.degree) & mask, n & mask
  end
  alias_method :+, :add
  alias_method :*, :mul
end
 
class ECDSA
  def initialize
    @curve = OpenSSL::PKey::EC::Group.new('secp256k1')
    @G = @curve.generator
    @n = @curve.order.to_i
    @d = OpenSSL::BN.rand(@curve.degree).to_i
    @Q = @G * @d
  end
 
  def inv(x)
    x.pow(@n - 2, @n)
  end
 
  def sign(msg)
    z = Digest::SHA256.hexdigest(msg).hex
    k = OpenSSL::BN.rand(@curve.degree / 3).to_s.unpack1('H*').hex
    x, y = (@G * k).xy
 
    # We should discourage every evil hacks
    s = (z + x * @d) * inv(k) % @n
 
    return x, s
  end
 
  def verify(msg, x, s)
    return false if x % @n == 0 || s % @n == 0
    z = Digest::SHA256.hexdigest(msg).hex
 
    # ditto
    x2, y2 = (@G * (z * inv(s)) + @Q * (x * inv(s))).xy
 
    return x == x2
  end
end
 
ecdsa = ECDSA.new
 
5.times do
  puts <<~EOS
    1. Sign
    2. Find rule
    3. Exit
  EOS
 
  print 'choice? '
 
  case gets.chomp
  when '1'
    x, s = ecdsa.sign('Baba')
    puts 'Baba is:'
    puts "x = #{x}"
    puts "s = #{s}"
  when '2'
    print 'Which rule do you want to know? '; msg = gets.chomp
    print 'x? '; x = gets.to_i
    print 's? '; s = gets.to_i
 
    if ecdsa.verify(msg, x, s)
      if msg == 'Baba'
        puts 'Baba is you'
      elsif msg == 'Flag'
        puts "Flag is #{ENV['FLAG']}"
      else
        puts 'Not Found :('
      end
    else
      puts 'Invalid :('
    end
  else
    exit
  end
end
 
puts 'You is defeat.'
 
 
cs

 

This challenge also took me ridiculously long because I made many mistakes and my intuition on lattices is not solid. 

 

It took me very long to realize that I have ruby installed on WSL and I could test what that whole unpack hex thing is. 

Of course, experienced CTF players may notice that unpack hex thing from last year's SECCON, but I didn't solve that challenge :P

 

Anyways, if you test out that unpack hex thing, we can see that $k$ has the form of $$ 48 \cdot \sum_{m=0}^{26} 256^m + \sum_{m=0}^{26} v_m \cdot 256^m$$ where $0 \le v_m \le 9$. We also know that $$k_1 s_1 \equiv z + x_1 d \pmod{n}, \quad k_2 s_2 \equiv z + x_2 d \pmod{n}$$ which, after canceling $d$ out, gives $$k_1(s_1x_2) - k_2(s_2x_1) \equiv z(x_2-x_1) \pmod{n}$$ This can be written as a linear equation of $26 \times 2$ variables between $0$ and $9$ inclusive, and we can shove it into CVP repository.

It seems like you need BKZ instead of LLL to find the correct values, which is understandable since BKZ is very strong.

 

I took a lot of time trying to use as many signatures as possible, leading to very large matrix size and longer runtime. 

I also tried a lot of various hacks which worked very well for ACSC Share the Flag, but they didn't work here. Lattices are hard...

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = mat.BKZ(block_size = 35)
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    print(result[num_ineq - 1- target[num_ineq-1])
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
 
 
 
= remote('34.146.212.53'35719)
 
= (1 << 256- (1 << 32- (1 << 9- (1 << 8- (1 << 7- (1 << 6- (1 << 4- 1
 
= EllipticCurve(GF(p), [07])
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ADA7726A3C4655DA4FBFC0E1108A8FD17B448A68554199C47D08FFB10D4B8
 
= E(Gx, Gy)
= E.order()
print(isPrime(n))
 
h1 = bytes_to_long(hashlib.sha256(b'Baba').digest())
h2 = bytes_to_long(hashlib.sha256(b'Flag').digest())
 
= []
= []
for _ in range(4):
    for i in range(3):
        r.recvline()
    r.sendline(b"1")
    r.recvline()
    X.append(int(r.recvline().split()[-1]))
    S.append(int(r.recvline().split()[-1]))
 
NUM_EQ = 4
test = False
 
= 26
 
supp = []
if test:
    d = rand.randint(1, n)
    for i in range(NUM_EQ):
        cc = []
        k = 0
        for j in range(2 * D):
            if j % 2 == 0:
                u = rand.randint(09)
                supp.append(u)
                k += u * (16 ** j)
                cc.append(u)
            else:
                k += 3 * (16 ** j)
        x = int((k * G).xy()[0])
        s = ((h1 + x * d) * inverse(k, n)) % n 
        X[i] = x
        S[i] = s 
    supp.append(d)
 
print(supp)
= Matrix(ZZ, 2 * D + 12 * D + 1)
lb = [0* (2 * D + 1)
ub = [0* (2 * D + 1
 
base_k = 0
for i in range(D):
    base_k += 3 * 16 * (256 ** i)
 
for i in range(2 * D):
    M[i, i] = 1
    lb[i] = 0
    ub[i] = 16 
 
for i in range(D):
    M[i, 2 * D] = int(((256 ** i) * (S[0* X[1])) % n)
    M[i + D, 2 * D] = int(n - ((256 ** i) * (S[1* X[0])) % n) 
    M[2 * D, 2 * D] = int(n)
    lb[2 * D] = int((h1 * (X[1- X[0]) - base_k * S[0* X[1+ base_k * S[1* X[0]) % n)
    ub[2 * D] = int((h1 * (X[1- X[0]) - base_k * S[0* X[1+ base_k * S[1* X[0]) % n)
 
 
result, applied_weights, fin = solve(M, lb, ub)
print(fin)
 
k0 = base_k 
for i in range(26):
    k0 += (256 ** i) * int(fin[i]) 
 
= (inverse(X[0], n) * (k0 * S[0- h1)) % n 
 
= Gx 
= (h2 + x * d) % n 
 
for i in range(3):
    print(r.recvline())
r.sendline(b"2")
r.sendline(b"Flag")
r.sendline(str(x))
r.sendline(str(s))
print(r.recvline())
print(r.recvline())
print(r.recvline())
cs

 

Lumberjack in Nature

1
2
3
4
5
6
7
8
9
10
11
12
from mpmath import mp, power, ln
import json
 
mp.dps = 1000000000
 
def decode(enc):
    return int(power(2, enc * ln(2)))
 
s, e = json.load(open('encoded.json'))
flag = decode(s << e)
 
print(flag.to_bytes((flag.bit_length() + 7// 8'big')[:74])
cs

 

To solve this problem, we need to know the higher bits of $$2^{s \cdot 2^e \cdot \ln 2}$$ where $e = 13371337$ is very large. This is equivalent to finding the decimal part of $s \cdot 2^e \cdot \ln 2$ to a very high precision. 

 

Since you need the decimal part, and $2^e$ is very large, if we want to do direct computation we would need at least $10^7$ binary digits of precision, which seems like too much to handle, even for SageMath. We would like the computation to be easier to do.

 

UPDATE : Never underestimate SageMath! Using $2 \cdot 10^7$ binary digits of precision works very well and fast.

 

The key idea is to approximate $\ln 2$ using the Taylor series $$\ln 2 = \sum_{n=1}^\infty \frac{1}{2^n n}$$ This implies that $$s \cdot 2^e \cdot \ln 2 = \sum_{n=1}^\infty \frac{s 2^{e-n}}{n}$$ and we can compute the decimal part of this as follows. We will sum from $n=1$ to $n=14000000$ as it is enough for precision.

  • If $e > n$, then compute $r = s \cdot 2^{e-n} \pmod{n}$ and add $r/n$ to the sum
  • If $n \le e \le n+600$, then compute $r = s \pmod{n \cdot 2^{n-e}}$ and add $r / (n \cdot 2^{n-e})$ to the sum
  • If $e > n+600$, then add $s / (n \cdot 2^{n-e})$ to the sum 
  • After each addition, if the value is larger than $1$, subtract $1$ from it

This is enough to compute the decimal part of $s \cdot 2^e \cdot \ln(2)$ with $10^4$ bits of precision in a few minutes. 

 

Now we can compute the higher bits of $2^{s \cdot 2^e \cdot \ln(2)}$ as well, and shift it and make it into bytes to get our flag.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
= RealField(10000)
s, e = 164407670104841080073659804452195762116507500922004735359869590815479854557466921362882298301347813164513610782999110714796659202306480268420598493560455658097643208225514854976313371337
print(s.bit_length())
 
res = R(0)
 
for i in tqdm(range(114000000)):
    # s / i* 2^(e-i)
    if i <= e:
        cc = int(  (s * int(pow(2, e - i, i)) ) % i )
        res += R(cc) / R(i)
    elif i <= e + 600:
        cc = s % (i * pow(2, i-e))
        res += R(cc) / R(i * (R(2** (i - e)))
    else:
        res += R(s) / R(i * (R(2** (i - e)))
    if res >= R(1):
        res -= R(1)
    
print(res)
res = R(2** res
 
for i in range(70 * 880 * 8):
    cc = int(res * R(2 ** i))
    print(cc.to_bytes((cc.bit_length() + 7// 8'big'))
cs

 

Lumberjack Against Nature

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from mpmath import power, ln
from random import SystemRandom
from string import ascii_letters
from signal import alarm
 
from secret import decode_fast, flag
 
alarm(10)
 
def to_string(number):
    return number.to_bytes((number.bit_length() + 7// 8'big')[:74]
def decode(enc):
    return to_string(int(power(2, enc * ln(2))))
 
assert(decode(1337 << 5== decode_fast(13375))
 
 
plaintext = ''.join(SystemRandom().choice(ascii_letters) for _ in range(74)).encode()
= 13371337
 
print(f'decode(s << {e}) == {plaintext}')
= int(input('s = ? '))
 
if 0 < s < 2 ** (75 * 8and decode_fast(s, e) == plaintext:
    print(f'Congrats! {flag}')
else:
    print(":P")
 
cs

 

Now we have to go around. Denote the decimal term of $2^{13371337} \cdot \ln(2)$ as $t$, and the target plaintext viewed as a integer as $v$.

 

We want to find an $0 \le s < 2^{600}$ such that $$2^{s \cdot t - z} \approx v$$ for some integer $z$. To solve this, we take the logarithm again and multiply $2^{5000}$, giving us $$s \cdot \lfloor 2^{5000} t \rfloor - 2^{5000} z \approx \lfloor \log_2(v) \cdot 2^{5000} \rfloor$$ It's clear that we can compute the two values $$T = \lfloor 2^{5000} t \rfloor , \quad V = \lfloor \log_2(v) \cdot 2^{5000} \rfloor$$ using the methods described in the challenge above and arbitrary precision logarithms from SageMath. Now we want something like $$ sT \pmod{2^{5000}} \approx V \pmod{2^{5000}}$$ If we plug in the values of the challenge above, we see that $$ V - 2^{4409} \pmod{2^{5000}} \le sT \pmod{2^{5000}} \le V + 2^{4409} \pmod{2^{5000}}$$ Here, note that $$L \pmod{M} \le x \pmod{M} \le R \pmod{M}$$ should be regarded as $x$ lies in the clockwise strip from $L$ to $R$ in a clock divided into $M$ pieces. Check the link below. 

 

Anyways, it's now clear that we want to solve the system $$0 \le s < 2^{600}, \quad V - 2^{4409} \pmod{2^{5000}} \le sT \pmod{2^{5000}} \le V + 2^{4409} \pmod{2^{5000}}$$ which is possible with the "special case variation" of the CVP repository. This will give around $2^{10}$ candidates for $s$. 

 

Since we have already precomputed $t$ and $T$, we can check the validity of each $s$ very easily.

While this solution works with a relatively low probability, it still works well enough to first blood this challenge. :)

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
def ceil(n, m): # returns ceil(n/m)
    return (n + m - 1// m
 
def is_inside(L, R, M, val): # is L <= val <= R in mod M context?
    if L <= R:
        return L <= val <= R
    else:
        R += M
        if L <= val <= R:
            return True
        if L <= val + M <= R:
            return True 
        return False
 
## some notes : it's good idea to check for gcd(A, M) = 1
## in CTF context, if gcd(A, M) != 1, we can factorize M and sometimes we can solve the challenge
## in competitive programming context, we need to check gcd(A, M) = 1 and decide whether solution even exists..
def optf(A, M, L, R): # minimum nonnegative x s.t. L <= Ax mod M <= R
    if L == 0:
        return 0
    if 2 * A > M:
        L, R = R, L
        A, L, R = M - A, M - L, M - R
    cc_1 = ceil(L, A)
    if A * cc_1 <= R:
        return cc_1
    cc_2 = optf(A - M % A, A, L % A, R % A)
    return ceil(L + M * cc_2, A)
 
# check if L <= Ax (mod M) <= R has a solution
def sol_ex(A, M, L, R):
    if L == 0 or L > R:
        return True
    g = GCD(A, M)
    if (L - 1// g == R // g:
        return False
    return True
 
## find all solutions for L <= Ax mod M <= R, S <= x <= E:
def solve(A, M, L, R, S, E):
    # this is for estimate only : if very large, might be a bad idea to run this
    # print("Expected Number of Solutions : ", ((E - S + 1) * (R - L + 1)) // M + 1)
    if sol_ex(A, M, L, R) == False:
        return []
    cur = S - 1
    ans = []
    num_sol = 0
    while cur <= E:
        NL = (L - A * (cur + 1)) % M
        NR = (R - A * (cur + 1)) % M
        if NL > NR:
            cur += 1
        else:
            val = optf(A, M, NL, NR)
            cur += 1 + val
        if cur <= E:
            ans.append(cur)
            # remove assert for performance if needed
            assert is_inside(L, R, M, (A * cur) % M)
            num_sol += 1
    print("Actual Number of Solutions : ", num_sol)
    return ans
 
= RealField(10000)
s, e = 113371337
res = R(0)
 
for i in tqdm(range(114000000)):
    # s / i* 2^(e-i)
    if i <= e:
        cc = int(  (s * int(pow(2, e - i, i)) ) % i )
        res += R(cc) / R(i)
    elif i <= e + 600:
        cc = s % (i * pow(2, i-e))
        res += R(cc) / R(i * (R(2** (i - e)))
    else:
        res += R(s) / R(i * (R(2** (i - e)))
    if res >= R(1):
        res -= R(1)
 
= int(res * R(2 ** 5000))
print(v)
 
sys.setrecursionlimit(10 ** 6)
 
while True:
    r = remote('34.146.212.53'53928)
    s = r.recvline()
    print(s)
    s = s[-76:-2]
    print(s)
 
    cc = bytes_to_long(s)
    res = R(cc).log() / R(2).log()
    res = int(res * R(2 ** 5000))
 
    # enc * v - integer * 2^5000 = ln_2(val) * 2^5000
    # enc * v - integer * 2^5000 = res 
    fin = solve(v, 1 << 5000, (res - (1 << 4409)) % (1 << 5000), (res + (1 << 4409)) % (1 << 5000), 01 << 600)
    dec = R(v) / R(2 ** 5000)
 
    finished = False
    for cand in fin:
        if finished:
            break
        val = dec * R(cand)
        val = val - val.floor()
        val = R(2** val
        for i in range(70 * 880 * 8):
            flag = int(val * R(2 ** i))
            flag = flag.to_bytes((flag.bit_length() + 7// 8'big')
            if s == flag[:74]:
                print(s)
                print(cand.bit_length())
                print(flag)
                print(cand)
                r.sendline(str(cand))
                ff = r.recvline()
                if b"? :P" in ff:
                    finished = True
                    break
                else:
                    print(ff)
    r.close()
cs

'수학 > 암호론 및 CTF' 카테고리의 다른 글

PBCTF 2021 Writeups  (0) 2021.10.13
TSGCTF 2021 Writeups  (0) 2021.10.03
DUCTF 2021 Writeups  (0) 2021.09.26
ACSC Crypto Writeups  (0) 2021.09.26
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05
Lattice Attacks Introductory Survey  (0) 2021.07.22

I briefly participated in DUCTF 2021, solving three crypto challenges and two simple rev challenges.

The reversing challenges were fun and hard enough for me, but they are labeled easy/medium so I will not explain them here.

Also, joseph (one of the problemsetters) has a very good writeup on https://jsur.in/posts/2021-09-26-ductf-2021-writeups, so check it out. 

 

yadlp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
def G_add(A, B):
    x1, y1 = A
    x2, y2 = B
    return ((x1*x2 + D*y1*y2) % p, (x1*y2 + x2*y1 + 2*y1*y2) % p)
 
def G_mul(A, k):
    out = (10)
    while k > 0:
        if k & 1:
            out = G_add(out, A)
        A = G_add(A, A)
        k >>= 1
    return out
 
def rand_element():
    while True:
        x = randint(1, p-1)
        d = x^2 * (D + 1- D
        if (x & 1 == d & 1and kronecker(d, p) == 1:
            y = (x + sqrt(Zmod(p)(d))) * inverse_mod(D, p) % p
            return (x, y)
 
= 13337
= 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
assert p.nbits() >= 512
assert ((p-1)//2).is_prime() # safe prime
 
FLAG = open('flag.txt''rb').read().strip()
assert len(FLAG) % 8 == 0
= [int.from_bytes(FLAG[i:i+8], 'big'for i in range(0len(FLAG), 8)]
 
= [rand_element() for _ in M]
= (10)
for m, gi in zip(M, G):
    c = G_add(c, G_mul(gi, m))
 
print(f'{D = }')
print(f'{p = }')
print(f'{G = }')
print(f'{c = }')
 
cs

 

Step 1 

In challenges like these, figuring out the curve we are on is usually the first step. To do this, we let $$y = \frac{x +\sqrt{(D+1)x^2 - D}}{D}$$ and work out some algebra to end up with $$(x+y)^2 - (D+1)y^2 = 1$$ which is a Pell's equation. Now we change $(x, y)$ to $(x+y, y)$ and change $D$ to $D+1$ and consider $x^2 - Dy^2 = 1$. 

 

The solutions of Pell's equation satisfy some good properties, which come from the identity $$(a^2-Db^2)(c^2-Dd^2) = (ac+Dbd)^2 - D(ad+bc)^2$$ which shows that if $(a, b), (c, d)$ are solutions of $x^2-Dy^2=1$, then $(ac+Dbd, ad+bc)$ is also such a solution. This turns out to be the group addition as well. The homomorphism to a multiplicative group of $\mathbb{F}_{p^2} = \mathbb{F}_p[x] / (x^2 - D)$ written as $$ (a, b) \rightarrow a + bx$$ is also notable. The results here so far can be studied from Pell's equation theory, so the point up to here were straightforward for me.

 

Step 2 

Now we have to look at the group structure. There are various methods to end up with the correct conclusion - that the group is a cyclic group of order $p+1$. You could just guess the group order, or give a solid mathematical proof. joseph gives a proof by using that the multiplicative group of $\mathbb{F}_{p^2}$ is cyclic and $\alpha^{p+1}=1$ for each $\alpha = a + bx$ for $(a, b)$ satisfying $a^2 - Db^2 = 1$. I think technically this proves that the group order is a divisor of $p+1$, but this is quite good as well. Here's another method that I used during my solve.

 

It suffices to show that there are exactly $p+1$ solutions for $a^2 - Db^2 \equiv 1 \pmod{p}$. This is equivalent to computing $$\sum_{b=0}^{p-1} 1 + \left( \frac{Db^2 + 1}{p} \right) = 2 + \sum_{b=1}^{p-1} 1 + \left( \frac{Db^2+1}{p} \right) $$ $$ = 2 + \sum_{b=1}^{p-1} 1+ \left( \frac{D + b^2}{p} \right)$$ which means the value is the number of solutions for $$a^2 - b^2 \equiv D \pmod{p}, \quad b \not\equiv 0 \pmod{p} $$ plus $2$. Of course, the given equation is equivalent to $$(a-b)(a+b) \equiv D \pmod{p}$$ and there are $p-1$ solutions of the form $$a-b \equiv i \pmod{p}, \quad a+b \equiv Di^{-1} \pmod{p}$$ for each $i \in \{1, \cdots , p-1\}$. The key is that none of the solutions have $b \equiv 0 \pmod{p}$ because $D$ is, in this problem, not a quadratic residue. Therefore, the number of solutions is $2 + (p-1) = p+1$, as desired. This concludes the proof.

 

Note that if $D$ was a quadratic residue, there would be $p-1$ solutions.

 

This is really the turning point of the challenge - if $D$ was a quadratic residue, the group order would be $p-1$ and the fact that $p$ is a safe prime will help greatly to make the cipher safe. However, $D$ is not a quadratic residue, which makes the fact that $p$ is "safe" mean absolutely nothing. In fact, $p+1$ is very smooth. I thought that the whole $p$ is "safe" thing in the given script was a very funny joke :)

 

Step 3

Now we compute the actual discrete logarithm. There are many ways to compute this - you could write a custom Pohlig-Hellman algorithm to account for different addition and multiplication formula, which is possible but a hassle. An easier way is to define $\mathbb{F}_{p^2} = \mathbb{F}_p[x] / (x^2 - D)$ and work discrete logarithm over this field. Of course, to find a discrete logarithm, we need a generator $g$ for the field. Theoretically, we can just find random points until we find a generator. In my solution, I just tried the given points.

 

Step 4

Now that we know all the discrete logarithms, all we need to do is compute the flag. We see that $$ \sum m_i \log_g(g_i) = \log_g(res) \pmod{p+1}$$ along with $0 \le m_i < 2^{64}$. This condition can be straightforwardly feeded into my CVP repository https://github.com/rkm0959/Inequality_Solving_with_CVP and we have the flag. This was a nice challenge combining a lot of fun math ideas :)

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
        # heuristic for number of solutions
    DET = 0
 
    if num_var == num_ineq:
        DET = abs(mat.det())
        num_sol = 1
        for i in range(num_ineq):
            num_sol *= (ub[i] - lb[i])
        if DET == 0:
            print("Zero Determinant")
        else:
            num_sol //= DET
            # + 1 added in for the sake of not making it zero...
            print("Expected Number of Solutions : ", num_sol + 1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            print("Fail : inequality does not hold after solving")
            break
    
        # recover x
    fin = None
 
    if DET != 0:
        mat = mat.transpose()
        fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
= 13337
= 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
= [(824914940549535049134693493358510941451078743259825009611468757037905313350871186248512803517454757191925623544169989938841766683559931596350748072767428510151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (101486582544154755882799565747721968985757181546439671636266944003630091685296458602809598108730283939708536437234250236788574082203309291165264672955425073332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (183932668108693992521485398085562602312041460603947441945549962588535727427581518939988035699537651402132911882906207114481856245726889232477383971353397717502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (31659559589682038792373443499625336425984410444816927701478078393729427158560475807660732222976925740259222603744099204176656000696651625025144031884325799382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (85002940632911245271086232819802558705075497343626042596459840443706586203853513387110519988860262606571329443536753351788719347982001630351902784834916337641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (123526856735509864536970355600066326281947889029213985456688284373398735442238959974405852278389199689296697383935356101033820848429004040054320076371939432453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)]
= (53885671676587869351584134016741684201444292771720647214726629135637756703202984619499793624021577642727627552363209890189894463607407200724886231027760157420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)
 
print(len(G))
 
'''
D = 13338
p = 17568142778435152362975498611159042138909402642078949814477371651322179417849164549408357464774644525711780515232117470272550677945089719112177956836141583
G = [(8249149405495350491346934933585109414510787432598250096114687570379053133508711862485128035174547571919256235441699899388417666835599315963507480727674285, 10151966144947987666795899106244951506314545969111450078363915090201899029695981970354886015549281568762501638756950135017679627954071369058817947706039379), (10148658254415475588279956574772196898575718154643967163626694400363009168529645860280959810873028393970853643723425023678857408220330929116526467295542507, 3332426625916817700349475905733631656792492189677766534230576987725484499618918928882667666640821403823057239790395654518704427126712280655564669757208129), (1839326681086939925214853980855626023120414606039474419455499625885357274275815189399880356995376514021329118829062071144818562457268892324773839713533977, 17502649671831125396398431215302241914145169143474764941575812028922929277656849105757332346628455059539582448544435155655055157181361580680672298566085040), (3165955958968203879237344349962533642598441044481692770147807839372942715856047580766073222297692574025922260374409920417665600069665162502514403188432579, 9382092026348588885644924948782239369051861025018411316856012639637274661831713783735305424388410778778529413114167923397187236739639802371814632949741663), (8500294063291124527108623281980255870507549734362604259645984044370658620385351338711051998886026260657132944353675335178871934798200163035190278483491633, 7641198814027309580920446604109217188703337221305342467525089149977505415741300885194767452232679123441594451455097533000754553745051816419202345186703390), (12352685673550986453697035560006632628194788902921398545668828437339873544223895997440585227838919968929669738393535610103382084842900404005432007637193943, 2453949984320580417885537763124479618094084392655766673219227195157341323190069350175423869908524758510177197973709821798974003013596311361995273762475822)]
c = (5388567167658786935158413401674168420144429277172064721472662913563775670320298461949979362402157764272762755236320989018989446360740720072488623102776015, 7420389277336940268114831002964626027945367662485419944369852006741899961686908509331719915794976159062761271182318814519641566938538911041229521838799714)
GG = []
for a, b in G:
    GG.append((a+b, b))
a, b = c
cc = (a+b, b)
K.<z> = GF(p**2, name='z', modulus=x^2 - D)
tt = (p+1) // 432
L = list(factor(tt))
print(L)
base = (a+b) + b * z
for a, b in GG:
    v = a + b * z
    print(v.log(base))
'''
 
logs = [2816026164685113357819599161916784095343437608176866348054691853599389483035986857942301105700772017038015800856893756018342135280046636282509828459475264
,4454166524908585051122091699367767320812675170250549943320148456830102311369800005419960817723812062960747357335951038181643917358801852112440501578475705
,10592989590744873457884645785658581545224173008189907961231282661924610752981017572693574053983522152348945200152352773129758671274319626386160131388585752
,9412387853225306787772668180506806539830098501890523194264793947862715307266992454894401276064400106485711592745559238039738469223857458389407805014776300
,11705006563236210956123096549924041531532105228094197348728492717298448400356434417842060810409623716614227796999859505036258530445896800424164580386003096
,7526156655082313923417616532606029321209669119704767191155046511306556916835849234170663657892790215760669790225464654694145090868608505033102329054110089]
 
= Matrix(ZZ, 77)
lb = [0* 7
ub = [0* 7
for i in range(6):
    M[i, 0= logs[i]
M[60= p + 1
lb[0= 1
ub[0= 1
 
for i in range(6):
    M[i, i+1= 1
    lb[i+1= 0
    ub[i+1= (1 << 64)
 
result, applied_weights, fin = solve(M, lb, ub)
 
flag = b''
for i in range(6):
    flag += long_to_bytes(int(fin[i]))
 
print(flag)
cs

 

power sign

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#!/usr/bin/env sage
 
proof.arithmetic(False# just makes things faster
 
def get_3m4_prime(N):
    while True:
        p = random_prime(2^N - 1, lbound=2^(N-1))
        if p % 4 == 3:
            return p
 
def generate_key(L, n, m):
    p = get_3m4_prime(L//2)
    q = get_3m4_prime(L//2)
    N = p*q
    r = next_prime(N)
    F.<x> = PolynomialRing(GF(r))
    K = F.quo(F.irreducible_element(n))
    return (K, m), N, (p, q)
 
def H(params, msg, u):
    K, m = params
    r, z = K.characteristic(), K.gens()[0]
    h = 0
    while msg > 0:
        h *= z
        h += msg % r
        msg //= r
    h += z*u
    for _ in range(m):
        h ^= r
    assert len(list(h)) != 0
    return int(h[0])
 
def sign(params, privkey, msg):
    p, q = privkey
    u = 1
    while True:
        c = H(params, msg, u) % (p*q)
        if legendre_symbol(c, p) == legendre_symbol(c, q) == 1:
            break
        u += 1
    xp = pow(c, (p+1)//4, p)
    xq = pow(c, (q+1)//4, q)
    x = crt([int(xp), int(xq)], [p, q])
    return x, u
 
def verify(params, pubkey, msg, sig):
    N = pubkey
    x, u = sig
    c = H(params, msg, u)
    return x^2 % N == c % N
 
def main():
    print('Welcome to the game. To get the flag, give me a message to sign, then sign a random message of mine!')
    FLAG = open('./flag.txt''r').read().strip()
 
    L, n, m = 1024153
    params, pubkey, privkey = generate_key(L, n, m)
    print('N:', pubkey)
 
    msg = int(input('message (in hex): '), 16)
    if msg < pubkey^m:
        print('That message is too small!')
        exit()
    if msg > pubkey^n:
        print('That message is too big!')
        exit()
    x, u = sign(params, privkey, msg)
    print('x:', x)
    print('u:', u)
 
    auth_msg = randint(1, pubkey^5)
    print('Now sign', hex(auth_msg))
    x = int(input('x: '))
    u = int(input('u: '))
 
    if verify(params, pubkey, auth_msg, (x, u)):
        print(FLAG)
    else:
        print('Incorrect!')
 
if __name__ == '__main__':
    main()
 
cs

 

There are a lot of approaches possible, and a lot of solutions are on joseph's writeup linked above. Here, I'll just write my solution. 

 

Ultimately, we need $x, u$ such that $$x^2 \equiv H(msg, u) \pmod{N}$$ holds. Obviously there must be some issue with the whole $H$, so let's take a look in that whole thing. 

 

In $H$, we write $msg$ as a polynomial in $GF(r^n)$ and then computes the constant part of $$(msg + zu)^{r^m}$$ My immediate idea was to utilize frobenius endomorphism to simplify $$(msg + zu)^{r^m} \equiv msg^{r^m} + z^{r^m} u^{r^m} \equiv msg^{r^m} + z^{r^m} u \pmod{r}$$ which was linear in $u$. This gave us $$H(msg, u) = H(msg, 0) + u H(0, 1) \pmod{r}$$ and both $H(msg, 0)$ and $H(0, 1)$ can be computed directly from the given data.

 

Therefore, we can just select $u$ appropriately to make $H(msg, u) \equiv 1 \pmod{r}$ and send $x=1$ to get the flag.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def H(params, msg, u):
    K, m = params
    r, z = K.characteristic(), K.gens()[0]
    h = 0
    while msg > 0:
        h *= z
        h += msg % r
        msg //= r
    h += z*u
    for _ in range(m):
        h = h ** r
    assert len(list(h)) != 0
    return int(h[0])
 
conn = remote('pwn-2021.duc.tf'31912)
conn.recvline()
 
= int(conn.recvline().split()[1])
 
= next_prime(N)
= PolynomialRing(GF(r), 'x')
= F.quo(F.irreducible_element(15))
params = (K, 3)
pubkey = N
 
conn.sendline(hex(pubkey ** 6)[2:].encode())
conn.recvline()
conn.recvline()
 
target = int(conn.recvline().split()[2][2:].decode(), 16)
 
val_1 = H(params, target, 0)
val_2 = H(params, 01)
 
= ((1 + r - val_1) * inverse(val_2, r)) % r
 
conn.sendline(str(1).encode())
conn.sendline(str(u).encode())
 
print(conn.recvline())
cs

 

l33tcrypt v2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
from Crypto.Util.number import getPrime, bytes_to_long
 
flag = open('flag.txt''rb').read().strip()
 
p, q = getPrime(1337), getPrime(1337)
= p*q
 
K.<z> = NumberField((x-p)^2 + q^2)
hint1 = p^2 + q^2
hint2 = []
 
= 1+337
for _ in range(1*3*3-7):
    a, b = getrandbits(1337), getrandbits(1337)
    x = K(a + getrandbits(l)/2^l) + K(b + getrandbits(l)/2^l)*z
    y = x*x.conjugate()
    hint2.append((int(y), a, b))
 
Zn.<I> = (ZZ.quo(n*ZZ))[]
ZnI.<I> = Zn.quo(I^2 + 1)
 
= randrange(1, n) + bytes_to_long(flag) * I
= pow(m, 0x1337)
 
print(f'hint1 = {hint1}', f'hint2 = {hint2}', f'c = {c}', sep='\n')
 
cs

 

Hour 1-2

CCE, a local CTF, was going on, but I was done with my part and had some time on my hands. 

That whole number field thing looked very scary, but the "error part" getrandbits and the "error part" from rounding $y$ made me believe that this is not really about number fields, but more about "approximate stuff" like lattices.

 

Also, I saw that after we find $p, q$, the remaining part can be copied from TetCTF 2021. (https://rkm0959.tistory.com/192)

 

After looking at basic conjugate things like $\overline{x} = 2p-x$ and $x \overline{x} = p^2 + q^2$ and doing some calculations on paper, I ended up with $$(a+r_1)^2 + 2p(a+r_1)(b+r_2) + (b+r_2)^2 (p^2+q^2) = y + r_3$$ where $0 \le r_1, r_2, r_3 < 1$. To make everything integer, multiplying $4^l$ gives $$(2^la + r_1)^2 + 2p(2^la+r_1)(2^lb+r_2) + (2^lb+r_2)^2 (p^2+q^2) + 4^ly + r_3$$ where $0 \le r_1, r_2 < 2^l$ and $0 \le r_3 < 4^l$ are integers. We have two equations, so in total, 6 error terms. 

 

We know $p^2+q^2$, so we only want the $p$ part. I wanted to plug in CVP repo, but it's not possible in this form. This is because the equations have parts like $r_1r_2p$, which is a large unknown value. This situation happened to me before - it was in AeroCTF horcrux (https://rkm0959.tistory.com/211) and I had talked about my solution with joseph before on discord. So I thought this might be the way. The idea is to cancel out $p$, making everything about the 6 error terms only. In the end, I would have a 6-variable polynomial to solve for small roots. 

 

In AeroCTF horcrux, the bounds were good enough that I could finish with CVP repo, not using the full power of the polynomials. To be more exact, I wouldn't need to use that $r_1r_2$ is $r_1$ multiplied by $r_2$ - just the fact that $0 \le r_1r_2 < 2^{2l}$. However, that was not true for this problem, as my CVP repo failed to give a correct solution. This meant that I actually needed the full power of 6 variable polynomials. I tried defund's repo, but it killed my computer. Another idea I had in mind was to use bounding to find one of $r_1, r_2$. However, not knowing $p$ precisely made this impossible. Then I went to work on writing up CCE and had dinner. 

 

Hour 3

I started with the bounding idea again - the part that kept bugging me was that $r_1$ really didn't matter. For example, if I had known $p$, I could find $r_2$ without the knowledge of $r_1$ or $r_3$ as the "impact" of $r_2$ is far greater than $r_1$ or $r_3$ in the whole equation.

 

To be more detailed, consider the equation $$(a+r_1)^2 + 2p(a+r_1)(b+r_2) + (b+r_2)^2 (p^2+q^2) = y + r_3$$ with $0 \le r_1, r_2, r_3 < 1$. When $r_1$ changes from $0$ to $1$, the LHS increases about 1337 * 2 bits. When $r_3$ changes from $0$ to $1$, the RHS increases about 1 bit. When $r_2$ changes from $0$ to $1$, the LHS increases about 1337 * 3 bits. This made me think about ignoring all $r_1, r_3$ parts as "noises", simplifying the equations at the cost of a looser bound and loss of information. 

 

Consider $0 \le r_1, r_2 < 2^l$ and $0 \le r_3 < 4^l$, with $$\left( a+ \frac{r_1}{2^l} \right)^2 + 2p \left(a + \frac{r_1}{2^l} \right) \left( b + \frac{r_2}{2^l} \right) + \left(b+\frac{r_2}{2^l} \right)^2 (p^2+q^2) = y + \frac{r_3}{2^{2l}}$$ we will divide this by $p^2+q^2$, and denote anything that is around 1 or smaller as $O(1)$. This gives $$ \frac{1}{p^2+q^2} \left( a+ \frac{r_1}{2^l} \right)^2 + \frac{1}{p^2+q^2} 2p \left(a + \frac{r_1}{2^l} \right) \left( b + \frac{r_2}{2^l} \right) + \left(b+\frac{r_2}{2^l} \right)^2  = \frac{1}{p^2+q^2} y + \frac{1}{p^2+q^2} \cdot \frac{r_3}{2^{2l}}$$ First, $a^2$ is 1337 * 2 bits and so is $p^2 + q^2$, implying that the first part is $O(1)$. For the second part, if we fully expand the numerator, the part excluding $2pab$ are all around 1337 * 2 bits, implying that it is $O(1)$ after division by $p^2+q^2$.

We can also see that $(r_2/2^l)^2$ is $O(1)$. Finally, clearly $r_3/4^l$ is already $O(1)$. In conclusion, we have the stunning equation $$O(1) + \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l} =  \frac{y}{p^2+q^2} $$ and in practice, the inequality $$ \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l} \le \frac{y}{p^2+q^2} \le 3 + \frac{2ab}{p^2+q^2} p + b^2 + \frac{2r_2b}{2^l}$$ worked well, which was verified with multiple testing with generated data. After clearing denominators, this was the perfect inequality to plug into CVP repo. Everything was known except $p$ and one error term for each equation, and everything was linear in terms of unknown values. I plugged this into the CVP repository, but there were multiple solutions. It took a few minutes to figure out that my candidates for $p$ were all consecutive integers, and I just had to take the next prime number to find the actual $p$, giving the flag.

 

This was a really really good challenge that taught me a lot. It had an interesting tradeoff of complexity and precision.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
 
def inthroot(a, n):
    return a.nth_root(n, truncate_mode=True)[0]
 
# Directly taken from rbtree's LLL repository
# From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI
def Babai_CVP(mat, target):
    M = IntegerLattice(mat, lll_reduce=True).reduced_basis
    G = M.gram_schmidt()[0]
    diff = target
    for i in reversed(range(G.nrows())):
        diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()
    return target - diff
 
 
def solve(mat, lb, ub, weight = None):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    if weight == None:
        weight = num_ineq * max_element
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return
 
    # heuristic for number of solutions
    DET = 0
 
    m = mat * mat.transpose()
    DET = inthroot(Integer(m.det()), 2)
    num_sol = 1
    for i in range(num_ineq):
        num_sol *= (ub[i] - lb[i])
    if DET == 0:
        print("Zero Determinant")
    else:
        num_sol //= DET
        # + 1 added in for the sake of not making it zero...
        # print("Expected Number of Solutions : ", num_sol + 1)
        # print(num_sol+1)
 
    # scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])
    applied_weights = []
 
    for i in range(num_ineq):
        ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(num_var):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    # Solve CVP
    target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])
    result = Babai_CVP(mat, target)
 
    for i in range(num_ineq):
        if (lb[i] <= result[i] <= ub[i]) == False:
            # print("Fail : inequality does not hold after solving")
            return NoneNoneNone
            break
    
        # recover x
    fin = None
 
    mat = mat.transpose()
    fin = mat.solve_right(result)
    
    ## recover your result
    return result, applied_weights, fin
 
hint1 = 9474114456792673515431877947943819508105969635542281515830563486137327168661333703401850605206493227243522275742966516648683239582868203596838274343178793480973891177607186024817920580636526398124249438530268326706106084200991464054888550590630591134888356623254262308517945404542523082470069480353068223694311508861801523183513245279545596528410382012946385366699431483305340128165852371328697376926968446708099825429442186214124021086080153564030893750081986851543881131351556953787562383902563532279388285764786107301410609469955447888060120474186646198067390958666731078269768973485409216649415321100676385488676994332545669638759522053210552702128133338413305324201806761866164474398103381334477039479224259925086453057512169480806903881772813089475880157326511289464083589335128877565750510634618850
hint2 = [(732546382458694012527789828012658378094702844241795401426843533262220812770028735455197287163119092985574791815396084039371039996745646333674579318749988785972110472195404257454757344814442424493794011566431937242360848878285030166984149693743077380791443878087350475749876855340312637158554338528312647367781264029940556029591883509296327157870585105957528288777977912893801651347425601258985587330670953298765350018187069720989197539655266126608555068568433785671130844623376557756307700624321155540004939237651224429899583558320317618753120682478549822994855115229255313084828494729871333964260804633974731539710591594817406548163223896591957023800247556355776277803866504762994363248426088927388107745396346246364269053285330511504658050763844166012473791572894552857353549047649195624795947489180260979461063462063828112399114859364813704521025921163040319096254633472956309716047137099678802685979113668885601296025318218875502044310139823328365450929054463143898168438742821823709383772324178942782797995009228644990630313338092741812684409459706859981433655900653533420603781201785114071059836464490109704785152549161122683211537057829631974746267465106271003835623120675868336217957493577419646574917016786960763971105924313670864643113152080247596101761667919974877317059734430884155146853783807463171001928603696124835265895296591581488900411484570933812177545618929573489183920330986109459899431831015221573294655414274883012371358092609067769905057144741729285256290725546405447624734438623235233946301969480294721959115680856021696640872884026385162811995627855934793386619910476937700613082779, 1543824598221623810544208805328287421613768036151947874139391287620165680044273642997713684429385602196228549596953402195253771549624806908757244012787647676921740972118119690619160814867773301029620094485726996907379061963500831983371578370700427374066341469843386724329442101058337650126328673673103875588454070821764869582749550357448526278027673495765146251605639297850930361919443005623694632013303, 278066231056905142305104802223227529510107823582373063981133703297010715328189269872672545717708004188569473458656648620603642909190690880317856689557616399347538953740829444695466029704435732263108744727780955070759083273384356847390585190707938226562580173928509689922077486197504519480359398971760153208230160873276281036727480009843280457680277644007154868247812957266590582948212002647347579597965), (2403931462615300014912573083791207269120927941165936946270714147348589275302782927254153349406751900409737005652653965419293500156635383418370534229776798159799544655491444625223239629070116271649566531509751492007287556686610922243146922720689240769956444136141045389983487722510967341333296316124861289680453311483583713394680884118860739515747245777714794715741583447733115461680095467478792575220154609730018111981467052398055564596522296491712770565301016865613056558617018826541540034369006769600336871572325043701351770219492587170369815095344397680717819930616599208355365092147396589419063661351495695927808384696467907751578957796331366383391221037004742878990846671674314297157060496951084267550785175020195260374151822097301166545332365173007130667658669023236685137146454027881996654859397883138679620794416770836903293285267689375186032800923071081877797299448490161970114063577601307797826188431113415671273120884557490666872780316977507218882738147619244927641770516473541881268874031321080906148751514801419469523784406736104695838521768957591700470012632981881278541917424550592192054960270762406248837436552253011562745897713476468254217503340327771690937113342506707740878371307784138197357653258554320947445665637325825934844545591362876466794093523698691499245458580590045390833227060694376995243735824822120025136206595444317852707366827787780703456414342309744435791623414331744392284997640092463157849832124166944965921884701468913065315740226664124591175781629426506057267248659303310396227692666112080517619152746622372541984530565220811971391954114052398015660212010257113648848847, 1095271776133890944180744243712910546278746562392568011876271303881431329832093376635925871119446466987231888845639447279594831752278087660346437418402997861987783151298417098367490883057794520011454228160352569059415183920272078930149476192223454197039306461996527833603604938471295363667754643414137116188016150205603690898270274189826416464265752825558069478170856048769787582750749123139364050774900, 503722937364073120219172142862403799517933100630972300242952550817433776953552478694914014362767990852845981728951892566080540126804572527879551832311854342967959495035585119889481210539549990451963720802920003582648892828543694739151645941765335597098334960962085798952240875279321239403245884262371088975882015803767312665173035156867269826854927631774910426072984288933637519024572470691768302645082)]
= 605102888419960227209554020321928680123927287488855374705023014664876415212834812004489811277243459845970579234661036307883657755039678491432326372452841243321229852171896023071850921050801342321482817352489245753590859528134913389224781053767643398051814697896895555141791201522215484812840325201515942495422062613986130075684389632368804195932004897586630630338128732739336582396560286087433253207646470438321442025408149861408487622053608073870706373371068091196032798889074109310838175523351596714632562756238346928415386196418507587810202943766172435188745498284802679701385932344117910084137055452834777639122479568560833213921960536746001563295384313906616645378042076612734674897406388665158992742560848871345048141300064428115232029157294890916882227084289355920878535418217759491272196240289158*+ 4029058763453606238903897463441562834907249422434463474076515876575829847522130192389016587404930865750330557087612323698180248796377295462524538856886086398759909290696184205993616487194215215220788562122976961077906744617472657126002125275580071372330371116294688544107523683271239033324714979085342248973341926663953843846046960739886947485863993625451601367382937578510847100654709310703410238862000749364014455073705910890023184023421059288913438268024784676942709153616462894290327611033397199003399769315399282676125251796552761022560343255167268538619398474794249565056809687349530329863724341722260050648912909130315084736439621962322946883555665867960336853966064629555225967168666632969614488585135849531033105444785970372310095381763641123031809302021416125564151419362313796375570121725315170
= 338
 
offset = 3
 
= Matrix(ZZ, 34)
lb = [0* 4
ub = [0* 4
 
y1, a1, b1 = hint2[0]
y2, a2, b2 = hint2[1]
 
target1 = (y1 // hint1 - b1 * b1) * (1 << (l-1)) * hint1
fx = hint1 * (1 << (l-1))
 
M[00= a1 * b1 * (1 << l)
M[10= hint1 * b1 
lb[0= target1 - offset * fx 
ub[0= target1 
 
target2 = (y2 // hint1 - b2 * b2) * (1 << (l-1)) * hint1 
 
M[01= a2 * b2 * (1 << l)
M[21= hint1 * b2
lb[1= target2 - offset * fx
ub[1= target2
 
M[12= 1
lb[2= 0
ub[2= 1 << l
 
M[23= 1
lb[3= 0
ub[3= 1 << l
 
result, applied_weights, fin = solve(M, lb, ub)
 
= next_prime(int(fin[0]))
= inthroot(Integer(hint1 - p * p), 2)
 
print(p * p + q * q - hint1)
 
'''
phi = (p * p - 1) * (q * q - 1)
d = int(inverse_mod(0x1337, phi))
n = p * q
Zn.<I> = (ZZ.quo(n*ZZ))[]
ZnI.<I> = Zn.quo(I^2 + 1)
c = 605102888419960227209554020321928680123927287488855374705023014664876415212834812004489811277243459845970579234661036307883657755039678491432326372452841243321229852171896023071850921050801342321482817352489245753590859528134913389224781053767643398051814697896895555141791201522215484812840325201515942495422062613986130075684389632368804195932004897586630630338128732739336582396560286087433253207646470438321442025408149861408487622053608073870706373371068091196032798889074109310838175523351596714632562756238346928415386196418507587810202943766172435188745498284802679701385932344117910084137055452834777639122479568560833213921960536746001563295384313906616645378042076612734674897406388665158992742560848871345048141300064428115232029157294890916882227084289355920878535418217759491272196240289158*I + 4029058763453606238903897463441562834907249422434463474076515876575829847522130192389016587404930865750330557087612323698180248796377295462524538856886086398759909290696184205993616487194215215220788562122976961077906744617472657126002125275580071372330371116294688544107523683271239033324714979085342248973341926663953843846046960739886947485863993625451601367382937578510847100654709310703410238862000749364014455073705910890023184023421059288913438268024784676942709153616462894290327611033397199003399769315399282676125251796552761022560343255167268538619398474794249565056809687349530329863724341722260050648912909130315084736439621962322946883555665867960336853966064629555225967168666632969614488585135849531033105444785970372310095381763641123031809302021416125564151419362313796375570121725315170
print(pow(c, d))
'''
cs

 

'수학 > 암호론 및 CTF' 카테고리의 다른 글

PBCTF 2021 Writeups  (0) 2021.10.13
TSGCTF 2021 Writeups  (0) 2021.10.03
DUCTF 2021 Writeups  (0) 2021.09.26
ACSC Crypto Writeups  (0) 2021.09.26
CryptoCTF Writeups (DoRSA, Polish)  (0) 2021.08.05
Lattice Attacks Introductory Survey  (0) 2021.07.22

This writeup is long overdue, sorry about that. I participated in ACSC finals, and solved nearly all crypto, as there was a cryptography challenge that was really more about SQL Injection than cryptography. To be more detailed, the exact same cryptogrpahic vulnerability is used in one of the cryptohack challenges (and it has very similar setups as well) so the cryptographic side of the challenge is next to none. I had some fun learning some basic SQL Injection and got close, but ultimately failed to solve the challenge. I did solve all others, including one that was solved only by me. This writeup will be relatively short and concise, as I do not have a lot of time on my hands.

 

The solutions codes are on the usual github, https://github.com/rkm0959/Cryptography_Writeups/tree/main/2021/ACSC  

 

RSA Stream

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
import gmpy2
from Crypto.Util.number import long_to_bytes, bytes_to_long, getStrongPrime, inverse
from Crypto.Util.Padding import pad
 
from flag import m
#m = b"ACSC{<REDACTED>}" # flag!
 
= open("chal.py","rb").read() # I'll encrypt myself!
print("len:",len(f))
= getStrongPrime(1024)
= getStrongPrime(1024)
 
= p * q
= 0x10001
print("n =",n)
print("e =",e)
print("# flag length:",len(m))
= pad(m, 255)
= bytes_to_long(m)
 
assert m < n
stream = pow(m,e,n)
cipher = b""
 
for a in range(0,len(f),256):
  q = f[a:a+256]
  if len(q) < 256:q = pad(q, 256)
  q = bytes_to_long(q)
  c = stream ^ q
  cipher += long_to_bytes(c,256)
  e = gmpy2.next_prime(e)
  stream = pow(m,e,n)
 
open("chal.enc","wb").write(cipher)
 
 
cs

 

We see that we are encrypting the given python file, so we know the plaintext and the ciphertext.

Since this is an XOR cipher, this implies that we know all the key streams used to encrypt the plaintext.

We note that the key streams are composed of $m^e \pmod{n}$ where $e$ are several primes. 

Of course, if we know $m^{e_1} \pmod{n}$ and $m^{e_2} \pmod{n}$ with $\gcd(e_1, e_2) = 1$, we can find $r_1, r_2$ such that $e_1r_1 + e_2r_2 = 1$.

Now we can finish calculating $m$ by simply using $$m \equiv m^{e_1 \cdot r_1} m^{e_2 \cdot r_2} \pmod{n}$$

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
length = 723
= 30004084769852356813752671105440339608383648259855991408799224369989221653141334011858388637782175392790629156827256797420595802457583565986882788667881921499468599322171673433298609987641468458633972069634856384101309327514278697390639738321868622386439249269795058985584353709739777081110979765232599757976759602245965314332404529910828253037394397471102918877473504943490285635862702543408002577628022054766664695619542702081689509713681170425764579507127909155563775027797744930354455708003402706090094588522963730499563711811899945647475596034599946875728770617584380135377604299815872040514361551864698426189453
= 65537
 
= open("chal.py","rb")
inp = f.read()
f.close()
 
= open("chal.enc""rb")
outp = f.read()
f.close()
 
data = []
= 65537
 
for i in range(0768256):
    cc = inp[i:i+256]
    if len(cc) < 256:
        cc = pad(cc, 256)
    res = bytes_to_long(cc) ^ bytes_to_long(outp[i:i+256])
    data.append([res, e])
    e = nextprime(e)
 
= inverse(6553765539)
= (65537 * u - 1// 65539
 
= (pow(data[0][0], u, n) * inverse(pow(data[1][0], v, n), n)) % n
 
print(long_to_bytes(m))    
cs

 

CBCBC

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#!/usr/bin/env python3
 
import base64
import json
import os
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from secret import hidden_username, flag
 
key = os.urandom(16)
iv1 = os.urandom(16)
iv2 = os.urandom(16)
 
 
def encrypt(msg):
    aes1 = AES.new(key, AES.MODE_CBC, iv1)
    aes2 = AES.new(key, AES.MODE_CBC, iv2)
    enc = aes2.encrypt(aes1.encrypt(pad(msg, 16)))
    return iv1 + iv2 + enc
 
 
def decrypt(msg):
    iv1, iv2, enc = msg[:16], msg[16:32], msg[32:]
    aes1 = AES.new(key, AES.MODE_CBC, iv1)
    aes2 = AES.new(key, AES.MODE_CBC, iv2)
    msg = unpad(aes1.decrypt(aes2.decrypt(enc)), 16)
    return msg
 
 
def create_user():
    username = input("Your username: ")
    if username:
        data = {"username": username, "is_admin"False}
    else:
        # Default token
        data = {"username": hidden_username, "is_admin"True}
    token = encrypt(json.dumps(data).encode())
    print("Your token: ")
    print(base64.b64encode(token).decode())
 
 
def login():
    username = input("Your username: ")
    token = input("Your token: ").encode()
    try:
        data_raw = decrypt(base64.b64decode(token))
    except:
        print("Failed to login! Check your token again")
        return None
 
    try:
        data = json.loads(data_raw.decode())
    except:
        print("Failed to login! Your token is malformed")
        return None
 
    if "username" not in data or data["username"!= username:
        print("Failed to login! Check your username again")
        return None
 
    return data
 
 
def none_menu():
    print("1. Create user")
    print("2. Log in")
    print("3. Exit")
 
    try:
        inp = int(input("> "))
    except ValueError:
        print("Wrong choice!")
        return None
 
    if inp == 1:
        create_user()
        return None
    elif inp == 2:
        return login()
    elif inp == 3:
        exit(0)
    else:
        print("Wrong choice!")
        return None
 
 
def user_menu(user):
    print("1. Show flag")
    print("2. Log out")
    print("3. Exit")
 
    try:
        inp = int(input("> "))
    except ValueError:
        print("Wrong choice!")
        return None
 
    if inp == 1:
        if "is_admin" in user and user["is_admin"]:
            print(flag)
        else:
            print("No.")
        return user
    elif inp == 2:
        return None
    elif inp == 3:
        exit(0)
    else:
        print("Wrong choice!")
        return None
 
 
def main():
    user = None
 
    print("Welcome to CBCBC flag sharing service!")
    print("You can get the flag free!")
    print("This is super-duper safe from padding oracle attacks,")
    print("because it's using CBC twice!")
    print("=====================================================")
 
    while True:
        if user:
            user = user_menu(user)
        else:
            user = none_menu()
 
 
if __name__ == "__main__":
    main()
 
cs

 

We have a cipher that uses AES-CBC two times. From line 118 we see that padding oracle attacks still work.

If we write out the entire decryption process, we get that $$P_n = D_k(D_k(C_n) \oplus C_{n-1}) \oplus D_k(C_{n-1}) \oplus C_{n-2}$$ where $C_0 = IV_2$ and $C_{-1} = IV_1$. Note that $P_n$ can be easily controlled by $C_{n-2}$.

Therefore, the whole padding oracle attacks work, it's just that we need to change 2 blocks before the targeted block to perform the attack. The remaining parts are straightforward if you have solid understanding of padding oracle attack.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
= remote('167.99.77.49'52171)
# r.interactive()
 
def read_menu(x):
    for _ in range(x):
        r.recvline()
 
read_menu(5)
 
read_menu(3)
r.sendline(b"1")
r.send(b"\n")
r.recvline()
token = r.recvline()
token = b64decode(token)
print(token)
print(len(token))
 
true_ptxt = [0* 80
 
for i in range(6416-16):
    for j in range(016):
        for k in tqdm(range(0256)):
            if i == 64 and j == 0 and k == 0:
                continue
            query_token = token[:i-j-17]
            query_token += bytes([token[i-j-17] ^ k])
            for u in range(j):
                query_token += bytes([token[i-j-16+u] ^ true_ptxt[i-j+16+u] ^ (j+1)])
            query_token += token[i-16:i+16]
            read_menu(3)
            r.sendline(b"2")
            r.sendline(b"abc")
            r.sendline(b64encode(query_token))
            res = r.recvline()
            if b"Check your token again" not in res:
                true_ptxt[i+15-j] = k ^ (j+1)
                break
        print(bytes(true_ptxt))
 
print(bytes(true_ptxt))
cs

 

Swap on Curve

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from params import p, a, b, flag, y
 
= int.from_bytes(flag, "big")
 
assert 0 < x < p
assert 0 < y < p
assert x != y
 
EC = EllipticCurve(GF(p), [a, b])
 
assert EC(x,y)
assert EC(y,x)
 
print("p = {}".format(p))
print("a = {}".format(a))
print("b = {}".format(b))
 
cs

 

Basically we have to solve $$y^2 = x^3 + ax + b, \quad x^2 = y^3 + ay + b$$ which can be done by doing algebra to change it into a one variable polynomial equation, or using resultants to achieve the same goal. I used the latter option, also using what I learned from joseph (https://twitter.com/josep68_) in CryptoHack discord. Sometimes the resultant function on Sagemath doesn't work for some reason I don't fully understand, but you can get around this by using sylvester matrix trickery. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
'''
from sage.matrix.matrix2 import Matrix 
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))
p = 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
a = 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
b = 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
# y^2 = x^3 + ax+b
# x^2 = y^3 + ay+b
POL.<x, y> = PolynomialRing(GF(p))
f = y * y - x * x * x - a * x - b
g = x * x - y * y * y - a * y - b 
res = resultant(f, g, y)
print(res.roots())
'''
 
 
= 10224339405907703092027271021531545025590069329651203467716750905186360905870976608482239954157859974243721027388367833391620238905205324488863654155905507
= 4497571717921592398955060922592201381291364158316041225609739861880668012419104521771916052114951221663782888917019515720822797673629101617287519628798278
= 1147822627440179166862874039888124662334972701778333205963385274435770863246836847305423006003688412952676893584685957117091707234660746455918810395379096
 
# y^2 = x^3 + ax+b
# x^2 = y^3 + ay+b
 
val = [(77010936765396008495452337756562661240243939011172848439081109615157875784261411855101635290874907070056020901709674867604250353250799895482424825163459961), (76777851164357276866499644465822802006538678473475083296658234236620122517398166826857547693953466022605068489266979760977164067377818930943400499575041621), (34181000969577773296415223858746017079573787698084416369226958825797414030997931351865933178274427186538927904848533932096678438894461559467254427322554481)]
 
for a, b in val:
    print(long_to_bytes(a))
cs

 

Two Rabin

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
import random
from Crypto.Util.number import *
from Crypto.Util.Padding import pad
 
from flag import flag
 
= getStrongPrime(512)
= getStrongPrime(512)
= p * q
= getStrongPrime(512)
 
= flag[0:len(flag)//2]
print("flag1_len =",len(m))
 
m1 = bytes_to_long(m)
m2 = bytes_to_long(pad(m,128))
 
assert m1 < n
assert m2 < n
 
c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n
 
print("n =",n)
print("B =",B)
print("c1 =",c1)
print("c2 =",c2)
 
# Harder!
 
= flag[len(flag)//2:]
print("flag2_len =",len(m))
 
m1 = bytes_to_long(m)
m1 <<= ( (128-len(m))*8 )
m1 += random.SystemRandom().getrandbits( (128-len(m))*8 )
 
m2 = bytes_to_long(m)
m2 <<= ( (128-len(m))*8 )
m2 += random.SystemRandom().getrandbits( (128-len(m))*8 )
 
assert m1 < n
assert m2 < n
 
c1 = (m1*(m1+B)) % n
c2 = (m2*(m2+B)) % n
 
print("hard_c1 =",c1)
print("hard_c2 =",c2)
 
 
cs

 

We have two separate problems, each of which needs to be solved to get the flag.

 

For the first problem, there is a known linear relation between the two messages since the pad is not random. Therefore, the two equations given can both be written as a polynomial equation of a single variable, which means that the system can be solved by polynomial GCD or basic algebra as both equations are only quadratic. I chose the latter option for some reason :P

 

For the second problem, the padding is small but they are random. Therefore, we can write the first message as $x$ and the second message as $x+y$ where $y$ is some small value. Since we have two quadratic equations on $x, y$, we can use resultants again to make a polynomial equation on $y$ only. Since $y$ is small, this polynomial equation can be solved via coppersmith's attack. After getting $y$, we now have two quadratic equations where $x$ is the only variable, which can be solved similarly as the first problem. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
flag1_len = 98
= 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
= 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
c1 = 47149257341850631803344907793040624016460864394802627848277699824692112650262968210121452299581667376809654259561510658416826163949830223407035750286554940980726936799838074413937433800942520987785496915219844827204556044437125649495753599550708106983195864758161432571740109614959841908745488347057154186396
c2 = 38096143360064857625836039270668052307251843760085437365614169441559213241186400206703536344838144000472263634954875924378598171294646491844012132284477949793329427432803416979432652621257006572714223359085436237334735438682570204741205174909769464683299442221434350777366303691294099640097749346031264625862
 
flag2_len = 98
hard_c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
hard_c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
 
= PolynomialRing(Zmod(n), 'x')
= P.gen()
 
 
= x * (x + B) - c1
mul = (1 << (8 * (128 - flag1_len)))
cc = bytes_to_long(b"\x1e" * 30)
 
= (mul * x + cc) * (mul * x + cc + B) - c2
= g.monic()
 
= f - g 
cc = h.coefficients()
 
= (int(cc[0]) * inverse(int(n - cc[1]), n)) % n
flag1 = long_to_bytes(m)
 
'''
from sage.matrix.matrix2 import Matrix 
def resultant(f1, f2, var):
    return Matrix.determinant(f1.sylvester_matrix(f2, var))
n = 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003326444660295787578301365987666679013861017982035560204259777436442969488099
B = 12408624070212894491872051808326026233625878902991556747856160971787460076467522269639429595067604541456868927539680514190186916845592948405088662144279471
flag2_len = 98
hard_c1 = 73091191827823774495468908722773206641492423784400072752465168109870542883199959598717050676487545742986091081315652284268136739187215026022065778742525832001516743913783423994796457270286069750481789982702001563824813913547627820131760747156379815528428547155422785084878636818919308472977926622234822351389
hard_c2 = 21303605284622657693928572452692917426184397648451262767916068031147685805357948196368866787751567262515163804299565902544134567172298465831142768549321228087238170761793574794991881327590118848547031077305045920819173332543516073028600540903504720606513570298252979409711977771956104783864344110894347670094
POL.<x, y> = PolynomialRing(Zmod(n))
f = x * (x + B) - hard_c1
g = (x + y) * (x + y + B) - hard_c2
res = resultant(f, g, x)
print(res)
POL.<y> = PolynomialRing(Zmod(n))
h = y^4 + 79890495413921998317755749042148232336863396932303122279875240130974185840791225375990895444267582903006871773965303045933569843994868097491212523442101173551279596449914721209311144221088483103651821516943100935730831208926818636117783500717523025942791406004609937226219367532136778920138824547343785869589*y^2 + 51092857055466673249380987427595244393604870491102664532822637562859699012127822437087645886784256843354629922356917208150074797607882719481678015312190222601448915412917964775219154717370030324105055787501129672958587186322761301111111401381772704665208028130495822463025972061040003730113313298834567354767
print(h.small_roots(X = (1 << 240), beta = 1.0, epsilon = 0.025))''
y_cands = [1637558660573652475698054766420163959191730746581158985657024969935597275, 105663510238670420757255989578978162666434740162415948750279893317701612062865075870926559751210244886747509597507458509604874043682717453885668881354391379276091832437791327382673554621542363370695590872213882821916016679451005257003324807101635213925825667932900258849901826251288979045274120411473033890824]
POL.<x> = PolynomialRing(Zmod(n))
for y in y_cands:
    f = x * (x + B) - hard_c1
    g = (x + y) * (x + y + B) - hard_c2
    h = f - g
    print(h)
    cc = h.coefficients()
    print(cc)
    x = - cc[0] / cc[1]
    print(h(x))
    x = int(x)
    print("result", x)
    print(int(x * (x + B) - hard_c1) % n)
    print(int((x+y)*(x+y+B)-hard_c2) % n)
    break
'''
x1 = 37412309942286574006158913496010620267687663146876352767622106656129986496651165862840203148321069273733293624726376167460944865534151793748073347584719705531628535234167400567407324714477822390166015938266208084466510307154956915004073076813624952897284616411776573796324151099101617608303133521659321079317
x1 = n - B - x1
 
print((x1 * (x1+ B) - hard_c1) % n)
 
 
= x1 >> 240
flag2= long_to_bytes(m)
print(flag2)
 
print(flag1 + flag2)
cs

 

Wonderful Hash

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
import os
import string
from Crypto.Cipher import AES, ARC4, DES
 
BLOCK = 16
 
 
def bxor(a, b):
  res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
  return bytes(res)
 
 
def block_hash(data):
  data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
  data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
  data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
  return data[:-2]
 
 
def hash(data):
  length = len(data)
  if length % BLOCK != 0:
    pad_len = BLOCK - length % BLOCK
    data += bytes([pad_len] * pad_len)
    length += pad_len
  block_cnt = length // BLOCK
  blocks = [data[i * BLOCK:(i + 1* BLOCK] for i in range(block_cnt)]
  res = b"\x00" * BLOCK
  for block in blocks:
    res = bxor(res, block_hash(block))
  return res
 
 
def check(cmd, new_cmd):
  if len(cmd) != len(new_cmd):
    return False
  if hash(cmd) != hash(new_cmd):
    return False
  for c in new_cmd:
    if chr(c) not in string.printable:
      return False
  return True
 
 
cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
       b"our days, some of them have excelent tasks, but in most cases "
       b"they're forgotten just after the CTF finished. We decided to make"
       b" some kind of CTF archive and of course, it'll be too boring to "
       b"have just an archive, so we made a place, where you can get some "
       b"another CTF-related info - current overall Capture The Flag team "
       b"rating, per-team statistics etc'")
 
 
def menu():
  print("[S]tore command")
  print("[E]xecute command")
  print("[F]iles")
  print("[L]eave")
  return input("> ")
 
 
while True:
  choice = menu()
  if choice[0== "S":
    new_cmd = input().encode()
    if check(cmd, new_cmd):
      cmd = new_cmd
    else:
      print("Oops!")
      exit(1)
  elif choice[0== "E":
    os.system(cmd)
  elif choice[0== "F":
    os.system(b"ls")
  elif choice[0== "L":
    break
  else:
    print("Command Unsupported")
    exit(1)
 
cs

 

We require some sort of a hash collision. Since the hash is simply XOR of the hash of each blocks, this problem is equivalent to finding $x_1, x_2, \cdots,  x_k$ given sets $X_1, X_2, \cdots, X_k$ such that the following holds. $$x_i \in X_i, \quad \oplus_{i=1}^k x_i = 0$$ Of course, if $k=2$ this is the well-known birthday problem. 

 

While I'm not sure if this was required for this challenge, this problem has been studied before. It's in the 2002 CRYPTO paper "A Generalized Birthday Problem", and it has been explained by barkingdog in his blog post https://www.secmem.org/blog/2020/08/19/A-Generalized-Birthday-Problem/. Using this, we can solve the problem in $\mathcal{O}(2^{n/(1+\log_2 k)})$. The basic idea is to make a binary tree and solve the problem "partially" (make LSBs zero) as we go upwards. For more details, consult the blog post above or the 2002 paper. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
= remote('wonderful-hash.chal.acsc.asia'10217)
 
for i in range(5):
    print(r.recvline())
ans = b'cat flag        DxriPBQeGgXmjlewgmpxnBnWbfoxGirrLUtUlukpPmjqMOlCBmaOIXXqKIGXoFJsdVGypWXGdXcPScZXFQPbnigusUZZdrxpCyMeGgKGqzJQIzbRqThOJXNgPPNXdPjIOtRhGKBXJDlYDGMfcnyAIojYUJaFyUhzjlsSQHZPasglvQOWIyVoYELtFwJQSsBPsNpvcKZYuKWBrEHwDQLkpCYWkbNIHPTHxbPqrzDgcXCnVvJKeIzkiMKqPhUwDRIe                                                                                                                                                 '
r.sendline("S")
r.sendline(ans)
for i in range(4):
    print(r.recvline())
 
r.sendline("E")
for i in range(10):
    print(r.recvline())
 
## main sol
BLOCK = 16
 
def bxor(a, b):
    res = [c1 ^ c2 for (c1, c2) in zip(a, b)]
    return bytes(res)
 
 
def block_hash(data):
    data = AES.new(data, AES.MODE_ECB).encrypt(b"\x00" * AES.block_size)
    data = ARC4.new(data).encrypt(b"\x00" * DES.key_size)
    data = DES.new(data, DES.MODE_ECB).encrypt(b"\x00" * DES.block_size)
    return data[:-2]
 
 
def hash(data):
    length = len(data)
    if length % BLOCK != 0:
        pad_len = BLOCK - length % BLOCK
        data += bytes([pad_len] * pad_len)
        length += pad_len
    block_cnt = length // BLOCK
    blocks = [data[i * BLOCK:(i + 1* BLOCK] for i in range(block_cnt)]
    res = b"\x00" * BLOCK
    for block in blocks:
        res = bxor(res, block_hash(block))
    return res
 
def get_random_block():
    res = "".join([rand.choice(string.ascii_letters) for _ in range(16)])
    return res.encode()
 
cmd = (b"echo 'There are a lot of Capture The Flag (CTF) competitions in "
       b"our days, some of them have excelent tasks, but in most cases "
       b"they're forgotten just after the CTF finished. We decided to make"
       b" some kind of CTF archive and of course, it'll be too boring to "
       b"have just an archive, so we made a place, where you can get some "
       b"another CTF-related info - current overall Capture The Flag team "
       b"rating, per-team statistics etc'")
 
# 27 
 
print(len(cmd))
 
target = bytes_to_long(hash(cmd))
 
fin_blocks = []
block0 = b"cat flag" + b" " * 8
fin_blocks.append(block0)
 
target ^= bytes_to_long(block_hash(block0))
 
back_blocks = []
for i in range(9):
    back_blocks.append(b" " * 16)
    target ^= bytes_to_long(block_hash(b" "*16))
back_blocks.append(b" ")
target ^= bytes_to_long(block_hash(b" " + bytes([15* 15)))
 
 
# now we need 16 blocks
 
grounds = []
for i in range(16):
    cur = []
    for j in range(6000):
        val = get_random_block()
        cc = block_hash(val)
        cc = bytes_to_long(cc)
        if i == 7:
            cc ^= target
        cur.append([[val], cc])
    grounds.append(cur)
 
def merger(l, r, tot): # merging [l, r) to have tot zeros
    print("WORKING", l, r, tot)
    global grounds
    if l + 1 == r:
        return grounds[l]
    cc1 = merger(l, (l+r)//2, tot - 12)
    cc2 = merger((l+r) // 2, r, tot - 12)
    print(l, (l+r)//2len(cc1))
    print((l+r)//2, r, len(cc2))
    LEFT = {}
    for i in range(len(cc1)):
        res = cc1[i][1] % (1 << tot)
        if res in LEFT.keys():
            arr = LEFT[res]
            arr.append(i)
            LEFT[res] = arr
        else:
            LEFT[res] = [i]
    ret = []
    for i in range(len(cc2)):
        res = cc2[i][1] % (1 << tot)
        if res in LEFT.keys():
            arr = LEFT[res]
            for idx in arr:
                xred = cc1[idx][1] ^ cc2[i][1]
                vals = cc1[idx][0+ cc2[i][0]
                ret.append([vals, xred])
    return ret
 
fin = merger(01648)
print(fin[0])
 
ret = fin[0][0]
 
sol = fin_blocks + ret + back_blocks
 
gogo = b""
for block in sol:
    gogo += block
 
print(gogo)
print(len(gogo))
 
print(hash(gogo))
print(hash(cmd))
cs

 

Share The Flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#!/usr/bin/env python3
import os
import random
import string
 
 
with open('flag.txt''rb'as f:
    FLAG = f.read().strip()
assert FLAG.startswith(b'ACSC{')
assert FLAG.endswith(b'}')
SECRET = FLAG[5:-1]
assert len(SECRET) == 16
 
= 251
 
def random_letters(n):
    return ''.join(random.choices(string.ascii_lowercase, k=n)).encode()
 
print("""\
.----------------.
| Share the flag |
'----------------'
 
Welcome to our flag-sharing service.
We understand some of you couldn't resist sharing flags with others,
but it is STRICTLY PROHIBITED by the rules.
In order to satisfy your desire...
We made the official flag sharing service for you,
with a new algorithm inspired by Shamir Secret Sharing.
 
""")
 
# You'll need at least `threshold` shares to unlock the flag
threshold = 32
 
# Admin holds `len(SECRET) + 1` shares.
nshares = threshold - (len(SECRET) + 1)
 
# Splitting the flag
padding = random_letters(threshold - len(SECRET))
coeff = list(SECRET + padding)
 
xs = bytes(random.sample(range(1, p), k=nshares))
ys = bytes(sum(c * pow(x, i, p) for i, c in enumerate(coeff)) % p for x in xs)
print(f'X: {xs.hex()}')
print(f'Y: {ys.hex()}')
 
cs

 

This will be explained further later when I upload the CVP repository updates. 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
def SVP_oracle(mat):
    M = mat.BKZ(block_size = 30)
    return M
 
def solve(mat, lb, ub):
    num_var  = mat.nrows()
    num_ineq = mat.ncols()
 
    max_element = 0 
    for i in range(num_var):
        for j in range(num_ineq):
            max_element = max(max_element, abs(mat[i, j]))
 
    # sanity checker
    if len(lb) != num_ineq:
        print("Fail: len(lb) != num_ineq")
        return NoneNone 
 
    if len(ub) != num_ineq:
        print("Fail: len(ub) != num_ineq")
        return NoneNone 
 
    for i in range(num_ineq):
        if lb[i] > ub[i]:
            print("Fail: lb[i] > ub[i] at index", i)
            return NoneNone 
 
    if num_var != num_ineq:
        print("Fail: This time, we require num_var = num_ineq")
        return NoneNone
    
    N = (num_var + num_ineq) // 2
    
    # heuristic for number of solutions
    DET = abs(mat.det())
    num_sol = 1
    for i in range(N):
        num_sol *= (ub[i] - lb[i] + 1)
    
    if DET == 0:
        print("Fail: Zero Determinant")
        return NoneNone
    else:
        num_sol //= DET
        # + 1 added in for the sake of not making it zero...
        print("Expected Number of Solutions : ", num_sol + 1)
 
    # recentering + scaling process begins
    max_diff = max([ub[i] - lb[i] for i in range(N)])
    applied_weights = []
 
    for i in range(N):
        ineq_weight = max_diff // (ub[i] - lb[i])
        applied_weights.append(ineq_weight)
        for j in range(N):
            mat[j, i] *= ineq_weight
        lb[i] *= ineq_weight
        ub[i] *= ineq_weight
 
    target = vector([(lb[i] + ub[i]) // 2 for i in range(N)])
 
    embedding = 251
 
    Kannan = Matrix(ZZ, N+1, N+1)
    for i in range(0, N):
        for j in range(0, N):
            Kannan[i, j] = mat[i, j]
        Kannan[i, N] = 0
    for i in range(0, N):
        Kannan[N, i] = target[i]
    Kannan[N, N] = embedding
 
    # SVP time
    result = SVP_oracle(Kannan)
 
    # finding solution
    fin_result = None 
    for i in range(N+1):
        isok = True
        if abs(result[i, N]) != embedding:
            isok = False
        result_vector = result[i]
        if result[i, N] == embedding:
            result_vector = -result_vector
            # now result = actual_vector - target
        for j in range(N):
            if (lb[j] <= result_vector[j] + target[j] <= ub[j]) == False:
                isok = False
        if isok == False:
            continue
        print("Found Vector!!")
        fin_result = result_vector[:N] + target
    
    if fin_result == None:
        print("Fail: could not solve...")
        return NoneNone
    
    return fin_result, applied_weights
 
 
 
# r = remote('share-the-flag.chal.acsc.asia', 37896)
# r.interactive()
 
= 251
= bytes.fromhex("02d4623be12c8f01cb2ebe5f837c1d")
= bytes.fromhex("bbdc06ceb34da7b16336b007dc5492")
X2 = bytes.fromhex("2fb9e753b237e68d35e266b0f01c9e")
Y2 = bytes.fromhex("20c0be9140f5a33d71b9e82f8f9409")
X3 = bytes.fromhex("f42e3ee10edeade0a3804a22e86a63")