# DiceCTF 2022 writeup

## writeup available for:
### Crypto:
1. [Provably Secure](#Provably-Secure)

## Provably Secure

Attachments:

* server.py

#!/usr/local/bin/python

# Normally you have unlimited encryption and decryption query requests in the IND-CCA2 game.
# For performance reasons, my definition of unlimited is 8 lol

from cryptography.hazmat.primitives.asymmetric import rsa, padding
from cryptography.hazmat.primitives import hashes
from secrets import randbits
from os import urandom
from Crypto.Util.strxor import strxor

def encrypt(pk0, pk1, msg):
    r = urandom(16)
    r_prime = strxor(r, msg)
    ct0 = pk0.encrypt(r, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
                         algorithm=hashes.SHA256(), label=None))
    ct1 = pk1.encrypt(r_prime, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()), 
                         algorithm=hashes.SHA256(), label=None))
    return ct0.hex() + ct1.hex()


def decrypt(key0, key1, ct):
    ct0 = ct[:256]
    ct1 = ct[256:]
    r0 = key0.decrypt(ct0, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
                           algorithm=hashes.SHA256(), label=None))
    r1 = key1.decrypt(ct1, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
                           algorithm=hashes.SHA256(), label=None))
    return strxor(r0, r1)


if __name__ == '__main__':
    print("""Actions:
0) Solve
1) Query Encryption
2) Query Decryption
""")
    for experiment in range(1, 129):
        print("Experiment {}/128".format(experiment))
        key0 = rsa.generate_private_key(public_exponent=65537, key_size=2048)
        key1 = rsa.generate_private_key(public_exponent=65537, key_size=2048)
        pk0 = key0.public_key()
        pk1 = key1.public_key()
        print("pk0 =", pk0.public_numbers().n)
        print("pk1 =", pk1.public_numbers().n)
        m_bit = randbits(1)
        seen_ct = set()
        en_count = 0
        de_count = 0
        
        while True:
            choice = int(input("Action: "))
            if choice == 0:
                guess = int(input("m_bit guess: "))
                if (guess == m_bit):
                    print("Correct!")
                    break
                else:
                    print("Wrong!")
                    exit(0)
            elif choice == 1:
                en_count += 1
                if (en_count > 8):
                    print("You've run out of encryptions!")
                    exit(0)
                m0 = bytes.fromhex(input("m0 (16 byte hexstring): ").strip())
                m1 = bytes.fromhex(input("m1 (16 byte hexstring): ").strip())
                if len(m0) != 16 or len(m1) != 16:
                    print("Must be 16 bytes!")
                    exit(0)
                msg = m0 if m_bit == 0 else m1
                ct = encrypt(pk0, pk1, msg)
                seen_ct.add(ct)
                print(ct)
            
            elif choice == 2:
                de_count += 1
                if (de_count > 8):
                    print("You've run out of decryptions!")
                    exit(0)
                in_ct = bytes.fromhex(input("ct (512 byte hexstring): ").strip())
                if len(in_ct) != 512:
                    print("Must be 512 bytes!")
                    exit(0)
                if in_ct.hex() in seen_ct:
                    print("Cannot query decryption on seen ciphertext!")
                    exit(0)
                print(decrypt(key0, key1, in_ct).hex())

    with open('flag.txt', 'r') as f:
        print("Flag: " + f.read().strip())

Nhận xét:
- Nhìn vào hàm encrypt và decrypt:

def encrypt(pk0, pk1, msg):
    r = urandom(16)
    r_prime = strxor(r, msg)
    ct0 = pk0.encrypt(r, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
                         algorithm=hashes.SHA256(), label=None))
    ct1 = pk1.encrypt(r_prime, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()), 
                         algorithm=hashes.SHA256(), label=None))
    return ct0.hex() + ct1.hex()


def decrypt(key0, key1, ct):
    ct0 = ct[:256]
    ct1 = ct[256:]
    r0 = key0.decrypt(ct0, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
                           algorithm=hashes.SHA256(), label=None))
    r1 = key1.decrypt(ct1, padding.OAEP(mgf=padding.MGF1(algorithm=hashes.SHA256()),
                           algorithm=hashes.SHA256(), label=None))
    return strxor(r0, r1)

- Ta có thể thấy

enc(pk0, r) = ct0
enc(pk1, msg^r) = ct1
ct0 + ct1 = enc

dec(key0, ct0) = r
dec(key1, ct1) = msg^r

lấy 2 cái trên xor nhau :(msg^r)^r = msg

- Tuy nhiên server đã chặn chúng ta decrypt những ciphertext thu được từ encryption:

elif choice == 2:
                de_count += 1
                if (de_count > 8):
                    print("You've run out of decryptions!")
                    exit(0)
                in_ct = bytes.fromhex(input("ct (512 byte hexstring): ").strip())
                if len(in_ct) != 512:
                    print("Must be 512 bytes!")
                    exit(0)
                if in_ct.hex() in seen_ct:
                    print("Cannot query decryption on seen ciphertext!")
                    exit(0)
                print(decrypt(key0, key1, in_ct).hex())

- Tuy nhiên, chúng ta vẫn có thể trick oracle của server như sau:

Nếu chúng ta gửi m0, m1 cho server và thu được ct0_1, ct1_1
sau đó lại gửi m0, m2 cho server và thu được ct0_2, ct1_2

nếu chúng ta lấy ct = ct0_1 + ct1_2 đi decrypt
ta sẽ có
dec(key0, ct0_1) = r_1
dec(key1, ct1_2) = r_2^msg1

tương tự

dec(key0, ct0_2) = r_2
dec(key1, ct1_1) = r_1^msg2

gọi 
A = r_1^(r_2^msg1) là kết quả decrypt ứng với ct0_1, ct1_2
B = r_2^(r_1^msg2) là kết quả decrypt ứng với ct0_2, ct1_1

Vậy nếu như A = B chứng tỏ msg được chọn là như nhau và chính bằng m0 
từ đó suy ra m_bit = 0. Ngược lại, m_bit = 1.

- Dựa trên logic trên, các bạn có thể code như thế nào cũng được, và đây là 1 cách làm của mình:

Full code in python:

from pwn import *
from Crypto.Util.strxor import strxor

context.log_level="debug"

host, port = "mc.ax", 31497



client=remote(host,port)

#get public key

client.recvuntil("pk0 = ")
data=client.recvline()
pk0=data[:-1]
print(pk0)

client.recvuntil("pk1 = ")
data=client.recvline()
pk1=data[:-1]
print(pk1)


#test encrypt
client.recvuntil("Action: ")
msg=b"1"
client.sendline(msg)

client.recvuntil("m0 (16 byte hexstring): ")
m00=b"0"*16
m00=m00.hex()
client.sendline(m00)

client.recvuntil("m1 (16 byte hexstring): ")
m01=b"1"*16
m01=m01.hex()
client.sendline(m01)


data=client.recvline()
print(data)
ct1=data[:-1]
print(ct1)


client.recvuntil("Action: ")
msg=b"1"
client.sendline(msg)

client.recvuntil("m0 (16 byte hexstring): ")
m10=b"2"*16
m10=m10.hex()
client.sendline(m10)

client.recvuntil("m1 (16 byte hexstring): ")
m11=b"0"*16
m11=m11.hex()
client.sendline(m11)


data=client.recvline()
print(data)
ct2=data[:-1]
print(ct2)

enc1=ct1[:512]+ct2[512:]
enc2=ct2[:512]+ct1[512:]



#test decrypt
client.recvuntil("Action: ")
msg=b"2"
client.sendline(msg)
#print(client.recv(4096))

client.recvuntil("ct (512 byte hexstring): ")
client.sendline(enc1)
data=client.recvline()
pt1=data[:-1]   


client.recvuntil("Action: ")
msg=b"2"
client.sendline(msg)
#print(client.recv(4096))

client.recvuntil("ct (512 byte hexstring): ")
client.sendline(enc2)
data=client.recvline()
pt2=data[:-1]   


print(pt1)
print(pt2)
pt1=bytes.fromhex(pt1.decode())
pt2=bytes.fromhex(pt2.decode())

key=strxor(pt1,pt2)
print(key,len(key))




#check key vs m0 hoac m1 de doan m_bit
if key==b'\x02'*16: m_bit=0
else: m_bit=1
print(m_bit)


#check m_bit
client.recvuntil("Action: ")
msg=b"0"
client.sendline(msg)
#print(client.recv(4096))

client.recvuntil("m_bit guess: ")
client.sendline(str(m_bit).encode())
#print(client.recv(4096))
#client.interactive()




#exp 2+

#get public key

client.recvuntil("pk0 = ")
data=client.recvline()
pk0=data[:-1]
print(pk0)

client.recvuntil("pk1 = ")
data=client.recvline()
pk1=data[:-1]
print(pk1)

#test encrypt
client.recvuntil("Action: ")
msg=b"1"
client.sendline(msg)

client.recvuntil("m0 (16 byte hexstring): ")
m00=b"0"*16
m00=m00.hex()
client.sendline(m00)

client.recvuntil("m1 (16 byte hexstring): ")
m01=b"1"*16
m01=m01.hex()
client.sendline(m01)


data=client.recvline()
print(data)
ct1=data[:-1]
print(ct1)


client.recvuntil("Action: ")
msg=b"1"
client.sendline(msg)

client.recvuntil("m0 (16 byte hexstring): ")
m10=b"2"*16
m10=m10.hex()
client.sendline(m10)

client.recvuntil("m1 (16 byte hexstring): ")
m11=b"0"*16
m11=m11.hex()
client.sendline(m11)


data=client.recvline()
print(data)
ct2=data[:-1]
print(ct2)

enc1=ct1[:512]+ct2[512:]
enc2=ct2[:512]+ct1[512:]



#test decrypt
client.recvuntil("Action: ")
msg=b"2"
client.sendline(msg)
#print(client.recv(4096))

client.recvuntil("ct (512 byte hexstring): ")
client.sendline(enc1)
data=client.recvline()
pt1=data[:-1]   


client.recvuntil("Action: ")
msg=b"2"
client.sendline(msg)
#print(client.recv(4096))

client.recvuntil("ct (512 byte hexstring): ")
client.sendline(enc2)
data=client.recvline()
pt2=data[:-1]   


print(pt1)
print(pt2)
pt1=bytes.fromhex(pt1.decode())
pt2=bytes.fromhex(pt2.decode())

key=strxor(pt1,pt2)
print(key,len(key))




#check key vs m0 hoac m1 de doan m_bit
if key==b'\x02'*16: m_bit=0
else: m_bit=1
print(m_bit)


#check m_bit
client.recvuntil("Action: ")
msg=b"0"
client.sendline(msg)
#print(client.recv(4096))

client.recvuntil("m_bit guess: ")
client.sendline(str(m_bit).encode())




for i in range(3,129):
	#exp 2+

	#get public key

	client.recvuntil("pk0 = ")
	data=client.recvline()
	pk0=data[:-1]
	print(pk0)

	client.recvuntil("pk1 = ")
	data=client.recvline()
	pk1=data[:-1]
	print(pk1)

	#test encrypt
	client.recvuntil("Action: ")
	msg=b"1"
	client.sendline(msg)

	client.recvuntil("m0 (16 byte hexstring): ")
	m00=b"0"*16
	m00=m00.hex()
	client.sendline(m00)

	client.recvuntil("m1 (16 byte hexstring): ")
	m01=b"1"*16
	m01=m01.hex()
	client.sendline(m01)


	data=client.recvline()
	print(data)
	ct1=data[:-1]
	print(ct1)


	client.recvuntil("Action: ")
	msg=b"1"
	client.sendline(msg)

	client.recvuntil("m0 (16 byte hexstring): ")
	m10=b"2"*16
	m10=m10.hex()
	client.sendline(m10)

	client.recvuntil("m1 (16 byte hexstring): ")
	m11=b"0"*16
	m11=m11.hex()
	client.sendline(m11)


	data=client.recvline()
	print(data)
	ct2=data[:-1]
	print(ct2)

	enc1=ct1[:512]+ct2[512:]
	enc2=ct2[:512]+ct1[512:]



	#test decrypt
	client.recvuntil("Action: ")
	msg=b"2"
	client.sendline(msg)
	#print(client.recv(4096))

	client.recvuntil("ct (512 byte hexstring): ")
	client.sendline(enc1)
	data=client.recvline()
	pt1=data[:-1]   


	client.recvuntil("Action: ")
	msg=b"2"
	client.sendline(msg)
	#print(client.recv(4096))

	client.recvuntil("ct (512 byte hexstring): ")
	client.sendline(enc2)
	data=client.recvline()
	pt2=data[:-1]   


	print(pt1)
	print(pt2)
	pt1=bytes.fromhex(pt1.decode())
	pt2=bytes.fromhex(pt2.decode())

	key=strxor(pt1,pt2)
	print(key,len(key))


	#check key vs m0 hoac m1 de doan m_bit
	if key==b'\x02'*16: m_bit=0
	else: m_bit=1
	print(m_bit)


	#check m_bit
	client.recvuntil("Action: ")
	msg=b"0"
	client.sendline(msg)
	#print(client.recv(4096))

	client.recvuntil("m_bit guess: ")
	client.sendline(str(m_bit).encode())



client.interactive()
#print(client.recv(4096))

- Một chút giải thích về code mình, ở code trên ngoài việc sử dụng logic trình bày ở trên thì mình còn áp dụng kĩ thuật choosen plaintext attack.
- Cụ thể hơn thay vì gửi m0, m1 và m0, m2 tới server thì mình sẽ chọn như sau

m0 = 16 byte 0
m1 = 16 byte 1

sau đó, mình lại gửi tiếp 

m0 = 16 byte 2
m1 = 16 byte 0

Khi đó khi decrypt mình sẽ thu được kết quả là r_1^(plain1^r_2)
và r_2^(plain2^r_1)

sau đó, đem 2 kết quả xor nhau ta thu được plain1^plain2

Vì thế khi decrypt kết quả mình thu được sẽ hoặc là byte 2 hoăc là byte 1
Do chỉ có 0^2 hoặc 0^1

Và nếu như là byte 2 chứng tỏ m0 đã được sử dụng trong 2 lần encrypt
=> m_bit = 0
và nếu là byte 1 thì m1 đã được sử dụng và m_bit = 1

- Cảm ơn các bạn đã đọc. Peace! 🥰

Mọi thắc mắc xin hãy liên hệ với mình qua discord: ``tranminhprvt01#7535``