Throughout the weekend of March 1st 2025 (and for a bit after the official competition ended), I tried my hand at some of the PwnMeCTF cryptography and reversing challenges.
I managed to generate strong parameters for our diffie-hellman key exchange, i think my message is now safe.
This challenge presents us with the following Python script that performs a Diffie-Hellman key exchange, derives an AES key and encrypts the flag. We are given the generated Diffie-Hellman parameters, as well as the encrypted flag.
from Crypto.Util.number import getPrime, long_to_bytes
from Crypto.Util.Padding import pad, unpad
from Crypto.Cipher import AES
from hashlib import sha256
import os
# generating strong parameters
flag = b"REDACTED"
p = getPrime(1536)
g = p-1
a = getPrime(1536)
b = getPrime(1536)
A = pow(g, a, p)
B = pow(g, b, p)
assert pow(A, b, p) == pow(B, a, p)
C = pow(B, a, p)
# Encrypting my message
key = long_to_bytes(C)
key = sha256(key).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
ciphertext = cipher.encrypt(pad(flag, AES.block_size))
print(f"{p = }")
print(f"{g = }")
print("ciphertext =", ciphertext.hex())
The given parameters are:
p = 1740527743356518530873219004517954317742405916450945010211514630307030225825627940655848700898186119703288416676610512180281414181211686282526701502342109420226095690170506537523420657033019751819646839624557146950127906808859045989204720555752289247833349649020285507405445896768256093961814925065500513967524214087124440421275882981975756344900858314408284866222751684730112931487043308502610244878601557822285922054548064505819094588752116864763643689272130951
g = 1740527743356518530873219004517954317742405916450945010211514630307030225825627940655848700898186119703288416676610512180281414181211686282526701502342109420226095690170506537523420657033019751819646839624557146950127906808859045989204720555752289247833349649020285507405445896768256093961814925065500513967524214087124440421275882981975756344900858314408284866222751684730112931487043308502610244878601557822285922054548064505819094588752116864763643689272130950
ciphertext = f2803af955eebc0b24cf872f3c9e3c1fdd072c6da1202fe3c7250fd1058c0bc810b052cf99ebfe424ce82dc31a3ba94f
For Diffie-Hellman to be secure, the parameters need to be chosen such that $g$ is a generator of a sufficiently large subgroup of $\mathbb{Z}^*_p$. Choosing $p$ randomly and setting $g = p-1$, as done in the code above, does not guarantee that that is the case.
As per Lagrange’s theorem, the order of the subgroups of \(\mathbb{Z}_p^*\) are divisors of the order of \(\mathbb{Z}_p^*\). As $p$ is prime, the order of \(\mathbb{Z}^*_p\) is $p-1$. We factor the order and quickly identify several of its divisors; 2, 3, 5, and 43. Assuming that the order of the subgroup generated by $g$ is one of these small divisors, we can retrieve the flag as follows:
for a in range(44):
for b in range(44):
A = pow(g, a, p)
C = pow(A, b, p)
key = long_to_bytes(C)
key = sha256(key).digest()[:16]
cipher = AES.new(key, AES.MODE_ECB)
plaintext = cipher.decrypt(ciphertext)
try:
text = unpad(plaintext, AES.block_size)
print(text)
except:
pass
We find many combinations of $a$ and $b$ that lead to the flag PWNME{411_my_h0m13s_h4t35_sm411_Gs}; indeed, the order of the subgroup generated by $g$ is 2.
Using the provided binary and the encrypted file, find a way to retrieve the flag contained in flag.enc.
Note : the binary would have been run in May 2024.
The binary supplied in this challenge is an x86-64 ELF binary. Loading it into Binary Ninja shows us what’s happening:
int64_t main(int32_t arg1, int64_t* arg2)
void* fsbase
int64_t rax = *(fsbase + 0x28)
int64_t result
if (arg1 s> 1)
int64_t time = time(nullptr)
printf("time : %ld\n", 0)
srand(time.d)
void* fhandle = fopen(arg2[1], "rb+")
if (fhandle != 0)
while (true)
int32_t file_char = _IO_getc(fhandle)
if (file_char == 0xffffffff)
break
fseek(fhandle, -1, 1)
int32_t r = rand()
int32_t rdx_6 = r s/ 0x7f
fputc((r.b - ((rdx_6 << 7).b - rdx_6.b)) ^ file_char.b, fhandle)
fclose(fhandle)
void var_118
strcpy(&var_118, arg2[1])
__builtin_strncpy(dest: &var_118 + strlen(&var_118), src: ".enc", n: 5)
if (rename(arg2[1], &var_118) == 0)
result = 0
// ...
The program seems to take a single filename as an argument and encrypts it in-place. We’ve also been supplied with flag.enc, which has supposedly been encrypted in May of 2024.
20340c1d2f2d0d4b3b6f18155d6c2f164257661b167807341c2b6c667b254151553a4d5d5f256b
The encryption seems somewhat convoluted, so we just assume it is some operation that we can mimic based on the output of rand(). The output of rand() is important, though, and appears to be seeded based on the current time; the timestamp is used as input into srand() to seed the random number generator.
After some fiddling with a C implementation of the above did not work, we resolve to simply changing the date on a linux system in a loop, running the binary for every second in May 2024. Remark that the program can be used to decrypt flag.enc, as the used XOR operation is symmetric.
Several hours (!) later this would reveal the flag: PWNME{4baf3723f62a15f22e86d57130bc40c3}
Revisiting this challenge later showed a crucial oversight: srand() and rand() were no calls to the libc implementations, but were functions in the binary. That makes sense, as there is no guarantee the output of rand() is identical across different systems – their implementations may very well vary.
The content of the relevant functions is as follows:
uint64_t srand(int32_t arg1)
uint64_t result = zx.q(arg1 - 1)
seed = result
return result
uint64_t rand()
uint64_t rax_1 = 0x5851f42d4c957f2d * seed + 1
seed = rax_1
return rax_1 u>> 0x21
Some more careful consideration of the encryption operation suggests that the operation it is computing is actually rand() % 127. Indeed, the following code also finds the flag:
#include <inttypes.h>
#include <stdbool.h>
#include <stdio.h>
int main()
{
uint64_t timestamp = 1714514400; // 2024-05-01
uint64_t seed, r;
void *fhandle;
for (int i = 0; i < 30 * 24 * 60 * 60; i++)
{
seed = timestamp;
fhandle = fopen("flag.enc", "rb");
while (true)
{
int32_t c = fgetc(fhandle);
if (c == EOF)
{
break;
}
seed = 0x5851F42D4C957F2D * seed + 1;
r = seed >> 0x21;
printf("%c", (unsigned char)(c ^ (r % 127)));
}
fclose(fhandle);
printf("\n");
timestamp += 1;
}
}
Tried to make an opensource zedencrypt in 2 weeks but i got doubts about it ...
This challenge presents us with a compression and encryption library called OpenZed. The library allows the user to supply a password to encrypt their data. The password is used to derive an AES key for use in a variant on AES-CBC. Crucially, the first 13 bytes of the password are also used in the initialization vector, and this IV is prepended to the ciphertext to enable decryption.
The challenge presents us with an encrypted flag file, and the code used to encrypt the flag. The code shows that a random 16-byte password was used.
file = openzed.Openzed(b'zed', os.urandom(16), 'flag.txt', len(FLAG))
Armed with this knowledge, we iterate over the remaining three bytes of the password. The file exposes a hash of the password, allowing us to quickly check password attempts.
import json
import zlib
from openzedlib import openzed
from hashlib import sha256
with open('flag.txt.ozed', 'rb') as f:
data = f.read()
metadata = json.loads(data[4:304].strip(b'\x00'))
encrypted = data[304:]
ciphertext = zlib.decompress(encrypted)
iv = ciphertext[:16]
password_prefix = iv[3:]
for i in range(256 ** 3):
password_postfix = int.to_bytes(i, 3, byteorder='big')
password = password_prefix + password_postfix
if metadata['password_hash'] == sha256(password).hexdigest():
file = openzed.Openzed(b'zed', password)
print(file.decrypt(encrypted))
This presents us with the flag:
PWNME{49e531f28d1cedef03103af6cec79669_th4t_v3Ct0r_k1nd4_l3aky}
After having a brief look at the follow-up challenge that supposedly patches the blatant weaknesses in openzedlib, I noticed that the derive_password function was also changed:
@@ -1,3 +1,3 @@
def derive_password(self):
- for i in range(100):
- self.key = sha256(self.password).digest()[:16]
+ salt = b"LESELFRANCAIS!!!"
+ self.key = PBKDF2(self.password, salt, 16, count=10000, hmac_hash_module=SHA256)
Given that sha256(password) is also part of the metadata included in the .ozed file, we did not even need to brute force the password to find the AES key. Oh well.
Using p or N is outdated, let's square N!
As usual, we’re given a Python script that was used to encrypt the flag and the script’s output.
from Crypto.Util.number import getStrongPrime
from math import gcd
from random import randint
from typing import Tuple
from Crypto.Cipher import AES
from hashlib import sha256
flag = b"PWNME{xxxxxxxxxxxxxxxxxxxxxxxxx}"
def generate_primes() -> int:
p = getStrongPrime(512)
q = getStrongPrime(512)
while gcd(p*q, (p-1)*(q-1)) != 1:
p = getStrongPrime(512)
q = getStrongPrime(512)
return p*q
def generate_public_key() -> Tuple[int, int]:
n = generate_primes()
k = randint(2, n-1)
while gcd(k, n) != 1:
k = randint(2, n-1)
g = 1 + k * n
return n, g, k
n, g, k = generate_public_key()
a = randint(2, n-1)
b = randint(2, n-1)
A = pow(g, a, n*n)
B = pow(g, b, n*n)
secret_key = pow(B, a, n*n)
def encrypt(m: bytes, secret_key: int) -> str:
hash_secret_key = sha256(str(secret_key).encode()).digest()
cipher = AES.new(hash_secret_key, AES.MODE_ECB)
return cipher.encrypt(m).hex()
print(f"{n = }")
print(f"{g = }")
print(f"{k = }")
print(f"{A = }")
print(f"{B = }")
print(f'enc = "{encrypt(flag, secret_key)}"')
And the corresponding output is:
n = 130480001264795511204952981970554765286628282097708497573805562495761746956689294837477924716000173700265689121058390655726461662172763702188805523675445230642476356316152454104476211773099930843629048798894397653741145611772970364363628025189743819724119397704649989182196725015667676292311250680303497618517
g = 14232999694821698106937459755169111250723143832548091913379257481041382160905011536064172867298828679844798321319150896238739468953330826850323402142301574319504629396273693718919620024174195297927441113170542054761376462382214102358902439525383324742996901035237645136720903186256923046588009251626138008729683922041672060805697738869610571751318652149349473581384089857319209790798013971104266851625853032010411092935478960705260673746033508293802329472778623222171537591292046922903109474029045030942924661333067125642763133098420446959785042615587636015849430889154003912947938463326118557965158805882580597710148
k = 109081848228506024782212502305948797716572300830339785578465230204043919222714279516643240420456408658167645175971167179492414538281767939326117482613367750888391232635306106151999375263906703485783436272382449557941704742019717763385971731987034043089865070488786181508175732060731733665723128263548176110391
A = 10331979810348166693003506393334562363373083416444082955583854323636220335613638441209816437198980825253073980493123573286927762799807446436773117670818921078297923733365129554252727963674496148945815529457095198387555733553703069705181377382893601879633657895337279524071439340411690401699779320407420258592904893010800421041848764790649945309236525529148459624417556599146885803882692326627657181584151248747924080070945415558421472606778565193931117263508570619290441914589981949634553417159683167906276897159926442471600725573380647253372071392282203683205441190912735696337884772579017885457286629133944441076065
B = 4081342267323018166249607688978380665241423816957875747125328810958590656153973787783246867777679461978030117454679495989870502705358238920918102708702013201363687875430336612386215884751792630402395947375495263771248401103245739000962715422458344125251671671250588124240486938525081520695571867300148511333511433839123962435025865462662009339451634433842267524048553313626315201481951251476302835595998914217740184369102003837614515913319042566394680732429410107620067602633793215206219823499602447575406162296590635685877032818801721681953430382920303700518722500790613216329394164889181089201919505288870098353385
enc = "abd9dd2798f4c17b9de4556da160bd42b1a5e3a331b9358ffb11e7c7b3120ed3"
We observe that $p$ and $q$ are so-called strong primes. According to the documentation of getStrongPrime, this guarantees that $p-1$ and $p+1$ have one large prime factor. Remark that the documentation suggests that $p$ must be strictly larger than 512, but the code accepts 512 as well. The resulting primes are multiplied to derive $n$. The loop in generate_primes tests whether $gcd(pq, (p-1)(q-1)) = 1$; the purpose of this is as of yet unclear to me.
Next, $k$, $a$ and $b$ are chosen such that $2 \le k, a, b \le n-1$, and $g = 1 + k \cdot n$. In a Diffie-Hellman-like fashion, $A \equiv g^a$ and $B \equiv g^b \mod{n^2}$, and the secret key is $B^a \mod{n^2}$.
By construction of $g$ and the Binomial theorem (1), we know that:
\begin{align} A &= g^a = (1 + kn)^a\\ &= 1 + kna + \binom{a}{2}k^2n^2 + \binom{a}{3}k^3n^3 + \ldots && (1) \\ &\equiv 1 + kna \mod{n^2} \\ \end{align}
As division in equivalence classes always feels tricky, let’s rewrite it as follows (for some $l \in \mathbb{Z}$):
\begin{align} A &\equiv 1 + kna \mod{n^2} \\ A &= 1 + kna + ln^2 \\ kna &= A - 1 + ln^2 \\ ka &= \frac{A - 1}{n} + ln \\ \end{align}
Switching back to equivalence modulo $n$, we can use the modular inverse of $k$ to compute $a$
\begin{align} ka &\equiv \frac{A - 1}{n} \mod{n} \\ a &\equiv \frac{A - 1}{n} \cdot k^{-1} \mod{n} \\ \end{align}
As, by construction, $a < n$, this is the original value of $a$. We can now find the secret key by computing $B^a \mod{n^2}$ and use it to decrypt the flag!
In code, this looks as follows:
ka = (A - 1) // n
a = ka * pow(k, -1, n) % n
C = pow(B, a, n * n)
hash_secret_key = sha256(str(C).encode()).digest()
cipher = AES.new(hash_secret_key, AES.MODE_ECB)
print(cipher.decrypt(bytes.fromhex(enc)))
The flag is PWNME{Thi5_1s_H0w_pAl1ier_WorKs}, referencing the Paillier cryptosystem.