This was a fun CTF. I solved all 6 crypto challenges and three other random ones. I decided to write up on all of them, because why not.
The six crypto challenges are:
- Binned (126 solves / 45 points)
- Chaffymasking (66 solves / 73 points)
- Mariana (59 solves / 80 points)
- Mindseat (33 solves / 128 points)
- Desired curve (19 solves / 194 points)
- Disinvolute (7 solves / 334 points)
The other three challenges I solved were:
- Prepsi (PPC / 90 solves / 58 points)
- Wormrep (Misc / 80 solves / 63 points)
- Comopti (Misc / 38 solves / 114 points)
We first begin by importing lots of potentially useful packages.
In [1]:
from pwn import *
from Crypto.Util.number import *
from sage.all import *
from sage.rings.factorint import factor_trial_division
from tqdm import trange
from ast import literal_eval
import os, re, string
Binned (126 solves)
This was a pretty standard mod n^2 challenge, i.e. (n+1)k=kn+1(modn2).
In [2]:
pubkey = 125004899806380680278294077957993138206121343727674199724251084023100054797391533591150992663742497532376954423241741439218367086541339504325939051995057848301514908377941815605487168789148131591458301036686411659334843972203243490288676763861925647147178902977362125434420265824374952540259396010995154324589
enc = 789849126571263315208956108629196540107771075292285804732934458641661099043398300667318883764744131397353851782194467024270666326116745519739176492710750437625345677766980300328542459318943175684941281413218985938348407537978884988013947538034827562329111515306723274989323212194585378159386585826998838542734955059450048745917640814983343040930383529332576453845724747105810109832978045135562492851617884175410194781236450629682032219153517122695586503298477875749138129517477339813480115293124316913331705913455692462482942654717828006590051944205639923326375814299624264826939725890226430388059890231323791398412019416647826367964048142887158552454494856771139750458462334678907791079639005383932256589768726730285409763583606927779418528562990619985840033479201147509241313757191997545174262930707521451438204766627975109619779824255444258160
print(long_to_bytes(enc % pubkey**2 // pubkey))
b'ASIS{8!N0miaL_3XpAn5iOn_Us4G3_1N_cRyp7o_9rApHy!}'
Chaffymasking (66 solves / 73 points)
I didn’t fully figure out what this challenge did, but basically you give it a 128-character salt and it XORs something with the flag. Of course you XOR this masked flag to get the flag back. My first attempt of 'a'*128 failed because it specifically wanted the two halves to be different, so of course I changed the last character to a b.
In [3]:
# nc 65.21.255.31 31377
# send a 128-char string consisting of 127*'a'+'b'
# get back: masked_flag = b'04f4f49d12840d96e23d0ecebb1e421cee4c0600ac8069cc7f64ae7c5622d15a04a905780561612470317977de7b0854154b7722fdcd5a80b5c25ec8c3ce5551'
foo = "FLAG=''.join(chr(i) for i in bytes.fromhex('04f4f49d12840d96e23d0ecebb1e421cee4c0600ac8069cc7f64ae7c5622d15a04a905780561612470317977de7b0854154b7722fdcd5a80b5c25ec8c3ce5551'))"
script = open('chaffymasking.py').read()
script = script.replace('from flag import FLAG', foo)
script = script.replace('sys.stdin.buffer.readline()', "b'aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab '")
exec(script)
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| | Welcome to chaffymask combat, we implemented a masking method to | | hide our secret. Masking is done by your 1024 bit input salt. Also | | I noticed that there is a flaw in my method. Can you abuse it and | | get the flag? In each step you should send salt and get the mask. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| | Give me your salt: | masked_flag = b'415349537b4c6174746963655f62617365645f686173685f636f6c6c6973696f6e5f69745f7761735f736f6f6f6f6f6f6f6f6f6f6f6f6f6f6f5f65617359217d' | Give me your salt: | masked_flag = b'415349537b4c6174746963655f62617365645f686173685f636f6c6c6973696f6e5f69745f7761735f736f6f6f6f6f6f6f6f6f6f6f6f6f6f6f5f65617359217d' | Give me your salt: | masked_flag = b'415349537b4c6174746963655f62617365645f686173685f636f6c6c6973696f6e5f69745f7761735f736f6f6f6f6f6f6f6f6f6f6f6f6f6f6f5f65617359217d' | Give me your salt: | masked_flag = b'415349537b4c6174746963655f62617365645f686173685f636f6c6c6973696f6e5f69745f7761735f736f6f6f6f6f6f6f6f6f6f6f6f6f6f6f5f65617359217d' | Give me your salt: | masked_flag = b'415349537b4c6174746963655f62617365645f686173685f636f6c6c6973696f6e5f69745f7761735f736f6f6f6f6f6f6f6f6f6f6f6f6f6f6f5f65617359217d'
In [4]:
# feed the new masked_flag back into the next line
print(bytes.fromhex('415349537b4c6174746963655f62617365645f686173685f636f6c6c6973696f6e5f69745f7761735f736f6f6f6f6f6f6f6f6f6f6f6f6f6f6f5f65617359217d'))
b'ASIS{Lattice_based_hash_collision_it_was_sooooooooooooooo_easY!}'
Mariana (59 solves / 80 points)
The aim is to find x such that gx≡x(modp) for a given g and p (of bit-size increasing with each level). Unfortunately the check was broken so we could just submit x = 1-p each time, which makes both sides of the equation congruent to 1 mod p.
In [5]:
with remote('65.21.255.31', 32066) as sh:
for _ in trange(40):
sh.recvuntil(b'p = ')
p = int(sh.recvline())
sh.sendline(str(1-p).encode())
print(sh.recvall())
[x] Opening connection to 65.21.255.31 on port 32066 [x] Opening connection to 65.21.255.31 on port 32066: Trying 65.21.255.31 [+] Opening connection to 65.21.255.31 on port 32066: Done
100%|███████████████████████████████████████████████████████████████████████████████████| 40/40 [00:24<00:00, 1.63it/s]
[x] Receiving all data [x] Receiving all data: 417B
[x] Receiving all data: 486B
[+] Receiving all data: Done (486B)
[*] Closed connection to 65.21.255.31 port 32066
b'| g = 9495790558239095895019487197338758073321069218704087668261189071620677664700893660561959632182481240114668318667801442485760017955636644391901301654159080058357573940908639774454835509957159525250909428304532946642435841822949205232463586824146435750929262597484422608341815507965506807881485296485354528980896729586491890667348618488491295306537312404742759865597114564350259785237563\n| Send the solution x = \n| Congratz! the flag is: ASIS{fiX3d_pOIn7s_f0r_d!5Cret3_l0g4riThmS!}\n'
Mindseat (33 solves / 128 points)
This was a DLOG challenge that changed mid-competition. We first solve k=134 by looking counting the number of zeroes at the end of bin(n-1).
Now, since n=(a⋅2k+1)(b⋅2k+1), we could simply partition the binary digits of n to obtain both the product ab and the sum a+b. This gives us the factorisation of n.
Finally, we want to compute the discrete log. We will focus on p=(a⋅2k+1), but instead of taking the entire multiplicative group, we just focus on the cyclic subgroup of order 2k.
In [6]:
PUBKEYS = [(10342840547250370454282840290754052390564265157174829726645242904324433774727630591803186632486959590968595230902808369991240437077297674551123187830095873, 5179654005441544601140101875149402241567866059199512232495766031194848985776186595289740052214499657697650832860279375151687044465018028876445070588827777), (6015512135462554031390611730578383462516861987731833360559070749140159284050335604168414434218196369921956160353365713819898567416920672209509202941444097, 2116441415129068001049624780654272734931672052541246678702416144768611225693039503554945326959705314527114860312641379671935648337975482830939466425225421), (6396980904648302374999086102690071222661654639262566535518341836426544747072554109709902085144158785649143907600058913175220229111171441332366557866622977, 1760317994074087854211747561546045780795134924237097786412713825282874589650448491771874326890983429137451463523250670379970999252639812107914977960011738), (9158217300815233129401608406766983222991414185115152402477702381950519098200234724856258589693986849049556254969769863821366592458050807400542885348638721, 6564146847894132872802575925374338252984765675686108816080170162797938388434600448954826704720292576935713424103133182090390089661059813982670332877677256)]
ENCS = [4595268033054096192076432659360373235610019564489694608733743330870893803828258295069937060360520598446948290913045781945314108935153236291467160667601985, 3390637292181370684803039833768819598968576813582112632809296088618666221278429695211004046274005776653775480723833818255766663573061866194380012311184611, 5197599582013327040903216369733466147938613487439777125659892779696104407398257678982801768761973934713675657188014051286238194316997970299887749668838196, 5093835186720390391696398671365109925058893544530286148616117890366909889206952477053316867658405460457795493886317792695055944930027477761411273933822112]
def solve_bytes(n, s, c):
k = 134
pd = n >> (2*k)
sm = (n >> k) % 2**k
a,b=var('a b')
soln=solve([a+b==sm, a*b==pd],a,b,solution_dict=True)[0]
a,b=soln[a],soln[b]
F = GF((int(a) << k) + 1)
return long_to_bytes((F(c)**a).log(F(s)**a))
print(b'ASIS{' + b''.join(solve_bytes(n, s, c) for (n,s),c in zip(PUBKEYS, ENCS)) + b'}')
b'ASIS{N3w_CTF_nEW_Joye_Libert_CrYpt0_5}'
Desired curve (19 solves / 194 points)
Another DLOG problem, this time on elliptic curves. We pick random numbers to create random curves with different orders, and then solve for m modulo these small orders. If we have enough of these we can CRT them into the flag.
In [7]:
with remote('65.21.255.31', 10101) as sh:
fullres, fullmod = 0, 1
for i in range(100):
y1, y2 = 0, i
sh.sendline(f'{y1},{y2}'.encode())
sh.recvuntil(b'q = ')
q = int(sh.recvline(False).decode())
sh.recvuntil(b'G = ')
G = literal_eval(sh.recvline(False).decode())
sh.recvuntil(b'm * G = ')
mG = literal_eval(sh.recvline(False).decode())
A = (y1**2 - y2**2 - 1337**3 + 31337**3) * inverse(-30000, q) % q
B = (y1**2 - 1337**3 - A * 1337) % q
E = EllipticCurve(GF(q), [A, B])
G, mG = E(G), E(mG)
order = G.order()
small = factor_trial_division(order, 2**24)[-1][0]
mod = order//small
if fullmod % mod:
res = discrete_log(small * mG, small * G, mod, operation='+')
fullres = crt([res, fullres], [mod, fullmod])
fullmod = lcm(fullmod, mod)
ans = long_to_bytes(fullres)
print(i, ans)
if ans.startswith(b'ASIS{'):
break
[x] Opening connection to 65.21.255.31 on port 10101
[x] Opening connection to 65.21.255.31 on port 10101: Trying 65.21.255.31
[+] Opening connection to 65.21.255.31 on port 10101: Done
0 b'\x15'
1 b'\x15'
2 b'\x0c\xa2(}'
3 b'\x1e\x02\xce\xf7H\xfa\xd2\xbd'
5 b'\x12}\xde\xcf\xe4D\x95\xb3='
6 b'\x06\x16\x80\x15\xddzd:S%'
7 b'>\xcd\xd2\x85\xaas\xbb7\xe8\x9e\x8f\xc6)@\xfd'
8 b'\x02j\x83\xe3\xd0\xf6d\xd7\xf3\xc0&\xcd!\xdc\x97k"}'
9 b'=\xb4\xab\x8f\xab\xc8\xb7vu\xc1g/~9(-Hc\xfd'
10 b'\x14\xcd-4X\x88\x83~D\xde1\x7f\x8d\xf6\x95\xe3\xb4L\x15{\xfd'
11 b'<\xdaN+\x84^B\xdd\xd5\xd5^\xbfS\xc5<$\xa4\xa0r\x10\xbe+\xe7}'
13 b'\n@M\xd8\xd5N\xd5yB\x826n\xffRT0\xefY8\xb8\x97\x94\xd4\xdd}'
15 b'ASIS{(e$l6LH_JfsJ:~<}1v&}'
[*] Closed connection to 65.21.255.31 port 10101
Disinvolute (7 solves / 334 points)
We are given that n=pq is the product of two strong primes, so that ϕ(n)=(p−1)(q−1) and ϕ(ϕ(n))=12(p−3)(q−3).
We are also give x and y whose difference must be some (small) rational multiple of ϕ(ϕ(n)).
Since ϕ(ϕ(n)) is itself very close to n2, it suffices to find a close fractional approximation for y−xn, as this fraction will be the exact value of y−x2ϕ(ϕ(n)).
In [8]:
# nc 65.21.255.31 12431
# "[E]ncrypted flag!" followed by "[F]acts"
encrypted_flag = 9975784787149906288323164651646098511260912073828519292647664009852965262234184239194482160682281323145686338707579539174936246755628548643071554893746685504241081607243937752928103836302171563325369474275285850351695028137059318550341706066897348550197283703914701214491304619762159057557708488116067496023
e = 65537
n = 122301129813151738377392491471615607403451921920446978132399462013231700303247932396046963166330330308999106828896234659860341431107142674026027085507407270007060612378624808128187949659861784368599129738197645057094023259799463164380656836969753218710369839503614070738774778151618768907933047489434256496397
x = 15961741473021265408025444939942314380043994779601209295320494007922051528117546405140453031921145140785269525565658092949546180281292504449417001254937509102338309814130703850654719987691857452127504881941980109074538957138347601037940026820654410798082984137712604541783645835937368954078875779392198915138
y = 7644662107689695444086486141738348810380098464495678751586655392689578504981570815843013655350050295187170706046635281483318346295036671632180817944041380146126289013624738076040978223308235099168589334359673704251676133194481665138782135013732603393704853429938024432292112947661999662123373239553942157197715658
ratio = (Integer(y-x)/n).n().nearby_rational(max_denominator = 2**64)
phi = int(2*n+(y-x)/ratio-6)//3
d = pow(e, -1, phi)
print(long_to_bytes(pow(encrypted_flag, d, n)))
b'ASIS{N3s7Ed_DLP_089823341e928d6d87f0e442245d5a765833b575}'
The remaining non-crypto challenges
Prepsi (PPC / 90 solves / 58 points)
If we work from the back, we have a list of flags whose bodies contain only incorrect characters. So we eliminate these incorrect characters unless we are left with only one candidate in each position.
In [9]:
allstr = string.printable[:62] + '!?@-_{|}'
result = [set(allstr) for _ in range(40)]
for line in open('output.txt').readlines()[::-1]:
for i in range(40):
result[i].discard(line[5+i])
if all(len(r) == 1 for r in result):
print('ASIS{' + ''.join(min(r) for r in result) + '}')
break
ASIS{Pr!v4t3_5E7_iNTeRS3c710N_p4St_Or_Pr3sEnT}
Wormrep (Misc / 80 solves / 63 points)
A quick look at the file through a hex editor suggests it might be XORed.
We try to XOR it with all 256 values, and one of these does in fact give us a flag.
In [10]:
bs = open('wormrep.klr.enc1', 'rb').read()
for i in range(256):
xored = xor(bs,i)
result = re.search(b'ASIS{.*}', xored)
if result:
print(result.group(0))
b'ASIS{N07_@ll_v!ru535_@r3_AS_8@d_a5_cov!d}'
Comopti (Misc / 38 solves / 114 points)
As before, we scroll through the file in a hex editor, and quickly find a PGM file beginning with P2. If we view this in a text editor we see some comments made up of 0s and 8s, which makes up this image:
Whereas if we open the PGM as in image, we get this image:
Then we just need to follow the instructions to decrypt the flag.
In [11]:
salt = '3b3gOa7RaVHPTmwKfLz'
payload = 'U2FsdGVkX18y5s1EWrMZLZCHf0BG5B2hjY9iazGPRGliZkEMIMjRG7dniuNp896aMVp/rUwi1vDc1U/lWdoCWQ=='
os.system(f'echo {payload} | openssl aes-256-cbc -pbkdf2 -a -d -salt -k {salt}')
ASIS{pgm_1M4gE_f0Rma7_ManUpL4T!On!}
原文始发于Github：ASIS CTF Quals 2022
相关文章
暂无评论...
