Diberikan file sabeb.py sebagai berikut dan akses ke service.
import binasciiimport randomcharset ='ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/'charset2 ='ABCDEFGHIJKLMNOPQRSTUVWXYZ'defgenerateSecret(): secret ="".join(random.choices(charset2, k=30))return secret.encode()defsabebencode(text):##############################################################################################################ceritanya ini rusak kesiram kopi##############################################################################################################if__name__=='__main__':print('Hi! I am Decoda, your personal base64 encoder 0_0')print('People said my calculations a little bit something... dunno. But, i\'ll do my best 0_0')print("My boss said bruteforce isn't needed, so you're only given 10 chances to use the encoder")print('====================================================')print('Please make a choice from the options below:') count =0 secret =generateSecret()whileTrue:if count ==10:print("You've reached your limit")print("Thank you and have a good time! ^_^")breakprint(f"Encode remaining: {10- count}")print('1. Print encoded secret')print('2. Encode plaintext')print('3. Submit secret and get flag') inputan =input('>> ')if inputan =='1':print('Here\'s your encoded secret sir:') res =sabebencode(secret)print(res)print('')print('Anything else? 0_0')elif inputan =='2':print('Please input your plaintext in hex 0_0.') text =input('>>')try: text = binascii.unhexlify(text) res =sabebencode(text)print('Beep boop... here\'s the result sir:')print(res)print('')print('Anything else? 0_0') count+=1except:print('Sorry sir... weird input detected 0_0\n')elif inputan =='3':print("Please submit the administrator's secret") secretsubmit =input('>>').encode()try:if secretsubmit == secret: flag ='REDACTED'print(f"Welcome back, admin. Here's your flag: {flag}\n")else:print("Wrong secret! You are not admin >:[\n");except:print('Sorry sir... weird input detected 0_0\n')else:print('Sorry sir... weird input detected 0_0\n')
Jadi intinya kita disuruh mengetahui value dari secretsubmit, namun disini kode dari sabebencode di hilangkan. Disini kita bisa melakukan analisis terhadap input dan output guna menentukan seperti apa algoritma yang ada pada sabebencode.
Bisa kita lihat dari input dan output diatas bahwa terdapat perbedaan antara encode aa dan aaaa pada base64 biasa dan sabeb64. Setelah kami validasi ternyata asumsi kami benar bahwa input di encode setiap 2 bytes, karena 2 bytes printable tidak terlalu banyak maka kita bisa petakan semua nilai dan decrypt secretsubmit dengan memetakannya kembali ke value aslinya.
from pwn import*from itertools import productdicc ={}r =remote("103.167.136.75",9988)for i inproduct(string.printable[:-6],repeat=2): tmp =''.join(i)try: r.recvuntil(b">> ") r.sendline(b"2") r.sendline(tmp.encode().hex().encode()) r.recvuntil(b":\n") res = r.recvline().strip().decode() dicc[res]= tmpexceptExceptionas e: r.close() r =remote("103.167.136.75",9988) r.recvuntil(b">> ") r.sendline(b"2") r.sendline(tmp.encode().hex().encode()) r.recvuntil(b":\n") res = r.recvline().strip().decode() dicc[res]= tmpr.close()print("nice")# backupimport json withopen('dicc.txt', 'w')as convert_file: convert_file.write(json.dumps(dicc))r =remote("103.167.136.75",9988)r.recvuntil(b">> ")r.sendline(b"1")r.recvuntil(b":\n")ct_secret = r.recvline().strip().decode()list_ct = []for i inrange(0,len(ct_secret),3): list_ct.append(ct_secret[i:i+3])secc =""for i in list_ct: secc += dicc[i]r.recvuntil(b">> ")r.sendline(b"3")r.recvuntil(b">>")r.sendline(secc.encode())r.interactive()
Flag : NCW22{jusT_a_littl3_d1ff3r3nt_C0ncept_0f_base_6nam_emp4t_x1x1x1_1be1ec3c3ea96b983a75e17dd3d44e8b}
Flag dikonversi ke binary jadi ada 2 kemungkinan yakni 1 atau 0 untuk variable sugar. Disini kita bisa mengembalikan nilai dari binary tersebut dengan cara mengecek apakah nilai pada encrypted merupakan bilangan square atau bukan , karena c_n1 dan g_c relatif prima namun c_n1 bukan prima maka kita bisa gunakan jacobi symbol untuk mengetahui apakah suatu bilangan square atau bukan. Berikut solver yang kami gunakan
from Crypto.Util.number import*from libnum import*c_n1 = 3855144799899048327534121215306941141185997589420691125094911911082597963257300429096794014315805279596530735439263764994759442420373314885435640329972555
c_n2 = 5299396373535953706628077154342198627748435935987447573061077335778202151741165833985790411265547771371574434052556785516415658261684773030001154912306733
encrypted = [507104000732472450402938437721529021378564745838604181711052463510983043412099070337891206768987338263502149153936534933899109822282227342709312445026628,...SNIPPET…, 1983121417614455624787082919584128947462950990156463566859101453080668678780641745395775761769267205914558434913337236643284756856405940720684555555234672]
res =""for i in encrypted:if(jacobi(i,c_n1)==0): res +="1"else: res +="0"print(long_to_bytes(int(''.join(res),2)))
Flag : NCW22{j4c0bi_symb0ls_101_w!th_c0mposit3_numbers}
Turmoil (491 pts)
Description
-
Solution
Diberikan file soal.py sebagai berikut
from Crypto.Util.number import*import randomimport mathm =bytes_to_long(b"REDACTED")defprimevalue(value): ind =0whilenotisPrime(value): value +=1 ind +=1print(f"added {ind}")return valuedefgeneratePrimes():print("generating random numbers...") p = random.getrandbits(512) q = random.getrandbits(512)print("calculating next prime...") p =primevalue(p) q =primevalue(q)print("comparing values...")print("=======| > |=======")if p > q elseprint("=======| < |=======")return p, qwhileTrue:try:print("==================================")print("J&M's EncRSAyption MacRSAhine 3000")print("==================================")print("1. Spill Administrator's message")print("2. Encrypt your own message") pilihan =input("[?] ")if pilihan =="1": p, q =generatePrimes() e =primevalue(random.randint(3, 100000)) n = p*q c =long_to_bytes(pow(m, e, n))print("\nToo bad this part is highly confidential, only the ciphertext are allowed to be displayed.")print(f"[>] {c.hex()}\n")elif pilihan =="2": p, q =generatePrimes() n = p * q phi = (p-1)*(q-1)print("")print("Input plaintext") message =bytes_to_long(input("[?] ").encode())whileTrue:print("Input your exponent") e =int(input("[?] "))if math.gcd(e, phi)!=1:print('Error! exponent and totient have same factor(s)')else: d =inverse(e, phi)print("Imma just show this to you, you already know your own message anyway")print(f"d = {d}")print("Use this exponent? (Y/N)") choice =input("[?] ")if choice =="Y"or choice =="y":breakelif choice =="N"or choice =="n":pass c =pow(message, e, n)print("Here's the result:")print(f"[>] n = {n}\n[>] e = {e}\n[>] c = {c}\n")except:print('Error\n')
Intinya kita bisa melakukan predict terhadap nilai prime karena digenerate berdasarkan getrandbits. Untuk nilai state sebelumnya kita bisa dapatkan karena kita mengetahui nilai d,e,n dan bisa melakukan recover terhadap p,q dimana p,q bisa kita kembalikan ke nilai state (getrandbits) dengan mengurangkan sesuai dengan penambahannya. Dan untuk mengetahui mana p dan q bisa dari hasil recover bisa diketahui dengan keterangan tambahan mengenai nilai besar kecil dari p q pada bagian “comparing values” . Terakhir cukup brute e pada enkripsi flag karena nilai e tidak terlalu besar. Disini sempet stuck karena mencoba mengimplementasikan recovery p,q secara naive (bisa dapat bisa tidak) yang ternyata setelah mencari-cari ada scriptnya :3 https://github.com/truongkma/ctf-tools/blob/master/RecoverPrimeFactors.py . Berikut solver yang kami gunakan.
from math import gcdfrom randcrack import RandCrackfrom pwn import*from Crypto.Util.number import*# import fractions # for gcd function (or easily implementable to avoid import)import random # for random elements drawing in RecoverPrimeFactorsdeffailFunction():print("Prime factors not found")defoutputPrimes(a,n): p =gcd(a, n) q =int(n // p)if p > q: p, q = q, p# print("Found factors p and q")# print("p = {0}".format(str(p)))# print("q = {0}".format(str(q)))return p, qdefRecoverPrimeFactors(n,e,d): k = d * e -1if k %2==1:failFunction()return0,0else: t =0 r = kwhile(r %2==0): r =int(r //2) t +=1for i inrange(1, 101): g = random.randint(0, n)# random g in [0, n-1] y =pow(g, r, n)if y ==1or y == n -1:continueelse:for j inrange(1, t):# j \in [1, t-1] x =pow(y, 2, n)if x ==1: p, q =outputPrimes(y -1, n)return p, qelif x == n -1:continue y = x x =pow(y, 2, n)if x ==1: p, q =outputPrimes(y -1, n)return p, qdefprimevalue(value): ind =0whilenotisPrime(value): value +=1 ind +=1return valuepub_exp = [65537]defget_pq(n,list_d,p_add,q_add,cmp_val,one_factor=False):for i inrange(len(pub_exp)): e = pub_exp[i] d = list_d[i] p,q =RecoverPrimeFactors(n,e,d)if(cmp_val): tmp_p =max(p,q) tmp_q =min(p,q)else: tmp_p =min(p,q) tmp_q =max(p,q) p = tmp_p - p_add q = tmp_q - q_add# print("p = {0}".format(str(p)))# print("q = {0}".format(str(q)))while p >0: rc.submit(p % (1<<32)) p = p >>32if(one_factor==False):while q >0: rc.submit(q % (1<<32)) q = q >>32rc =RandCrack()r =remote("103.167.136.75",9966)# r = process("./soal.py")for i inrange(20):# print(i) r.recvuntil(b"[?] ") r.sendline(b"2") r.recvuntil(b"added ") p_add =int(r.recvline().strip().decode()) r.recvuntil(b"added ") q_add =int(r.recvline().strip().decode()) r.recvuntil(b"=======|") cmp_val = r.recvline().strip().decode() r.recvuntil(b"[?] ") r.sendline(b"a") list_d = []for e in pub_exp: r.recvuntil(b"[?] ") r.sendline(str(e).encode()) zzz = r.recvline()if(b"Error!"in zzz): list_d.append(0)continue r.recvuntil(b"d = ") d =int(r.recvline().strip().decode()) list_d.append(d) r.recvuntil(b"[?] ")# print(e)if(e == pub_exp[-1]): r.sendline(b"Y")else: r.sendline(b"N") r.recvuntil(b"n = ") n =int(r.recvline().strip().decode())if(i==19):if(">"in cmp_val):get_pq(n,list_d,p_add,q_add,True,True)else:get_pq(n,list_d,p_add,q_add,False,True)else:if(">"in cmp_val):get_pq(n,list_d,p_add,q_add,True)else:get_pq(n,list_d,p_add,q_add,False)print("noice")r.recvuntil(b"[?] ")r.sendline(b"1")r.recvuntil(b"added ")e_add =int(r.recvline().strip().decode())r.recvuntil(b"[>] ")ct =bytes_to_long(bytes.fromhex(r.recvline().strip().decode()))print("CT",ct)r.close()junk = rc.predict_randrange(0, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095)
p = rc.predict_randrange(0, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095)
q = rc.predict_randrange(0, 13407807929942597099574024998205846127479365820592393377723561443721764030073546976801874298166903427690031858186486050853753882811946569946433649006084095)
p =primevalue(p)q =primevalue(q)# print(p)# print(q)phi = (p-1)*(q-1)n = p*qfor e inrange(3, 100000):if(isPrime(e)):try: d =inverse(e,phi) tmp =long_to_bytes(pow(ct,d,n))if(b"NCW"in tmp):print(e,tmp)breakif(tmp.decode()):print(e,tmp)breakexcept:continue