# UDCTF 2023 - Strong Primes

I've written a diffie hellman server. I made sure not to let people select their parameters, and I use only strong primes. Those are safe, right?

We're given five files: alice.py, server.py, auth.log, strong_primes.txt, and gen_agreed_primes.py. alice.py performs a Diffie–Hellman key exchange, which consists of the following steps:

• alice.py invokes server.py
• server.py selects a random 2048-bit prime number $p$ from strong_primes.txt
• server.py generates a random secret $b$, and computes public value $B = 2^b \bmod p$
• server.py sends $p$ and $B$ to alice.py
• alice.py computes $A = 2^a \bmod p$, where $a$ is a fixed, unknown secret
• alice.py sends this value to server.py
• Both parties compute the shared secret
• server.py uses the shared secret to encrypt the flag using AES
• server.py sends the ciphertext to alice.py, which decrypts the flag

For each exchange, server.py logs the ciphertext, $A$, $B$, and $p$ to auth.log. However, normally this information is not enough to compute the shared secret. The security of DH relies on the fact that it is generally difficult to determine $x$ given the value of $g^x$ for cyclic groups. This is called the discrete logarithm problem.

gen_agreed_primes.py contains the code used to generate the primes used for the exchanges. We see that the primes were generated using pycrypto's Crypto.Util.number.getStrongPrime() function, "strong" meaning that $p - 1$ has at least one large prime factor.

The factorization of $p - 1$ matters, because for prime values of $p$ the order of the multiplicative group of integers mod $p$ is equal to $p - 1$. If the order of a cyclic group has prime factor $r$, we can compute the value of $x \bmod r$ in $\sqrt{r}$ time.

To identify factors of $p - 1$, we can simply try dividing it against a list of primes. In my case I used a list of primes up to $10^7$. This revealed that for many of the primes used in the authentication, $p - 1$ contains "small" prime factors.

Suppose we are able to calculate $x \bmod r$ for values $r_1, r_2, \dots\, r_n$. The Chinese remainder theorem states that from these values we can compute the value of $x \bmod (r_1 \times r_2 \times \dots \times r_n)$. If we are able to do this for enough values of $r$, we can leak Alice's entire secret value, whic allows us to compute the shared secret and decrypt the ciphertexts. (The server uses a different secret value each time, so we can't apply the same strategy there.)

We have to be careful, since $2$ may only generate a subgroup of the full group. However, we know that the order of the full group divisible by the order of the subgroup (Lagrange's theorem), so we can easily determine whether a factor of $p - 1$ is also a factor of the subgroup's order:

let order = p - 1n;
const subgroupFactors = [];
for(const factor of factorize(order)) {
// if order/factor is equal to or a multiple of the subgroup's order, 2^order/factor will be equal to 1
if(powMod(2n, order / factor, p) == 1n) {
order /= factor;
} else {
subgroupFactors.push(factor);
}
}

To determine $x \bmod r$, we start by transforming our $g$ and $y = g^x$ to elements of a cyclic group of order $r$:

$g' = g^\frac{p - 1}{r}$ $y' = y^\frac{p - 1}{r}$

Then, we just need to solve $(g')^{x'} = y'$ for $x'$. For this I made a small implementation of the baby-step giant-step algorithm since there wasn't one for JS, but you can easily accomplish this using tools like SageMath. Because $r$ is small, this process is fast.

const discreteLog = (g, y, p, order) => {

if(y==1n) return order;

const m = sqrt(order);

const arr = new Array(m);
for(let j = 0n; j < m; j++) {
arr[powMod(g, j, p)] = j;
}

const c = powMod(g, m * (order - 1n), p);
let gamma = y;
for(let i = 0n; i < m; i++) {
if(gamma in arr) {
return i * m + arr[gamma];
}
gamma = (gamma * c) % p;
}

};

So at this point, we have a list of values for $r$ and $x \bmod r$. We just need to solve this system of congruences and check if $g^x$ matches Alice's public value (meaning we have retrieved the full key):

const factors = Object.keys(map).map(BigInt);
let N = factors.reduce((a,c) => a*c, 1n);
let ans = 0n;
for(const factor of factors) {
ans += map[factor] * (N / factor) * inverse(N / factor, factor);
}
ans %= N;

// test if we have the full secret
if(powMod(g, ans, p) == y) {
console.log(ans);
process.exit(0);
}

Once we have Alice's secret, we can use it to compute the encryption key and decrypt any ciphertext of your choosing from auth.log.

import hashlib
from Crypto.Cipher import AES

# fill in parameters from auth.log
# p = ...
# B = ...
# iv = bytes.fromhex('...')
# ct = bytes.fromhex('...')

g = 2
aliceSecret = ...
ss = pow(B,aliceSecret,p)
key = hashlib.sha256(ss.to_bytes(2048//8,'big')).digest()[:16]
cipher = AES.new(key,AES.MODE_CBC,iv)

print(Padding.unpad(cipher.decrypt(ct),AES.block_size).decode('utf-8'))

yielding

UDCTF{th3_d3vil_15_1n_th3_det4il5}

# Resources §

Full solution code

Diffie-Hellman key exchange

Chinese remainder theorem

Baby-step giant-step

Pohlig–Hellman algorithm