Super Guessers won SECCON CTF 2021, with a clean all-solve. I have repeated in this CTF, i.e. won this CTF two years in a row, last year with a strong union of (mostly) Korean cybersecurity professionals. The writeups from last year is at https://rkm0959.tistory.com/165.

This year, there is no collab, only Super Guesser, which is cool :)

Due to some other busy work, I didn't participate fully and solved 3 out of 6 cryptography challenges, and others were done by Baaarkingdog. I also finished one misc challenge, (it was our final solve) but it built on work of many others. (I just finished the challenge)

Challenges were very clean and good, and not very hard (this is usually expected from Japan I think, haha)

## oOoOoO (by kurenaif)

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 import signal from Crypto.Util.number import long_to_bytes, bytes_to_long, getPrime import random from flag import flag   message = b"" for _ in range(128):     message += b"o" if random.getrandbits(1) == 1 else b"O"   M = getPrime(len(message) * 5) S = bytes_to_long(message) % M   print("M =", M) print('S =', S) print('MESSAGE =', message.upper().decode("utf-8"))   signal.alarm(600) ans = input('message =').strip().encode()   if ans == message:     print(flag) else:     print("🧙")   Colored by Color Scripter cs

Thinking about the effect of each "o" or "O" for the value of bytes_to_long(message), we see that this problem is essentially a subset sum problem over modulo $M$. Indeed, the problem is equivalent to solving the system $$\sum_{i=0}^{127} [79^k \text{ or } 111^k] \equiv S \pmod{M}$$ which is same as $$\sum_{i=0}^{127} [79^k \pmod{M} \text{ or } 111^k \pmod{M}] \equiv S \pmod{M}$$ Since the left hand side is between $0$ and $128M$, we can just solve the following for $0 \le c \le 127$. $$\sum_{i=0}^{127} [79^k \pmod{M} \text{ or } 111^k \pmod{M}] = (S \pmod{M}) + cM$$ which is now a standard knapsack problem, and can be solved via CJLOSS 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 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 # https://github.com/jhs7jhs/LLL/tree/master/low-density-attack   def inthroot(a, n):     return a.nth_root(n, truncate_mode=True)[0]   class HighDensityException(Exception):     pass     class CJLOSSAttack:       def __init__(self, array, target_sum, try_on_high_density=False):         self.array = array         self.n = len(self.array)         self.target_sum = target_sum         self.density = self._calc_density()         self.try_on_high_density = try_on_high_density       def _calc_density(self):         return self.n / log(max(self.array), 2)       def _check_ans(self, ans):         calc_sum = sum(map(lambda x: x[0] * x[1], zip(self.array, ans)))         return self.target_sum == calc_sum       def solve(self):         if self.density >= 0.9408 and not self.try_on_high_density:             raise HighDensityException()           # 1. Initialize Lattice         L = Matrix(ZZ, self.n + 1, self.n + 1)         N = inthroot(Integer(self.n), 2) // 2         for i in range(self.n + 1):             for j in range(self.n + 1):                 if j == self.n and i < self.n:                     L[i, j] = 2 * N * self.array[i]                 elif j == self.n:                     L[i, j] = 2 * N * self.target_sum                 elif i == j:                     L[i, j] = 2                 elif i == self.n:                     L[i, j] = 1                 else:                     L[i, j] = 0           # 2. LLL!         B = L.LLL()           # 3. Find answer         for i in range(self.n + 1):             if B[i, self.n] != 0:                 continue               if all(v == -1 or v == 1 for v in B[i][:self.n]):                 ans = [ (-B[i, j] + 1) // 2 for j in range(self.n)]                 if self._check_ans(ans):                     return ans           # Failed to find answer         return None   conn = remote('oooooo.quals.seccon.jp', 8000)   REMOTE = True   if REMOTE:     M = int(conn.recvline().split()[-1])     S = int(conn.recvline().split()[-1])     conn.recvline() else:     message = b""     for _ in range(128):         message += b"o" if rand.getrandbits(1) == 1 else b"O"     print(message)       M = getPrime(len(message) * 5)     S = bytes_to_long(message) % M   base = 0 for i in range(128):     base += 79 * (256 ** i)     sums = ((S - base) * inverse(32, M)) % M   arr = [(256 ** i) % M for i in range(128)] target_sum = sums   st = time.time()   for i in tqdm(range(128)):     attack = CJLOSSAttack(arr, target_sum + i * M, True)     res = attack.solve()     if res != None:         msg = ""         for i in range(128):             if res[i] == 0:                 msg += "O"             else:                 msg += "o"         msg = msg[::-1]         conn.sendline(msg.encode())         print(conn.recvline())     en = time.time()   print(en - st)   Colored by Color Scripter cs

## XXX (by theoremoon)

 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 import os   flag = os.getenv("FLAG", "fake{fakeflag_blahblah}") x = int.from_bytes(flag.encode(), "big")   p = random_prime(1 << int(x.bit_length() * 2.5)) Fp = GF(p)   params = [] while len(params) != 6:     try:         y = randint(2, x)         a = randint(2, p-1)         b = (y^2 - (x^3 + a*x)) % p           EC = EllipticCurve(Fp, [a, b])         EC(x, y)           params.append([a, b])     except ValueError:         pass   print(p) print(params)   Colored by Color Scripter cs

We have 796 bit prime $p$ and around 320 bit $x$, which is the flag.

We are given 6 parameters $(a_i, b_i)$ such that $y_i^2 \equiv x^3 + a_ix + b_i \pmod{p}$ and $y_i < x$.

Subtracting, we see that $$(a_1 - a_j)x + (b_1 - b_j) \equiv y_1^2 - y_j^2 \pmod{p}$$ so $$-2^{640} < (a_1 - a_j) x + (b_1 - b_j) \pmod{p} < 2^{640}$$ which can be rewritten as $$-2^{640} < (a_1 - a_j) x + (b_1 - b_j) + p c_j< 2^{640}$$ for $2 \le j \le 6$. Since we know all $a_j, b_j$ values, the only unknown is $x$ and $c_j$ values, and this can be plugged in my CVP repository.

 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 # Directly taken from rbtree's LLL repository # From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI def Babai_CVP(mat, target):     M = IntegerLattice(mat, lll_reduce=True).reduced_basis     G = M.gram_schmidt()[0]     diff = target     for i in reversed(range(G.nrows())):         diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()     return target - diff     def solve(mat, lb, ub, weight = None):     num_var  = mat.nrows()     num_ineq = mat.ncols()       max_element = 0      for i in range(num_var):         for j in range(num_ineq):             max_element = max(max_element, abs(mat[i, j]))       if weight == None:         weight = num_ineq * max_element       # sanity checker     if len(lb) != num_ineq:         print("Fail: len(lb) != num_ineq")         return       if len(ub) != num_ineq:         print("Fail: len(ub) != num_ineq")         return       for i in range(num_ineq):         if lb[i] > ub[i]:             print("Fail: lb[i] > ub[i] at index", i)             return           # heuristic for number of solutions     DET = 0       if num_var == num_ineq:         DET = abs(mat.det())         num_sol = 1         for i in range(num_ineq):             num_sol *= (ub[i] - lb[i])         if DET == 0:             print("Zero Determinant")         else:             num_sol //= DET             # + 1 added in for the sake of not making it zero...             print("Expected Number of Solutions : ", num_sol + 1)       # scaling process begins     max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])     applied_weights = []       for i in range(num_ineq):         ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])         applied_weights.append(ineq_weight)         for j in range(num_var):             mat[j, i] *= ineq_weight         lb[i] *= ineq_weight         ub[i] *= ineq_weight       # Solve CVP     target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])     result = Babai_CVP(mat, target)       for i in range(num_ineq):         if (lb[i] <= result[i] <= ub[i]) == False:             print("Fail : inequality does not hold after solving")             break              # recover x     fin = None       if DET != 0:         mat = mat.transpose()         fin = mat.solve_right(result)          ## recover your result     return result, applied_weights, fin     p = 238351830708404244219528012300346183698089704036958197073088590986781126046128139277876261847918986388464392075919752504036124478387675086320279831883061575773130731731512289308600548817918823754759741014480607490178191084213685771095081699 params = [[61721446814822499191022412902217320153137633897387846710512310039336410477728264217681745891863200893378034581997664894522756658992873501693353425063400655105194107970249009691442632015429658305792298714043235777934090212343625933540920419, 38215859743437160276358618194105173963536621422404142018824002222927344371846641995139103441786202367296704680389815780441043250270096100089370169391316241550354639472704197195039115443263083720157181161573037786722518518073244876576521645], [193846031065431615171138398907554474490243593010426445660159995023421690918389029501570918601414789147460375901577546434319012002193067152560178159337882412597981169953017381602553449608161376011387225337945790490301205500988070592667260307, 182624605832152240064165962388331595893516884552600324435147374044032575325900262356701606616541732441503871912325334315545721127713601115727804588364391211951651086408749934094159068720206922998283686393892033283362379079277585875317733125], [186116431294956584507622251083552464237708766317037184701883695099192545170797758914491959325056548294443112027689221562090922906211642613451222485059412249593287539268632182815867453113262026976033832305075048778306269837158521655897206104, 188291640755725711120730552161550568363878329035151394705358843149734090074525252662747799270008290175006002913694732659518178709233238519205580102532883270488509830279127451754878651121923932212399426641171488518541036604555898762653636767], [147690737704193380929256042516354642591634312528093128869923487184997632263182669491324548799394778507341925228715095053166787082158079876801508640863174460376667578857398193776134734184654976792585753897823602173550210678811026343180632574, 90919616852165947744756990575400745193091744707583913218090901120971522401412921713920030755420236486444344985420141669115268509030823280811858196495296299291522098961629224878356500400137160049480897176934761512803911650692781199738944358], [147919066213305504909474311411803269104114976277480371373734903513860210330631554119249090143860674441819199276919740940095535099825251133312941478015230935296046855247122689436697731644543102898280018067875178726421332069314230553359546674, 233189046301154960459915044289449599538936202863814191691219472024725663885482828960872087873090796952667099967198895490748125927000604303160065032535117589864975437392352615652017307656160862671237257143553966268386859872891179982158931538], [137450316462129268877711035250763668980618551403674476273480945205694245899369623646082468202341690739837762419221648759226283935459299779254296497766202256170266366890970940886869389464332464546003480305741255956702385666111816886488497002, 42626852637723346847761898432034196330200006970228231831316278507491404141071325164359383210554480496801017672657717855189744860778897395023272448045289999028710960807199386287807443723368642574520040320693565244086076826717435666078357317]]   # x 320 bit   # a1x + b1 + x^3 == y1^2 (mod p)   M = Matrix(ZZ, 6, 6) lb = [0] * 6 ub = [0] * 6 for i in range(1, 6):     dif_a = (params[0][0] - params[i][0]) % p      dif_b = (params[0][1] - params[i][1]) % p      # -2^640 <= dif_a * x + dif_b <= 2^640 mod p     M[0, i - 1] = dif_a      M[i, i - 1] = p     lb[i - 1] = - (1 << 640) - dif_b     ub[i - 1] = (1 << 640) - dif_b M[0, 5] = 1 lb[5] = 0 ub[5] = 1 << 320   result, applied_weights, fin = solve(M, lb, ub)   x = int(fin[0] % p)     print(long_to_bytes(x)) Colored by Color Scripter cs

## Sign Wars

 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 from Crypto.Util.number import bytes_to_long, long_to_bytes from Crypto.Util.Padding import pad import random from secret import msg1, msg2, flag   flag = pad(flag, 96) flag1 = flag[:48] flag2 = flag[48:]   # P-384 Curve p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319 a = -3 b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575 curve = EllipticCurve(GF(p), [a, b]) order = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643 Z_n = GF(order) gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087 gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871 G = curve(gx, gy)   for b in msg1:     assert b >= 0x20 and b <= 0x7f z1 = bytes_to_long(msg1) assert z1 < 2^128   for b in msg2:     assert b >= 0x20 and b <= 0x7f z2 = bytes_to_long(msg2) assert z2 < 2^384   # prequel trilogy def sign_prequel():     d = bytes_to_long(flag1)     sigs = []     for _ in range(80):         # normal ECDSA. all bits of k are unknown.         k1 = random.getrandbits(128)         k2 = z1         k3 = random.getrandbits(128)         k = (k3 << 256) + (k2 << 128) + k1         kG = k*G         r, _ = kG.xy()         r = Z_n(r)         k = Z_n(k)         s = (z1 + r*d) / k         sigs.append((r,s))       return sigs   # original trilogy def sign_original():     d = bytes_to_long(flag2)     sigs = []     for _ in range(3):         # normal ECDSA         k = random.getrandbits(384)         kG = k*G         r, _ = kG.xy()         r = Z_n(r)         k = Z_n(k)         s = (z2 + r*d) / k         sigs.append((r,s))       return sigs     def sign():     sigs1 = sign_prequel()     print(sigs1)     sigs2 = sign_original()     print(sigs2)     if __name__ == "__main__":     sign() Colored by Color Scripter cs

There are two mistakes - one is the insecure random of "prequel" which fixes the middle 128 bits, and the insecure python random which is used in the "original". The natural plan is to attack the "prequel" first using the insecure random via standard LLL, find the python random seed using some library, then directly find the random $k$ values for the "original". The latter part can be done very easily with some libraries, so we'll focus on the first one. We write the system as follows. For each 60 equations, we have $$ks \equiv z_1 + rd \pmod{n}$$ $$k \equiv s^{-1}z_1 + rs^{-1}d \pmod{n}$$ $$k_1 + z_1 \cdot 2^{128} + k_3 \cdot 2^{256} \equiv s^{-1}z_1 + rs^{-1}d \pmod{n}$$ $$0 \le k_1 = z_1(s^{-1} - 2^{128}) + rs^{-1}d - k_3 \cdot 2^{256} \pmod{n} < 2^{128}$$ $$0 \le z_1(s^{-1} - 2^{128}) + rs^{-1}d - k_3 \cdot 2^{256} + cn < 2^{128}$$ and now this can be plugged in CVP repository. Note that $d, z_1$ is fixed and $0 \le z_1 < 2^{128}$, $0 \le k_3 < 2^{128}$.

 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 # Directly taken from rbtree's LLL repository # From https://oddcoder.com/LOL-34c3/, https://hackmd.io/@hakatashi/B1OM7HFVI def Babai_CVP(mat, target):     M = IntegerLattice(mat, lll_reduce=True).reduced_basis     G = M.gram_schmidt()[0]     diff = target     for i in reversed(range(G.nrows())):         diff -=  M[i] * ((diff * G[i]) / (G[i] * G[i])).round()     return target - diff     def solve(mat, lb, ub, weight = None):     num_var  = mat.nrows()     num_ineq = mat.ncols()       max_element = 0      for i in range(num_var):         for j in range(num_ineq):             max_element = max(max_element, abs(mat[i, j]))       if weight == None:         weight = num_ineq * max_element       # sanity checker     if len(lb) != num_ineq:         print("Fail: len(lb) != num_ineq")         return       if len(ub) != num_ineq:         print("Fail: len(ub) != num_ineq")         return       for i in range(num_ineq):         if lb[i] > ub[i]:             print("Fail: lb[i] > ub[i] at index", i)             return           # heuristic for number of solutions     DET = 0       if num_var == num_ineq:         DET = abs(mat.det())         num_sol = 1         for i in range(num_ineq):             num_sol *= (ub[i] - lb[i])         if DET == 0:             print("Zero Determinant")         else:             num_sol //= DET             # + 1 added in for the sake of not making it zero...             print("Expected Number of Solutions : ", num_sol + 1)       # scaling process begins     max_diff = max([ub[i] - lb[i] for i in range(num_ineq)])     applied_weights = []       for i in range(num_ineq):         ineq_weight = weight if lb[i] == ub[i] else max_diff // (ub[i] - lb[i])         applied_weights.append(ineq_weight)         for j in range(num_var):             mat[j, i] *= ineq_weight         lb[i] *= ineq_weight         ub[i] *= ineq_weight       # Solve CVP     target = vector([(lb[i] + ub[i]) // 2 for i in range(num_ineq)])     result = Babai_CVP(mat, target)       for i in range(num_ineq):         if (lb[i] <= result[i] <= ub[i]) == False:             print("Fail : inequality does not hold after solving")             break              # recover x     fin = None       if DET != 0:         mat = mat.transpose()         fin = mat.solve_right(result)          ## recover your result     return result, applied_weights, fin     SIG1 = [(12122920644857436418668108677431446821511965161835906257619686170008223981633617118848536864333256883344783807472533, 14197268540776373741177673820089672023976732299858030846681305575389640921071188098294211283607291412628404706330635), (30023311263693682916692119631904793161812704258670063725046946028381482586508452744969994191586576481159969039892535, 16094000621518284822857020964974522983541224425681758135622160784082988267314022122458996489586892811938506732931748), (20274365333087648992099914855887452427265725062234768121150756210734918282305324594709095440941680006674472249980168, 26128948049631412381227970242480771408976962602375493955244402440727109476811862753343673422200707132102306861245065), (30768939097894626895378677401324579041720728810052060616179712179254924186139940391745214635086621700092451846257475, 23800973758418165064781275855199658315920145808589994209139192398347876290686870300287776343940629270010735723235385), (28473557828088061979399196473136471402585047600303142695341163640729652130707043952255899907766676152597539289628315, 28281625820520087035698954279133768588017050298800453267610958044101108252535161164763310762642756504428205563108030), (961118250385917764507600420510572217848406774402919254807074729943580199634194943936928534369937371624710732726857, 24031640471683802687061395705285266808842836983869848057857017127967668008272515010890509063551366550912420338902834), (19370494654235267454217217719890760732479633443331393690560476118111139682942513564572505092689607226193201989778575, 2433781820944268337733283393291854175920938847482642777771696759267025446311242119383222969981818996711424713151752), (30779090043894032830605276175884042975994811516472755795216312382846355682168692296678880256197033821390044997147420, 4893123418105561169402880287889300261310663472852291300562230045024356786173678817075957809203454759484532173136896), (14643705489977528788970058117566828771249298225825962912655208159781673578193298484890200020885473583280037544119578, 15935318488540400173648065087608623889419958306790544362968141852933585912044021990423536612481693468915965522445032), (26190847735254363003436975683906714419695452818227446664219556609524851687182160032913188662574521358473164521270318, 1593531527201615623099098664942415943763347197253061444470827851943278116759392933621884906245655648264221554908273), (2444983458103763169338770323724579409115782087673217289810500838726321984003897473707801517318376539252731600634354, 31519693975000372684536588360058886155393128374920715958105917368560178529829092541542334254564649031015390295526257), (5539202944379041047645815730619570855915700610921747198866014997007285622810384696777658611658354790466198556409538, 20332957999843652613921660609152489318731466697459198872422541589848932160246010821103577261742306246402279741839395), (29969504934312616092773577215293054327868412131595687908164133237389228991764362661689008330244463167067377417804848, 23502790732595477415220062415069646202303453814634558339724957279860279173977141614843448086419994681526804050994011), (28663099246038192816273570466053103880330161954725039364215397713591731084208919109404788115439838323705057354906183, 32343362746546345028906807296090845637927648209201182279186066312617262402540993950717856425293636562311369826695241), (37811425966842340383821228402925951424928841073943712670686829246012732634532778206829440348798738360996829177934659, 1512161086988707363568355555539355341485927942150807857139424735463213909258176919376930783632168090029799006962452), (6779019396487335250176376177316480940562897505935292947586838966405847326392683369310422331267556304950213385562403, 21277628400501469478914168423023057684740585069176201105893608414023541256985765180901007757435611069875893412465586), (6366948926057872251073324724715646697709396244107534411996999604518484325522941417643164680481781327650121512161589, 31835229197999276237723592037000880402276309404799202930304320555417861589116989270114086456362377584676026798317441), (15281845709607491920369813817013377362178255708702641554534892473368410191641487999506001924287614983557554388444790, 2984115935788221541188290047888309109458147722093547866020985007410124451071701982135991689832422756636714734848410), (17261327950609380032505415413729345506837563477802335104261903199945292046286371909764527605537844250765520460420883, 4414083024903566067346682354660036193755195663970474589205389345245255956774402052618861533800845720100684618788066), (23285217326555475016519552330905568382923977489456237456732496253903350233528472100890947226393609572097915969599580, 15864787645844524123645508552473833769050437498168559566442342764983309617043514215685980718642756051823094216138112), (38735613502207617543460798902089924117030110156904845492417889885452926231509412677457364662728826603870166089048783, 2764799580566369130997255183073579096790304637375189258729225097121531798414933779603126159724061297478107963529944), (34397686468933908386713398593117199247477408535310063872486364205758893481567076156685158122992765644664863620408441, 32278070177934959080616216483052122171696315094028362684579162316990518944414668141213923548802330689237360305444057), (36888596144580310076666982554379754727579693141157953039821763246320596624002076072694376360349327605151628461938344, 20359599307803961599163637268447617008934461534173375543520973121462531279483793982707344429872033956688432496029494), (35731945369165024527067708422190934453114426930189147171662677061124488912009487138831725596607769036223677431254394, 38690463610329621441610277699868091296837875356478232771729649752351130839647804626642276143604085382240751091874980), (23677628634176723569940322462564200990434883563619558260828733247431579872437268289228719660272457754577432647629267, 5694960089075991074464290708570332306998548315951489339220678741537951501152608587055469175810163056202380723484162), (36183304484234246866110911449167537754372333309427114844147387618829024530231991189605158113348204109845980352696465, 23965168344478037213105641624609514777278543321778037076016154890855496855531577133265749426868642365368798849451496), (33162978581198415974999091637775219015609843478885981431365405627376986149964493390352996432902431398214990453120700, 17522675770165519045405383886383499046920674272323023864859028070652034097791735019059447013185908178315975726718027), (37977524287531621731269652998518444039221788561001084681446374543680582455529006667074181965831283556770601026406412, 34014871750340380154692206012455554620218508761966344769331999972401940089831171697348255247018267326994810496665301), (1507013781859412581460229968016871686472000162722420853292672399595213588246897578540619347856535893357627270900677, 7123198841569413454577310078272821534024280579100722414329202844057424863366193509058084349838170744321137899380851), (16162098325755207229063189997383396611921725235544867443071126936768120496007100174087010708793986788501933456531117, 35843125491563878831891747420494968566047358046579202101829199006631647636438358745741154644883785641557638179703196), (27146246587667190740076698462480327352334872042637035686499133830505424921309618795732649623443166432157485441206513, 29374852723618836996041990307719900335299612538156861129617267376582701400599574166091116228943846822827095705431420), (20318873596559259511055531147506382540328039101211632617939893607230146992770755366357547004154440123877927279562805, 21880244506505391597381900288791130929029500377960791610120410522262499720103003893165761379437860585723438454338357), (2677089679217144714677235060642211123498261589343453643587089980258267670810054471717380695130400677765718942750715, 22811216118007709181671732510261424038689262085998138698823325592895788252084744051591190795979078528619437443272430), (28242261012068041277293540110291951864968606243755362285072828317158908834811289543798540567848975185502994215611619, 28337300861435742639020944587343125537033416178222051556584188414720653042082343068603170738957875834942311839398955), (21313784566242236288558209540398728358450102518073033970974355085249250643681779922552823541265620185702575612865123, 25973923581441774490467725510310356393118571760442289368631380634139185801852675014798484820655377425355874214608838), (3972247474338783322467875314927935482812576258324764658865475177091575186850519760736477068863287011253657979695035, 1949243324150001215851803463575673078965313534368782887187770074096642168523503805499517384914614086023503127806847), (1151944487736036555640946065337093366220353301888076465796765130037778971904962274932934887966419998200175365995781, 19564575441055199178132952897543045993451659948447588920651596150288550414960098453945167530353880987093029030638144), (34162335734397557091228494111777449419659314364130585745202913773828419992559542465196157154618586692393424347136785, 34816069361672535828713924897177961374080352312052306803897119805834580104455380505473277752161016451540002438069017), (6214420518977400720115040915606936189332457649954029722703185627542783153439822172938794340141280694328697860997151, 35036609860976357406366810820445499231048373436931375253989834911997779342195269560660560149275988782146654615055395), (17932296848485476028307829364900722350664622103067434376880482465660776884118027615894824834062520974562950696190800, 25284454559391441356742861992714899157880349238554132025565451660342323497911181209889041052025003714876311648649308), (16729838562359475474212958363183560420250559702291016364521051500450026103395443198630456476103970943753669154249375, 32346909821898954875794104426207252965578694675212598600013619876939291316966520281348030524571180602992351937324549), (18383357524600760202019477696462766408564829389632201092711392752822975200725339011191785469174324590811632757501470, 36650204800420829652120261290123142229312040551658496656556239024215868372978503733453573308931372634821353503537954), (12679474326846184225965528024726547768506690550379875402442700592477187625032566343282886015393973299453970347716666, 31594434445787142355786158780673084733603186104893515951267587710628733125154787164728421585888101421671404571441460), (1460155946173513465605000753006943939473815980031454177632679861455928714118380298806901823644725063756743440478323, 28595065903087426074566358753005915622433302916683368431103530322432724436087166807363512661383021500064699866636573), (1712191697812545578149205758294464160112058894608923583568724616471266315677289849142337215940784518880963429394123, 15549321728923260877275319522523938368845573355479005888471636555747793775030205015093656278438688710952666664504896), (27247850567913925982695067834491518101584714379758703325384826250084810338850873054903173768682909886315224820151843, 18441987213600418235028717811172592400392968984874201495657937932256496057636260779718506455774046512049959224326533), (23125206105423712170494578086460408200155706950388584751758217770641881139847092343076320949651253557057860975699290, 617384558916714490913646402391877958626488085682864653677413549966260928717156654411337297014822767990795093863229), (10309859796084513086949474325745742289943652601164042295798749216013816749262406978527658506169631041432182034483264, 3401470346181096624340649421457463749621102267436616681750603386976006189520143441710738979453350404845158395485486), (16368609105601996512123657503983976901814846135585476552914466414979175179581723778823773810904335136988607343388641, 12887327683770298631686858909410191002874101297863064763857850276211374735131663350575035482893318627486961140493060), (12597783086712780955829102511325977339556480314456317226084059427852975744410298400466570369739729859822682094743763, 18143629657739573817392351951162537846408025200449845703036545707816887229856135678162116712273281752461460773286157), (18149765203212365095922365541429595804115110638460797557247425663278065057761683694963435074306083146559748910820933, 4623808735710466757897562443056494514986872251154643072124080945722371896930429940197336707416267350592331887509370), (36685770489292450862829854673422281288659959443468144451918042753101522158121942740628396053876144087903556902670459, 25427602196870003078247382997147130945403862270376348600679340464766087619183853473530884327535652383782148396318369), (26400994935887323685812785588779777604807033818459784383379336636723016041989131355813709350621150638600337397745755, 35441443644761879722810537983899640132591168390041946180094287752185744760148684344825560100034902852843703022913572), (21549464322285949487974060839290414317291085580470644413175603703659811599686802128539665387707492575120952990974169, 27426668476821276280862019979056999027369355304092859933896625743859680072036382523929860072977660288769061968841056), (17945055270149004672174407200101186426733019188557222629374387229166321253248131455944582958258851086680992327717775, 22763432714358352994467634787642451136567944768237186044385733037319457391071748311079692136983455628393624590912773), (19679372898006128640291583077178951435604248960537272688952385068434563933226836358777706619530975918926211454093254, 22558450199634522395989325930989798822306499440080795289426594476903491433232767149595712438138190142613146382805102), (5053808002622613648696016012235196453213394765089545993472533920762659290879000238284401142373566610359754334503119, 25596265678131212259962460250737224350948937567171043241527736952385125964273084970352617767438577469728391374901104), (35021535942876477664620323193569084612777266590551110729944867045139787961246598034847607119451282633173220627617528, 24412900363309066203864154425415165066253353692376637520978763141267068333052991517573772819303004361631432100082761), (30382344157317014521174359938595199590313101376532894077961655976102849666994412986977757526700903573837979050569748, 36380054077835016119489703494179753668737802402599719907220000486624011084909818429478518718710302969894134810399414), (23392455319924374624407363218414017792726341637348154289368001919553092631539423722056128035028761955761251335231397, 24615969593765671009089175669046441351199855489516238368580612855661905474214253402259306074086838224100682009493110), (39043410087571658849777088723644840444773112471772958075589595817236649732325361138357268471190048890890922330173113, 24256166337102519478716198099822063504670413826816008063467295625641151486658627000887001654580846329391802379723304), (25198309246276017483121163348865597630643532403493815715878126594393814779012937502862557889192295110821475991529943, 31183736084868762605705341491981967451872193027043779034558377529784073696083378450370565887268611112401715464692322), (21490370993563026264971775993182460905215869236047670304210535706894812928914407971234995821500730800223031598266257, 30524538483293986209920139400952501355824771895617776073345360374702907548949007510552008565834914052456239691889902), (37366673614850776444692939328421732388527123695286819437966655615675408069366910860035074204029318799945903064048527, 17779215295739572760353458898043288811931339150166396214780752407992014275252723707803456409767620788479105600423376), (23880907135038389168803046756901468214206189168117058906553768830712533102670877117203361468021971439264847643087559, 36554798683087533081747521419888907675190192122029480300791517998074362122003489313160167552894436296245959628579534), (1839816617790796393877679129129689526692744195784843313918019394276687774692559082426410650970115204065124516740192, 33280887100325540541044876347841631022975706016854603366960877001893277240119020663116400162762880357011028194015505), (37860238532878533314237881709991803144640720532159211259802653676233680439794809051955788290617724291896314228484287, 2079530852252634619529204167324028013909690544367420298080750988365566999876311319237386168370876748621061304030325), (33076401294910426866408725898185517353797089714631638085904654063741185770239407827102674966897738352568845852795461, 32388782563029207071708238813265723145823101733798639269010838632868478704546695027802504168693070745244529700498871), (19664630416995907039268499340971147354543906991316471257330973370399289180202716179184726176333997501833047008445188, 15010332454096306874561434765152776137424843532232617982537812287828972466131420109345949260515569323587248864746943), (25871769372685370569925822425693820620619794598214474123600511253778185796962172073208206762818745309605540739100621, 12733332659612677892428319839726866498876500931386736309794894873372522229292842342178191364595143966422220824826073), (12769045455084894273436527159204816902432305644017210629296787933904295785281457448881044929402038399496940189044093, 11594689177180251431669445510565369712938818714831055440921516382728285369019679675944135089038247905820859659761517), (1865703770871313754195006900013207845562542245675070113698481870088723236246390202799490489472079377268354306242668, 5125550573798542551697831171912361478992101952449490976854228951650529010822626202419835861052330070344633285976669), (37096662612327463148937337171394483039720908237996642157433470567568444060739072904671016601404440533704833919544285, 4790007747398249736115034551686542360219836448905259482276520130644298771477774260329772071196479778643314968168876), (31170630741028077467666117690922124046397732731173001565911078911132891410318903435039074418130660922292175028485161, 36700267333965429842826985729957565986107482356086995641315664499740118242353501066703906197210995388334971341587044), (16429305562010070045918008502995674904932019310071872766389089174936173832847431470110417157600205840910967654695105, 13348678473612360711357762565221644167552517488898971900250507563637477504294039445796012121832852740292220571524010), (36814999620410624650408927593101102311832288601200212772521220280747373268407838162653769833122342138193850888479316, 21678377395564601107395386759737337329969405189315349034054067649380849056748928922052454754064625128419150919292053), (37080204662579811419723925250553811343118062800721020347850990442377486549932418090303179252403198539322519694444276, 15821341762768738218228176979267566826815656142437698746345759451195866137662375460664107143767858376489559348158119), (31900665212807794653067892050991087787174739879112603157270515722601016232361976337248279931832041244757837789022461, 11910037530034363325480855721128870881334951395240192762039726365170413466292618778748338552446589898886095541743053), (22713234938446144853039935121713734891074107932043602957345904095128407091303028830418630224869359322276067322228220, 37648033797699949313050109414984677478246381964295991074283362304879984221990727828373537248000765921622593274507531), (26966642227721045071442724645484661519368889576738311756067876287666319883156972945382104473351822669036919304411830, 33837552398136675647634120649336283866568054003022435569393484219100126804419072284913749466938666527692475735307495)] SIG2 = [(1049639883029709557497416807885448950887522866921671928450292553333188509467250311602354191758381412870243165308138, 34790284668131148498252310249426530965492667679223859021102993403672099203069041205214172414075756555276490789178956), (3085218467051892206002417901865728576393577451338770207618129262272350718747277968031614020531383301753358875936613, 35069145156217342955289020258826302551823920792084376060949622353808056721610402437441970841628302496074418474626297), (24094905265337534276165828047859782238987431219303883218554480297297861668847922558928617159973811943649844468445020, 9328776074819457901331657355801560516363178058099225535915537394781684440774078985119798155365962514386879323530606)]     p = 39402006196394479212279040100143613805079739270465446667948293404245721771496870329047266088258938001861606973112319 a = -3 b = 27580193559959705877849011840389048093056905856361568521428707301988689241309860865136260764883745107765439761230575 curve = EllipticCurve(GF(p), [a, b]) n = 39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643 Z_n = GF(n) gx = 26247035095799689268623156744566981891852923491109213387815615900925518854738050089022388053975719786650872476732087 gy = 8325710961489029985546751289520108179287853048861315594709205902480503199884419224438643760392947333078086511627871 G = curve(gx, gy)   # ks == z1 + r * d mod n # (k1 + z1 * 2^128 + k3 * 2^256)s == z1 + r * d mod n # k1 + z1 * 2^128 + k3 * 2^256 == s^-1 (z1 + r * d) mod n # k1 + z1 * (2^128 - s^-1) + k3 * 2^256 - s^-1 r d == 0 mod n # -2^128 <= z1 * (2^128 - s^-1) + k3 * 2^256 - s^-1 r d mod n <= 0   num_sig = 20 M = Matrix(ZZ, 2 * num_sig + 2, 2 * num_sig + 2) lb = [0] * (2 * num_sig + 2) ub = [0] * (2 * num_sig + 2)   for i in range(num_sig):     r, s = SIG1[i]     M[0, i] = ((1 << 128) - inverse(s, n)) % n      M[1, i] = (- r * inverse(s, n)) % n      M[2 + i, i] = 1 << 256     M[2 + num_sig + i, i] = n      lb[i] = - (1 << 128)     ub[i] = - 1   for i in range(num_sig):     M[2 + i, num_sig + i] = 1     lb[num_sig + i] = 1     ub[num_sig + i] = 1 << 128   M[0, 2 * num_sig] = 1 lb[2 * num_sig] = 1 ub[2 * num_sig] = 1 << 128   M[1, 2 * num_sig + 1] = 1 lb[2 * num_sig + 1] = 1 ub[2 * num_sig + 1] = n    result, applied_weights, fin = solve(M, lb, ub) flag1 = long_to_bytes(int(fin[1] % n)) z1 = int(fin[0] % n) d = int(fin[1] % n)   predictor = MT19937Predictor()   for i in range(80):     r, s = SIG1[i]     k = ((z1 + r * d) * inverse(s, n)) % n     k1 = k & ((1 << 128) - 1)     predictor.setrandbits(k1, 128)     k3 = k >> 256     predictor.setrandbits(k3, 128)   ks = [] for i in range(3):     ks.append(predictor.getrandbits(384))   d2 = ((ks[1] * SIG2[1][1] - ks[0] * SIG2[0][1]) * inverse(SIG2[1][0] - SIG2[0][0], n)) % n    flag2 = long_to_bytes(int(d2))   print(flag1 + flag2) Colored by Color Scripter cs

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

 SECCON CTF 2021 Writeups  (0) 2021.12.14 2021.11.22 2021.10.13 2021.10.03 2021.09.26 2021.09.26

Super Guesser played N1CTF and got 1st place, also giving us a good amount of CTFtime points.

### checkin

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 from Crypto.Util.number import * from secret import flag   p = getPrime(512) q = getPrime(512) n = p*q x = 2021*p+1120*q h = (inverse(x,n)+x)%n e = 65537 c = pow(bytes_to_long(flag), e, n)   print('n =', n) print('c =', c) print('h =', h) print('p0 =', p >> 490)   # n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793 # c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833 # h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806 # p0 = 4055618   Colored by Color Scripter cs

There must be a more efficient solution, but here's a solution that took around 5 hours.

From $p_0$, we get a range of $p$. From this range, we can calculate the possible range of $x$. After simple calculation, we see that $$L \le x \le R$$ where $R-L < 2^{501}$. Now since we know the equation $$x^2 - hx + 1 \equiv 0 \pmod{n}$$ we can use Coppersmith's attack with $\epsilon = 0.01$. This gives a solution that requires LLL algorithm on a matrix of size 100 x 102, taking 5 hours to run. After finding $x$, we can calculate $p, q$ with quadratic equations. Interested in a faster solution.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 def inthroot(a, n):     return a.nth_root(n, truncate_mode=True)[0]      set_verbose(2)   n = 124592923216765837982528839202733339713655242872717311800329884147642320435241014134533341888832955643881019336863843062120984698416851559736918389766033534214383285754683751490292848191235308958825702189602212123282858416891155764271492033289942894367802529296453904254165606918649570613530838932164490341793 c = 119279592136391518960778700178474826421062018379899342254406783670889432182616590099071219538938202395671695005539485982613862823970622126945808954842683496637377151180225469409261800869161467402364879561554585345399947589618235872378329510108345004513054262809629917083343715270605155751457391599728436117833 h = 115812446451372389307840774747986196103012628652193338630796109042038320397499948364970459686079508388755154855414919871257982157430015224489195284512204803276307238226421244647463550637321174259849701618681565567468929295822889537962306471780258801529979716298619553323655541002084406217484482271693997457806 p0 = 4055618   p_left = p0 << 490 p_right = (p0 + 1) << 490   xleft = 2021 * p_left + 1120 * (n // p_left) xright = 2021 * p_right + 1120 * (n // p_right)   dif = xright - xleft   POL = PolynomialRing(Zmod(n), 'x') x = POL.gen()   f = (xleft + x) ** 2 - (xleft + x) * h + 1    # print(f.small_roots(X = dif, beta = 1.0, epsilon = 0.01)) # 2912576656137471917598083572790822084936420051386777204728781209115923077150356900578287157481616426957057687378386181070414819714103076914618075908917   x = xleft + 2912576656137471917598083572790822084936420051386777204728781209115923077150356900578287157481616426957057687378386181070414819714103076914618075908917   # 2021*p+1120*q = x # 2021p^2 + 1120n = px    p = (x + inthroot(Integer(x * x - 4 * 2021 * 1120 * n), 2)) // (2 * 2021) q = n // p    phi = (p - 1) * (q - 1) d = inverse(65537, phi)   m = pow(c, int(d), n)   print(long_to_bytes(m)) Colored by Color Scripter cs

### n1ogin

 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 import os import json import time   from Crypto.PublicKey.RSA import import_key from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes from cryptography.hazmat.primitives import hashes, hmac   from secret import FLAG, SALT     # generated by openssl genrsa -out n1ogin.pem 2048 PRIV_KEY = import_key(open("n1ogin.pem", "r").read())   # nonce for replay attack Nonces = set()     def cal_password_hash(password):     hash = password.encode() + SALT     for _ in range(7777):    # enhanced secure         digest = hashes.Hash(hashes.MD5())         digest.update(hash)         hash = digest.finalize()     return hash   def RSA_decrypt(rsa_data):     cc = int.from_bytes(rsa_data, 'big')     mm = pow(cc, PRIV_KEY.d, PRIV_KEY.n)     message = mm.to_bytes(2048//8, 'big')       if check_PKCS1(message):         payload = message[-48:]     else:         # To prevent Bleichenbacher's attack, we continue with random bytes         # when the PKCS1 check is not passed         payload = os.urandom(48)     return payload   def check_PKCS1(message):     # message: 0x00 || 0x02 || padding string || 0x00 || (48 bytes) payload     ok = all([         message[0] == 0x00,         message[1] == 0x02,         all(byte != 0x00 for byte in message[2:-49]),         message[-49] == 0x00     ])     return ok   def check_time(timestamp):     return abs(int(time.time()) - timestamp) < 30   def check_nonce(nonce):     if nonce in Nonces:         return False     Nonces.add(nonce)     return True   def AES_decrypt(key, enc_data):     # key: aes_key || hmac_key     aes_key = key[:24]     hmac_key = key[24:]     # enc_data: iv || cipher || mac     iv, cipher, mac = enc_data[:16], enc_data[16:-16], enc_data[-16:]       aes = Cipher(algorithms.AES(aes_key), modes.CBC(iv))     decryptor = aes.decryptor()     data = decryptor.update(cipher) + decryptor.finalize()       # check padding     data = unpad(data)     if not data:         return None, "padding error"       # check hmac     cal_mac = iv + cipher     for _ in range(7777):    # enhanced secure         h = hmac.HMAC(hmac_key, hashes.MD5())         h.update(cal_mac)         cal_mac = h.finalize()     if cal_mac != mac:         return None, "hmac error"       return data, None   def pad(pt):     pad_length = 16 - len(pt)%16     pt += bytes([pad_length]) * pad_length     return pt   def unpad(ct):     pad_length = ct[-1]     if pad(ct[:-pad_length]) == ct:         return ct[:-pad_length]     else:         return None   def login(username, password):     if username not in Users or Users[username] != cal_password_hash(password):         print("login failed...")         return     print(f"{username} login ok!")     echo_shell(username)   def register(username, password):     if username in Users or len(username) > 20:         print("register failed...")     else:         Users[username] = cal_password_hash(password)         print(f"{username} register ok!")   def echo_shell(username):     while True:         command = input(f"{username}@local> ")         if username == "admin" and command == "flag":             print(FLAG)         elif command == "exit":             exit(0)         else:             print(command)   def handle(envelope):     try:         envelope_json = json.loads(envelope)           key = RSA_decrypt(bytes.fromhex(envelope_json["rsa_data"]))         content, err = AES_decrypt(key, bytes.fromhex(envelope_json["aes_data"]))         if err:             print("Error!")             return           content = json.loads(content)         # check nonce         if not check_nonce(content["nonce"]):             print("Error!")             return         # check time         if not check_time(content["timestamp"]):             print("Error!")             return         # handle login/register         choice = content["choice"]         if choice == "login":             login(content["username"], content["password"])         elif choice == "register":             register(content["username"], content["password"])         else:             print("Error!")       except Exception as e:         print("Error!")     Users = {     # username:password_hash     "admin": "REACTED",  # admin password obeys the strong password policy     "guest": cal_password_hash("guest") }     def main():     print("Welcome to the n1ogin system!")     while True:         envelope = input("> ")         handle(envelope)   if __name__ == "__main__":     main()   Colored by Color Scripter cs

The data (aes/rsa data) that the admin sent is given in a pcap file. The client file is also given to make lives easier.

In the cryptography world, there are a bunch of attacks that involve exploiting error messages. For example, there are padding oracle attack and Bleichenbacher's attack. There are a bunch of errors in this challenge as well, but Bleichenbacher's attack is guarded as PKCS padding error is simply ignored by taking some random bytes as the unpadded result.

It seems that the same goes for the padding check and HMAC check - there are a bunch of errors possible in the AES decryption (and content verification) but all of them simply return "Error!" making it hard to see which error was actually thrown. If we could decide whether AES padding was the issue, we could easily use padding oracle attack to recover the admin password, giving us the flag.

How can we achieve this goal? If we look at lines 71-84, the padding error is checked first, then the HMAC error. If padding error was found, then the server skips the HMAC computation. Because the HMAC function was applied 7777 times, that HMAC computation takes a significant amount of time, around 0.1 seconds. This means that with a stable server, we can decide whether or not padding error was found via timing attack. This solves the challenge :) To make the exploit more stable, I timed everything 5 times and took the median.

 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 admin_data = {"rsa_data": "391b06a1740b8c9cf1c8d2bb66ba5b191caa8534b4be18c22ce81069658dd2cd3ca3a8d1a3fc8dfab4b68a6b076bf89be807404e0a98dd1bf9daaf8ba34e0556131d3e56cae61c0302d24a177481209e82de7ecf91c2fe66aa39162d7af9c2fdabaf0c444badfc6b82b071fda8e3b26d4d3e57dba25c36298601ae0153c73b7469c472ac4702531c38849772e7c6e24313e6eb7def64a7bec1c21150c1fded52b3ca716d4444b4d75836dff8c92a371f6256ee7a48034f6d5ea949d982f9f05c04d3d7cce10bd11b806cc02088b42fa0cb069390700fb586287ba224ea0b210ebd0479a4f1d2ef5f914bcc861125b7d8d714cf0feecb515c1b1ef869e91ca179", "aes_data": "1709bf9489f6df6dc31491cee4711f7a2a3e050f1ed3e9772442e8a8483e341313713383dd31fbf0133d55e977b8edf54ba832002ee4ee52da32c260b083a35b01626201c36dad6fca7b2be2aa03d90bf5c9a601a24149f55cdcd39f0bf6a032bfabeebee5259a21e188f5c5f8776cd9d7c072054781169174bddbc390e6da21bd7b85f76c93f48914fb1958ac89e464511d9a17fb2174aab825cb13eb3f0dfa"}     conn = remote("43.155.59.224", 7777) conn.readline()     PUB_KEY = import_key(open("n1ogin.pub", "r").read())   def send_data(data):     envelope = json.dumps(data)     st = time.time()     conn.sendlineafter(b"> ", envelope.encode())     res = conn.recvline().decode()     en = time.time()     return en - st   aesdata = bytes.fromhex(admin_data["aes_data"]) iv, cipher, mac = aesdata[:16], aesdata[16:-16], aesdata[-16:] res = iv + cipher      conn.sendline(b"asdf") conn.recvline()   true_ptxt = [0] * (len(res))   for i in range(len(res), 16, -16):     for j in range(0, 16):         tt = []         sol = -1         record = 0         for k in tqdm(range(256)):             if i == len(res) and j == 0 and k == 0:                 continue             if (k ^ (j + 1)) > 128:                 continue             query_token = res[:i-j-17]             query_token += bytes([res[i-j-17] ^ k])             for u in range(j):                 query_token += bytes([res[i-j-16+u] ^ true_ptxt[i-j+u] ^ (j+1)])             query_token += res[i-16:i]             # print(query_token)             query_token += os.urandom(16)             tot = []             for _ in range(5):                 dat = {                     "rsa_data" : admin_data["rsa_data"],                     "aes_data" : query_token.hex()                 }                 spent = send_data(dat)                 tot.append(spent)             tot.sort()             tot = tot[2]             tt.append((tot, chr(k ^ (j+1))))             if tot > record:                 sol = k                 record = tot         tt.sort()         print(tt[-7:])         true_ptxt[i-j-1] = sol ^ (j + 1)         print(bytes(true_ptxt)) Colored by Color Scripter cs

### n1token1

 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 from Crypto.Util.number import * import random from secret import flag   def gettoken(c):     X = 0     while ((pow(X, (p-1)//2, p)!=1) or (pow(X, (q-1)//2, q)!=1)):         X = 1         while X.bit_length() < 920:             X *= random.choice(primes)     xp = pow(X, (p + 1)//4, p)     xq = pow(X, (q + 1)//4, q)     xp = random.choice([xp,-xp%p])     xq = random.choice([xq,-xq%q])     x = c * (xp*inverse(q,p)*q + xq*inverse(p,q)*p) % n     return x   def getmyPrime(nbits):     p = getPrime(nbits)     while(p%4==1):         p = getPrime(nbits)     return p   primes = random.sample(sieve_base, 920) p = getmyPrime(512) q = getmyPrime(512) e = 65537 n = p*q c = pow(bytes_to_long(flag), e, n)   with open("output.txt", "w")as f:     f.write("n = " + str(n) + "\n")     for i in range(920):         f.write("Token #"+str(i+1)+': '+str(gettoken(c))+'\n')     Colored by Color Scripter cs

We have 1024 bit modulus $n$ and 920 tokens. To calculate the tokens, the following procedure took place.

• select 920 distinct small primes and store it in an array (this array is fixed)
• compute some product of these small primes which is just over 920 bits long and is a QR modulo $n$
• compute the square root of this value and multiply $c$ to it

We have to compute $c$ and also factorize $n$ from these data.

#### Step 1 : Computing $c^2$.

Denote the token as $t$ and the selected product of primes as $X$. We have $$t \equiv c \cdot \sqrt{X} \pmod{n} \implies t^2 \equiv c^2 \cdot X \pmod{n} \implies X \equiv t^2 c^{-2} \pmod{n}$$ Note that $n$ is 1024 bits and $X$ is less than 930 bits. Now this is just a hidden number problem, so LLL can solve it.

Thanks to barkingdog for thinking of this idea and computing $c^2$! I had the idea for Step 2, but couldn't think of this.

#### Step 2 : Computing $c$ and Factorizing $n$.

Since we know $c^2 \pmod{n}$, we can now compute all $X$ values corresponding to each tokens.

We can now easily factorize these values, as they are smooth. Consider the prime factorization of $X$.

$X$ is composed of prime factors that belong to the fixed set of 920 prime factors.

If we consider only the parity of each exponent in the prime factorization, we can regard each number as a binary vector of length 920.

Since there are 920 vectors of length 920 over $\mathbb{F}_2$, it's tempting to look for kernels. Indeed, if we find a nontrivial kernel, we can multiply all equations corresponding to the kernel - and since the product of $X$'s will be a square, we can get some interesting results.

For example, if there are $l$ tokens such that the product of their $X$'s is a square, we get $$\prod t^2 \equiv c^{2l} \cdot \prod X \pmod{n} \implies \prod t \equiv c^l \cdot \sqrt{\prod X} \cdot \text{(some square root of 1)} \pmod{n}$$

If $l$ is odd, we can get a candidate of $c$ that agrees with the found value of $c^2 \pmod{n}$.

If $l$ is even, we can get some square root of 1. If this is $1$ or $-1$, we are out of luck. If not, we can factorize $n$ with GCD.

If turns out the the kernel is of dimension 2, one with $l$ odd and one with $l$ even. We are lucky on the $l$ even case as well.

 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 from Crypto.Cipher import AES, PKCS1_OAEP, PKCS1_v1_5 from Crypto.PublicKey import RSA from Crypto.Util.Padding import pad, unpad from Crypto.Util import Counter from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long, isPrime, getPrime, getRandomRange, sieve_base from tqdm import tqdm from pwn import * from sage.all import * import gmpy2, pickle, itertools, sys, json, hashlib, os, math, time, base64, binascii, string, re, struct, datetime, subprocess import numpy as np import random as rand import multiprocessing as mp from base64 import b64encode, b64decode from sage.modules.free_module_integer import IntegerLattice from Crypto.Hash import SHA3_256, HMAC, BLAKE2s from Crypto.Cipher import AES, ARC4, DES   def inthroot(a, n):     return a.nth_root(n, truncate_mode=True)[0]   fr = open("output.txt", "r") n = int(fr.readline()[4:])   tokens = [int(fr.readline().split(": ")[1]) for _ in range(920)] xsq = [pow(x, 2, n) for x in tokens]   # obtained via LLL, thanks BarkingDog! ''' SZ = 50   M = [[0]*SZ for _ in range(SZ+1)]   for i in range(SZ):   M[0][i] = xsq[i]   for i in range(SZ):   M[i+1][i] = n   M = matrix(ZZ, M)   T = M.LLL()   print(T[1])   for i in range(SZ):     v = T[1][i]     A = v * pow(xsq[i],-1,n) % n     print(A)   csqinv = 52983076548811446642078416561526103296256117483454486324354864860934507167817419284299797979785979560318778718382121118437029467788929084290109421055494194638653398930615132561955251638059730256502250470596999508030459148548384745026728889238876530368915312995370308785841757845456662731412090368303339076885 csq = inverse(csqinv, n)   print(csq) '''   csq = 45826812852445545573935979277992443457076371872089648644915475778319093098825670699151487782654163657210516482531915639455166133358119343973980849423144111072114848219032243215219360482938562035117641611780636775341778802057146053472950017702818869239750207365020007621660815809140827723451995480125236607450 csqinv = 52983076548811446642078416561526103296256117483454486324354864860934507167817419284299797979785979560318778718382121118437029467788929084290109421055494194638653398930615132561955251638059730256502250470596999508030459148548384745026728889238876530368915312995370308785841757845456662731412090368303339076885   X = [v * csqinv % n for v in xsq] primes = [] for p in sieve_base:     for x in X:         if x % p == 0:             primes.append(p)             break   SZ = 920 mat = [[0] * SZ for _ in range(SZ)] # mat[i][j] : number of factor primes[i] in X[j]   for i in range(920):     v = X[i]     for j in range(920):         while v % primes[j] == 0:             v //= primes[j]             mat[j][i] += 1      M = Matrix(GF(2), mat) basis_ = M.right_kernel().basis()   # Part 1 : find c xmult = Integer(1) Xmult = Integer(1) cnt = 0 for i in range(920):     cc = basis_[0][i]     if int(cc) == 1:         xmult = xmult * Integer(tokens[i])         Xmult = Xmult * Integer(X[i])         cnt += 1   print(cnt) v = inthroot(Xmult, 2) xmult = xmult % n  c_cnt = (xmult * inverse(int(v % n), n)) % n  c = (c_cnt * inverse(pow(csq, (cnt - 1) // 2, n), n)) % n    # Part 2 : find some sqrt of 1 xmult = Integer(1) Xmult = Integer(1)   cnt = 0 for i in range(920):     cc = basis_[1][i]     if int(cc) == 1:         xmult = xmult * Integer(tokens[i])         Xmult = Xmult * Integer(X[i])         cnt += 1   print(cnt) v = inthroot(Xmult, 2) xmult = xmult % n  c_cnt = (xmult * inverse(int(v % n), n)) % n  sq1 = (c_cnt * inverse(pow(csq, cnt // 2, n), n)) % n    print(n) p = GCD(sq1+1, n) q = GCD(sq1-1, n) assert p != 1 and q != 1 and p * q == n   for u in [1, -1]:     for v in [1, -1]:         cc = crt(u, v, p, q)         c_real = (c * cc) % n         phi = (p - 1) * (q - 1)         d = inverse(65537, phi)         print(long_to_bytes(pow(c_real, d, n)))   Colored by Color Scripter cs

### n1token2

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 import random from secret import FLAG   assert FLAG.startswith('n1ctf{') assert FLAG.endswith('}') SECRET = bytes.fromhex(FLAG[6:-1]) assert len(SECRET) == 16   p = 251   e = [1, 20, 113, 149, 219]   y = b''  for x in range(1, p):     coeff = [random.choice(e)] + list(SECRET)     y += bytes([sum(c * pow(x, i, p) for i, c in enumerate(coeff)) % p])      print(f'Token: {y.hex()}')   Colored by Color Scripter cs

We have some polynomial $p$ of degree $16$, and have a length 5 candidate set for all $p(x)$.

To solve this, we note that if $p(x)$ is one of $a, b, c, d, e$, then the following is always true. $$(p(x) - a)(p(x) - b)(p(x)-c)(p(x)-d)(p(x)-e) \equiv 0 \pmod{p}$$ Now considering $p(x), p(x)^2, p(x)^3, p(x)^4, p(x)^5$ as independent polynomials of degree $16,32,48,64,80$, we can set up a matrix equation and solve the linear system to find $p$. This is a classical idea that I really like, so I enjoyed this challenge.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 from Crypto.Cipher import AES, PKCS1_OAEP, PKCS1_v1_5 from Crypto.PublicKey import RSA from Crypto.Util.Padding import pad, unpad from Crypto.Util import Counter from Crypto.Util.number import inverse, long_to_bytes, bytes_to_long, isPrime, getPrime, getRandomRange, sieve_base from tqdm import tqdm from pwn import * from sage.all import * import gmpy2, pickle, itertools, sys, json, hashlib, os, math, time, base64, binascii, string, re, struct, datetime, subprocess import numpy as np import random as rand import multiprocessing as mp from base64 import b64encode, b64decode from sage.modules.free_module_integer import IntegerLattice from Crypto.Hash import SHA3_256, HMAC, BLAKE2s from Crypto.Cipher import AES, ARC4, DES     token = '1d85d235d08dfa0f0593b1cfd41d3c98f2a542b2bf7a614c5d22ea787e326b4fd37cd6f68634d9bdf5f618605308d4bb16cb9b9190c0cb526e9b09533f19698b9be89b2e88ba00e80e44d6039d3c15555d780a6a2dbd14d8e57f1252334f16daef316ca692c02485684faee279d7bd926501c0872d01e62bc4d8baf55789b541358dfaa06d11528748534103a80c699a983c385e494a8612f4f124bd0b2747277182cec061c68197c5b105a22d9354be9e436c8393e3d2825e94f986a18bd6df9ab134168297c2e79eee5dc6ef15386b96b408b319f53b66c6e55b3b7d1a2a2930e9d34287b74799a59ab3f56a31ae3e9ffa73362e28f5751f79' token = bytes.fromhex(token)   # (p(x) + 1 - h)(p(x) + 20 - h)(p(x) + 113 - h)(p(x) + 149 - h)(p(x) + 219 - h) # p(x) p(x)^2 p(x)^3 p(x)^4 p(x)^5   p = 251 e = [1, 20, 113, 149, 219] POL = PolynomialRing(GF(p), 'x') x = POL.gen()   M = [[0] * 245 for _ in range(250)] target = []   for i in range(0, p-1):     t = i + 1     v = int(token[i])     f = (x + 1 - v) * (x + 20 - v) * (x + 113 - v) * (x + 149 - v) * (x + 219 - v)     arr = f.coefficients(sparse=False)     target.append(p - arr[0])     for j in range(0, 16 + 1):         M[i][j] = (arr[1] * (t ** j)) % p     for j in range(17, 17 + 32 + 1):         M[i][j] = (arr[2] * (t ** (j - 17))) % p      for j in range(17 + 33, 17 + 33 + 48 + 1):         M[i][j] = (arr[3] * (t ** (j - 17 - 33))) % p     for j in range(17 + 33 + 49, 17 + 33 + 49 + 64 + 1):         M[i][j] = (arr[4] * (t ** (j - 17 - 33 - 49))) % p     for j in range(17 + 33 + 49 + 65, 17 + 33 + 49 + 65 + 80 + 1):         M[i][j] = (arr[5] * (t ** (j - 17 - 33 - 49 - 65))) % p   M = Matrix(GF(p), M) target = vector(GF(p), target)   v = M.solve_right(target) print(M.right_kernel().basis()) flag = 'n1ctf{'   for i in range(1, 17):     flag += bytes([v[i]]).hex()   flag += "}"   print(flag)          Colored by Color Scripter cs

### babydefi

The source code is omitted due to size reasons. We have the following setup.

• There are two ERC20 tokens, "FlagToken" and "N1Token".
• We can flashloan some "N1Token"s.
• There is a Uniswap LP Pool for "FlagToken" and "N1Token".
• This LP Pool has no 0.3% fees like Uniswap, and doesn't support flashloans.
• There is a Farming Pool called "N1Farm".
• There are some "N1Tokens" initially
• If we deposit "N1Tokens", then "FlagTokens" are minted as rewards.
• There is a sellSomeForFlag() function that sells all "N1Tokens" for "FlagTokens".
• We have no tokens at the beginning. The goal is to have a lot of FlagTokens and some N1Tokens.

The main vulnerability is from Cover Protocol exploit. I'll let google help you on details for this.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 function deposit(address token,uint256 _amount) external {         require(token == tokenAccept,"Fake Token.");         PoolInfo memory poolInfo = poolInfos[token]; // HERE!         updatePool(token);         UserInfo storage user = userInfo[msg.sender];         if (user.amount > 0) {             uint256 pending = user.amount.mul(poolInfo.accRewardsPerToken).div(1e18).sub(user.rewardDebt);             if (pending > 0) {                 IMintToken(flagToken).mint(msg.sender, pending);             }         }         if (_amount > 0) {             IERC20(token).safeTransferFrom(address(msg.sender), address(this), _amount);             user.amount = user.amount.add(_amount);         }         user.rewardDebt = user.amount.mul(poolInfo.accRewardsPerToken).div(1e18);         emit Deposit(msg.sender,_amount);     }           Colored by Color Scripter cs

We note that the poolInfo is "memory" which means that the updated poolInfo from updatePool() is not used.

This means that the accRewardPerToken is undervalued, meaning rewardDebt is undervalued.

Therefore, in the later withdrawl, the reward we get will be way larger than what the developers intended.

Let's ignore that the N1Farm address holds N1Tokens for now. We'll resolve this later.

Consider the following scenario : we deposit X, then withdraw X-1, then deposit X-1, then withdraw X.

In the second deposit, when rewardDebt is calculated, the poolInfo used is calculated right before the X-1 tokens are withdrawed to the caller's wallet, i.e. the updatePool() in the withdraw function. This means the rewards accrued while there were only one N1Token is ignored, so a large accRewardsPerToken is not accounted in calculation. In the next withdraw, X tokens are accounted for the large amount of unnoticed accRewardTokens, which means that a very large amount of FlagTokens are minted to the caller. This is the Cover Protocol exploit.

The difference between the Cover Protocol case and ours is that we do not have any N1Tokens yet.

Even if we can get our hands on some N1Tokens via flashloan, since everything must be in one transaction (and in one block, obviously) the updatePool() function cannot operate as we desire more than once. We need to actually get some N1Tokens.

To do that, we look again at the sellSomeForFlag() function. This function is public, so we can call it at will.

Since this function is guaranteed to buy FlagTokens, we can front-run this very easily.

We need to flashloan N1Tokens, then buy FlagTokens ourselves, call the sellSomeForFlag() function, then sell our FlagTokens.

This will give us more N1Tokens than our initial balance, so we can pay back the flashloan and send the rest to our address.

Note that this also makes N1Farm have zero N1Tokens, as we wanted above. This practically solves the challenge.

There are two ways to finish here.

The first method is to use the deposit X, withdraw X-1, deposit X-1, withdraw X strategy multiple times.

I used this method, and it took about 15 cycles over around 30 minutes. This gives the flag, but is slow.

The second method is to perform the cycle then swap the FlagTokens received for some N1Tokens.

This makes the farming much more efficient, and will reach the desired FlagToken balance faster.

web3 exploit written with ethersjs

solidity exploit for front running

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

 SECCON CTF 2021 Writeups  (0) 2021.12.14 2021.11.22 2021.10.13 2021.10.03 2021.09.26 2021.09.26
1. 가슴이 웅장해진다..

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

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

### Goodhash

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

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

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

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

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

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

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

Solution 1

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

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

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

Solution 2

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

• Since the equation is over $GF(2^{128})$ we can convert this into 128 linear equations over $GF(2)$.
• This is a total of 27 characters, which is equivalent to 216 fixed bits over $GF(2)$.

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

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

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

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

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

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

### Yet Another RSA

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

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

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

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

The Group

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

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

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

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

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

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

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

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

### Yet Another PRNG

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

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

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

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

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

### Seed Me

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

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

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

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

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

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

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

 SECCON CTF 2021 Writeups  (0) 2021.12.14 2021.11.22 2021.10.13 2021.10.03 2021.09.26 2021.09.26

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

### Beginner's Crypto

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

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

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

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

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

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

### Minimalist's Private

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

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

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

### Baba is Flag

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

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

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

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

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

### This is DSA

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

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

Step 1 : removing all "irrational" ideas

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

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

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

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

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

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

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

Step 2 : actually knowing what the challenge is

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 3 : the finish

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

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

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

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

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

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

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

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

### Flag is Win

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

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

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

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

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

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

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

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

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

### Lumberjack in Nature

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

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

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

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

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

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

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

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

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

### Lumberjack Against Nature

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

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

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

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

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

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

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 def ceil(n, m): # returns ceil(n/m)     return (n + m - 1) // m   def is_inside(L, R, M, val): # is L <= val <= R in mod M context?     if L <= R:         return L <= val