# Cyber Jawara 2024 Quals

Pada event CJ 2024 (pada Januari 2025) ini, saya membuat tiga challenge kripto, dua diantaranya khusus untuk kategori umum dan satu untuk kategori umum dan pelajar. Ini adalah writeup singkat untuk ketiga challenge tersebut.

## Class Select
Chall ini pada dasarnya meminta kita untuk mendekripsi pesan sebesar 4 blok yang dienkripsi dengan AES mode OFB, menggunakan mode AES lainnya.

import os
import signal
import json
from Crypto.Cipher import AES
from typing import Tuple

FLAG = open('flag.txt', 'r').read()
PASSWORD = os.urandom(32).hex()
KEY = os.urandom(16)
used = []

def check_mode(mode: int):
    mode = int(mode)
    global used
    if mode in used: raise ValueError("Value already used")
    used.append(mode)
    
def encrypt(data: bytes, params: dict) -> bytes:
    check_mode(params['mode'])    
    cipher = AES.new(KEY, **params)
    ct = cipher.encrypt(data)
    return ct

def decrypt(data: bytes, params: dict) -> bytes:
    check_mode(params['mode'])    
    cipher = AES.new(KEY, **params)
    ct = cipher.decrypt(data)
    return ct

def user_input() -> Tuple[bytes, dict]:
    data = bytes.fromhex(input("Data: ").strip())
    params = json.loads(input("Params: ").strip())
    if 'iv' in params:
        params['iv'] = bytes.fromhex(params['iv'])
    if 'nonce' in params:
        params['nonce'] = bytes.fromhex(params['nonce'])
     
    assert(len(data) < 41)
    
    return data, params
    
    
def main():
    IV = os.urandom(16)
    params = {'mode': 5, 'iv': IV}
    print("Guess my password and I gib flag")
    print(f"Encrypted password: {encrypt(PASSWORD.encode(), params).hex()}")
    print(f"IV: {IV.hex()}")
    print()
    
    for _ in range(3):
        print("="*50)
        print("1. Encrypt")
        print("2. Decrypt")
        print("3. Guess pw")
        print("="*50)
        
        choice = int(input(">>> "))
        
        if choice == 1:
            params = user_input()
            result = encrypt(*params)
            print(f'Result: {result.hex()}')
        elif choice == 2:
            params = user_input()
            result = decrypt(*params)
            print(f'Result: {result.hex()}')
        elif choice == 3:
            guess = input("Guess: ").strip()
            if guess == PASSWORD:
                print(f"Gratz: {FLAG}")
            else: print("Meh, try again.")
            
if __name__ == '__main__':
    signal.alarm(120)
    try:
        main()
    except Exception as e:
        print(e)
        exit(1)

Mode cipher OFB pada dasarnya hanya mengenerate keystream dengan mengenkripsi IV berulang ulang.

Pada chall, kita diberikan dua kesempatan untuk melakukan encrypt atau decrypt dengan max 2 blok data per query. Dengan membaca dokumentasi library atau Wikipedia, diperoleh salah satu solusi yaitu menggunakan CBC dan CFB.

Pada mode cipher CBC, dengan meenkripsi 2 blok plaintext yang berisi null bytes, kita dapat memperoleh 2 blok output keystream OFB (dari enkripsi IV).


Pada mode cipher CFB-16, hal yang serupa dapat dilakukan untuk mendapatkan output keystream OFB.


Satu hal yang perlu diperhatikan saat menginject parameter CFB-16 adalah default value pada library pycryptodome yang memiliki segment size CFB sebesar 8 bits (CFB-1).

https://pycryptodome.readthedocs.io/en/latest/src/cipher/aes.html

### Solver

from Crypto.Cipher import AES
from azunyan.conn import process, remote
from pwn import xor
import json

#r = process(['python3', 'chall.py'], level='debug')
r = remote('localhost', 8040)

r.recvuntil(b'Encrypted password:')
ct = r.recvtype(bytes)
assert len(ct) == 64
r.recvuntil(b'IV: ')
iv = r.recvtype(bytes)
assert len(iv) == 16

def encrypt(data: bytes, iv: bytes, mode: int, set_size = False):
    r.sendlineafter(b'>>> ', b'1')
    r.sendlineafter(b'Data:', data.hex().encode())
    params = {'iv': iv.hex(), 'mode': mode}
    if set_size: params['segment_size'] = 16 * 8
    
    r.sendlineafter(b'Params:', json.dumps(params))
    r.recvuntil(b'Result:')
    res = r.recvtype(bytes)
    return res
    
# MODE CBC
cbc_ct = encrypt(b'\x00' * 32, iv, AES.MODE_CBC)
assert len(cbc_ct) == 32
pws = [xor(cbc_ct[i: i+16], ct[i: i+16]) for i in range(0, 32, 16)]
guess_pw = b''.join(pws)
print(pws)
# MODE CFB
target = cbc_ct[-16:]
cfb_ct = encrypt(b'\x00' * 32, target, AES.MODE_CFB, set_size=True)
assert len(cfb_ct) == 32
pws = [xor(cfb_ct[i: i+16], ct[i+32: i+48]) for i in range(0, 32, 16)]
guess_pw += b''.join(pws)

r.sendlineafter(b'>>> ', b'3')
r.sendlineafter(b'Guess:', guess_pw)
r.interactive()

## ZK-KRSA
Chall ini pada dasarnya meminta kita untuk merecover parameter dari Kid-RSA dari hasil output enkripsi yang obsfucated.

from sympy.crypto import *
from Crypto.Util.number import getPrime
from libnum import n2s, s2n
import signal

FLAG = open('flag.txt', 'rb').read()

params = [getPrime(1024) for _ in range(3)] + [s2n(FLAG)]
pub = kid_rsa_public_key(*params)

def main():
    print("--------Another baby RSA--------")
    print("1. Encrypt")
    print("2. Decrypt")
    print("--------------------------------")
    
    choice = int(input(">>> "))
    if choice == 1:
        pt = bytes.fromhex(input("Data: "))
        pt = s2n(pt)
        ct = pt
        for _ in range(pt.bit_length() + 1):
            ct = encipher_kid_rsa(ct, pub)
        print(f"Result: {n2s(ct).hex()}")
    # elif choice == 2:
    #     ct = bytes.fromhex(input("Data: "))
    #     ct = s2n(ct)
    #     pt: int = decipher_kid_rsa(ct, priv)
    #     print(f"Result: {n2s(pt).hex()}")
    else: raise NotImplementedError()
    
if __name__ == '__main__':
    signal.alarm(120)
    try:
        while True: main()
    except:
        exit(1)

Terdapat tiga parameter penting yang perlu kita recover dari kid RSA, yaitu public key `e`, private key `d`, dan modulus `n`. Enkripsi pada chall pada dasarnya adalah `f(data) = data * pow(e, x) mod n` dimana `x = data.bit_length() + 1`.

Recovery modulus `n` dapat dilakukan dengan berbagai cara, umumnya dengan melakukan operasi diluar modulo `n` hingga diperoleh `0 (mod n)`. Salah satu solusi adalah sebagai berikut:
1. Pilih suatu fixed `x > 3`, misal `x = 4`.
2. Kirim enkripsi data dengan bit length tersebut, misal `f(8), f(9), ..., f(15)`.
3. Untuk tiap pasang data, `z1, z2` dan `f(z1), f(z2)`, perhatikan bahwa `z1 * f(z2) = z2 * f(z1) = z1 * z2 * e ^ x (mod n)`, tetapi jika komputasi kita lakukan tanpa modulus, maka nilai `z1 * f(z2) - z2 * f(z1) = 0 (mod n)` akan memiliki bentuk `k * n` untuk suatu `k >= 0`.
4. Catat tiap nilai yang diperoleh dan ambil GCDnya.
5. Nilai `n` merupakan hasil GCD semua nilai. Jika `n` tidak diperoleh, nilai `x` dapat diincrement dan proses diulang dari awal.

Kemudian, setelah `n` diperoleh, `e` dapat direcover dengan berbagai metode. Misalnya, dengan `f(1)` dan `f(2)`, diperoleh `f(2) * pow(2 * f(1), -1, n) = 2e^2 / 2e = e`. Perhatikan bahwa modulo inverse pada persamaan sebelumnya belum tentu bisa dilakukan dengan `n` yang diperoleh, tetapi recovery dapat di-retry dengan value enkripsi lain atau dengan `n` lain (koneksi baru).

https://macs4200.org/chapters/11/1/kidrsa


Setelah memperoleh `n, e`, kunci privat dapat dihitung dengan `d = pow(e, -1, n)`, dan nilai `M` dari `M = (ed - 1) // n`. Terakhir, flag dapat diperoleh dari `b' = d // M`.

### Solver

from azunyan.conn import remote, process
from Crypto.Util.number import getPrime
from libnum import n2s, s2n
from math import gcd

#r = process(['python3', 'chall.py'])
r = remote('localhost', 8041)

def encrypt(number: int) -> int:
    r.sendlineafter('>>> ', '1')
    r.sendlineafter('Data: ', n2s(number).hex().encode())
    r.recvuntil('Result: ')
    return s2n(r.recvtype(bytes))

n = 0

base = encrypt(16)
for i in range(17, 32):
    next = encrypt(i)
    mult = next * 16 - base * i
    n = gcd(n, mult)

print(n.bit_length())
e2 = encrypt(1) # e^2
e3 = encrypt(2) # 2 * e^3

e = (e3 * pow(e2 * 2, -1, n)) % n

assert(e * e % n == e2)
d = pow(e, -1, n)
M = (e * d - 1) // n

flag = d // M

print(n2s(flag))

## AES
Chall ini pada dasarnya mengimplementasikan suatu block cipher yang berdasarkan Feistel Network.

from aes import *
from typing import Tuple, List

BLOCK_SIZE = 32
ROUNDS = 10

class Immerspin:
    def __init__(self, master_key: bytes):
        assert(len(master_key) == 16)
        aes_base = AES(master_key)
        self.keys = aes_base._key_matrices[1:]
                
    def __bytesxor__(self, a: bytes, b: bytes) -> bytes:
        return bytes([i ^ j for i, j in zip(a, b)])
    
    def __mux__(self, state):
        state[0][0] ^= state[1][1] ^ (state[2][3] & 0x07)
        state[2][3] ^= state[3][1] >> 4
        state[1][2] ^= (state[0][2] >> 3) ^ state[3][0] & 0xf4
    
    def f(self, block: bytes, round_key) -> bytes:
        state = bytes2matrix(block)
        add_round_key(state, round_key)
        shift_rows(state)
        mix_columns(state)
        self.__mux__(state)
        return matrix2bytes(state)
    
    def round_encrypt(self, l_block: bytes, r_block: bytes, i: int) -> Tuple[bytes, bytes]:
        assert(i < len(self.keys))    
        return r_block, self.__bytesxor__(l_block, self.f(r_block, self.keys[i]))
    
    def encrypt_block(self, block: bytes) -> bytes:
        assert(len(block) == BLOCK_SIZE)
        l_block = block[:16]
        r_block = block[16:]
        for i in range(ROUNDS):
            l_block, r_block = self.round_encrypt(l_block, r_block, i)
        
        return l_block + r_block
    
    def encrypt_cbc(self, data: bytes, iv: bytes) -> bytes:
        assert(len(data) % BLOCK_SIZE == 0)
        assert(len(iv) == BLOCK_SIZE)
        
        blocks = [data[i: i+32] for i in range(0, len(data), BLOCK_SIZE)]
        prev = iv
        ct = b''
        for block in blocks:
            prev = self.encrypt_block(self.__bytesxor__(prev, block))
            ct += prev
        return ct

Kemudian, pada chall kita diberikan beberapa kesempatan untuk mengquery enkripsi menggunakan kunci yang sama, tetapi IV yang berbeda.

from immerspin import Immerspin, BLOCK_SIZE, ROUNDS
from Crypto.Util.Padding import pad
from hashlib import md5
from os import urandom

cipher = Immerspin(urandom(16))
FLAG = open('msg.txt', 'rb').read() # English text
IV = urandom(BLOCK_SIZE)
MSG = IV.hex() + cipher.encrypt_cbc(pad(FLAG, BLOCK_SIZE), IV).hex()

def main():
    print(f"Speeeen to wiin: {MSG}")
    for _ in range(ROUNDS - 1):
        pt = bytes.fromhex(input('Enc? (hex): '))
        pt = pt + md5(pt).digest() + pt
        iv = urandom(BLOCK_SIZE)
        ct = cipher.encrypt_cbc(pad(pt, BLOCK_SIZE), iv)
        print(f"iv={iv.hex()}")
        print(f"ct={ct.hex()}")
    print("Tschüss")
    
if __name__ == "__main__":
    try: main()
    except: exit(1)

Observasi terpenting dalam chall ini adalah bahwa cipher yang diimplementasikan seluruhnya linear. Fungsi round `f` melakukan add round key yang dapat direpresentasikan dengan operasi penjumlahan dalam `GF(2)`, dan tiga fungsi transformasi (shift rows, mix columns, mux) dapat direpresentasikan dengan operasi perkalian matrix `GF(2)`.

Kemudian, Feistel network sendiri hanya berupa swapping posisi `(l, r)`, sehingga secara sederhana, satu round dapat direpresentasikan sebagai `f = (M + K_i) * T` dimana `M` adalah plaintext, `K_i` adalah kunci round `i`, dan `T` adalah suatu matriks transformasi.

Untuk seluruh 10 round, enkripsi dapat dijabarkan sebagai berikut:

enc(M)
  = ((((M + K_1) * T + K_2) * T)....) + K_10 
  = M * T ^ 10 + K_1 * T ^ 10 + K_2 * T ^ 9 + ... + K_10
  = M * T ^ 10 + g(K)

dimana `g` adalah suatu fungsi yang hanya bergantung pada kunci cipher, karena `T` adalah **konstan** berdasarkan desain cipher sendiri.

### Solve dengan Invers Fungsi

Dari sini solve dapat dilakukan serupa dengan AES tanpa S-Box, misalnya sebagai berikut:

cr: @Wrth
https://wrth.medium.com/cracking-aes-without-any-one-of-its-operations-c42cdfc0452f


Solusi ini dijamin working, tetapi implementasinya cukup sulit, karena fungsi `T` yaitu fungsi transformasi harus dihitung, entah secara manual atau secara simbolik dengan sagemath/z3, agar inversnya dapat diperoleh.

### Solve dengan Transformasi Konstan

Ide solve ini pada dasarnya 'merubah kunci' yang digunakan ciphertext berdasarkan observasi sebagai berikut:
1. Initialize satu object cipher di lokal dengan kunci random `K1`, dan misalkan kunci yang digunakan server `K2`.
2. Untuk suatu message `M`, hitung `enc_lokal(M) = M * T ^ 10 + g(K1)` dan query `enc_server(M) = M * T ^ 10 + g(K2)`.
3. Hitung `enc_server(M) + enc_lokal(M) = g(K1) + g(K2)`. Ingat bahwa dalam `GF(2)`, operasi penjumlahan dan pengurangan ekuivalen, atau concisely, `a + a = 0`.
4. Hitung `enc_server(Flag) + g(K1) + g(K2) = Flag * T ^ 10 + g(K1).`

Perhatikan bahwa value terakhir yang kita hitung ekuivalen dengan `enc_lokal(Flag)`, atau dengan kata lain, kita memperoleh ciphertext flag yang dienkripsi dengan **kunci lokal**.

Langkah terakhir yang perlu dilakukan hanyalah mengimplementasikan dekripsi pada cipher, karena fungsi dekripsi tidak diberikan. Implementasi cukup sederhana, cukup mengikuti format dekripsi network Feistel dengan feeding `(l, r)` pada fungsi `f`. Invers dari shift_rows, mix_columns, dan mux tidak diperlukan sama sekali.

    def decrypt_block(self, block: bytes) -> bytes:
        assert(len(block) == BLOCK_SIZE)
        
        l_block = block[:16]
        r_block = block[16:]
        
        for i in range(ROUNDS - 1, -1, -1):
            l_block, r_block = self.round_decrypt(l_block, r_block, i)
        
        return l_block + r_block

    def decrypt(self, data: bytes) -> bytes:
        assert(len(data) % BLOCK_SIZE == 0)
        
        blocks = [data[i: i+32] for i in range(0, len(data), BLOCK_SIZE)]
        pt = b''
        for block in blocks:
            pt += self.decrypt_block(block)
        return pt
    
    def decrypt_cbc(self, data: bytes, iv: bytes) -> bytes:
        assert(len(data) % BLOCK_SIZE == 0)
        assert(len(iv) == BLOCK_SIZE)
        
        blocks = [data[i: i+32] for i in range(0, len(data), BLOCK_SIZE)]
        prev = iv
        ct = b''
        for block in blocks:
            dec = self.decrypt_block(block)
            ct += self.__bytesxor__(dec, prev)
            prev = bytes([i for i in block])
            
        return ct

### Solver
Solver menggunakan metode [Transformasi Konstan](#Solve-dengan-Transformasi-Konstan) dengan patching yang sesuai pada cipher.

from azunyan.conn import process, remote
from immerspin import Immerspin
from hashlib import md5
from Crypto.Util.Padding import pad

#r = process(['python3', 'chall.py'])
r = remote('localhost', 8042)
msg = r.recvafter(b'Speeeen to wiin: ', bytes)
iv_flag = msg[:32]
ct_flag = msg[32:]

cipher_ = Immerspin(b'password' * 2)

pt = b'w' * (len(ct_flag) // 2)
r.sendlineafter(b':', pt.hex().encode())
pt = pad(pt + md5(pt).digest() + pt, 32)
iv = r.recvafter(b'iv=', bytes)
ct = r.recvafter(b'ct=', bytes)

print(len(iv), len(pt), len(ct))
my_ct = cipher_.encrypt_cbc(pt, iv)
diff = cipher_.__bytesxor__(my_ct, ct)

ct_flag = cipher_.__bytesxor__(ct_flag, diff)
print(cipher_.decrypt_cbc(ct_flag, iv_flag))

## Notes
Fun fact: 2/3 chall ditargetkan kurang lebih 10 solve untuk kategori umum, dan sepertinya adjustment difficulty cukup sukses karena dua chall pertama memiliki sekitar 12 solve.