My writeups for the Cryptography challenges of the 2023 PWNme Qualifications.
Information
These are all the Crypto challenges I managed to solve. Here’s the link to my github repo that has the full solving scripts. There was a mixture of categories, and my favourite was the Scream like Viking challenge, because I 😍RSA.
Challenges
Just a XOR
Difficulty: Intro
Description: You are in possession of an encrypted message as well as the algorithm that encrypted it. Find the original message PS: According to a reliable source who intercepted a part of the message before encryption, you have in your possession some characters of the original message (The * are the unknown parts of the message)
Code Analysis
#!/usr/bin/env python3
import random
from itertools import cycle
MESSAGE = open("./original-message.txt", "r").read()
SECRET = [chr(random.randint(0,0x2600) % 256) for i in range(16)]
def encrypt(message):
return [str((ord(a) ^ ord(b))) for a, b in zip(message, cycle(SECRET))]
with open('./message-encrypted.txt', 'w') as f:
f.write(','.join(encrypt(MESSAGE)))
#interecepted_message
S*********s***y***k************w***s****************n***********************P***********_r*4*********************o***uck*****t******************
We are given two files, the encrypted message, which is xored with random integers between 0-256, and the ‘intercepted_message’, which contains known plaintext strings. We can recover the key in two parts. First, we iterate over each item in the intercepted and encrypted message. If the value in the intercepted message is not ‘*’, we xor the integer representation of the character, to the corresponding integer in the encrypted message.
Next, we need to recover the correct order of the key. We iterate on the list created before, and this time, if the value is not a string (’NA’) in this case, then we reduce it to modulo 256, and its index to modulo 16, so that we have the correct 16-byte key.
Solution
import random
from itertools import cycle
ENC = open("files/message-encrypted.txt", "r").read()
HELP = open("files/intercepted-original-mesage.txt", "r").read()
ENC = [int(x) for x in ENC.split(',')]
kek = []
zipped = list(zip(HELP,ENC))
for x in zipped:
if x[0] != '*':
kek.append(ord(x[0])^x[1])
else:
kek.append('NA')
key=[0]*16
for i in range(len(kek)):
if kek[i] != 'NA':
key[i%16] = kek[i]%256
def decrypt(message,SECRET):
return [chr((a^b)%256) for a, b in zip(message, cycle(SECRET))]
dec =''.join(decrypt(ENC,key))
print(dec)
#So, I can see you know how XOR works.. Congratulation :) Here is your flag: PWNME{1t_W4s_r34aLy_Ju3s7_A_x0R} ! Good luck for the next challenges
Flag: PWNME{1t_W4s_r34aLy_Ju3s7_A_x0R}
Gib me Initials of Victor
Difficulty: Easy
Description:
Imagine making an encryption system. That’s what someone did…Find a way to recover the flag.
Code Analysis
We are provided a ciphertext and the encryption function:
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
import os
FLAG = "PWNME{redacted}"
KEY = os.urandom(16)
def encrypt_flag():
iv = os.urandom(16)
cipher = AES.new(KEY, AES.MODE_CBC, iv)
encrypted = cipher.encrypt(pad(FLAG.encode(), 16))
signature = [hex(a ^ b)[2:].zfill(2) for a, b in zip(iv, KEY[::-1])]
signature = "".join(signature)
ciphertext = iv.hex()[4:] + encrypted.hex() + signature
return {"ciphertext": ciphertext}
#{'ciphertext': 'ec99a438e52de135ad277039ce232c148aedd7c3f9a0688a3c95b6de4b4c35acca54edced84032f70c8ea88a1338d361b0fec7861c2eb26c244b99de45e60f9c361b0e2a7331b40cdf3df7bb2d4c'}
Well, easy. The ciphertext is not – just the encrypted plaintext, it’s:
- the IV, missing the first 2 bytes
- the encrypted plaintext
- the signature, which is the reversed key xored with the iv.
We can perform a bruteforce attack, since we are missing only two bytes of the iv. This means that the maximum bits are 2**16 and minimum 2**8
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import long_to_bytes
from pwn import xor
def brute_force(iv,enc,sig):
for i in range(2**8, 2**16):
my_iv = long_to_bytes(i) + iv
my_key = xor(my_iv,sig)[::-1]
try:
cipher = AES.new(my_key, AES.MODE_CBC, my_iv)
pt = cipher.decrypt(enc)
if pt[0:5] == b'PWNME':
print(pt.decode())
break
else:
pass
except:
pass
return
ct = bytes.fromhex('ca92b5919084c02658a2e3d57ee3a37b8ab32e581d2615359cc7858e966090d328df2be8b5ad889561d9abce6f961fe03a95a2051e882db2373b33b5a43a1c13ff62af7f835df3cc1ccc64571e74f8b84587c727d56c4d37983e7b80ce3c')
iv = ct[0:14]
enc = ct[14:-16]
sig = ct[-16:]
brute_force(iv,enc,sig)
#PWNME{1t_1s_d4ng3r0us_wh3n_t0_m4ny_1nf0_4r3_g1v3n}
Flag: PWNME{1t_1s_d4ng3r0us_wh3n_t0_m4ny_1nf0_4r3_g1v3n}
Scream Like Viking
Difficulty: Medium
Description: Our protagonist John is in a room, he hears some kind of noise, like something resonating. But he doesn’t understand it… Perhaps he could play with his own echoes to guess what the meaning of this famous resonance could be…
Code Analysis
#!/usr/bin/env python3
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
e = 17
p = getPrime(512)
q = getPrime(512)
N = p * q
def encrypt(m):
assert 0 <= m < N
c = pow(bytes_to_long(pad(long_to_bytes(m), 50)), e, N)
return int(c)
def encrypt_flag():
with open("flag.txt", "rb") as f:
flag = f.read()
c = pow(bytes_to_long(pad(flag, 50)), e, N)
return c
def main():
try:
while True:
print("Enter your option (Encrypt or Flag) > ", end='')
cmd = (input().strip())
if cmd == "Encrypt":
print("Enter your integer to encrypt > ", end='')
m = int(input())
c = encrypt(m)
print(str(c) + '\n')
elif cmd == "Flag":
c = encrypt_flag()
print("Flag cipher for you: " + str(c) + '\n')
return
except Exception as e:
print("An error occured:\n", e)
if __name__ == "__main__":
main()
Solution
This challenge needs a connection to a remote server to work. We have two options, send an integer to encrypt, and get the flag. When we send an integer, the server converts it to bytes, pads it to 50 block size, converts it back to an integer and then performs the classic RSA : C = m^e mod N. We are not provided N at any point, but we can quickly solve for it, since the padding is deterministic, we know the value of the plaintext.
Given that the exponent stays the same, but the moduli changes each time there’s a new connection, we can do a CRT attack. For this attack to work, the moduli cannot be coprime to one another. So it’s better to send multiple requests, and filter for good values.
from pwn import *
from copy import deepcopy
from Crypto.Util.number import getPrime, bytes_to_long, long_to_bytes
from Crypto.Util.Padding import pad
e = 17
def sub_m(m,c1):
fx = bytes_to_long(pad(long_to_bytes(int(m)), 50))^17
fx_ = fx-c1
return fx_
def send_m(m):
conn.sendlineafter(b'Enter your option (Encrypt or Flag) > ', b'Encrypt')
m1 = int(m)
conn.sendlineafter(b'Enter your integer to encrypt > ', str(m1).encode())
c = int(conn.recvline().strip().decode())
return c
def recover_n(host,port):
c1 = send_m(1)
c2 = send_m(2)
fx1 = sub_m(1,c1)
fx2=sub_m(2,c2)
N = gcd(fx1,fx2)
return N
def get_flag(host,port):
conn.sendlineafter(b'Enter your option (Encrypt or Flag) > ', b'Flag')
c = int(conn.recvline().strip().decode()[len("Flag cipher for you: "):])
return c
def clean(ns,encs):
NN = deepcopy(ns)
CC = deepcopy(encs)
while True:
NV = deepcopy(NN)
CV = deepcopy(CC)
for i in range(len(NN)):
for j in range(len(NN)):
if i != j and gcd(NN[i], NN[j]) != 1:
NV[i] = 0
CV[i] = 0
NN=[x for x in NV if x !=0]
CC=[x for x in CV if x !=0]
if len(NN) == len(NV):
break
return NN,CC
def crt_attack_(ns,encs,e=17):
cleaned_ns,cleaned_encs = clean(ns,encs)
for i in range(len(cleaned_ns)):
new_t = cleaned_ns[i:i+17]
new_c = cleaned_encs[i:i+17]
try:
pt = ZZ(crt(new_c,new_t)).nth_root(e)
if pt:
print(long_to_bytes(pt).decode())
break
except:
pass
host,port = "51.68.95.78", int(32773)
ns =[]
encs =[]
for i in range(200):
conn = remote(host,port)
N = recover_n(host,port)
enc= get_flag(host,port)
ns.append(N)
encs.append(enc)
conn.close()
crt_attack_(ns,encs,e=17)
#PWNME{3e851a6cc5525581446cad5694185b99}
Flag: PWNME{3e851a6cc5525581446cad5694185b99}
Like a Whispering Entropy
Difficulty: hardcore
Description: I don’t trust those who wrote crypto implementations, so I had to write my own… I created everything from scratch so I know it is safe ! No one backdoored my Diffie-Hellman implementation ! Btw, I gave you an output of a connection to my service, but anyway you won’t be able to get back the secret message
Code Analysis
chall.sage
#!/bin/env sage
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import getStrongPrime, long_to_bytes, bytes_to_long
import hashlib
from os import getenv, urandom
from random import getrandbits
FLAG = getenv("FLAG", "PWNME{dummyflag}").encode()
class PRNG(object):
def __init__(self):
self._seed = None
self.q = 279622638356169037213136872013126932777
self.n = 12
self.A = Matrix(GF(self.q), 1, self.n, [
19159356164385140466,
19848194065535878410,
33461959522325830456,
12213590058439028697,
35299014249932143965,
13327781436808877193,
20921178705527762622,
9371898426952684667,
9769023908222006322,
28712160343104144896,
32272228797175569095,
14666990089233663894
])
# LCG props
self.a = getrandbits(32)
self.c = getrandbits(32)
self._lcgseed = getrandbits(32)
self.mod = 2551431067
@property
def noise(self):
self._lcgseed = (self.a * self._lcgseed + self.c) % self.mod
return self._lcgseed
@property
def seed(self):
if self._seed is None:
self._seed = Matrix(GF(self.q), self.n, 1, [
getrandbits(102) for i in range(self.n)
])
return self._seed
def randint(self):
b = (self.A * self.seed + self.noise)[0][0]
self.A = Matrix(GF(self.q), 1, self.n, [
int(x * b^(i+1)) % 2^65 for i, x in enumerate(self.A[0])
])
return b
def encrypt(shared_secret: int, iv: bytes, msg: bytes):
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
ciphertext = cipher.encrypt(pad(msg, 16))
data = {}
data['iv'] = iv.hex()
data['encrypted_msg'] = ciphertext.hex()
return data
def main():
# Initialize PRNG:
rng = PRNG()
g = 2
p = 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919
n = 100
ivs = [
long_to_bytes(int(rng.randint())).ljust(16, b'\0') for _ in range(n)
]
secret_keys = [
int(rng.randint()) |
int(rng.randint() << 128) |
int(rng.randint() << 256) |
int(rng.randint() << 384) |
int(rng.randint() << 512) |
int(rng.randint() << 640) for _ in range(n)
]
public_keys = [
pow(g, sk, p) for sk in secret_keys
]
for i, e in enumerate(zip(ivs, secret_keys, public_keys)):
iv, sk, pk = e
print(f"Alice's public key: { pk }")
pk2 = bytes_to_long(urandom(0x60))
print(f"User #{i} public key: { pk2 }")
shared_secret = pow(pk2, sk, p)
print(f"{encrypt(shared_secret, iv, FLAG) = }")
print("-------------------------")
if __name__ == '__main__':
main()
Code Analysis
This is a PRNG challenge, which uses Matrices to calculate the random integer. I spent SO much time trying to understand and reverse the PRNG function, but it was more straightforward than that. We are provided with a logs file, which contains the public key pairs, and the encrypted ciphers with the IVs.
Two things two notice here:
– The IVS are the first values to be calculated from the PRNG.
– The Secret Keys are calculated afterwards, but using bitwise or and shift left.
If we read the file, we will notice that Alice’s public keys are NOT unique, so there has been a secret key reuse somewhere. After spending hours reversing the PNRG class, I eventually decided to apply the same or/shift left operation on the IVs and use the values to calculate public_keys (pow(g, iv_shift, p)), and surprise surprise, some of the new public_keys were in the logs!
Solve Script
from Crypto.Cipher import AES
from Crypto.Util.Padding import pad, unpad
from Crypto.Util.number import getStrongPrime, long_to_bytes, bytes_to_long
import hashlib
g = 2
p = 1552518092300708935130918131258481755631334049434514313202351194902966239949102107258669453876591642442910007680288864229150803718918046342632727613031282983744380820890196288509170691316593175367469551763119843371637221007210577919
n = 100
def get_data(fname):
splt = '-------------------------'
with open(fname,'r') as inf:
data = inf.read()
v1 = "Alice's public key: "
v2 = "\nUser #0 public key: "
data = [x.strip() for x in data.split(splt) if x.strip() != '']
pk_alice=[]
pk_bob = []
ct=[]
ivs =[]
for val in data:
vx=val.strip()[len(v1):].split('\n')[0]
v2=val.strip()[len(v1):].split('\n')[1].split(': ')[-1]
v3 = val.strip()[len(v1):].split('\n')[2].split('= ')[-1]
pk_alice.append(int(vx))
pk_bob.append(int(v2))
ivs.append(bytes.fromhex(eval(v3)['iv']))
ct.append(eval(v3))
return pk_alice,pk_bob,ivs,ct
def calculate_secrets_ivs(ivs):
Fx = GF(279622638356169037213136872013126932777)
ivs = [Fx(bytes_to_long(x)) for x in ivs]
redact_i = lambda i: int(ivs[i+0])|int(ivs[i+1]<<128)|int(ivs[i+2]<<256)|int(ivs[i+3]<<384)|int(ivs[i+4]<<512)|int(ivs[i+5]<<640)
ivsc=[]
for i in range(0,len(ivs)-5,5):
ivsc.append(redact_i(i))
new_publics = [pow(g,x,p) for x in ivsc]
return ivsc,new_publics
def decrypt(shared_secret,data):
iv = bytes.fromhex(data['iv'])
enc = bytes.fromhex(data['encrypted_msg'])
sha1 = hashlib.sha1()
sha1.update(str(shared_secret).encode('ascii'))
key = sha1.digest()[:16]
cipher = AES.new(key, AES.MODE_CBC, iv)
pt = cipher.decrypt(enc)
return unpad(pt, 16)
def solve(fname):
pk_alice,pk_bob,ivs,ct = get_data(fname)
new_secrets,new_pubs = calculate_secrets_ivs(ivs)
secrets_known = [new_secrets[new_pubs.index(x)] for x in new_pubs if x in pk_alice]
bob_values = [pk_bob[pk_alice.index(x)] for x in new_pubs if x in pk_alice]
cipher_values = [ct[pk_alice.index(x)] for x in new_pubs if x in pk_alice]
shared_secrets = [pow(pk2, sk, p) for pk2,sk in zip(bob_values,secrets_known)]
for shared_secret,data in zip(shared_secrets,cipher_values):
pt = decrypt(shared_secret,data)
print(pt.decode())
solve('logs')
#PWNME{d334d082994743b12464c529ea597ed85dcd08e49e6d2d644b46f295b24a2f25}
#PWNME{d334d082994743b12464c529ea597ed85dcd08e49e6d2d644b46f295b24a2f25}
#PWNME{d334d082994743b12464c529ea597ed85dcd08e49e6d2d644b46f295b24a2f25}
