Shared Secrets picoCTF 2026 Solution

Description

1. Step 1

   Analyse the encryption scheme

   Observation

   I noticed the challenge description said 'one side of the exchange leaked something' and that encryption.py was provided, which suggested reading the source first to understand exactly which Diffie-Hellman parameters were published versus which value had leaked before attempting any computation.

   The source shows a Diffie-Hellman exchange with g=2 and a large prime p. Both parties publish their public key (g^priv mod p). The shared secret is A^b mod p where A is one party's public key and b is the other's leaked private key.

   Learn more

   Diffie-Hellman key exchange (1976) was the first published public-key cryptographic protocol, enabling two parties to establish a shared secret over an insecure channel without having met before. Each party generates a private key (a random integer) and computes a public key as g^private mod p. They exchange public keys, and each can compute the same shared secret: shared = other_public^my_private mod p. An eavesdropper who sees both public keys cannot compute the shared secret without solving the discrete logarithm problem - finding x such that g^x = A mod p.

   The security of DH depends entirely on the private keys remaining secret. If either party leaks their private key, the shared secret is immediately compromised: anyone can compute A^b mod p from the public key A and the leaked private b. This is a fundamental lesson in cryptographic key management - even a mathematically secure protocol is broken by implementation failures like logging private keys or storing them insecurely.

   In modern systems, DH is used in TLS (as DHE or ECDHE cipher suites), Signal protocol, and WireGuard VPN. The "E" in DHE stands for "Ephemeral" - a new key pair is generated for every session, providing forward secrecy: compromising the server's long-term key does not expose past session keys. ECDH uses elliptic curve groups instead of multiplicative groups, providing equivalent security with smaller key sizes.

2. Step 2

   Compute the shared secret

   Observation

   I noticed that encryption.py revealed a leaked private key b alongside Alice's public key A and the prime p, which meant I could directly compute the DH shared secret as pow(A, b, p) without needing to solve the discrete logarithm problem.

   Pull p, A, b, and the ciphertext (verify the encoding - hex, base64, or raw - from encryption.py rather than guessing). Validate 1 < A,B < p as a sanity check, compute shared = pow(A, b, p), then try the obvious key derivations until one yields a printable picoCTF{...} prefix.

   python

   python3 << 'EOF'
   import hashlib
   
   # Confirm the ciphertext encoding by reading encryption.py:
   #   - hex string  -> bytes.fromhex(...)
   #   - base64      -> base64.b64decode(...)
   #   - raw bytes   -> open(..., "rb").read()
   p = YOUR_PRIME
   A = YOUR_PUBLIC_KEY   # g^a mod p
   b = YOUR_LEAKED_PRIV  # leaked private key
   
   # Sanity check on the public values
   assert 1 < A < p, "A must satisfy 1 < A < p"
   
   shared = pow(A, b, p)
   ct = bytes.fromhex("YOUR_CIPHERTEXT_HEX")
   
   # Try the obvious key derivations in order:
   candidates = [
       ("low byte",  bytes([shared & 0xFF])),
       ("byte 1",    bytes([(shared >> 8) & 0xFF])),
       ("sha256[:1]", hashlib.sha256(str(shared).encode()).digest()[:1]),
       ("sha256[:16]", hashlib.sha256(str(shared).encode()).digest()[:16]),
   ]
   
   for name, key in candidates:
       pt = bytes(c ^ key[i % len(key)] for i, c in enumerate(ct))
       if pt.startswith(b"picoCTF{"):
           print(name, "->", pt.decode(errors="replace"))
           break
   EOF

   Copied!

   Expected output

   low byte -> picoCTF{dh_sh4r3d_s3cr3t_...}

   What didn't work first

   Tried: Compute the shared secret using both public keys (pow(A, B, p)) instead of one public key and the leaked private key

   pow(A, B, p) raises public key A to the other public key B, not to any private exponent. The real DH shared secret is pow(A, b, p) where b is the LEAKED PRIVATE KEY from the message file. Using B (the other public key) in place of b gives a completely different number that produces garbage when XORed with the ciphertext - the math only works when one side of the exponent is a private key that the other party used to generate their public key.

   Tried: Try SHA-256 of the full shared integer as the decryption key before checking the low-byte derivation

   SHA-256 of the shared secret would be a 32-byte key, but the encryption.py source shows a single-byte XOR using shared % 256 (the low byte). Applying a 32-byte key produces output that cycles on a 32-byte period instead of a 1-byte period, so the plaintext never starts with picoCTF{ even though every 32nd byte might accidentally align. Always read encryption.py to confirm the exact key derivation before trying alternatives.

   Learn more

   What pow(A, b, p) actually does. Python's three-argument pow runs square-and-multiply modular exponentiation: scan the bits of the exponent b from MSB to LSB, square the running result mod p on every step, and multiply by A mod p when the current bit is 1. That is O(log b) multiplications, each of which is at most a 1024x1024-bit modular multiply for this challenge. A 1024-bit b means roughly 1500 mod-mul operations. Done in microseconds. Naively computing A**b first would produce a number with ~10^308 digits and never finish.

   Validate inputs. A real DH stack rejects values where A <= 1, A == p-1, or A >= p; a leaked private key paired with a degenerate public value can collapse the shared secret into a small set. Check 1 < A < p and 1 < B < p before doing anything else.

   Entropy collapse. A 1024-bit prime p means the shared secret has roughly 1024 bits of entropy. Reducing to shared % 256 throws away the other 1016 bits and gives you 256 candidate keys total - already brute-forceable without DH. A real KDF (HKDF) would absorb the whole shared secret and expand into a full-size key; this protocol throws all that work away in one line.

   If shared % 256 doesn't produce a flag, read encryption.py more carefully and try the next-most-likely derivations: high byte (shared >> 8 & 0xFF), the SHA-256 of str(shared) truncated to 1 or 16 bytes, or the raw shared bytes via shared.to_bytes((shared.bit_length()+7)//8, 'big'). The brute snippet above tries the common ones in order.

   See RSA attacks for CTF for the broader public-key attack catalogue and AES for CTF for symmetric KDF practice.

   Diffie-Hellman walkthrough (toy parameters):
     Public params:  p = 23,  g = 5
   
     Alice picks a = 6 (private)
       Computes A = g^a mod p = 5^6 mod 23
                 = 15625 mod 23
                 = 8
     Bob picks b = 15 (private)
       Computes B = g^b mod p = 5^15 mod 23
                 = 30517578125 mod 23
                 = 19
   
     Public exchange: Alice sends A=8, Bob sends B=19.
   
     Alice computes shared = B^a mod p = 19^6 mod 23
                                       = 47045881 mod 23
                                       = 2
     Bob computes   shared = A^b mod p = 8^15 mod 23
                                       = 35184372088832 mod 23
                                       = 2
   
   Both arrive at the same shared = 2 without exchanging it.
   
   Now suppose Bob's private key b = 15 LEAKS.
   An eavesdropper sees A = 8 (from the public network) and learns
   b = 15 from the leak. They compute:
     shared = A^b mod p = 8^15 mod 23 = 2
   
   The shared secret is recovered without ever solving the discrete
   log problem.
   
   In this challenge, p is a 1024-bit prime, but the principle is
   identical: pow(A, b, p) recovers shared in microseconds.
   
   Then key = shared % 256 reduces to one byte. XOR each ciphertext
   byte with this byte:
     ct[i] XOR key  -->  pt[i]
   
   For the toy: if ct = [0x70, 0x69, 0x63, 0x6f] XOR 0x02 = [0x72, 0x6b, 0x61, 0x6d],
   then "rkam" is the wrong recovery (toy params lack proper byte semantics);
   in the real challenge the recovered byte XOR produces "pico..." and the
   flag emerges.

Flag

Diffie-Hellman with a leaked private key b. Compute shared = A^b mod p, then key = shared % 256. XOR each ciphertext byte with key to decrypt the flag.