kavklaw@llm $ cat writeup.md
Bleichenbacher's RSA Signature Forgery (e=3, CVE-2006-4339)
CloudCompany's email signing server uses RSA to sign outgoing emails. Threat actors impersonated the vendor by forging email signatures. We're given the server source code and need to replicate the attack — forge a valid signature that's different from the original.
Before we dive in, let's make sure we understand the fundamental concepts this challenge is built on. If you already know RSA and digital signatures, feel free to skip ahead to the vulnerability analysis.
RSA is a system that uses two mathematically linked keys:
The math is elegant: raising a number to the power e and then to the power d (both modulo n) gives you back the original number. In other words: (me)d mod n = m. This works because of how e, d, and n are constructed from prime numbers.
A digital signature proves that a message really came from who it claims. Here's how RSA signatures work:
d: signature = hash(message)d mod ne: result = signaturee mod n. If result equals the hash of the message, the signature is valid.Without the private key d, you can't create a valid signature. At least, that's how it's supposed to work...
The challenge server does the following:
e = 3 (this is unusual — we'll explain why)There are two bugs here that, combined, make forgery trivial. Let's examine each one.
class RSA():
def __init__(self, key_length):
self.e = 3 # ← Dangerously small public exponentThe public exponent e is how "hard" it is to reverse an RSA operation. Standard RSA uses e = 65537. This challenge uses e = 3.
Why does this matter? Remember, verification computes signaturee mod n. With e = 3, we're computing signature3 mod n — that's just a cube. And computing cube roots is easy — even for numbers with thousands of digits.
Here's a simple analogy. Imagine RSA verification is like a lock that requires you to guess a number that, when cubed, gives a specific result. If the "cubing" is replaced by "raising to the 65537th power," guessing becomes impossibly hard. But cubing? You just compute the cube root. That's elementary math.
Let's make this concrete with small numbers:
# With e=3: Find s such that s³ = target
# Target: 27 → s = ∛27 = 3. Trivial!
# With e=65537: Find s such that s^65537 = target
# This is computationally infeasible without the private key.Before we look at the code, let's understand what PKCS#1 v1.5 is supposed to look like. When you sign a message with RSA, the signature doesn't just contain the hash — it contains a structured block that fills the entire key length (256 bytes for a 2048-bit key):
Proper PKCS#1 v1.5 signature block (256 bytes total):
┌──────────────────────────────────────────────────┐
│ 0x00 0x01 │ 0xFF 0xFF 0xFF ... 0xFF │ 0x00 │ ASN.1 │ SHA-1 hash │
│ 2 bytes │ at least 8 bytes of │1 byte│15 bytes│ 20 bytes │
│ │ 0xFF padding │ │ │ │
└──────────────────────────────────────────────────┘
↑ ↑ ↑ ↑ ↑
Header Padding (fills Separator Algorithm The actual
the ENTIRE block) identifier hash valueThe ASN.1 bytes identify which hash algorithm was used (SHA-1, SHA-256, etc.), and the padding 0xFF bytes fill ALL remaining space. A correct verifier checks that the entire block matches this structure exactly.
Now let's look at the challenge's broken verification code:
def verify(self, message, signature):
keylength = len(long_to_bytes(self.n))
decrypted = self.encrypt(signature) # s^e mod n
clearsig = decrypted.to_bytes(keylength, "big")
r = re.compile(b'\x00\x01\xff+?\x00(.{15})(.{20})', re.DOTALL)
m = r.match(clearsig)
# ^^^^
# CRITICAL: \xff+? is non-greedy — only needs ONE \xff byte
# AND: no check for what comes AFTER the 20-byte hash!
if not m:
raise VerificationError('Verification failed')
if m.group(1) != self.asn1:
raise VerificationError('Verification failed')
if m.group(2) != sha1(message).digest():
raise VerificationError('Verification failed')
return TrueThe verification uses a regex to check the decrypted signature block. Let's break down what the regex \x00\x01\xff+?\x00(.{15})(.{20}) is looking for:
\x00\x01 — The header bytes (correct)\xff+? — One or more 0xFF bytes... but with a non-greedy quantifier! The ? after + means "match as few as possible." This means the regex is satisfied with just one single 0xFF byte, instead of requiring the padding to fill the entire block.\x00 — The separator byte (correct)(.{15}) — Captures 15 bytes (the ASN.1 identifier)(.{20}) — Captures 20 bytes (the SHA-1 hash)Three critical flaws:
\xff+? (non-greedy) — Only requires one \xff byte. Proper PKCS#1 requires the padding to fill the entire block, which for a 2048-bit key means about 218 bytes of \xff.This means the verifier will accept a block that looks like this:
What the verifier ACTUALLY requires (only 39 bytes of structure!):
┌────────────────────────────────────────────────────────────────┐
│ 0x00 0x01 │ 0xFF │ 0x00 │ ASN.1 (15 bytes) │ SHA-1 (20 bytes) │ ANYTHING │
│ 2 bytes │1 byte│1 byte│ │ │217 bytes!│
└────────────────────────────────────────────────────────────────┘
↑
We control these!
They can be garbage!This is exactly CVE-2006-4339 — Daniel Bleichenbacher's 2006 attack against PKCS#1 v1.5 signature verification. Bleichenbacher presented this at CRYPTO 2006, and it affected Firefox, OpenSSL, GnuTLS, NSS, and dozens of other implementations. The core insight: if the verifier doesn't check the entire block, the attacker has enormous freedom to forge signatures.
Let's combine both bugs. We need to find an integer s (our forged signature) such that when the server computes s3 mod n, the result matches the loose regex pattern.
Since we can fill 217 out of 256 bytes with anything we want, we only need to control the first 39 bytes of s³. Here's the target structure:
s³ = \x00\x01\xff\x00 + ASN.1(15 bytes) + SHA1(20 bytes) + [anything]
^^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^^ ^^^^^^^^^^^^^^ ^^^^^^^^^^
4 bytes 15 bytes 20 bytes 217 bytes of garbageThat's only 39 bytes (312 bits) of constrained prefix out of 256 total bytes (2048 bits). The remaining 217 bytes (1,736 bits) can be anything — that's enormous freedom.
Here's the key insight that makes the attack work. Since e = 3, "verifying" the signature means computing s³ mod n. But what if s³ is smaller than n? Then the modular reduction does nothing: s³ mod n = s³ exactly. No modular arithmetic needed!
This means: if we can find a number s whose cube starts with our 39-byte prefix, we have a valid forgery. And finding such an s is just... computing a cube root.
The algorithm:
\x00\x01\xff\x00 + ASN.1 + SHA1(user_email)\x00 for the lower bound and \xff for the upper bounds = ⌈∛(lower_bound)⌉ (the smallest integer whose cube is ≥ the lower bound)s³ falls within [lower_bound, upper_bound]With 217 bytes of unrestricted suffix, the range [target_low, target_high] spans 21736 consecutive integers. How many perfect cubes exist in this range?
The density of perfect cubes near a number N is approximately 1 / (3 × N2/3). For our range, that gives approximately 21736 / (3 × 21365) ≈ 2370 valid cubes. That's an astronomically large number — we're guaranteed to find one immediately.
Now let's turn the theory into working code:
#!/usr/bin/env python3
"""Bleichenbacher e=3 RSA Signature Forgery"""
import socket, re
from hashlib import sha1
from Crypto.Util.number import long_to_bytes, bytes_to_long
from Crypto.PublicKey import RSA as PYRSA
def integer_cube_root(n):
"""Newton's method for integer cube root."""
if n == 0: return 0
x = 1 << ((n.bit_length() + 2) // 3)
while True:
y = (2 * x + n // (x * x)) // 3
if y >= x: return x
x = y
def forge_signature(n, user):
keylength = len(long_to_bytes(n)) # 256 bytes
asn1 = b"\x30\x21\x30\x09\x06\x05\x2b\x0e\x03\x02\x1a\x05\x00\x04\x14"
hash_value = sha1(user).digest()
# Construct target block prefix (39 bytes)
prefix = b'\x00\x01\xff\x00' + asn1 + hash_value
suffix_len = keylength - len(prefix) # 217 bytes
# Lower bound: prefix + all zeros
target_low = int.from_bytes(prefix + b'\x00' * suffix_len, 'big')
# Upper bound: prefix + all 0xff
target_high = int.from_bytes(prefix + b'\xff' * suffix_len, 'big')
# Find s where target_low <= s³ <= target_high
s = integer_cube_root(target_low)
while s ** 3 < target_low:
s += 1
# Verify
cube = s ** 3
assert target_low <= cube <= target_high, "Cube out of range!"
assert cube < n, "Cube wraps around mod n!"
# Confirm regex matches
clearsig = cube.to_bytes(keylength, 'big')
r = re.compile(b'\x00\x01\xff+?\x00(.{15})(.{20})', re.DOTALL)
m = r.match(clearsig)
assert m and m.group(1) == asn1 and m.group(2) == hash_value
return long_to_bytes(s)
# Connect → get n from certificate → forge → profit
sock = connect(host, port)
n, user, original_sig = parse_response(sock)
forged = forge_signature(n, user)
sock.send(forged.hex().encode() + b"\n")
# → HTB{...}Let's walk through what this code does, function by function:
The integer_cube_root function uses Newton's method to compute integer cube roots. Even for numbers with thousands of digits, this converges in about 20 iterations — it's practically instant.
The forge_signature function:
\xff + separator + ASN.1 + SHA-1 hash)\xff bytes)s — our forged signatureThe server sends us a signed email containing:
signature: — the original hex-encoded signaturecertificate: — the RSA public key in PEM formatWe extract the modulus n from the PEM certificate and note e = 3.
The user string (what gets signed) is: IT Department <[email protected]>
We compute SHA-1(user) — a 20-byte hash — and construct the 39-byte prefix that must appear at the start of s³.
Using Newton's method for integer cube roots, we find the smallest s where s³ ≥ target_low. This takes microseconds — it's a single integer cube root computation on a ~2048-bit number.
We send our forged signature (which differs from the original, since there are ~2370 valid forgeries and we're almost certainly not hitting the same one). The server computes s³ mod n, runs the flawed regex, and... it passes! Since it's different from the original → we get the flag.
"A Bleichenbacher RSA vuln" — the flag says it all.
e = 3 for RSA signatures. The standard e = 65537 makes this attack computationally infeasible. With e = 65537, you'd need a 65537th root instead of a cube root — and there's no efficient algorithm for that.\xff bytes fill the entire block (not just "one or more")\xff+ (greedy: match as many as possible) and \xff+? (non-greedy: match as few as possible) might seem minor, but it's the difference between a secure and completely broken implementation.pycryptodome — RSA key parsing, number theory utilitieshashlib — SHA-1 hash computation\xff+ (greedy) and \xff+? (non-greedy) transforms a correct check into one that accepts a single padding byte, leaving 217 bytes of attacker-controlled garbage