Writeup Cryptography Final Gemastik 13

Pada pelaksanaan final Gemastik 13, terdapat 2 soal Cryptography. Berikut penyelesaian saya untuk tiap soalnya.

NO AES No Party

Diberikan sebuah source code dan service.

flag = open("flag.txt").read()
ulti_key = os.urandom(8)
adds_key = os.urandom(2)
main_key = os.urandom(16)
main_iv  = os.urandom(16)
def encrypt_1(strs, key, iv):
 obj = AES.new(key, AES.MODE_CFB, iv)
 return obj.encrypt(strs)
def encrypt_2(strs, key):
 obj = AES.new(key, AES.MODE_ECB)
 return obj.encrypt(strs)
while True:
 print("""We Open Encryption Service For Free\n1. Get Encrypted Key\n2. Get Encrypted Flag\n3. Encrypt Message""")
 option = input("> ")
 if option == "1":
  enc_ult_key = encrypt_1(ulti_key + os.urandom(24), main_key, main_iv)
  print(binascii.hexlify(enc_ult_key).decode())
 elif option == "2":
  enc_flag = encrypt_2(flag.encode(), ulti_key+(adds_key*4))
  print(binascii.hexlify(enc_flag).decode())
 elif option == "3":
  input_msg = input("Msg: ")
  try:
   input_msg = binascii.unhexlify(input_msg)
   enc_input_msg = encrypt_1(input_msg, main_key, main_iv)
   print(binascii.hexlify(enc_input_msg).decode())
  except:
   print("Invalid Msg")
 else:
  print("Invalid Option")

Pada source code diketahui bahwa terdapat 2 jenis enkripsi, yaitu CFB dan ECB.

Terdapat 3 pilihan service :

● Encrypt pt berupa (Ulti_key+random string) menggunakan key_main, dan iv_main dengan CFB.
● Encrypt flag dengan ECB, dan key berupa (ulti_key + 2 random chars*4)
● Choosen plaintext CFB.

Karena, enkripsi flag cukup sederhana, hanya menggunakan ECB saja, jika kita bisa mendapatkan nilai ulti_key, maka tentu kita bisa mendekrip enc_flag nya. Maka tujuan pertama kita di chall ini adalah mendapatkan nilai ulti_key.

Ulti_key digunakan sebagai plaintext pada service 1, dengan metode CFB. Dan pada service 3, kita bisa melakukan choosen plaintext CFB.

Sebelumnya mari kita lihat bagaimana CFB bekerja.

Kita mengetahui bahwa plaintext pada service 1 terdiri atas 3 blok.
ulti_key + 8 random chars + 8 random chars.
Artinya, kita hanya perlu mendapatkan nilai plaintext pada block 1.
Setelah melakukan beberapa research, saya menduga bahwa kita bisa melakukan persamaan seperti ini

C0 aksen ^ P0 Aksen ^ C0 = P0

Namun, setelah beberapa try dan error, sepertinya saya keliru di suatu tempat. Maka dari itu, saya mencoba cara lain. Berdasarkan gambar diatas, kita mengetahui bahwa block 1 ciphertext merupakan hasil dari `IV-KEY ^ block 1 plaintext`.
Karena nilai iv dan key disana konstan, dan kita diberikan service 3 berupa choosen plaintext CFB dengan iv dan key yang sama, artinya kita bisa melakukan bruteforce pada multiple byte xor nya.

Setelah mendapatkan nilai ulti_key, kita hanya perlu membruteforce 2 random char lagi, untuk digunakan sebagai key dalam mendekrip enc_flag.

Berikut solver saya :

from Crypto.Cipher import AES
from pwn import *
import string
r = remote('18.141.220.66',10201)
r.recvuntil('>')
r.sendline('1')
keyenc=r.recvline().strip()
print("KEY ENC :",keyenc)
r.recvuntil('>')
r.sendline('2')
encflag=r.recvline().strip()
encflag=encflag.decode('hex')
print("ENC FLAG :",encflag.encode('hex'))
key=''
list = "0123456789abcdef"
while(len(key)!=16):
 for i in (list):
  for j in list:
   payload=key+i+j
   r.recvuntil('>')
   r.sendline('3')
   r.sendline(payload)
   cek=r.recvline().strip("Msg: ").strip()
   #print(cek,keyenc[:(len(cek))])
   if(cek==keyenc[:(len(cek))]):
    key+=i+j
    print("FOUND",key)
key=key.decode('hex')
for i in range(256):
    for j in range(256):
            add=""+chr(i)+chr(j)
            keys=key+(add*4)
            obj = AES.new(keys, AES.MODE_ECB)
            try:
                    x = obj.decrypt(encflag)
                    if "gemastik" in x:
                            print x
            except:
                    continue

Sennin Mode

Diberikan sebuah source code RSA dan service, dimana terdapat banyak persamaan math dan random number.

def genKey():
 p = getPrime(1337)
 q = getPrime(1337)
 e = 0x10001
 n = p*q
 phi = (p-1)*(q-1)
 d = inverse(e,phi)
 x = (random.randint(-9,9)*p + q)*(random.randint(-9,9)*q + p)
 y = (p + random.randint(-9,9)*q)*(q + random.randint(-9,9)*p)
 return n,e,d,x,y
def getVerySecureSeed(init):
 value     =  bytes_to_long(init)
 ret_seed  =  len(init)
 ret_seed ^=  ((value >> 437) & 28391)
 ret_seed |=  ((value >> 488) & 1273) 
 ret_seed -=  ((value >> 432) ^ 734)
 ret_seed |=  ((value >> 484) & 9102)
 ret_seed +=  ((value >> 443) | 8764)
 ret_seed |=  ((value >> 528) & 9283)
 ret_seed -=  ((value >> 506) + 89827)
 ret_seed +=  ((value >> 433) - 9234)
 ret_seed ^=  ((value >> 494) % 23452)
 ret_seed -=  ((value >> 445) | 12)
 ret_seed ^=  ((value >> 438) * 928)
 ret_seed -=  ((value >> 477) ^ 8542)
 ret_seed +=  ((value >> 444) << 176)
 ret_seed |=  ((value >> 521) * 3)
 ret_seed ^=  ((value >> 513) + 999)
 return ret_seed
flag = open("flag.txt").read()
seed = getVerySecureSeed(flag.encode())
random.seed(seed)
target = 9
for i in range(10):
 n,e,d,x,y = genKey()
plain = bytes_to_long(urandom(21))
 enc_plain = pow(plain, e, n)
 dec_plain = pow(enc_plain, d, n)
 
 print("Solve 10 stage to get the flag")
 print("n = {}".format(n))
 print("e = {}".format(e))
 print("c = {}".format(enc_plain))
 print("x = {}".format(x))
 print("y = {}".format(y))
 input_dec = input("Give me decrypted c : ")
 
 try:
  start = time.time()
  input_dec = int(input_dec)
  end = time.time()
  if end - start > 7:
   print("Times Up")
   break
  if input_dec == dec_plain:
   print("Nice")
  else:
   print("Not Nice")
   break
  if i == target:
   print("Congrats")
   print(flag)
 except:
  print("Something Error")
  break

Tujuan dari challenge ini adalah agar kita dapat menjawab seluruh pertanyaan yang diberikan.
Soal ini sebenarnya hanya RSA biasa namun menjadi rumit karena mengimplementasikan berbagai persamaan matematika disini.

Untuk setiap stage, kita diberikan nilai e,n,c,x, dan y. Nilai x dan y sendiri adalah hasil dari kalkulasi bilangan bilangan random yang melibatkan p dan q.

Disini bagian yang menarik adalah
x = (random.randint(-9,9)*p + q)*(random.randint(-9,9)*q + p)
y = (p + random.randint(-9,9)*q)*(q + random.randint(-9,9)*p)

dan kita diberikan nilai x,y dan n nya. Note : n == p*q.
Mari kita gunakan persamaan matematis untuk menyelesaikannya.
Kita asumsikan,

x1 = random.randint(-9,9)
x2 = random.randint(-9,9)
y1 = random.randint(-9,9)
y2 = random.randint(-9,9)
Untuk semua kemungkinan, kita akan membruteforce dengan worst case130321 kemungkinan , yang relatif sedikit.

Untuk tiap nilai x1,x2,y1,y2 kita susun persamaan sebagai berikut :

x= (x1*p + q) * (x2*q + p) => x1x2pq + x1p2 + x2q2 + pq
y= (p + y1*q) * (q + y2*p) => y1y2pq + y1q2 + y2p2 + pq
x == x1*x2*n + x1*(p**2) + x2*(q**2) + n
y == y1*y2*n + y2*(p**2) + y1*(q**2) + n
y1*x == y1*x1*x2*n + y1*x1*(p**2) + y1*x2*(q**2) + y1*n
x2*y == x2*y1*y2*n + x2*y2*(p**2) + x2*y1*(q**2) + x2*n
— — — — — — — — — — — — — — — — — — — — — — — — — — — — eliminasi
(y1*x — x2*y) == (y1*x1*x2*n — x2*y1*y2*n) + (y1*x1*(p**2) — x2*y2*(p**2) ) + (y1*n — x2*n)

Kita telah mendapatkan persamaan yang bebas dari variabel q, dan tersisa variabel p saja. Kita misalkan,

R = (y1*x - x2*y)
S = (y1*x1*x2*n - x2*y1*y2*n)
T = (y1*n - x2*n)
u1 = y1*x1
u2 = x2*y2

Maka persamaannya menjadi
R == S + (u1*(p**2) — u2*(p**2) ) + T

R - S - T == (u1*(p**2) - u2*(p**2) ) 
R - S - T == (p**2)*(u1-u2)
(R - S - T)/(u1-u2) == (p**2)
p == iroot((R - S - T)/(u1-u2),2)[0]

Nilai p berhasil didapatkan, artinya kita juga mendapatkan nilai q.

Setelah mendapatkan nilai p, dan melengkapi q. sisanya hanya permasalahan RSA biasa.

Berikut beberapa percobaan yang saya lakukan di lokal beserta waktu eksekusi dalam detik untuk tiap 10 pertanyaan :

Artinya solver sudah oke, langsung saja kita menuju service dan mengirimkan tiap nilai m untuk tiap pertanyaan yang diberikan.

Karena hanya ada 2 soal cryptography pada sesi final ini, sekian writeup dari saya. Terima kasih.