Breaking ChaCha20-Poly1305: Exploiting Nonce Reuse in picoCTF 2025
Challenge Info:
- Platform: picoCTF 2025
- Category: Cryptography
- Difficulty: Hard
- Vulnerability: Nonce Reuse (ChaCha20-Poly1305)
What you'll need:
- Basic XOR operations (we'll explain as we go)
- What a polynomial is (like $x^2 + 2x + 1$)
- Some Python familiarity (we provide all the code)
Understanding the Challenge
So we've got a server encrypting messages with ChaCha20-Poly1305 - a modern, supposedly bulletproof encryption algorithm. Looks pretty secure on the surface.
But there's a massive screwup: The server reuses the same Nonce (Number Used Once) for every single message.
What we're doing: Exploiting this "Nonce Reuse" bug to break both the encryption (confidentiality) and the message authentication (integrity), then forge our own valid message to get the flag.
Figure 1: Here's the whole attack laid out. It all starts with the server screwing up by reusing the same nonce over and over (Step 1). Once we spot that, we grab some encrypted messages (Step 2), XOR them together to extract the keystream (Step 3), solve some polynomial equations to break the authentication math (Step 4), and finally craft our own fake message that passes all the checks (Step 5). Each step builds on the one before it - it's like a chain reaction where breaking one thing lets us break everything else.
Analyzing the Vulnerable Code
Here's the vulnerable server script. Notice how nonce gets generated once at the top and then reused in the encrypt function for every message.
import secrets
import hashlib
from Crypto.Cipher import ChaCha20_Poly1305
flag = open("flag.txt").read().strip()
def shasum(x):
return hashlib.sha256(x).digest()
key = shasum(shasum(secrets.token_bytes(32) + flag.encode()))
# Generate a random nonce to be extra safe
# PROBLEM: This runs ONCE when the program starts...
nonce = secrets.token_bytes(12)
messages = [
"Did you know that ChaCha20-Poly1305 is an authenticated encryption algorithm?",
"That means it protects both the confidentiality and integrity of data!"
]
goal = "But it's only secure if used correctly!"
def encrypt(message):
# ...and gets reused here EVERY time!
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
ciphertext, tag = cipher.encrypt_and_digest(message)
return ciphertext + tag + nonce
def decrypt(message_enc):
ciphertext = message_enc[:-28]
tag = message_enc[-28:-12]
nonce = message_enc[-12:]
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)
plaintext = cipher.decrypt_and_verify(ciphertext, tag)
return plaintext
for message in messages:
print("Plaintext: " + repr(message))
message = message.encode()
print("Plaintext (hex): " + message.hex())
ciphertext = encrypt(message)
print("Ciphertext (hex): " + ciphertext.hex())
print()
print()
user = bytes.fromhex(input("What is your message? "))
user_message = decrypt(user)
print("User message (decrypted): " + repr(user_message))
if goal in repr(user_message):
print(flag)
Identifying the Bug
The bug is tiny but catastrophic. Check out these two lines:
- Line 14:
nonce = secrets.token_bytes(12)- Runs once at startup. Picks one random number.
- Line 25:
cipher = ChaCha20_Poly1305.new(key=key, nonce=nonce)- Runs every time a message gets encrypted.
- Uses that same random number over and over.
Think of it like this: You lock your house with a new key every day, but you hide it under the same doormat every time. An attacker doesn't need to pick the lock - just check under the mat once. Because the hiding spot (Nonce) never changes, security is toast.
Understanding the Impact
The Core Problem
Encryption relies on randomness. If you use the same Nonce twice with the same key, the whole security thing falls apart. This challenge shows how one reuse lets us break both secrecy (ChaCha20) and integrity (Poly1305).
Breaking the Encryption (ChaCha20)
ChaCha20 is a Stream Cipher. It generates a long stream of random bytes called a Keystream $K$, then combines it with your message $P$ to make ciphertext $C$.
The operation is just XOR $\oplus$: $$C = P \oplus K$$
Normally, $K$ changes for every message because the Nonce changes. But here, $K$ stays the same. If we grab a known message pair ($P_1, C_1$), we can just recover the Keystream: $$K = P_1 \oplus C_1$$
Once we have $K$, we can decrypt anything or encrypt our own message $P_{goal}$ by XORing again: $$C_{goal} = P_{goal} \oplus K$$
Breaking the Authentication (Poly1305)
This part's trickier. Even if we can encrypt a fake message, the server will reject it because we don't have the right Authentication Tag. We need to forge this.
Poly1305 makes a Tag $T$ using a polynomial:
What's a Polynomial? Like a recipe:
- Take ingredient 1, multiply by $r^3$
- Take ingredient 2, multiply by $r^2$
- Add them all up
The result is your authentication tag (before adding 's').
$$T = \underbrace{(m_1 r^n + m_2 r^{n-1} + \dots)}_{\text{Polynomial } P(r)} + s \pmod p$$
- $r$ (Evaluation Point): Stays constant for the session.
- $s$ (Secret Mask): Should be random per message, but it's static here because of nonce reuse.
Attack Phase 1: The Mathematical Foundation
We need to find the secret keys $r$ and $s$.
The "Elimination" Trick
We have two equations from two messages we captured:
- $T_1 = P_1(r) + s$
- $T_2 = P_2(r) + s$
Since $s$ is the same in both, we can subtract them to make $s$ disappear!
Simple Example
Say we have two equations where s is 10:
- Tag 1: $50 = (Message_1 \times r) + 10$
- Tag 2: $30 = (Message_2 \times r) + 10$
Subtract them: $$50 - 30 = (Message_1 \times r) - (Message_2 \times r)$$ $$20 = r \times (Message_1 - Message_2)$$
The secret 10 just vanished! Now we can solve for r.
In our challenge, we're using polynomials instead of simple multiplication. But the principle is identical: subtract them, and 's' is gone.
$$T_1 - T_2 = P_1(r) - P_2(r)$$
Now we have an equation with just one unknown: $r$.
Figure 2: How subtraction works. Both messages follow the same curve but shifted up by s. When we subtract (Msg 1 - Msg 2), we kill the vertical shift s, leaving just the "difference" function. Finding where this equals zero gives us the secret r.
Quick recap:
- Nonce reuse → We can grab the keystream (easy XOR)
- Same nonce → The secret 's' stays the same
- Two messages → Two equations with same 's'
- Subtract equations → 's' disappears, solve for 'r'
- Know r and s → We can forge anything
Attack Phase 2: Implementing the Solution
Finding $r$ (Root Finding)
We make a new function $F(x)$ from our combined equation: $$F(x) = P_1(x) - P_2(x) - (T_1 - T_2)$$
We just need to find where $F(x) = 0$. Using SymPy, we can use the Cantor-Zassenhaus algorithm to find roots instantly over the huge prime field $GF(2^{130}-5)$.
Finding $s$
Once we have $r$, plug it back into our first equation: $$s = T_1 - P_1(r)$$
Forging the Message
With $r$, $s$, and the Keystream ($K$), we have total control.
Attack Phase 3: Executing the Exploit
We build the attack in Python with pwntools and sympy.
Step 1: Grab the Keystream
Capture a known plaintext/ciphertext pair from the server and XOR them to get $K$.
keystream = xor(p1, c1)
Step 2: Solve for $r$ and $s$
Format the messages as polynomials and use SymPy to find roots. Important: we check a small range for the modulo $2^{128}$ overflow ($k$).
# SymPy finds the polynomial roots
candidates = solve_r_sympy(c1, t1, c2, t2)
Step 3: Verify
The solver might return multiple roots. We verify the right one by checking if it correctly predicts the tag for the second message.
Step 4: Forge the Payload
With the correct keys, we encrypt our request and generate a valid tag.
# Encrypt
c_goal = xor(msg_goal, keystream)
# Generate Tag
t_goal = (poly_eval(c_goal, r) + s) % 2**128
The server accepts our forged message as legit, and we win.
Complete Exploit Script
from pwn import *
from sympy import symbols, Poly
from Crypto.Util.number import bytes_to_long
# --- Configuration ---
HOST = 'activist-birds.picoctf.net'
PORT = 56031
P = 2**130 - 5 # The Poly1305 Prime
msg_goal = b"But it's only secure if used correctly!"
# --- Helper Functions ---
def parse_output(io):
# Grabs (Plaintext, Ciphertext, Tag) tuples from server
io.recvuntil(b"Plaintext (hex): ")
p1 = bytes.fromhex(io.recvline().strip().decode())
io.recvuntil(b"Ciphertext (hex): ")
c1_full = bytes.fromhex(io.recvline().strip().decode())
io.recvuntil(b"Plaintext (hex): ")
p2 = bytes.fromhex(io.recvline().strip().decode())
io.recvuntil(b"Ciphertext (hex): ")
c2_full = bytes.fromhex(io.recvline().strip().decode())
# Extract Nonce, Ciphertext, and Tag
nonce = c1_full[-12:]
c1 = c1_full[:-28]
t1 = c1_full[-28:-12]
c2 = c2_full[:-28]
t2 = c2_full[-28:-12]
return (p1, c1, t1), (p2, c2, t2), nonce
def to_blocks(data):
# Split data into 16-byte blocks
return [data[i:i+16] for i in range(0, len(data), 16)]
def poly1305_encode(msg):
# Padding and length block
pad_len = (16 - len(msg) % 16) % 16
msg_padded = msg + b'\x00' * pad_len
len_block = (0).to_bytes(8, 'little') + len(msg).to_bytes(8, 'little')
full_block = msg_padded + len_block
coeffs = []
for block in to_blocks(full_block):
val = bytes_to_long(block[::-1])
val += 2**128 # The "Clamp" bit
coeffs.append(val)
# CRITICAL: Poly1305 polynomials end at r^1, not r^0.
# We append 0 so SymPy treats [c1, c2] as c1*x^2 + c2*x + 0
coeffs.append(0)
return coeffs
def solve_r_sympy(c1, t1, c2, t2):
print("[*] Solving for r using SymPy...")
x = symbols('x')
coeffs1 = poly1305_encode(c1)
coeffs2 = poly1305_encode(c2)
# Create Polynomials over the Galois Field
P1 = Poly(coeffs1, x, domain=f'GF({P})')
P2 = Poly(coeffs2, x, domain=f'GF({P})')
tag1 = bytes_to_long(t1[::-1])
tag2 = bytes_to_long(t2[::-1])
diff_tags = tag1 - tag2
possible_roots = []
# Scan for overflows
# Equation: P1(r) - P2(r) - (T1 - T2 + k*2^128) = 0 mod P
for k in range(-5, 6):
target_val = (diff_tags + k * (2**128))
F = P1 - P2 - target_val
try:
# Fast root finding
roots_dict = F.ground_roots()
for root in roots_dict:
possible_roots.append(int(root))
except:
continue
return list(set(possible_roots))
# --- Main Execution ---
io = remote(HOST, PORT)
print("[*] Capturing traffic...")
(p1, c1, t1), (p2, c2, t2), nonce = parse_output(io)
# 1. Recover Keystream
print("[*] Recovering Keystream...")
keystream = xor(p1, c1)
# 2. Encrypt Goal Message
if len(keystream) < len(msg_goal):
print("[-] Not enough keystream bytes.")
exit()
c_goal = xor(msg_goal, keystream[:len(msg_goal)])
# 3. Find 'r'
candidates = solve_r_sympy(c1, t1, c2, t2)
if not candidates:
print("[-] No roots found. The solver failed.")
exit()
# 4. Verify correct 'r' and find 's'
final_r = None
final_s = None
print(f"[*] Verifying {len(candidates)} candidate roots...")
for r_cand in candidates:
# Manual Poly1305 evaluation
# Note: strip the trailing 0 we added for SymPy
coeffs1 = poly1305_encode(c1)[:-1]
h1 = sum(c * pow(r_cand, len(coeffs1)-i, P) for i, c in enumerate(coeffs1)) % P
s_cand = (bytes_to_long(t1[::-1]) - h1) % (2**128)
coeffs2 = poly1305_encode(c2)[:-1]
h2 = sum(c * pow(r_cand, len(coeffs2)-i, P) for i, c in enumerate(coeffs2)) % P
t2_calc = (h2 + s_cand) % (2**128)
if t2_calc == bytes_to_long(t2[::-1]):
final_r = r_cand
final_s = s_cand
break
if final_r is None:
print("[-] Roots found but verification failed.")
exit()
print(f"[+] Found correct keys!\n r: {hex(final_r)}\n s: {hex(final_s)}")
# Forge Tag
coeffs_goal = poly1305_encode(c_goal)[:-1] # Strip trailing 0
h_goal = sum(c * pow(final_r, len(coeffs_goal)-i, P) for i, c in enumerate(coeffs_goal)) % P
t_goal_int = (h_goal + final_s) % (2**128)
t_goal = t_goal_int.to_bytes(16, 'little')
payload = c_goal + t_goal + nonce
print(f"[+] Sending Payload: {payload.hex()}")
io.sendline(payload.hex().encode())
io.interactive()
Understanding the Code
Here's why each part of the script matters:
poly1305_encode(msg): Turning bytes into math
What it does: Converts raw bytes into a list of numbers (coefficients) that SymPy can work with.
How: Poly1305 splits messages into 16-byte chunks, treats each as a little-endian integer, and adds a $2^{128}$ bit (clamping).
The critical fix: We append a 0 at the end: coeffs.append(0). This aligns polynomial degrees so SymPy's $x$ variable matches Poly1305's $r$ variable perfectly.
solve_r_sympy(...): The Engine
Why SymPy? Brute-forcing or using logic solvers (Z3) is way too slow for $2^{130}$. SymPy uses the Cantor-Zassenhaus algorithm to factor polynomials over the finite field $GF(2^{130}-5)$. Finds roots in milliseconds.
The k loop - why range(-5, 6)? When Poly1305 adds 's' to the polynomial result, it uses modulo $2^{128}$ (wraps around like an odometer). This wrapping might cause the value to "overflow" into the larger field modulus $P$ a few times. Since we don't know the exact overflow count (could be 0, ±1, ±2 times), we test a small range to find which gives us valid roots.
Verification Loop
The solver might return multiple roots (math candidates), or we might have guessed wrong on k.
We filter these by trying to get $s$ from the first message and checking if it correctly predicts the second message's tag. Only the real $r$ will satisfy both equations.
The Forgery
Once we confirm $r$ and $s$, we calculate the tag for our goal message.
t_goal_int = (h_goal + final_s) % (2**128): We apply final modulo $2^{128}$ because Poly1305 tags are 128-bit integers, even though internal math happens in the larger field $P$.
Key Takeaways
This challenge hammers home that crypto algorithms like ChaCha20 and Poly1305 are only secure if you use them correctly.
The math relies entirely on certain values (Nonces) never being reused. One tiny implementation mistake - reusing a counter or random value - completely destroys security. Attackers can not just decrypt messages but also forge new ones that look totally valid to the server.