patarisac also known as patsac

CTF writeup : Gemastik XVI Cryptography Challenges

04 Aug 2023

logo gemastik

Babak penyisihan Gemastik XVI : Divisi II Keamanan Siber (2023) telah dilaksanakan akhir pekan lalu. Pada Gemastik tahun ini, ada tiga soal untuk kategori Cryptography yang dibuat oleh sepuh-sepuh CTF Cryptography Indonesia, yaitu prajnapras19 dan Chovid99.

Tiga soal kategori cryptography tersebut adalah :

  1. easy AES
  2. k-1
  3. naughty-boy
Penyisihan Gemastik XVI : Divisi II Keamanan Siber dilaksanakan selama 8 jam dan beruntungnya saya berhasil mengerjakan ketiga soal kategori cryptography tersebut.

easy AES

Soal

Description

Attack on AES OFB

File

Solution

Pada challenge ini kita harus memberikan secret yang random untuk mendapatkan flag. Pertama, kita lihat dulu skema enkripsi & dekripsi block cipher OFB mode.

logo gemastik logo gemastik

Dari skema di atas, kita ketahui bahwa enkripsi dan dekripsi OFB mode sama persis, hanya ditukar saja plaintext dan ciphertext-nya. Oleh karena itu, pada challenge ini kita bisa tinggal mengambil encrypted secret, kemudian encrypt kembali encrypted secret tersebut untuk mendapatkan secret yang asli. Tapi jangan lupa kalau secret hanya terdiri dari 128 byte sedangkan enkripsi pada service ditambahkan padding, sehingga kita harus mengambil 128 byte awal saja untuk mengambil secret.

Berikut ini adalah full solvernya.

#!/usr/bin/env python3
from patsac import *

if not args.LOCAL:
    with open("nc.sh") as f:
        NC = f.read().strip().split()
        f.close()
    SRVR = NC[1]
    PORT = NC[2]
    r = remote(SRVR, PORT, level="warning")
else:
    r = process("./chall.py", level="debug")


def main():
    r.sendlineafter(b"> ", b"2")
    r.recvuntil(b"ciphertext = ")
    ct0 = int(r.recvline(0).decode())
    r.sendlineafter(b"> ", b"1")
    r.sendlineafter(b"plaintext = ", str(ct0).encode())
    r.recvuntil(b"ciphertext = ")
    ct1 = int(r.recvline(0).decode())
    secret = str(bytes_to_long(long_to_bytes(ct1)[:128])).encode()
    r.sendlineafter(b"> ", b"3")
    r.sendlineafter(b"secret: ", secret)
    print(r.recv().decode())
    return 0


if __name__ == "__main__":
    main()

Flag

gemastik{33d4cfb92569d8f21851f9c3dc96c244c3e344064ffb0b35603a550802b7531e}

Note: Flag dinamis, berubah setiap interval tertentu.

References


k-1

Soal

Description

Shamir said we need k shares to recover the secret.

File

Solution

Untuk mendapatkan flag, kita perlu menghitung nilai password. Pada challenge ini kita diberikan nilai share yang isinya adalah x dan y dengan deskripsi sebagai berikut.
\[x = random\ 1024\ bits\ integer\] \[y = \displaystyle\sum_{i=0}^{k-1} coeffs_{i} \cdot x^{i}\] \[coeffs_{0} = password\]
Kita sudah tahu pasti coeffs[0] adalah password yang artinya password tidak dikalikan dengan x karena x pangkat 0 adalah 1. Itu artinya jika kita menghitung y modulo x, kita akan mendapatkan nilai password.

Berikut adalah full solvernya.

#!/usr/bin/env python3
from patsac import *

if not args.LOCAL:
    with open("nc.sh") as f:
        NC = f.read().strip().split()
        f.close()
    SRVR = NC[1]
    PORT = NC[2]
    r = remote(SRVR, PORT, level="warning")
else:
    r = process("./chall.py", level="debug")


def main():
    k = r.recvline(0)
    xy = r.recvline(0)[1:-1].split(b", ")
    x, y = int(xy[0]), int(xy[1])
    ans = str(y % x).encode()
    r.sendlineafter(b"password: ", ans)
    print(r.recv().decode())

    return 0


if __name__ == "__main__":
    main()

Flag

gemastik{a5061d673d03123fe19bbbcc853da16c9f6fee9e55c26f2c9b7b937b60c0ec83}

Note: Flag dinamis, berubah setiap interval tertentu.


naughty-boy

Soal

Description

La La La - Naughty Boy Lyrics La La, La La La La La na na na na na La La na na, La La La La La na na na na na La La, La La La La La na na na na na La La na na, La La La La La na na na na na

File

Solution

Untuk mendapatkan flag, kita harus mendapatkan secret_val. Pertama, kita bisa membedah terlebih dahulu nilai hint_2.
\[hint2 = hiddenval^{4 \cdot modd}\mod{modd}\] \[Fermat\ little\ theorem\] \[hint2 = hiddenval^{4}\mod{modd}\]
Karena hint2 adalah hiddenval pangkat 4 mod modd, maka kita bisa menghitung hiddenval dengan menghitung akar kuadrat dari hint2 sebanyak dua kali, dalam kata lain kita menghitung quadratic residue sebanyak dua kali. Dalam kasus ini saya menggunakan solusi Lagrange untuk menghitung quadratic residue dengan syarat sebagai berikut.
\[Syarat\] \[modd \equiv 3\pmod{4}\] \[Solusi\ Lagrange\] \[hiddenval\_kuadrat \equiv \pm hint2^{(modd+1)/4}\pmod{modd}\] \[hiddenval \equiv \pm hiddenval\_kuadrat^{(modd+1)/4}\pmod{modd}\]
Setelah sudah mendapatkan hiddenval, selanjutnya mencari z3. Prediksi z3 bisa dihitung dengan mencari dahulu nilai rand1.
\[hiddenval = z1 \cdot z2 \cdot z3 + rand1\] \[hiddenval = n \cdot z3 + rand1\] \[rand1 \approx hiddenval\mod{n}\] \[z3 = (hiddenval-rand1)/n\]
Sambil mencari z3, kita juga bisa langsung mencari nilai z2 dengan cara yang hampir sama dengan mencari nilai z3 tetapi dengan hint1.
\[hint1 = z3^{8} \cdot z2 + 0x1337 \cdot z2 \cdot z1^{2} + rand2\] \[hint1 = z3^{8} \cdot z2 + n \cdot z1 \cdot 0x1337 + rand2\] \[hint1\mod{z3^{8}} \approx n \cdot z1 \cdot 0x1337 + rand2\] \[z3^{8} \cdot z2 \approx hint1 - (hint1\mod{z3^{8}})\] \[z2 \approx [hint1-(hint1\mod{z3^{8}})] / z3^{8}\]
Dengan begitu, jika sudah mendapatkan z2, karena n = z1 x z2, maka kita bisa menghitung z1 serta melakukan dekripsi RSA seperti biasa untuk mendapatkan secret 🫠

Berikut ini adalah full solvernya.

#!/usr/bin/env python3
from patsac import *

if not args.LOCAL:
    with open("nc.sh") as f:
        NC = f.read().strip().split()
        f.close()
    SRVR = NC[1]
    PORT = NC[2]
    r = remote(SRVR, PORT, level="warning")
else:
    r = process("./chall.py", level="debug")


def recon():
    global r, SRVR, PORT
    r.close()
    if not args.LOCAL:
        r = remote(SRVR, PORT, level="warning")
    else:
        r = process("./chall.py", level="debug")


def prev_prime(n):
    n -= 2
    n |= 1
    while not isPrime(n):
        n -= 2
    return n


def main():
    global r
    while True:
        e = 65537
        r.recvuntil(b"c = ")
        c = int(r.recvline(0))
        r.recvuntil(b"n = ")
        n = int(r.recvline(0))
        r.recvuntil(b"modd = ")
        modd = int(r.recvline(0))
        if modd % 4 != 3:
            print("Nilai modd belum cocok. Reconnecting...")
            recon()
            continue
        r.recvuntil(b"hint_1 = ")
        hint1 = int(r.recvline(0))
        r.recvuntil(b"hint_2 = ")
        hint2 = int(r.recvline(0))

        # hitung nilai hidden_val dengan 2 kali hitung quadratic residue
        test = pow(hint2, divexact(modd + 1, 4), modd)
        test = pow(test, divexact(modd + 1, 4), modd)
        if test.bit_length() > 1280:
            test = -test % modd

        # hitung nilai asli hidden_val (kurangin dengan rand_1)
        rand1 = test % n
        z123 = test - rand1

        # prediksi nilai z3
        z3 = divexact(z123, n)
        while z3.bit_length() >= 256 and rand1.bit_length() <= 1035:
            z3 = prev_prime(z3)
            z123 = n * z3
            rand1 = test - z123
            if z3.bit_length() == 256 and rand1.bit_length() == 1035:
                # cari nilai z2
                sisa = hint1 % pow(z3, 8)
                z32 = hint1 - sisa
                z2 = int(divexact(z32, pow(z3, 8)))
                # kalau n % z2 == 0, artinya inilah z3 yang benar
                if n % z2 == 0:
                    break

        # dekripsi rsa seperti biasa
        z1 = divexact(n, z2)
        phi = (z1 - 1) * (z2 - 1)
        d = pow(e, -1, phi)
        secret = str(pow(c, d, n)).encode()
        r.sendlineafter(b"What is the secret: ", secret)
        r.recvuntil(b"GG! Here is your prize:\n")
        print(r.recvline(0).decode())
        break

    return 0


if __name__ == "__main__":
    main()

Flag

gemastik{643dba5a7e68ce4f395bc78ed366284baa146d2f7f76cd507128fc8a6dba910d}

Note: Flag dinamis, berubah setiap interval tertentu.

References


Penutup

Solusi yang tertulis dalam artikel ini adalah solusi yang saya kerjakan sendiri ketika babak penyisihan dan mungkin saja bukan solusi paling optimal atau solusi yang diharapkan oleh problem setter. Seluruh source code soal babak penyisihan Gemastik Divisi Keamanan Siber 2023 serta intended solution dari problem setter dapat dilihat di Repository Github.

Related posts