patarisac also known as patsac

CTF writeup : Gemastik XV Cryptography Challenges

01 Nov 2022

logo gemastik

Akhir pekan lalu, telah diadakan penyisihan Gemastik XV : Divisi II Keamanan Siber. Terdapat dua soal untuk kategori Cryptography yang dibuat oleh Lord CTF Cryptography Indonesia, tidak lain dan tidak bukan, ialah deomkicer.

Dua soal kategori cryptography tersebut adalah :

  1. doublesteg
  2. Relation
Penyisihan Gemastik XV : Divisi II Keamanan Siber dilaksanakan selama 5 jam dan beruntungnya saya berhasil mengerjakan kedua soal kategori cryptography, alias rata, hehe.

doublesteg

Soal

Description

Single STEG encryption is weak, how about double STEG encryption?

File

  • chall.py
  • flag.enc

chall.py

#!/usr/bin/env python3
from Crypto.Cipher import AES
from Crypto.Hash import SHA256
from Crypto.Util.Padding import *
import random

FLAG = open("flag.png", "rb").read()
STEG = b"gemasteg"


def getrandsteg():
    x = list(STEG)
    random.shuffle(x)
    return bytes(x)


def encrypt(msg: bytes, key: bytes):
    key = SHA256.new(key).digest()
    iv = STEG * 2
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc = aes.encrypt(msg)
    return enc


def double(msg: bytes, keys: list[bytes]):
    msg = pad(msg, AES.block_size)
    for key in keys:
        msg = encrypt(msg, key)
    return msg


def fwrite(filename: str, data: bytes):
    f = open(filename, "wb")
    f.write(data)
    f.close()


keys = [getrandsteg() for _ in range(2)]
fwrite("flag.enc", double(FLAG, keys))

Solution

Dari source chall.py dapat dilihat bahwa flag adalah file PNG dan dienkripsi dengan AES CBC dua kali dengan dua key berbeda. Untungnya, saya sudah pernah mengerjakan challenge serupa. Kita bisa menggunakan Meet-in-the-middle attack pada sistem seperti ini.


Meet-in-the-middle attack dapat dilakukan dengan melakukan bruteforce pada encryption dan decryption key, kemudian menyimpan kedua hasil bruteforce ke dalam sebuah dictionary dengan hasil enkripsi / dekripsi sebagai dictionary key dan encryption / decryption key sebagai value-nya. Setelah itu, kita buat dua set yang berisikan dictionary key dari kedua dictionary yang sudah kita bentuk, kemudian dari kedua set itu kita ambil intersection-nya, alias kita ambil isi yang sama. Seharusnya ada tepat satu isi yang sama. Setelah dapat intersection-nya, kita bisa dapat encryption key dengan mengambil value dari dictionary yang berisi hasil enkripsi, dan decryption key dengan mengambil value dari dictionary yang berisi hasil dekripsi.


Setelah mendapatkan kedua key, kita tinggal melakukan decryption AES CBC pada flag.enc dengan decryption key terlebih dahulu, kemudian melakukan decryption AES CBC lagi dengan encryption key. BOOM!!!. Kita berhasil mendapatkan flag.png.


“Talk is cheap. Show me the code.” ― Linus Torvalds

Berikut ini adalah full solvernya.

#!/usr/bin/python3
from Crypto.Hash import SHA256
from Crypto.Cipher import AES
from all_key import ALL_KEY

ENC = open("flag.enc", "rb").read()
STEG = b"gemasteg"
PLAIN = bytes.fromhex("89504E470D0A1A0A0000000D49484452")


def decrypt_cbc(msg: bytes, key: bytes):
    key = SHA256.new(key).digest()
    iv = STEG * 2
    aes = AES.new(key, AES.MODE_CBC, iv)
    plain = aes.decrypt(msg)
    return plain


def encrypt_cbc(msg: bytes, key: bytes):
    key = SHA256.new(key).digest()
    iv = STEG * 2
    aes = AES.new(key, AES.MODE_CBC, iv)
    enc = aes.encrypt(msg)
    return enc


def get_table(gas, isencrypt=False):
    table = {}
    msg = None
    if isencrypt:
        msg = PLAIN[:16]
    else:
        msg = ENC[:16]
    for key in ALL_KEY:
        custom = gas(msg, bytes(key))
        table[custom] = bytes(key)
    return table


def get_keys():
    block1 = ENC[:16]
    enc_table = get_table(encrypt_cbc, True)
    dec_table = get_table(decrypt_cbc)
    enc_table_set = set(enc_table.keys())
    dec_table_set = set(dec_table.keys())
    intersection = enc_table_set.intersection(dec_table_set).pop()
    key1 = enc_table[intersection]
    key2 = dec_table[intersection]
    return key1, key2


def main():
    key1, key2 = get_keys()
    if key1 == None:
        print("KEYs NOT FOUND")
        exit(0)
    print(f"{key1 = }")
    print(f"{key2 = }")
    mid = decrypt_cbc(ENC, key2)
    flag = decrypt_cbc(mid, key1)

    with open("flag.png", "wb") as f:
        f.write(flag)
        f.close()
    print("DONE GAN, CEK flag.png")

    return 0


if __name__ == "__main__":
    main()

Flag

flag.png

Gemastik2022{uji_nyali_encrypt_message_pakai_weak_key}

References


Relation

Soal

Description

Can you find the relation between these 2 encrypted files?

Hint

If you have decrypted the PNG header but the image is still corrupted (e.g. invalid CRC), remember that the block size is 191 bytes (except the last block)

File

  • chall.py
  • flag1.enc
  • flag2.enc
  • key.pem

chall.py

#!/usr/bin/env python3
from Crypto.PublicKey import RSA

FLAG = open("flag.png", "rb").read()
NBIT = 1536


def bytes_to_blocks(msg: bytes, size: int):
    return [msg[i : i + size] for i in range(0, len(msg), size)]


def blocks_to_bytes(blocks: list[bytes]):
    return b"".join(blocks)


def relation(pt: bytes, key):
    m1 = int.from_bytes(pt, "big")
    m2 = 7 * m1 + 7
    cts = []
    for m in [m1, m2]:
        assert m < key.n
        c = pow(m, key.e, key.n)
        ct = c.to_bytes(NBIT // 8, "big")
        cts.append(ct)
    return cts


def fwrite(filename: str, data: bytes):
    f = open(filename, "wb")
    f.write(data)
    f.close()


blocks = bytes_to_blocks(FLAG, (NBIT // 8) - 1)
rsa = RSA.generate(NBIT, e=7)

box1 = []
box2 = []

for block in blocks:
    cts = relation(block, rsa)
    box1.append(cts[0])
    box2.append(cts[1])

fwrite("flag1.enc", blocks_to_bytes(box1))
fwrite("flag2.enc", blocks_to_bytes(box2))
fwrite("key.pem", rsa.public_key().export_key())

Solution

Dari source chall.py, kita mengetahui bahwa flag adalah file PNG dan dienkripsi dengan RSA menghasilkan flag1.enc. Tetapi selain itu, flag juga dimodifikasi dengan persamaan linear kemudian dienkripsi dengan RSA menghasilkan flag2.enc. Setelah membacanya dan berpikir beberapa jam sambil googling. Saya akhirnya ingat saya pernah mengerjakan soal seperti ini juga. Kita bisa mendapatkan plaintext (flag) dengan melakukan Franklin-Reiter Related Message Attack.


Untuk solver Franklin-Reiter Related Message Attack saya menggunakan base solver dari salah satu sumber belajar cryptography terkenal, yaitu Crypton. Setelah memodifikasi sedikit untuk penyesuaian terhadap soal, akhirnya saya berhasil mendapatkan flag.png.


Berikut ini adalah full solvernya.

#!/usr/bin/sage

from Crypto.PublicKey import RSA
from Crypto.Util.number import bytes_to_long as b2l, long_to_bytes as l2b
from sage.all import *

def gcd(a, b): 
    while b:
        a, b = b, a % b
    return a.monic()

def franklinreiter(C1, C2, e, N, a, b):
    P.<X> = PolynomialRing(Zmod(N))
    g1 = (a*X + b)^e - C1
    g2 = X^e - C2
    result = -gcd(g1, g2).coefficients()[0]
    return hex(int(result))[2:]


def main():
    block = 192
    pubkey = open("key.pem", 'rb').read()
    pb = RSA.import_key(pubkey)
    enc1 = open("flag1.enc", 'rb').read()
    enc2 = open("flag2.enc", 'rb').read()
    png_bytes = b""
    for i in range(0, len(enc2), block):
        m = franklinreiter(b2l(enc2[i:i+block]), b2l(enc1[i:i+block]), pb.e, pb.n, 7, 7)
        if i < 67776:
            m = m.zfill(382)
        else:
            m = '0' + m
        png_bytes += bytes.fromhex(m)
    
    with open("flag.png", 'wb') as f:
        f.write(png_bytes)
        f.close()
    print("DONE CUY, CEK flag.png")


    return 0


if __name__ == "__main__":
    main()

Flag

flag.png

Gemastik2022{in_2022_FR_attack_is_everywhere}

References

Related posts