zakigeyanzakigeyan

Gemastik 2020 Final - Crypto

  • Nov 25, 2020

Terdapat 10 challenges yang tersebar secara adil di 5 kategori berbeda, yaitu Web, Reverse Engineering, Forensic, Binary Exploit, dan Cryptography. Berikut solusi dan pembahasan dari​ 2 challenges Cryptography yang berhasil tim kami selesaikan pada babak Final Keamanan Jaringan Gemastik XIII 2020.

No AES No Party

Loh e loh e …

nc 18.141.220.66 10201

Author: 0x124f13

Challenge

#!/usr/bin/env python3
from Crypto.Cipher import AES
import binascii
import os
import sys

class Unbuffered(object):
  def __init__(self, stream):
    self.stream = stream
  def write(self, data):
    self.stream.write(data)
    self.stream.flush()
  def writelines(self, datas):
    self.stream.writelines(datas)
    self.stream.flush()
  def __getattr__(self, attr):
    return getattr(self.stream, attr)

sys.stdout = Unbuffered(sys.stdout)

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")

Solution

Diberikan servis dimana kita diberi tiga pilihan yang berbeda, yaitu sebagai berikut.

  1. Get Encrypted Key
  2. Get Encrypted Flag
  3. Encrypt Message

Secara garis besar, enkripsi menggunakan AES dengan dua mode, yaitu MODE CFB dan MODE ECB.

Pada MODE CFB, IV dienkripsi menggunakan random key, lalu dixor dengan plainteks yang dimasukkan. Untuk MODE CFB, banyaknya byte plainteks yang dimasukkan tidak perlu memenuhi kriteria kelipatan block_size, sehingga kita bisa membandingkan secara satu-per-satu byte ulti_key yang tepat dengan memanfaatkan layanan ke-3.

Dari sini kita dapat mengembalikan 8 bytes dari ulti_key. Masuk tahap berikutnya, key pada enkripsi MODE ECB diambil dari ​ ulti_key + urandom(2) * 4​. Terdapat 2 unknown bytes, tentunya kita dapat melakukan bruteforce 2 bytes, lalu mencoba decrypt encrypted flag menggunakan key tersebut. Berikut kodenya.

Implementation

from deom import *
import string

p = remote("18.141.220.66", 10201)

p.sendlineafter('> ', '1')
enckey = p.recvline().strip()
print enckey

pload = ''
for i in range(8):
    for j in range(256):
        submit = (pload + chr(j)).encode('hex')
        p.sendlineafter('> ', '3')
        p.sendlineafter('Msg: ', submit)
        enciv = p.recvline().strip()
        if enckey.startswith(enciv):
            pload += chr(j)
            print repr(pload)
            break

p.sendlineafter('> ', '2')
encflag = p.recvline().strip().decode('hex')
print len(encflag)

for i in range(256):
    for j in range(256):
        tmp = chr(i)+chr(j)
        teskey = pload + tmp*4
        aes = AES.new(teskey, AES.MODE_ECB).decrypt(encflag)
        if 'gemas' in aes:
            print teskey.encode('hex'), aes
            break

$ python solve-aes.py
[+] Opening connection to 18.141.220.66 on port 10201: Done
1781cb03b03746d7ff210edc10de267c9794a4e7b09138fad214da5b4f7cca71
d20e09ac72c8e792be56be56be56be56 gemastik13{gak_afdol_challs_kripto_kalo_gaada_aesnya_yaudah_cfb}
[*] Closed connection to 18.141.220.66 port 10201

Flag

gemastik13{gak_afdol_challs_kripto_kalo_gaada_aesnya_yaudah_cfb}

Sennin Mode

Apakah kamu harus mempunyai kekuatan sennin mode untuk menyelesaikan soal ini ?

nc 18.141.220.66 10202

Author: 0x124f13

Challenge

#!/usr/bin/env python3
from Crypto.Util.number import *
import random
from os import urandom
import time
import sys

class Unbuffered(object):
  def __init__(self, stream):
    self.stream = stream
  def write(self, data):
    self.stream.write(data)
    self.stream.flush()
  def writelines(self, datas):
    self.stream.writelines(datas)
    self.stream.flush()
  def __getattr__(self, attr):
    return getattr(self.stream, attr)

sys.stdout = Unbuffered(sys.stdout)

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

Solution

Servis memberikan challenge RSA yang terdiri dari 10 stage. Pada tiap stage, kita diberikan nilai dari public key RSA dan juga nilai $ x $ dan $ y $.

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)

Kami melakukan analisis secara manual. Berikut persamaan yang kami tuliskan.

(2p + q) * (3q + p) >  6n + 2p2 + 3q2 + n
(5q + p) * (7p + q) > 35n + 7p2 + 5q2 + n

(x5)  30n + 10p2 + 15q2 + 5n
(x3) 105n + 21p2 + 15q2 + 3n
----------------------------
     -75n - 11p2        + 2n

Kita bisa membangkitkan nilai $ i $ dan $ j $ dimana $ p^{2} $ atau $ q^{2} $ dapat dieliminasi pada persamaan $ ix + jy $. Nilai $ i $ dan $ j $ kecil, sehingga kita bisa melakukan bruteforce dalam waktu singkat. Semenjak kita memiliki nilai $ n $, kita bisa kurangi juga angka tersebut dengan $ kn $ dimana nilai $ k $ juga kecil dan dapat di-bruteforce. Cukup banyak variabel yang perlu di-bruteforce, namun bruteforce dirasa cukup cepat karena range nilai cenderung kecil. Dengan begitu, kita bisa mengembalikan salah satu prime yang digunakan dengan menghitung FPB antara angka yang dihasilkan dengan modulus awal. Berikut kodenya.

Implementation

from deom import *

p = remote("18.141.220.66", 10202)

def solve(n, e, c, pp):
    q = n/pp
    d = inverse(e, (pp-1)*(q-1))
    m = pow(c, d, n)
    p.sendlineafter('c : ', str(m))
    print p.recvline().strip()

def cari():
    for i in range(-9, 10):
        for j in range(-9, 10):
            v1 = x*i + y*j
            for k in range(-256, 256):
                v2 = v1 - k*n
                for l in range(1, 64):
                    if v2 % l == 0:
                        v3 = v2 / l
                        if v3 > 0:
                            v4 = iroot(v3, 2)
                            if v4[1] and gcd(v4[0], n) != n and gcd(v4[0], n) != 1:
                                wew = gcd(v4[0], n)
                                solve(n, e, c, wew)
                                return 0

while True:
    try:
        p.recvuntil('n = ')
        n = int(p.recvline().strip())
        p.recvuntil('e = ')
        e = int(p.recvline().strip())
        p.recvuntil('c = ')
        c = int(p.recvline().strip())
        p.recvuntil('x = ')
        x = int(p.recvline().strip())
        p.recvuntil('y = ')
        y = int(p.recvline().strip())
        a = cari()
    except:
        p.interactive()
        exit()

$ python solve-rsa.py
[+] Opening connection to 18.141.220.66 on port 10202: Done
Nice
Nice
Nice
Nice
Nice
Nice
Nice
Nice
Nice
Nice
[*] Switching to interactive mode
Congrats
gemastik13{at_least_this_calls_is_good_enough_right_question_mark}
[*] Got EOF while reading in interactive
$
[*] Interrupted
[*] Closed connection to 18.141.220.66 port 10202

Flag

gemastik13{at_least_this_calls_is_good_enough_right_question_mark}