Challenge 2 Writeup

Challenge overview

The challenge script performs a Diffie-Hellman style key exchange modulo a secret choice p from a published list ps, derives an AES key from the shared secret with SHA-256, and encrypts the flag in AES-CFB mode.

The attack path is:

1. determine which entry of ps could actually have been used,
2. recover the discrete logs of the public values with Pohlig-Hellman,
3. recompute the shared secret,
4. derive the AES key exactly as the challenge does,
5. decrypt the ciphertext.

The recovered flag is:

PUCTF26{M4st3ring_7he_P0hlig_Hel1man_4lgorithm_sh0uld_be_repeated_3_t1mes_a6ae23853267b9964675e266b280e347}

Files provided

chal.py

from random import randint, randbytes, choice
from Crypto.Cipher import AES
from hashlib import sha256

ps = []
g = 2
p = choice(ps)
a, b = randint(g,p-1), randint(g,p-1)

alice = pow(g,a,p)
bob = pow(g,b,p)
key = sha256(str(pow(alice,b,p)).encode()).digest()

with open('flag.txt', 'rb') as f:
    flag = f.read()

iv = randbytes(16)
cipher = AES.new(key, AES.MODE_CFB, iv)
ct = cipher.encrypt(flag)

output.txt

ps=[141442943855542333994414589811195017680431581364948955093953219715587695134633104733274044847134829402412365064909550741498664986279296704662519661231428041669230930032527935286812940799586243786095549698482175080426369705811250449417385962805245986884052156268728809379760398447362671029332535856482512492606869583, 22961133863252503761602805543298276014118072439464883363019468299117127696238274662103546847817623427181405171614902787584793857445546273744224899002293181238444401201255946281008600786791532114716348934328847184209436071813767461111123276322942808488839784496279744972288955574690616418397984278688612792063971827, 101572737323200812805157246340579316274748962553700200191086529263323492804113520483808009653989701447112764775081468669578756214069953447985030994651536622487189356704256867029666208084353560574624738051172090103573309605960049120060165947965072541070258400532733383524230505706359890056712284215727301925055937439]
alice=8640880789158906431863623319272162021876723017854051280755671744793453169911238933616092949080993851719445357291051872996514097202425505577790374105219878002746527478374375884828513624691962609069446978181489874222870343773696363866847303394775257472874381585227500085750844580666488581547917455355276110778276917
bob=80734274392683306219352286032376399315530333258200021505195249263919507424827013718872547787006892763343465770762074354605225633890364993385425612777918679350968499988839056142272128649081891276323895290067432472053655716749422846370445332210266967111816456188723246112524150997551785915312136199827304384150730970
iv='ebb5d2bc8255a3e92a1d715b5f5a4fc0'
ct='7fa27326f0d85cf753972ceffdf8a0d1bfc7f24a9d12618b39922cb9ece263fb9a5bd1c2a221277e2a358f6bee6102446a703feaf46e960bcf0485219e8f48680c02d9312fe9ee9ddc566130fd532f04ee0767064ca498a791ec954a72499007f6d19b17f3cba3b0380562'

solve.py

The provided solver already contains the correct attack: validate the right modulus, solve the discrete logs with Pohlig-Hellman, rebuild the shared secret, then decrypt.

Vulnerability / weakness

The whole challenge depends on the hardness of the discrete logarithm problem in the subgroup generated by g = 2 modulo the chosen prime p.

For the correct choice p = ps[2], the order of 2 is not a large prime. Instead,

ord_p(2) = (p - 1) / 2

and this value factors completely into many smallish prime factors. That makes discrete logs easy with Pohlig-Hellman, because the problem splits into many small discrete logs modulo prime factors and then recombines with CRT.

So the weakness is: the public base lies in a smooth-order subgroup.

Mathematical analysis

Diffie-Hellman here publishes:

• alice = g^a mod p
• bob = g^b mod p
• shared secret s = g^(ab) mod p

Since g = 2, if we can recover either private exponent modulo the order of g, we can reconstruct the same shared secret. In practice we recover both a and b modulo ord_p(2) and compute:

shared = 2^((a * b) mod ord_p(2)) mod p

The key observation is that the discrete log is only hard when the subgroup order has a large prime factor. If the subgroup order is smooth, Pohlig-Hellman reduces the problem to a collection of much smaller logs.

Why ps[1] is invalid

This candidate can be rejected immediately because modular exponentiation outputs a value in the range [0, p - 1], but the published bob is larger than ps[1].

Concretely:

• bob < ps[1] is false,
• but bob = pow(2, b, p) must always satisfy 0 <= bob < p.

Therefore ps[1] cannot be the modulus used by the challenge.

Why ps[0] is invalid

This case is subtler. Here both alice and bob are less than p, so size alone does not reject it.

For ps[0], we have p % 8 == 7. By the supplementary law of quadratic reciprocity,

(2 / p) = 1 when p ≡ ±1 (mod 8).

So 2 is a quadratic residue modulo ps[0]. That means every power of 2 also lies inside the quadratic-residue subgroup. Equivalently, any valid public key of the form 2^x mod p must satisfy Euler's criterion:

y^((p - 1) / 2) ≡ 1 (mod p).

Checking the published values for ps[0] gives:

• alice^((p - 1) / 2) mod p = 1
• bob^((p - 1) / 2) mod p = -1 mod p

So alice is in the subgroup generated by 2, but bob is not. Since the challenge generated bob as pow(2, b, p), this is impossible.

Hence ps[0] is also invalid.

Why ps[2] is correct

For ps[2], all consistency checks line up:

• alice < p and bob < p,
• p % 8 == 7, so 2 is a quadratic residue,
• alice^((p - 1) / 2) mod p = 1,
• bob^((p - 1) / 2) mod p = 1.

So both public values lie in the same quadratic-residue subgroup generated by powers of 2, which matches the challenge code.

This is the only candidate that is consistent with all published data.

Subgroup / order reasoning

For p = ps[2], the working subgroup order is:

order = (p - 1) // 2
      = 50786368661600406402578623170289658137374481276850100095543264631661746402056760241904004826994850723556382387540734334789378107034976723992515497325768311243594678352128433514833104042176780287312369025586045051786654802980024560030082973982536270535129200266366691762115252853179945028356142107863650962527968719

The complete factorization used by the solver is:

factors = [
    2303131849, 2387901083, 2523341879, 2524054229, 2544055441, 2586315449,
    2588187221, 2732264309, 2780124449, 2792565329, 2792893577, 2879373881,
    2928781859, 3008880727, 3170120621, 3204892231, 3297569843, 3329495833,
    3467204387, 3512436689, 3581402117, 3603124817, 3611945551, 3759106381,
    3767707781, 3799053859, 3803643601, 3902862961, 3985492321, 4008746029,
    4102030649, 4126505029, 4140791209,
]

and these 33 prime factors multiply exactly to order.

Also, for every listed factor q,

2^(order / q) mod p != 1

so the order of 2 is exactly order, not a proper divisor. That is important because it means exponents are recovered modulo the full subgroup order.

How Pohlig-Hellman is used

Pohlig-Hellman solves a discrete log in a group of smooth order by reducing it modulo each prime-power factor of the order. Here every factor appears only once, so the implementation is especially clean.

We want to solve, for example,

2^a ≡ alice (mod p).

For each prime factor q of order, set:

• e = order / q
• g_q = 2^e mod p
• h_q = alice^e mod p

Then g_q has order q, and solving

g_q^x ≡ h_q (mod p)

recovers a mod q.

Because q is only around 32 bits, each of these smaller logs is solved quickly with baby-step giant-step.

After computing all residues a mod q, the Chinese Remainder Theorem recombines them into a unique value modulo order. The exact same process is repeated for bob to recover b.

Baby-step giant-step inside Pohlig-Hellman

The helper bsgs(base, target, mod, subgroup_order) computes a discrete log in a subgroup of known order q.

It works by choosing m = ceil(sqrt(q)), storing baby steps

base^0, base^1, ..., base^(m-1)

and then walking giant steps by multiplying the target by base^(-m) repeatedly until a collision appears.

That gives a logarithm in roughly O(sqrt(q)) time and memory, which is very manageable for these 32-bit prime factors.

Shared-secret recovery

Once a and b are known modulo order, the Diffie-Hellman shared secret is:

shared = 2^(ab mod order) mod p

This is equivalent to the challenge's original computation:

pow(alice, b, p)

because alice = 2^a mod p and exponent arithmetic happens modulo the subgroup order.

The solver then derives the AES key exactly like the challenge:

key = sha256(str(shared).encode()).digest()

The decimal string representation is important here. Hashing the raw bytes of the integer would produce the wrong key.

AES-CFB decryption details

The challenge uses:

cipher = AES.new(key, AES.MODE_CFB, iv)
ct = cipher.encrypt(flag)

So decryption is just the matching inverse operation with the same key and IV:

iv = bytes.fromhex("ebb5d2bc8255a3e92a1d715b5f5a4fc0")
ct = bytes.fromhex("7fa27326f0d85cf753972ceffdf8a0d1bfc7f24a9d12618b39922cb9ece263fb9a5bd1c2a221277e2a358f6bee6102446a703feaf46e960bcf0485219e8f48680c02d9312fe9ee9ddc566130fd532f04ee0767064ca498a791ec954a72499007f6d19b17f3cba3b0380562")
pt = AES.new(key, AES.MODE_CFB, iv=iv).decrypt(ct)

CFB mode is a stream-like mode, so there is no padding issue to handle.

Final flag

PUCTF26{M4st3ring_7he_P0hlig_Hel1man_4lgorithm_sh0uld_be_repeated_3_t1mes_a6ae23853267b9964675e266b280e347}

Concise solve script explanation

The solve script does the following:

1. hardcodes the published ps, alice, bob, iv, and ct,
2. selects p = ps[2],
3. sets order = (p - 1) // 2,
4. uses the known factorization of order,
5. solves log_2(alice) and log_2(bob) with Pohlig-Hellman,
6. recomputes the shared secret 2^(ab mod order) mod p,
7. derives the key with sha256(str(shared).encode()),
8. decrypts the ciphertext with AES-CFB and prints the flag.

In short, the intended hardness of Diffie-Hellman disappears because the generator lives in a smooth-order subgroup, making both discrete logs tractable.

Minimal reproduction

Run the included solver:

python3 solve.py

It prints:

PUCTF26{M4st3ring_7he_P0hlig_Hel1man_4lgorithm_sh0uld_be_repeated_3_t1mes_a6ae23853267b9964675e266b280e347}