Post

TCP1P CTF 2024

Posted Updated
TCP1P CTF 2024.
TCP1P CTF 2024.
By swusjask
33 min read
TCP1P CTF 2024

Saya bermain dengan tim dimas fans club yang dicarry berat sehingga dapat posisi pertama.

Scoreboard

Untuk kategori cryptography, tim kami berhasil menyelesaikan 6 dari 7 soal yang ada. Berikut ini adalah writeup dari soal-soal yang kami selesaikan.

TCP51Prime

1
2
3
4
5
6
7
8
9
10
11

from secret import a,b,p,flag
from hashlib import sha512
from pwn import xor
from Crypto.Util.number import isPrime

assert p == a**51 + 51*b**51 and isPrime(p) and a > 0 and b > 0
print(hex(p)[2:])
print(xor(flag,sha512((str(a)+str(b)).encode()).digest()).hex())

# ... (output)
# ... (output)

Ringkasan

Diberikan $p$ adalah sebuah bilangan prima dengan suatu parameter rahasia $a^{51} + 51b^{51}$ dan $a,b > 0$. Untuk mendapatkan flag diharuskan mendapatkan nilai $a$ dan $b$ yang benar.

Solusi

Kita bisa mendapatkan nilai $a$ dan $b$ sebagai berikut. Perhatikan bahwa

\[\begin{align*} a^{51} + 51b^{51} &\equiv 0 &\pmod p \\ a^{51} &\equiv -51b^{51} &\pmod p \\ \left({a \over b}\right)^{51} &\equiv -51 &\pmod p \\ {a \over b} &\equiv \sqrt[51]{-51} &\pmod p \\ \end{align*}\]

Kita dapat mencari akar dengan mudah karena persamaan tersebut berada pada modulo bilangan prima. Dan untuk mendapatkan nilai $a$ dan $b$ sendiri, karena nilainya jauh lebih kecil dibanding $p$, kita bisa mendapatkannya dengan menggunakan fungsi rational_reconstruction dari library sage (teknik ini sebenarnya bisa juga menggunakan lattice reduction). Berikut ini script yang dijalankan untuk mendapatkan flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

from sage.all import *
from hashlib import sha512
from pwn import xor


p = ...

Fp = GF(p)
x = int(Fp(-51).nth_root(51))
a_div_b = rational_reconstruction(x, p)


a = a_div_b.numerator()
b = a_div_b.denominator()

assert p == a**51 + 51*b**51

out = bytes.fromhex("...")
print(xor(out,sha512((str(a)+str(b)).encode()).digest()))

Flag: TCP1P{prime_prime_prime_prime_prime_prime_prime_prime_prime_prime}

That one RSA challenge

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

from Crypto.Util.number import *
from secret import flag
z = 567
p = getPrime(1024)
q = getPrime(1024)
n = p*q
c = pow(bytes_to_long(flag), 65537, n)
tot = (p-1) * (q-1)
d = int(pow(65537, -1, tot))
dinv = int(pow(d, -1, n))

h = int(dinv >> z)
hpq = (int((p+q)>> z))

with open('out.txt', 'w+') as f:
    f.write(f'{n=}\n')
    f.write(f'{h=}\n')
    f.write(f'{hpq=}\n')
    f.write(f'{c=}\n')

Ringkasan

Diberikan hint yaitu upper bit dari $p+q$ dan $dinv$ secara berurutan adalah $hpq$ dan $h$. Jika kita misalkan lower bit dari $p+q$ adalah $x$ dan lower bit dari $dinv$ adalah $y$. Maka

\[\begin{align*} p+q &= 2^zhpq + x \\ dinv &= 2^zh + y \quad x,y < 2^z \\ \end{align*}\]

Sehingga diperoleh (misalkan $e=65537$)

\[\begin{align*} d \cdot dinv &\equiv 1 &\pmod{n} \\ ed \cdot dinv &\equiv e &\pmod{n} \\ (1 + k(p-1)(q-1))dinv - e &\equiv 0 &\pmod{n} \\ (1 + k(n - (p+q) - 1))dinv - e &\equiv 0 &\pmod{n} \\ (1 - k(p+q - 1))dinv - e &\equiv 0 &\pmod{n} \\ (1 - k(2^zhpq + x - 1))(2^zh + y) - e &\equiv 0 &\pmod{n} \\ \end{align*}\]

Dengan melakukan bruteforce dalam $k$, karena nilainya cukup kecil karena $k < e$, kita bisa mencari small root bivariate coppersmith dalam $x$ dan $y$. Setelah itu, kita bisa mendapatkan pemfaktoran $n$ dan bisa mendekripsi ciphertext.

Solusi

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

import sys
from tqdm import tqdm
from multiprocessing import Pool, cpu_count
from Crypto.Util.number import long_to_bytes

sys.path.append("../../../lattice-based-cryptanalysis")
from lbc_toolkit import small_roots

n = 13986357905153484822874300783445968480194277882812317554826224241536479785567487956712558237728345348661360577246137576216953724039680969623887884690471844396542763308129517234365819619617071449273126659007918716307793788623728052337632935762139796688014791419718949572448772521789488223910450877828732015095423443037519388747356327730350934152781671783952028215703864406564741666179193772037496984854699143314813242721157017296866888522135989818414587193505121794302821401677072507471357592358012342178011963104524959087968374300060349343826214249928530346877968114749229074874962737714935221065368318487049394644831
h = 10474216468878927114435400909130676124750910912012236182806861194655854223324539867768381265996955193355030239325750528328250897464859373863289680002879536341349759323910048168674147097644573874679268018966497862685092382336865554114348153248267599439087357199554652601126191061921516650448119261614064051599968120061991607030873881013657693987836636730528537557619595799676312850875727477092697270452300532360780188724484703363561848754770976459
hpq = 492124417091708682668644108145880307537308922842816506360717440112116492381514432506339907757228214359689270777951081610062506962769167209
c = 4715651972688371479449666526727240348158670108161494767004202259402013317642418593561463200947908841531208327599049414587586292570298317049448560403558027904798159589477994992384199008976859139072407664659830448866472863679123027179516506312536814186903687358198847465706108667279355674105689763404474207340186200156662095468249081142604074167178023479657021133754055107459927667597604156397468414872149353231061997958301747136265344906296373544580143870450924707559398134384774201700278038470171319329716930036843839101955981274793386611943442507144153946307781795085665793554799349509983282980591388585613674226899
z = 567

# Polynomial ring declaration
P.<x, y> = PolynomialRing(ZZ)

# Worker function to process each iteration
def worker(k):
    f = (1 - k * ((hpq << z) + x - 1)) * ((h << z) + y) - 65537
    try:
        roots = small_roots(f.change_ring(Zmod(n)), (2**z, 2**z), algorithm='resultants', m=2, d=1)
        if roots:
            print(f"found in {k}")
            true_x = ZZ(roots[0][0])
            p_plus_q = (hpq << z) + true_x
            p_minus_q = (p_plus_q**2 - 4 * n).sqrt()
            p = (p_plus_q + p_minus_q) // 2
            q = n // p

            # Check factorization correctness
            assert p * q == n
            d = pow(65537, -1, (p-1)*(q-1))
            m = int(pow(c, d, n))
            decrypted_message = long_to_bytes(m)
            print(decrypted_message)
            
            return None
    except Exception:
        return None

# Function to parallelize the loop using multiprocessing
def parallel_loop():
    # Define the range of k1
    k_range = range(65537)

    # Set up multiprocessing pool
    with Pool(processes=cpu_count()) as pool:
        # Use tqdm to show progress bar
        list(tqdm(pool.imap(worker, k_range), total=len(k_range)))

# Call the parallel loop function
if __name__ == '__main__':
    parallel_loop()

Flag: TCP1P{AmEeeeeEE33333eeee333_T_T_8883938ef7571cc2}

talking phase

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147

import random
import time
import base64
from messages import *
from secret import flag
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding

class Entity:
	def __init__(self, name):
		self.name = name
		self.privself = None
		self.pubself = None
		self.pubpeer = None
		self.crypt_init()

	def checkflag(self, message):
		if message == b"giv me the flag you damn donut":
			return True
		else:
			return False

	def crypt_init(self):
		self.privself = rsa.generate_private_key(public_exponent=65537,key_size=2048,)
		self.pubself = self.privself.public_key()

	def send_key(self, receiver):
		pubpem = base64.b64encode(self.pubself.public_bytes(encoding=serialization.Encoding.PEM, format=serialization.PublicFormat.SubjectPublicKeyInfo)).decode()
		receiver.receive_key(self, pubpem)

	def send_key_too(self, receiver):
		pubpem = base64.b64encode(self.pubself.public_bytes(encoding=serialization.Encoding.PEM, format=serialization.PublicFormat.SubjectPublicKeyInfo)).decode()
		receiver.receive_key_too(self, pubpem)

	def receive_key(self, sender, key):
		try:
			self.pubpeer = serialization.load_pem_public_key(base64.b64decode(key))
			self.send_key_too(sender)
		except:
			print("[!] Error, Shutting down...")
			exit()

	def receive_key_too(self, sender, key):
		try:
			self.pubpeer = serialization.load_pem_public_key(base64.b64decode(key))
			return
		except:
			print("[!] Error, Shutting down...")
			exit()

	def encrypt_message(self, plaintext):
		msg = self.pubpeer.encrypt(plaintext.encode(), padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),algorithm=hashes.SHA256(),label=None))
		return base64.b64encode(msg)


	def decrypt_message(self, ciphertext):
		ciphertext = base64.b64decode(ciphertext)
		msg = self.privself.decrypt(ciphertext,padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),algorithm=hashes.SHA256(),label=None))
		return msg

	def send_message(self, receiver, message):
		time.sleep(random.uniform(0.5, 1.5))
		encrypted_message = self.encrypt_message(message).decode()
		receiver.receive_message(self, encrypted_message)

	def receive_message(self, sender, message):
		try:
			decrypted_message = self.decrypt_message(message)
			if self.checkflag(decrypted_message):
				msg_sent = flag
			else:
				msg_sent = random.choice(message_choice)

			self.send_message(sender, msg_sent)
		except:
			print("[!] Error, Shutting down...")
			exit()


class Attacker:
	def __init__(self, entityone, entitytwo):
		self.entityone = entityone
		self.entitytwo = entitytwo

	def relay_message(self, receiver, message):
		receiver.receive_message(self, message)

	def receive_message(self, sender, message):
		print(f"{sender.name}: {message}")
		tamp = input(f"{sender.name} (tamper): ")
		if tamp == "fwd":
			msg_sent = message
		else:
			msg_sent = tamp.encode()

		if sender == self.entityone:
			self.relay_message(self.entitytwo, msg_sent)
		elif sender == self.entitytwo:
			self.relay_message(self.entityone, msg_sent)

	
	def relay_key(self, receiver, key):
		receiver.receive_key(self, key)

	def relay_key_too(self, receiver, key):
		receiver.receive_key_too(self, key)

	def receive_key(self, sender, key):
		print(f"{sender.name}: {key}")
		tamp = input(f"{sender.name} (tamper): ")
		if tamp == "fwd":
			key_sent = key
		else:
			key_sent = tamp.encode()

		if sender == self.entityone:
			self.relay_key(self.entitytwo, key_sent)
		elif sender == self.entitytwo:
			self.relay_key(self.entityone, key_sent)

	def receive_key_too(self, sender, key):
		print(f"{sender.name}: {key}")
		tamp = input(f"{sender.name} (tamper): ")
		if tamp == "fwd":
			key_sent = key
		else:
			key_sent = tamp

		if sender == self.entityone:
			self.relay_key_too(self.entitytwo, key_sent)
		elif sender == self.entitytwo:
			self.relay_key_too(self.entityone, key_sent)


entity_a = Entity("Entity A")
entity_b = Entity("Entity B")
entity_c = Attacker(entity_a, entity_b)


def begin_communication():
	while True:
		entity_a.send_key(entity_c)
		entity_a.send_message(entity_c, random.choice(message_choice))

begin_communication()

Appresiasi kepada mas jossie yang sudah menyelesaikan soal ini pada waktu kompetisi.

Ringkasan

Diberikan suatu protokol enkripsi dengan melakukan key exchange terlebih dahulu di awal. Di sini, kita sebagai attacker bisa melakukan relay key exchange maupun relay message dan melakukan tampering di tengah-tengah komunikasi.

Solusi

Seperti yang sudah dijelaskan di atas, dengan kita bisa menjadi pihak diantara kedua orang yang sedang berkomunikasi. Kita bisa melakukan serangan man-in-the-middle. Yaitu dengan memberikan kunci palsu kita kepada A dan B. Sehingga semua pesan yang dikirim dan diterima oleh A dan B bisa kita atur. Berikut ini script yang digunakan untuk mendapatkan flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80

from pwn import *
import base64
from messages import *
from cryptography.hazmat.primitives.asymmetric import rsa
from cryptography.hazmat.primitives import serialization
from cryptography.hazmat.primitives import hashes
from cryptography.hazmat.primitives.asymmetric import padding


class Entity:
	def __init__(self, name):
		self.name = name
		self.privself = None
		self.pubself = None
		self.pubpeer = None
		self.crypt_init()

	def checkflag(self, message):
		if message == b"giv me the flag you damn donut":
			return True
		else:
			return False

	def crypt_init(self):
		self.privself = rsa.generate_private_key(public_exponent=65537,key_size=2048,)
		self.pubself = self.privself.public_key()

	def send_key(self):
		pubpem = base64.b64encode(self.pubself.public_bytes(encoding=serialization.Encoding.PEM, format=serialization.PublicFormat.SubjectPublicKeyInfo)).decode()
		return pubpem

	def send_key_too(self, receiver):
		pubpem = base64.b64encode(self.pubself.public_bytes(encoding=serialization.Encoding.PEM, format=serialization.PublicFormat.SubjectPublicKeyInfo)).decode()
		receiver.receive_key_too(self, pubpem)

	def receive_key(self, sender, key):
		try:
			self.pubpeer = serialization.load_pem_public_key(base64.b64decode(key))
			# print("Loaded key")
			# self.send_key_too(sender)
		except:
			print("[!] Error, Shutting down...")
			exit()


	def encrypt_message(self, plaintext):
		msg = self.pubpeer.encrypt(plaintext.encode(), padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),algorithm=hashes.SHA256(),label=None))
		return base64.b64encode(msg)


	def decrypt_message(self, ciphertext):
		ciphertext = base64.b64decode(ciphertext)
		msg = self.privself.decrypt(ciphertext,padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),algorithm=hashes.SHA256(),label=None))
		return msg

# f=process(["python3","chall.py"])
f=remote("ctf.tcp1p.team","1965")
fake_a = Entity("Entity A")
fake_b = Entity("Entity B")
pub_A = f.readline().strip(b"Entity A: ").decode()
fake_b.receive_key(fake_a, pub_A)
print("[*] sending key")
f.sendline(fake_a.send_key().encode())
pub_B = f.readline().strip(b"Entity A (tamper): Entity B: ").decode().rstrip()
print(pub_B)
fake_a.receive_key(fake_b, pub_B)
f.sendline(fake_b.send_key().encode())
msg_a = f.readline().strip(b"Entity B (tamper): Entity A: ").decode()

print(fake_b.decrypt_message(msg_a))


tamper_a = fake_a.encrypt_message("giv me the flag you damn donut")
print('='*32)
print(tamper_a)
f.sendline(tamper_a)
msg_b = f.readline().strip(b"Entity A (tamper): Entity B: ").decode()
print(fake_a.decrypt_message(msg_b))

f.close()

Flag: TCP1P{smooth_talker_or_talk_smoother}

Guessing Master

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

import math
import os
from Crypto.Random import random

def bin2hex(binary):
    return hex(int(binary,2))[2:]

def hex2bin(msg):
    return bin(int(msg, 16))[2:]

def count_bit(data_length):
    i = 0
    while (1 << i) - 1 < i + data_length:
        i += 1
    return i

def flip_bit(binary, index):
    return binary[:index] + ('1' if binary[index] == '0' else '0') + binary[index+1:]

def add_bit(index, data):
    output = 0
    length = len(data) + count_bit(len(data)) + 1
    for i in range(1, length):
        if (i & (i - 1)) != 0 and (i >> (index - 1)) & 1:
            output ^= int(data[i - math.ceil(math.log2(i)) - 1])
    return str(output)

def random_flip(binary):
    binary = binary[::-1]
    length = len(binary) + count_bit(len(binary)) + 1
    encoded = ""
    index = 0
    for i in range(1, length):
        if math.log2(i) % 1 == 0: 
            bit = add_bit(int(math.log2(i)) + 1, binary)
            encoded += bit
        else:
            encoded += binary[index]
            index += 1
    rand = random.randrange(0, len(encoded))
    flipped = flip_bit(encoded, rand)
    return flipped[::-1], rand

def main():
    flag = open("flag.txt", "rb").read()
    binarys = hex2bin(flag.hex())
    output = []
    for binary in binarys:
        temp = hex2bin(os.urandom(16).hex())
        encoded, rand = random_flip(temp)
        if int(binary):
            output.append([bin2hex(encoded), rand])
        else:
            output.append([bin2hex(encoded), random.randrange(0, len(encoded))])
    print(output)

if __name__ == "__main__":
    main()

Appresiasi kepada mas jossie yang sudah menyelesaikan soal ini pada waktu kompetisi.

Ringkasan

Pada soal dilakukan encoding yang terjadi pada fungsi random_flip. Pada fungsi tersebut juga dilakukan flipping pada bit secara acak. Setiap bit pada flag akan mempengurah output diberikan, yaitu jika bit bernilai 1 maka bit yang diflip sesuai, sedangkan jika bit bernilai 0 maka bit yang diflip tidak sesuai.

Solusi

Karena pada output diketahui bit yang diflip, kita bisa melakukan decoding ulang. Dan melakukan random_flip sekali lagi pada hasil decoding. Jika hasilnya sama dengan output yang diberikan, maka bit tersebut adalah 1, jika tidak maka bit tersebut adalah 0. Berikut ini script yang digunakan untuk mendapatkan flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78

import math
import os
from Crypto.Random import random
from Crypto.Util.number import *

enc_flag = eval(open("output.txt", "r").read())

def bin2hex(binary):
    return hex(int(binary,2))[2:]

def hex2bin(msg):
    return bin(int(msg, 16))[2:]

def count_bit(data_length):
    i = 0
    while (1 << i) - 1 < i + data_length:
        i += 1
    return i

def flip_bit(binary, index):
    return binary[:index] + ('1' if binary[index] == '0' else '0') + binary[index+1:]

def add_bit(index, data):
    output = 0
    length = len(data) + count_bit(len(data)) + 1
    for i in range(1, length):
        if (i & (i - 1)) != 0 and (i >> (index - 1)) & 1:
            output ^= int(data[i - math.ceil(math.log2(i)) - 1])
    return str(output)

def random_flip(binary,rnd):
    binary = binary[::-1]
    length = len(binary) + count_bit(len(binary)) + 1
    encoded = ""
    index = 0
    for i in range(1, length):
        if math.log2(i) % 1 == 0: 
            bit = add_bit(int(math.log2(i)) + 1, binary)
            encoded += bit
        else:
            encoded += binary[index]
            index += 1
    rand = rnd
    flipped = flip_bit(encoded, rand)
    return flipped[::-1], rand

def decode(binary,rnd):
    binary = binary[::-1]
    binary = flip_bit(binary,rnd)
    decoded = ""
    index = 0
    for i in range(1,len(binary)+1):
        if math.log2(i) % 1 == 0:
            index+=1
        else:
            decoded += binary[index]
            index += 1
    
    return decoded[::-1]


def main():
    flag=""
    for i in enc_flag:
        enc,rnd = i[0],i[1]
        enc = hex2bin(enc)
        try:
            dec = decode(enc,rnd)
            temp = random_flip(dec,rnd)
            if temp[0] == hex2bin(i[0]):
                flag+="1"
            else:
                flag+="0"
        except:
            flag+="1"
    print(long_to_bytes(int(flag,2)))
if __name__ == "__main__":
    main()

Flag: TCP1P{now_you_are_the_guessing_master}

What’s the Worst That Could Happen

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

from Crypto.Util.Padding import pad
from aes import AES
from secret import flag
import os

c = AES(os.urandom(16))

admin_id = os.urandom(8).hex().encode()
enc_id = c.encrypt(admin_id)

print(f"Encrypted ID: {enc_id.hex()}")

while True:
    print("1. Encrypt")
    print("2. Admin Login")
    print("3. Exit")
    choice = int(input(">> "))
    if choice == 1:
        msg = input("message: ").encode()
        msg = pad(msg, 16)
        msg_block = [msg[i:i+16] for i in range(0, len(msg), 16)]
        ct_block = []
        for m in msg_block:
            ct_block.append(c.encrypt(m))
        print("Encrypted:", b''.join(ct_block).hex())
    elif choice == 2:
        id = input("Enter ID: ")
        if id.encode() == admin_id:
            print("Welcome Admin!")
            print(flag)
        else:
            print("Invalid ID")
    elif choice == 3:
        break
    else:
        print("Invalid Choice")

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222

#!/usr/bin/env python
from Crypto.Util.number import *

"""
    Copyright (C) 2012 Bo Zhu http://about.bozhu.me

    Permission is hereby granted, free of charge, to any person obtaining a
    copy of this software and associated documentation files (the "Software"),
    to deal in the Software without restriction, including without limitation
    the rights to use, copy, modify, merge, publish, distribute, sublicense,
    and/or sell copies of the Software, and to permit persons to whom the
    Software is furnished to do so, subject to the following conditions:

    The above copyright notice and this permission notice shall be included in
    all copies or substantial portions of the Software.

    THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
    IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
    FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
    THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
    LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
    FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
    DEALINGS IN THE SOFTWARE.
"""

Sbox = (
    0x63, 0x7C, 0x77, 0x7B, 0xF2, 0x6B, 0x6F, 0xC5, 0x30, 0x01, 0x67, 0x2B, 0xFE, 0xD7, 0xAB, 0x76,
    0xCA, 0x82, 0xC9, 0x7D, 0xFA, 0x59, 0x47, 0xF0, 0xAD, 0xD4, 0xA2, 0xAF, 0x9C, 0xA4, 0x72, 0xC0,
    0xB7, 0xFD, 0x93, 0x26, 0x36, 0x3F, 0xF7, 0xCC, 0x34, 0xA5, 0xE5, 0xF1, 0x71, 0xD8, 0x31, 0x15,
    0x04, 0xC7, 0x23, 0xC3, 0x18, 0x96, 0x05, 0x9A, 0x07, 0x12, 0x80, 0xE2, 0xEB, 0x27, 0xB2, 0x75,
    0x09, 0x83, 0x2C, 0x1A, 0x1B, 0x6E, 0x5A, 0xA0, 0x52, 0x3B, 0xD6, 0xB3, 0x29, 0xE3, 0x2F, 0x84,
    0x53, 0xD1, 0x00, 0xED, 0x20, 0xFC, 0xB1, 0x5B, 0x6A, 0xCB, 0xBE, 0x39, 0x4A, 0x4C, 0x58, 0xCF,
    0xD0, 0xEF, 0xAA, 0xFB, 0x43, 0x4D, 0x33, 0x85, 0x45, 0xF9, 0x02, 0x7F, 0x50, 0x3C, 0x9F, 0xA8,
    0x51, 0xA3, 0x40, 0x8F, 0x92, 0x9D, 0x38, 0xF5, 0xBC, 0xB6, 0xDA, 0x21, 0x10, 0xFF, 0xF3, 0xD2,
    0xCD, 0x0C, 0x13, 0xEC, 0x5F, 0x97, 0x44, 0x17, 0xC4, 0xA7, 0x7E, 0x3D, 0x64, 0x5D, 0x19, 0x73,
    0x60, 0x81, 0x4F, 0xDC, 0x22, 0x2A, 0x90, 0x88, 0x46, 0xEE, 0xB8, 0x14, 0xDE, 0x5E, 0x0B, 0xDB,
    0xE0, 0x32, 0x3A, 0x0A, 0x49, 0x06, 0x24, 0x5C, 0xC2, 0xD3, 0xAC, 0x62, 0x91, 0x95, 0xE4, 0x79,
    0xE7, 0xC8, 0x37, 0x6D, 0x8D, 0xD5, 0x4E, 0xA9, 0x6C, 0x56, 0xF4, 0xEA, 0x65, 0x7A, 0xAE, 0x08,
    0xBA, 0x78, 0x25, 0x2E, 0x1C, 0xA6, 0xB4, 0xC6, 0xE8, 0xDD, 0x74, 0x1F, 0x4B, 0xBD, 0x8B, 0x8A,
    0x70, 0x3E, 0xB5, 0x66, 0x48, 0x03, 0xF6, 0x0E, 0x61, 0x35, 0x57, 0xB9, 0x86, 0xC1, 0x1D, 0x9E,
    0xE1, 0xF8, 0x98, 0x11, 0x69, 0xD9, 0x8E, 0x94, 0x9B, 0x1E, 0x87, 0xE9, 0xCE, 0x55, 0x28, 0xDF,
    0x8C, 0xA1, 0x89, 0x0D, 0xBF, 0xE6, 0x42, 0x68, 0x41, 0x99, 0x2D, 0x0F, 0xB0, 0x54, 0xBB, 0x16,
)

InvSbox = (
    0x52, 0x09, 0x6A, 0xD5, 0x30, 0x36, 0xA5, 0x38, 0xBF, 0x40, 0xA3, 0x9E, 0x81, 0xF3, 0xD7, 0xFB,
    0x7C, 0xE3, 0x39, 0x82, 0x9B, 0x2F, 0xFF, 0x87, 0x34, 0x8E, 0x43, 0x44, 0xC4, 0xDE, 0xE9, 0xCB,
    0x54, 0x7B, 0x94, 0x32, 0xA6, 0xC2, 0x23, 0x3D, 0xEE, 0x4C, 0x95, 0x0B, 0x42, 0xFA, 0xC3, 0x4E,
    0x08, 0x2E, 0xA1, 0x66, 0x28, 0xD9, 0x24, 0xB2, 0x76, 0x5B, 0xA2, 0x49, 0x6D, 0x8B, 0xD1, 0x25,
    0x72, 0xF8, 0xF6, 0x64, 0x86, 0x68, 0x98, 0x16, 0xD4, 0xA4, 0x5C, 0xCC, 0x5D, 0x65, 0xB6, 0x92,
    0x6C, 0x70, 0x48, 0x50, 0xFD, 0xED, 0xB9, 0xDA, 0x5E, 0x15, 0x46, 0x57, 0xA7, 0x8D, 0x9D, 0x84,
    0x90, 0xD8, 0xAB, 0x00, 0x8C, 0xBC, 0xD3, 0x0A, 0xF7, 0xE4, 0x58, 0x05, 0xB8, 0xB3, 0x45, 0x06,
    0xD0, 0x2C, 0x1E, 0x8F, 0xCA, 0x3F, 0x0F, 0x02, 0xC1, 0xAF, 0xBD, 0x03, 0x01, 0x13, 0x8A, 0x6B,
    0x3A, 0x91, 0x11, 0x41, 0x4F, 0x67, 0xDC, 0xEA, 0x97, 0xF2, 0xCF, 0xCE, 0xF0, 0xB4, 0xE6, 0x73,
    0x96, 0xAC, 0x74, 0x22, 0xE7, 0xAD, 0x35, 0x85, 0xE2, 0xF9, 0x37, 0xE8, 0x1C, 0x75, 0xDF, 0x6E,
    0x47, 0xF1, 0x1A, 0x71, 0x1D, 0x29, 0xC5, 0x89, 0x6F, 0xB7, 0x62, 0x0E, 0xAA, 0x18, 0xBE, 0x1B,
    0xFC, 0x56, 0x3E, 0x4B, 0xC6, 0xD2, 0x79, 0x20, 0x9A, 0xDB, 0xC0, 0xFE, 0x78, 0xCD, 0x5A, 0xF4,
    0x1F, 0xDD, 0xA8, 0x33, 0x88, 0x07, 0xC7, 0x31, 0xB1, 0x12, 0x10, 0x59, 0x27, 0x80, 0xEC, 0x5F,
    0x60, 0x51, 0x7F, 0xA9, 0x19, 0xB5, 0x4A, 0x0D, 0x2D, 0xE5, 0x7A, 0x9F, 0x93, 0xC9, 0x9C, 0xEF,
    0xA0, 0xE0, 0x3B, 0x4D, 0xAE, 0x2A, 0xF5, 0xB0, 0xC8, 0xEB, 0xBB, 0x3C, 0x83, 0x53, 0x99, 0x61,
    0x17, 0x2B, 0x04, 0x7E, 0xBA, 0x77, 0xD6, 0x26, 0xE1, 0x69, 0x14, 0x63, 0x55, 0x21, 0x0C, 0x7D,
)


# learnt from http://cs.ucsb.edu/~koc/cs178/projects/JT/aes.c
xtime = lambda a: (((a << 1) ^ 0x1B) & 0xFF) if (a & 0x80) else (a << 1)


Rcon = (
    0x00, 0x01, 0x02, 0x04, 0x08, 0x10, 0x20, 0x40,
    0x80, 0x1B, 0x36, 0x6C, 0xD8, 0xAB, 0x4D, 0x9A,
    0x2F, 0x5E, 0xBC, 0x63, 0xC6, 0x97, 0x35, 0x6A,
    0xD4, 0xB3, 0x7D, 0xFA, 0xEF, 0xC5, 0x91, 0x39,
)


def text2matrix(text):
    text = bytes_to_long(text)
    matrix = []
    for i in range(16):
        byte = (text >> (8 * (15 - i))) & 0xFF
        if i % 4 == 0:
            matrix.append([byte])
        else:
            matrix[i // 4].append(byte)
    return matrix


def matrix2text(matrix):
    text = 0
    for i in range(4):
        for j in range(4):
            text |= (matrix[i][j] << (120 - 8 * (4 * i + j)))
    return long_to_bytes(text)


class AES:
    def __init__(self, master_key):
        self.change_key(master_key)

    def change_key(self, master_key):
        self.round_keys = text2matrix(master_key)
        # print self.round_keys

        for i in range(4, 4 * 11):
            self.round_keys.append([])
            if i % 4 == 0:
                byte = self.round_keys[i - 4][0]        \
                     ^ Sbox[self.round_keys[i - 1][1]]  \
                     ^ Rcon[i // 4]
                self.round_keys[i].append(byte)

                for j in range(1, 4):
                    byte = self.round_keys[i - 4][j]    \
                         ^ Sbox[self.round_keys[i - 1][(j + 1) % 4]]
                    self.round_keys[i].append(byte)
            else:
                for j in range(4):
                    byte = self.round_keys[i - 4][j]    \
                         ^ self.round_keys[i - 1][j]
                    self.round_keys[i].append(byte)

        # print self.round_keys

    def encrypt(self, plaintext):
        self.plain_state = text2matrix(plaintext)

        self.__add_round_key(self.plain_state, self.round_keys[:4])

        for i in range(1, 10):
            self.__round_encrypt(self.plain_state, self.round_keys[4 * i : 4 * (i + 1)])

        self.__sub_bytes(self.plain_state)
        self.__shift_rows(self.plain_state)
        self.__add_round_key(self.plain_state, self.round_keys[40:])

        return matrix2text(self.plain_state)

    def decrypt(self, ciphertext):
        self.cipher_state = text2matrix(ciphertext)

        self.__add_round_key(self.cipher_state, self.round_keys[40:])
        self.__inv_shift_rows(self.cipher_state)
        self.__inv_sub_bytes(self.cipher_state)

        for i in range(9, 0, -1):
            self.__round_decrypt(self.cipher_state, self.round_keys[4 * i : 4 * (i + 1)])

        self.__add_round_key(self.cipher_state, self.round_keys[:4])

        return matrix2text(self.cipher_state)

    def __add_round_key(self, s, k):
        for i in range(4):
            for j in range(4):
                s[i][j] ^= k[i][j]


    def __round_encrypt(self, state_matrix, key_matrix):
        self.__sub_bytes(state_matrix)
        self.__shift_rows(state_matrix)
        self.__mix_columns(state_matrix)
        self.__add_round_key(state_matrix, key_matrix)


    def __round_decrypt(self, state_matrix, key_matrix):
        self.__add_round_key(state_matrix, key_matrix)
        self.__inv_mix_columns(state_matrix)
        self.__inv_shift_rows(state_matrix)
        self.__inv_sub_bytes(state_matrix)

    def __sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = Sbox[s[i][j]]


    def __inv_sub_bytes(self, s):
        for i in range(4):
            for j in range(4):
                s[i][j] = InvSbox[s[i][j]]


    def __shift_rows(self, s):
        s[0][1], s[0][2], s[0][3], = s[0][2], s[0][3], s[0][1]
        s[1][1], s[1][2], s[1][3], = s[1][2], s[1][3], s[1][1]
        s[2][1], s[2][2], s[2][3], = s[2][2], s[2][3], s[2][1]
        s[3][1], s[3][2], s[3][3], = s[3][2], s[3][3], s[3][1]


    def __inv_shift_rows(self, s):
        s[0][1], s[0][2], s[0][3], = s[0][3], s[0][1], s[0][2]
        s[1][1], s[1][2], s[1][3], = s[1][3], s[1][1], s[1][2]
        s[2][1], s[2][2], s[2][3], = s[2][3], s[2][1], s[2][2]
        s[3][1], s[3][2], s[3][3], = s[3][3], s[3][1], s[3][2]

    def __mix_single_column(self, a):
        # please see Sec 4.1.2 in The Design of Rijndael
        t = a[0] ^ a[1] ^ a[2] ^ a[3]
        u = a[0]
        a[0] ^= t ^ xtime(a[0] ^ a[1])
        a[1] ^= t ^ xtime(a[1] ^ a[2])
        a[2] ^= t ^ xtime(a[2] ^ a[3])
        a[3] ^= t ^ xtime(a[3] ^ u)


    def __mix_columns(self, s):
        for i in range(4):
            self.__mix_single_column(s[i])


    def __inv_mix_columns(self, s):
        # see Sec 4.1.3 in The Design of Rijndael
        for i in range(4):
            u = xtime(xtime(s[i][0] ^ s[i][2]))
            v = xtime(xtime(s[i][1] ^ s[i][3]))
            s[i][0] ^= u
            s[i][1] ^= v
            s[i][2] ^= u
            s[i][3] ^= v

        self.__mix_columns(s)

Appresiasi kepada mas jossie yang sudah menyelesaikan soal ini pada waktu kompetisi.

Ringkasan

Pada soal ini kita diberikan sebuah program yang melakukan enkripsi AES yang sudah dimodifikasi, yaitu pada shift row

1
2
3
4
5

def __shift_rows(self, s):
    s[0][1], s[0][2], s[0][3], = s[0][2], s[0][3], s[0][1]
    s[1][1], s[1][2], s[1][3], = s[1][2], s[1][3], s[1][1]
    s[2][1], s[2][2], s[2][3], = s[2][2], s[2][3], s[2][1]
    s[3][1], s[3][2], s[3][3], = s[3][2], s[3][3], s[3][1]

Kita juga bisa melakukan chosen plaintext attack pada program tersebut.

Solusi

Kesalahan implementasi adalah pada shift row, yang pada shift row tersebut aslinya hanya melakukan shift pada column. Hal ini menyebabkan masing-masing 4 byte pada hasil ciphertext saling independen. Yang artinya kita bisa melakukan bruteforce pada masing-masing 4 byte dari input hex yang mungkin, yang jika apabila outputnya sama dengan ciphertext dari admin_id, maka kita bisa mendapatkan admin_id yang tepat. Berikut ini script yang dijalankan untuk mendapatkan flag

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

from pwn import remote

def blocks(data):
    return [data[i:i+16] for i in range(0, len(data), 16)]

io = remote("ctf.tcp1p.team", 19328)
io.recvuntil(b"Encrypted ID: ")
enc_id = bytes.fromhex(io.recvline().strip().decode())
print(f"len(enc_id): {len(enc_id)}")

def encrypt(p):
    io.sendlineafter(b">> ", b"1")
    io.sendlineafter(b"message: ", p.encode())
    io.recvuntil(b"Encrypted: ")
    return bytes.fromhex(io.recvline().strip().decode())

def blocks(data):
    return tuple([data[i:i+16] for i in range(0, len(data), 16)])

admin_id = [0] * 4

for i in range(256):
    print(i)
    p = ""
    for j in range(256*i, 256*(i+1)):
        p += hex(j)[2:].zfill(4) * 4
    
    print(len(encrypt(p)), len(encrypt(p)))
    test_enc = blocks(encrypt(p))

    for block_enc in test_enc:
        for k in range(4):
            if block_enc[4*k:4*(k+1)] == enc_id[4*k:4*(k+1)]:
                print("sini")
                admin_id[k] = hex(test_enc.index(block_enc) + 256*i)[2:].zfill(4)


print(admin_id)
admin_id = "".join(admin_id)
io.sendlineafter(b">> ", b"2")
io.sendlineafter(b"Enter ID: ", admin_id.encode())
io.interactive()

io.close()

Flag: TCP1P{well_well_well_9a80dfee0912}

molecular cryptography

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91

import numpy as np
from secret import flag
from chaotic import generate_sequences

dna_rules = {
    1: {'00': 'A', '11': 'T', '01': 'G', '10': 'C'},
    2: {'00': 'A', '11': 'T', '10': 'G', '01': 'C'},
    3: {'01': 'A', '10': 'T', '00': 'G', '11': 'C'},
    4: {'01': 'A', '10': 'T', '11': 'G', '00': 'C'},
    5: {'10': 'A', '01': 'T', '00': 'G', '11': 'C'},
    6: {'10': 'A', '01': 'T', '11': 'G', '00': 'C'},
    7: {'11': 'A', '00': 'T', '01': 'G', '10': 'C'},
    8: {'11': 'A', '00': 'T', '10': 'G', '01': 'C'}
}

def dna_encode_matrix(P, rule_number):
    rule = dna_rules[rule_number]
    return np.array([
        [rule[f'{num:08b}'[i:i+2]] for num in row for i in range(0, 8, 2)]
        for row in P
    ])

def xor_matrices(matrix1, matrix2, rule_number):
    rule = dna_rules[rule_number]
    rev_rule = {v: k for k, v in rule.items()}
    return np.array([
        [rule[format(int(rev_rule[b1], 2) ^ int(rev_rule[b2], 2), '02b')]
         for b1, b2 in zip(row1, row2)]
        for row1, row2 in zip(matrix1, matrix2)
    ])

def generate_random_keystream(total_bases):
    return np.random.choice(['A', 'C', 'G', 'T'], size=total_bases)

def scramble_matrix(P, lx, ly):
    return P[lx, :][:, ly]

def string_to_matrix(s, num_columns=4):
    ascii_vals = [ord(c) for c in s]
    padded_len = -(-len(ascii_vals) // num_columns) * num_columns
    padded_vals = ascii_vals + [0] * (padded_len - len(ascii_vals))
    return np.array(padded_vals).reshape(-1, num_columns)

def dna_sequence_to_dna_matrix(s, num_columns=16):
    padding_length = (num_columns - len(s) % num_columns) % num_columns
    s_padded = s + 'A' * padding_length
    return np.array(list(s_padded)).reshape(-1, num_columns)

def adjust_sequences(seq, new_length):
    filtered_seq = seq[seq < new_length]
    repeats = -(-new_length // len(filtered_seq))
    return np.tile(filtered_seq, repeats)[:new_length]

if __name__ == "__main__":
    P0 = string_to_matrix(flag)
    rule_number = 3
    dna_encoded_P = dna_encode_matrix(P0, rule_number)
    total_bases = dna_encoded_P.size
    keystream = generate_random_keystream(total_bases)
    key_matrix = keystream.reshape(dna_encoded_P.shape)

    row, col = P0.shape
    lx, ly = generate_sequences(row, 4 * col)
    lx, ly = np.array(lx), np.array(ly)

    scrambled_P = scramble_matrix(dna_encoded_P, lx, ly)
    Pc = xor_matrices(scrambled_P, key_matrix, rule_number)
    print("Encrypted Flag:")
    print(''.join(Pc.flatten()))

    for i in range(1, 3):
        user_input = input(f"Give DNA encryption a try! What do you want to encrypt? ({i}/2)")
        if not all(c in 'ACGT' for c in user_input):
            print("Invalid input")
            continue

        dna_matrix_user = dna_sequence_to_dna_matrix(user_input, num_columns=16)
        data_rows, data_cols = dna_matrix_user.shape
        total_bases_user = data_rows * data_cols

        repeats_key = -(-total_bases_user // total_bases)
        extended_keystream = np.tile(keystream, repeats_key)[:total_bases_user]
        extended_key_matrix = extended_keystream.reshape((data_rows, data_cols))

        lx_user = adjust_sequences(lx, data_rows)
        ly_user = adjust_sequences(ly, data_cols)

        scrambled_user = scramble_matrix(dna_matrix_user, lx_user, ly_user)
        result = xor_matrices(scrambled_user, extended_key_matrix, rule_number)
        print("Encryption Result:")
        print(''.join(result.flatten()))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import numpy as np
from scipy.integrate import solve_ivp
import random

# System Parameters
a, b, c, d = 36, 3, 28, 16

# Initial Conditions
x0 = round(random.uniform(-20, 20), 1)
y0 = round(random.uniform(-30, 30), 1)
z0 = round(random.uniform(0.1, 40), 1)
q0 = round(random.uniform(-20, 20), 1)
k = round(random.uniform(-0.7, 0.7), 2)

# Time Settings
h = 0.001  # Time step
T = 1.0    # Total time
t_eval = np.arange(0, T, h)  # Evaluation times

# Define the system of ODEs
def chaos(t, vars):
    x, y, z, q = vars
    dx = a * (y - x)
    dy = -x * z + d * x + c * y - q
    dz = x * y - b * z
    dq = x + k
    return [dx, dy, dz, dq]

def generate_sequences(M, N):
    sol = solve_ivp(chaos, [0, T], [x0, y0, z0, q0], t_eval=t_eval, method='RK45')
    x = sol.y[0]
    y = sol.y[1]

    # Discard Transient Data
    transient = int(0.5 / h)  # Discard the first 0.5 units of time
    x_data = x[transient:]
    y_data = y[transient:]

    # Sampling Parameters
    total_samples = len(x_data)
    indices_x = np.linspace(0, total_samples - 1, M, dtype=int)
    indices_y = np.linspace(0, total_samples - 1, N, dtype=int)

    # Sample the Sequences
    x_sequence = x_data[indices_x]
    y_sequence = y_data[indices_y]
    
    lx = np.argsort(x_sequence)
    ly = np.argsort(y_sequence)

    return lx, ly

Ringkasan

Program menerima input dan mengeluarkan output berupa DNA sequence dengan aturan tertentu untuk encoding dan decodingnya. DNA sequence tersebut diubah menjadi matrix untuk selanjutnya diproses menuju enkripsinya. Untuk enkripsinya sendiri, pertama dibuat keystream misalkan $K$. Input DNA sequence yang sudah diubah menjadi matrix $P$ akan dilakukan permutasi baris dan kolomnya dari $lx$ dan $ly$ yang secara acak dibuat pada fungsi chaotic.py. Misalkan $f_{lx,ly}$ adalah fungsi yang melakukan permutasi baris dan kolomnya. Maka output ciphertext $C$ adalah $K \oplus f_{lx,ly}(P)$. Diberikan $C_{flag} = K \oplus f_{lx,ly}(P_flag)$. Kemudian kita juga bisa melakukan chosen plaintext attack sebanyak 2 kali. Misalkan juga bahwa

\[\begin{align*} C_1 &= K \oplus f_{lx,ly}(P_1) \\ C_2 &= K \oplus f_{lx,ly}(P_2) \\ \end{align*}\]

Solusi

Dari semua informasi yang diketahui, perhatikan bahwa

\[C_1 \oplus C_2 = f_{lx,ly}(P_1) \oplus f_{lx,ly}(P_2) \\ = f_{lx,ly}(P_1 \oplus P_2)\]

Seandainya kita bisa mendapatkan $lx$ dan $ly$, maka kita bisa mendapatkan key dengan $K = C_1 \oplus f_{lx,ly}(P_1)$. Dan kemudian bisa mendaptkan flag dari $P_{flag} = K \oplus C_{flag}$.

Untuk itu, permasalahannya adalah mencari permutasinya. Pertama akan fokus dicari nilai $ly$ terlebih dahulu.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

all_possible_perm = set()

for j in range(16):
    possible_perm = []
    for perm in permutations(range(16), 4):
        for i in range(16):
            if np.array_equal(P[i][np.array(perm)], P_perm[j][:4]):
                possible_perm.append(perm)

    if len(all_possible_perm) == 0:
        all_possible_perm = set(possible_perm)
    else:
        all_possible_perm = all_possible_perm.intersection(set(possible_perm))

    if len(all_possible_perm) == 1:
        break
    print(f"j = {j}, len = {len(all_possible_perm)}")

Disini dilakukan pengecekan bahwa, 4 nilai ly pertama yang valid apabila disetiap baris pada $P_{perm}$, terdapat permutasi dari suatu baris pada $P$ yang bersesuaian. Dari hasil tersebut, kita sudah memfilter sedikit nilai ly saja yang memenuhi, selanjutnya kita akan mendapatkan nilai-nilai ly berikutnya dengan cara berikut

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

for l in range(6):
    ct_dict = {}

    for perm in all_possible_perm:
        for next_perm in permutations(set(range(16)) - set(perm), 2):
            cur_perm = list(perm) + list(next_perm)
            ct = 0
            for j in range(16):
                for i in range(16):
                    if np.array_equal(
                        P[i][np.array(cur_perm)], P_perm[j][: 6 + 2 * l]
                    ):
                        ct += 1

            ct_dict[tuple(cur_perm)] = ct

    max_ct = max(ct_dict.values())

    all_possible_perm = [k for k, v in ct_dict.items() if v == max_ct]

Di sini saya mencoba mengecek secara bertahap penambahan 2 permutasi, apabila ly tersebut sesuai, maka secara statistik banyak permutasi yang cocok adalah yang paling banyak. Di sini saya teruskan sampai diperoleh semua nilai $ly$ yang valid.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

for ly in all_possible_perm:
    ly = np.array(ly)
    all_poss_lx = []
    for j in range(16):
        temp = []
        for i in range(16):
            if np.array_equal(P[i][ly], P_perm[j]):
                temp.append(i)

        all_poss_lx.append(temp)

    for lx in product(*all_poss_lx):
        lx = np.array(lx)
        if np.array_equal(scramble_matrix(P, lx, ly), P_perm):
            result.append((lx, ly))

Setelah diperoleh semua nilai $ly$, maka kita ambil nilai $lx$ yang mungkin. Selanjutanya kita validasi juga, apabila benar bahwa $P_{perm} = f_{lx,ly}(P)$, maka kita bisa mendapatkan permutasi yang sesuai. Dari sini kita telah mendapatkan $lx$ dan $ly$ yang valid, selanjutnya kita bisa mendapatkan key dan flag seperti yang telah dijelaskan sebelumnya.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174

from pwn import *
import numpy as np
from itertools import product, permutations

dna_rules = {
    1: {"00": "A", "11": "T", "01": "G", "10": "C"},
    2: {"00": "A", "11": "T", "10": "G", "01": "C"},
    3: {"01": "A", "10": "T", "00": "G", "11": "C"},
    4: {"01": "A", "10": "T", "11": "G", "00": "C"},
    5: {"10": "A", "01": "T", "00": "G", "11": "C"},
    6: {"10": "A", "01": "T", "11": "G", "00": "C"},
    7: {"11": "A", "00": "T", "01": "G", "10": "C"},
    8: {"11": "A", "00": "T", "10": "G", "01": "C"},
}


def scramble_matrix(P, lx, ly):
    return P[lx, :][:, ly]


def inverse_array(l):
    res = np.empty_like(l)
    res[l] = np.arange(len(l))
    return res


def generate_random_stream(total_bases):
    return np.random.choice(["A", "C", "G", "T"], size=total_bases)


def inverse_scramble_matrix(P, lx, ly):
    return P[inverse_array(lx), :][:, inverse_array(ly)]


def xor_matrices(matrix1, matrix2, rule_number):
    rule = dna_rules[rule_number]
    rev_rule = {v: k for k, v in rule.items()}
    return np.array(
        [
            [
                rule[format(int(rev_rule[b1], 2) ^ int(rev_rule[b2], 2), "02b")]
                for b1, b2 in zip(row1, row2)
            ]
            for row1, row2 in zip(matrix1, matrix2)
        ]
    )


def dna_decode_matrix(P, rule_number):
    rule = dna_rules[rule_number]
    rev_rule = {v: k for k, v in rule.items()}
    return np.array(
        [
            [
                int(
                    rev_rule[row[i]]
                    + rev_rule[row[i + 1]]
                    + rev_rule[row[i + 2]]
                    + rev_rule[row[i + 3]],
                    2,
                )
                for i in range(0, 16, 4)
            ]
            for row in P
        ]
    )


def matrix_to_string(matrix):
    return "".join(chr(c) for c in matrix.flatten() if c != 0)


def recover_perm(P, P_perm):
    all_possible_perm = set()

    print("get first all 4 perm")
    for j in range(16):
        possible_perm = []
        for perm in permutations(range(16), 4):
            for i in range(16):
                if np.array_equal(P[i][np.array(perm)], P_perm[j][:4]):
                    possible_perm.append(perm)

        if len(all_possible_perm) == 0:
            all_possible_perm = set(possible_perm)
        else:
            all_possible_perm = all_possible_perm.intersection(set(possible_perm))

        if len(all_possible_perm) == 1:
            break
        print(f"j = {j}, len = {len(all_possible_perm)}")

    print("get last 12 perm")
    print(all_possible_perm)

    for l in range(6):
        ct_dict = {}

        for perm in all_possible_perm:
            for next_perm in permutations(set(range(16)) - set(perm), 2):
                cur_perm = list(perm) + list(next_perm)
                ct = 0
                for j in range(16):
                    for i in range(16):
                        if np.array_equal(
                            P[i][np.array(cur_perm)], P_perm[j][: 6 + 2 * l]
                        ):
                            ct += 1

                ct_dict[tuple(cur_perm)] = ct

        max_ct = max(ct_dict.values())

        all_possible_perm = [k for k, v in ct_dict.items() if v == max_ct]

    print("get possible lx and ly")

    result = []
    for ly in all_possible_perm:
        ly = np.array(ly)
        all_poss_lx = []
        for j in range(16):
            temp = []
            for i in range(16):
                if np.array_equal(P[i][ly], P_perm[j]):
                    temp.append(i)

            all_poss_lx.append(temp)

        for lx in product(*all_poss_lx):
            lx = np.array(lx)
            if np.array_equal(scramble_matrix(P, lx, ly), P_perm):
                result.append((lx, ly))

    return result


def encrypt(P):
    io.sendlineafter(b"/2)", "".join(P).encode())
    io.recvuntil(b"Result:\n")
    C = io.recvline().strip().decode()
    return np.array(list(C))


# io = process(["python3", "chall.py"])
io = remote("ctf.tcp1p.team", 1975)
io.recvuntil(b"Flag:\n")
C_flag = io.recvline().strip().decode()
C_flag = np.array(list(C_flag)).reshape(16, 16)

P1 = generate_random_stream(256)
P2 = generate_random_stream(256)

C1 = encrypt(P1)
C2 = encrypt(P2)

P1, P2, C1, C2 = (
    P1.reshape(16, 16),
    P2.reshape(16, 16),
    C1.reshape(16, 16),
    C2.reshape(16, 16),
)

possible_lx_ly = recover_perm(xor_matrices(P1, P2, 3), xor_matrices(C1, C2, 3))

for lx, ly in possible_lx_ly:
    print(lx,ly)
    key_matrices = xor_matrices(scramble_matrix(P1, lx, ly), C1, 3)
    flag_perm = xor_matrices(C_flag, key_matrices, 3)
    flag = inverse_scramble_matrix(flag_perm, lx, ly)
    print(matrix_to_string(dna_decode_matrix(flag, 3)))


io.close()

Flag: TCP1P{That_time_I_got_Chemistry_Olympiad_instead_of_CTF_on_weekends_:(}

CTF, Cryptography
writeup small roots RSA AES
This post is licensed under CC BY 4.0 by the author.