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

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

#### RSA Stream

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

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

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

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

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

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

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

#### CBCBC

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

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

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

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

#### Swap on Curve

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

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

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

#### Two Rabin

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

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

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

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

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

#### Wonderful Hash

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

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

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

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

#### Share The Flag

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

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

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

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

 TSGCTF 2021 Writeups  (0) 2021.10.03 2021.09.26 2021.09.26 2021.08.05 2021.07.22 2021.07.19