PriMeD5

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-22 | Status: Solved Techniques: gcd_oracle_leak, md5_identical_prefix_collision, prime_composite_collision, rsa_signature_reuse

Summary

Task: a service signs RSA-PKCS1v15 over MD5(long_to_bytes(p)) only for primes p, but the check path re-uses the signature without re-testing primality and leaks FLAG[:gcd(a,p)]. Solution: generate an MD5 collision between a PRIME p0 and a COMPOSITE p1 (both <=1024 bits, same MD5 of long_to_bytes) using fastcoll identical-prefix collisions, where p1 has a small known prime factor f>=26 (found f=199); sign p0 to obtain a signature valid for p1's identical digest, then call check(p1, sig, a=f) so gcd(f,p1)=f>=len(flag) leaks the entire 26-char flag at once.

PriMeD5 — cryptohack (Hashes)

Description

"Primality checking is expensive so I made a service that signs primes, allowing anyone to quickly check if a number is prime."

Server socket.cryptohack.org:13392:

 python read-only • copy allowed Copy
FLAG = "crypto{??????????????????}"          # 26 chars

elif msg["option"] == "sign":
    p = int(msg["prime"])
    if p.bit_length() > 1024:    return {"error": "The prime is too large."}
    if not isPrime(p):           return {"error": "You must specify a prime."}
    hash = MD5.new(long_to_bytes(p))
    return {"signature": sig_scheme.sign(hash).hex()}      # RSA PKCS1v15 over MD5
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

elif msg["option"] == "check":
    p   = int(msg["prime"])
    sig = bytes.fromhex(msg["signature"])
    hash = MD5.new(long_to_bytes(p))
    sig_scheme.verify(hash, sig)                            # NO isPrime here!
    a = int(msg["a"])
    if a < 1:    return {"error": "`a` value invalid"}
    if a >= p:   return {"error": "`a` value too large"}
    g = math.gcd(a, p)
    return {"msg": f"Valid signature. First byte of flag: {FLAG[:g]}"}

Analysis

The leak FLAG[:gcd(a,p)] is the goal — we need gcd(a,p) >= 26 to dump the whole flag. Note the asymmetry: the sign path enforces isPrime(p), but the check path does not. If p were prime, gcd(a,p) with 1 <= a < p is always 1 (only one flag char). So we must get a valid signature for a composite p that has a known factor >= 26. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

The signature is RSA_PKCS1v15.sign(MD5(long_to_bytes(p))). The signature binds only the MD5 digest, not the integer p itself. So if two distinct numbers p0 and p1 satisfy MD5(long_to_bytes(p0)) == MD5(long_to_bytes(p1)), a signature obtained for p0 is equally valid when verifying with p1.

Attack plan (classic MD5 collision abuse, hence "part two"):

1. Find an MD5 collision pair (p0, p1) with MD5(long_to_bytes(p0)) == MD5(long_to_bytes(p1)).
2. Arrange that p0 is prime (so we can sign it) and p1 is composite with a small known prime factor f >= 26 (so check(p1, sig, a=f) leaks FLAG[:f] = the whole flag).
3. Both must be <= 1024 bits. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

fastcoll produces identical-prefix MD5 collisions: two 128-byte messages with equal MD5. With no prefix, each 128-byte blob is a 1024-bit integer, and long_to_bytes(int(blob)) round-trips to the same blob as long as the top byte is nonzero (so the byte length is preserved). We just keep generating fresh collision pairs and test both orderings until one side is prime and the other is composite with a small prime factor >= 26.

Solution

Search (full solver solve_primed5.py, search loop primed5_search.py, factor found: 199): ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

 python read-only • copy allowed Copy
import subprocess, os
from Crypto.Hash import MD5
from Crypto.Util.number import long_to_bytes, isPrime

FASTCOLL = ".../resources/fastcoll/fastcoll"
SMALL_PRIMES = sieve(100_000)

def trial_factor(n):                      # smallest prime factor >= 26 (short -> small `a`)
    for d in SMALL_PRIMES:
        if d < 26: continue
        if d >= n: break
        if n % d == 0: return d
    return None

def gen_pair():
    subprocess.run([FASTCOLL, "-q", "-o", "p_m1.bin", "p_m2.bin"], check=True, capture_output=True)
    return open("p_m1.bin","rb").read(), open("p_m2.bin","rb").read()
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def find_collision():
    while True:
        a, b = gen_pair()
        na, nb = int.from_bytes(a,"big"), int.from_bytes(b,"big")
        if long_to_bytes(na)!=a or long_to_bytes(nb)!=b:        continue   # length round-trip
        if MD5.new(long_to_bytes(na)).digest() != MD5.new(long_to_bytes(nb)).digest(): continue
        if na.bit_length()>1024 or nb.bit_length()>1024:        continue
        for prime_cand, comp_cand in ((na,nb),(nb,na)):
            if isPrime(prime_cand):
                f = trial_factor(comp_cand)
                if f is not None and 40 <= f < comp_cand:
                    return prime_cand, comp_cand, f

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Then drive the oracle:

 python read-only • copy allowed Copy
p0, p1, f = find_collision()                  # p0 prime, p1 composite, f = 199 (found)
assert isPrime(p0) and p1 % f == 0
assert MD5.new(long_to_bytes(p0)).digest() == MD5.new(long_to_bytes(p1)).digest()

sign  = call({"option":"sign",  "prime": str(p0)})            # signs MD5(p0)
sig   = sign["signature"]
check = call({"option":"check", "prime": str(p1),             # same digest -> verifies
              "signature": sig, "a": str(f)})                  # gcd(199,p1)=199 >= 26
print(check["msg"])                                            # "First byte of flag: crypto{...}"

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Since gcd(a=199, p1) = 199 >= 26 = len(FLAG), FLAG[:199] == FLAG — the full flag is returned.

The actual collision found (primed5_found.txt): p0 (prime) and p1 (composite, factor 199) are the two 1024-bit integers; f = 199.

Takeaways

Use this technique when:

• A signature/verification scheme binds only a hash digest (here MD5) and the hash is collision-broken — sign a benign message, reuse the signature for a colliding malicious one.
• Validation is inconsistent between sign and verify paths (sign tests isPrime, check does not) — find any property checked on one side but trusted on the other.
• A leak is gated by gcd(a, n) and n is attacker-influenced — make n composite with a chosen factor so the gcd (and the leaked prefix length) is large.
• fastcoll gives free identical-prefix MD5 collisions; round-trip both blobs through long_to_bytes/int.from_bytes and keep the top byte nonzero to preserve the integer length. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍