Export-grade

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: cipher_suite_downgrade, mitm_negotiation_rewrite, pohlig_hellman, small_dlp

Summary

Task: MITM a DH cipher-suite negotiation (socket.cryptohack.org 13379) where Alice offers groups from DH1536 down to DH64, then passively observe. Solution: rewrite the negotiation so Bob accepts the weakest group DH64 (a 64-bit prime), passively capture p, g, A, B, solve the 64-bit discrete log a=dlog_g(A) with sympy discrete_log / Pohlig-Hellman, compute shared=B^a mod p, derive key=sha1(str(shared))[:16] and AES-CBC decrypt the flag — a Logjam-style downgrade.

Export-grade — cryptohack (Diffie-Hellman)

Description

"Alice and Bob are using legacy codebases and need to negotiate parameters they both support. You've man-in-the-middled this negotiation step, and can passively observe thereafter. How are you going to ruin their day this time?" Connect at socket.cryptohack.org 13379.

Alice and Bob first negotiate a DH group from a supported list, then perform the key exchange and send the AES-CBC encrypted flag (key = sha1(str(shared)).digest()[:16]). We sit in the middle for the negotiation and can rewrite messages, then can only observe. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Recon / Analysis

Alice advertises a list of cipher suites / groups, strongest first:

supported = ["DH1536", "DH1024", "DH512", "DH256", "DH128", "DH64"]

This is the classic Logjam-style export-grade downgrade. Because we control the negotiation, we rewrite Bob's view so that the agreed group is the weakest one, DH64 — a Diffie-Hellman group with a 64-bit prime modulus. A 64-bit discrete log is trivially solvable (Pohlig-Hellman / BSGS / sympy.discrete_log in well under a second), so once we passively capture the public values we recover the private exponent and the shared secret. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Solution

1. MITM the negotiation: intercept Alice's offered list and reply to Bob so that the chosen group is forced to DH64. After agreement, switch to passive observation.
2. Capture the agreed p (64-bit), g, Alice's A = g^a mod p, and Bob's B = g^b mod p.
3. Solve the small DLP: a = dlog_g(A) mod p with sympy.discrete_log (Pohlig-Hellman under the hood).
4. Shared secret & decrypt: shared = B^a mod p, then AES-CBC.

 python read-only • copy allowed Copy
import json
from hashlib import sha1
from sympy.ntheory.residue_ntheory import discrete_log
from Crypto.Cipher import AES
from Crypto.Util.Padding import unpad
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# After forcing DH64 in the negotiation and observing the exchange:
# p, g, A, B  (p is a 64-bit prime),  iv, encrypted_flag

a = discrete_log(p, A, g)           # 64-bit DLP -> instant (Pohlig-Hellman)
shared = pow(B, a, p)               # = g^(a*b) mod p

key = sha1(str(shared).encode()).digest()[:16]
pt  = AES.new(key, AES.MODE_CBC, bytes.fromhex(iv)).decrypt(bytes.fromhex(encrypted_flag))
print(unpad(pt, 16).decode())

crypto{REDACTED}

Takeaways

• Downgrade attacks are devastating when the negotiation step is unauthenticated: a MITM forces the weakest mutually-supported group, regardless of how strong the parties' real preferences are. This is exactly the real-world Logjam attack against export-grade DH.
• A 64-bit DH prime gives a 64-bit discrete log, solvable instantly with sympy.discrete_log / Pohlig-Hellman; from a = dlog_g(A) recover shared = B^a mod p.
• Defense: authenticate the negotiation (sign the transcript) and refuse weak/export-grade groups entirely.
• Recognize it by: an MITM-able cipher-suite/group negotiation that includes a tiny group (DH64, DH128) in the supported list, followed by a normal DH exchange. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍