//p34kC0nj3c7ur3
Author: jrke
Remote: nc remote.infoseciitr.in 4002
Flag: flag{1r0n_m4n_f0r_c0ll4tz_3ndg4m3_0f_cryp70gr4phy_1s_p34k_r16h7_313}
>TL;DR
The server leaked uniqueHash(uniqueHash(message)). Because uniqueHash is just the Collatz step counter capped at 10k, the secret myHash = uniqueHash(message) is at most 10000. That means we can enumerate every possible myHash that maps to the leaked value and simply test each candidate by sending 2^myHash (whose hash equals its exponent). Once we learn the real myHash, we can algorithmically generate as many valid preimages as we need—either composites (easy) or primes (a bit trickier). After feeding ten valid values, the server prints the flag.
>Challenge Overview
chall.py implements:
uniqueHash(x)– Collatz steps until hitting1, capped at10000iterations.- Converts an unknown
messageto a long integer and computesmyHash = uniqueHash(message). - Prints
uniqueHash(myHash)and requires 10 distinct inputs whose hashes equalmyHashand whose primality matches that of the real message.
Key excerpts:
python
message = bytes_to_long(message)
myHash = uniqueHash(message)
print("This is my hash of hash:", uniqueHash(myHash))
if uniqueHash(x) == myHash and isPrime(x) == isPrime(message):
print("Correct!")
Observations:
uniqueHashoutput is small (≤ 10k).uniqueHashis not injective, so the leaked outer hash narrowsmyHashdown to a few dozen candidates.- Simple test vectors (
2^k) giveuniqueHash(2^k) = k, so probing is trivial. - Collatz is reversible enough to manufacture composites and even primes with a chosen step count.
>Local Recon and Strategy
- Stub the message: I dropped in a dummy
message.py(flag{test_flag_for_local}) to run the script offline. - Measure uniqueHash ranges: Random 256-bit samples showed step counts well under the 10k cap, so brute force on
myHashis viable. - Find candidate myHash values: For any leaked
h2 = uniqueHash(myHash), computeuniqueHash(n)for every1 ≤ n ≤ 10000and keep those withuniqueHash(n) == h2. This yields at most ~200 candidates. - Probe
myHash: Sendingx = 1 << candidatereturns the same step count ascandidate. The response tells us whether the target message is prime (server replies "Well Well…") or composite ("Correct!"). - Generate valid submissions:
- Composite case: take any odd base with known step count, left-shift it enough to reach the target steps; shifting preserves parity and ensures compositeness.
- Prime case: reverse Collatz a couple of steps at a time using the formula (x = \frac{b \cdot 2^{k+1} - 1}{3}) with carefully chosen
bandk. Random sampling plus primality tests produces suitable primes quickly.
All of that logic lives in solver.py (see below).
Local End-to-End Test
bash
python3 solver.py 47 --target 1494 --count 10 > locals.txt
python3 - <<'PY'
from solver import composite_preimages, unique_hash
from Cryptodome.Util.number import bytes_to_long
from message import message
my_hash = unique_hash(bytes_to_long(message))
values = composite_preimages(my_hash, 10)
...
PY
Feeding those values into chall.py printed flag{test_flag_for_local}, confirming the approach.
>Solver Script
Full source for solver.py used for both local and remote exploitation:
python
import argparse
import random
from typing import List
from Cryptodome.Util.number import isPrime
MAX_STEPS = 10_000
def unique_hash(x: int) -> int:
"""Deterministic Collatz step counter with a hard stop at MAX_STEPS."""
if x < 0:
raise ValueError("unique_hash expects a non-negative integer")
steps = 0
while x != 1:
steps += 1
if x % 2 == 0:
x //= 2
else:
x = 3 * x + 1
if steps >= MAX_STEPS:
return steps
return steps
def candidates_for_second_hash(second_hash: int) -> List[int]:
"""Return every myHash candidate that matches the leaked hash-of-hash."""
if second_hash <= 0:
raise ValueError("hash-of-hash must be positive")
candidates: List[int] = []
for value in range(1, MAX_STEPS + 1):
if unique_hash(value) == second_hash:
candidates.append(value)
return candidates
def composite_preimages(target: int, count: int = 10, base_limit: int = 2000) -> List[int]:
"""Generate many composites whose unique_hash equals target."""
numbers: List[int] = []
seen = set()
for odd in range(3, base_limit, 2):
steps = unique_hash(odd)
if steps >= target:
continue
shift = target - steps
if shift <= 0:
continue
candidate = odd << shift
if candidate in seen:
continue
numbers.append(candidate)
seen.add(candidate)
if len(numbers) == count:
return numbers
raise RuntimeError("Not enough composite preimages; bump base_limit or target")
def prime_preimages(
target: int,
count: int = 10,
max_trials: int = 500_000,
base_bits: int = 256,
) -> List[int]:
"""Generate primes with the requested step count via structured inverse steps."""
rng = random.SystemRandom()
primes: List[int] = []
seen = set()
for _ in range(max_trials):
base = rng.getrandbits(base_bits) | 1
if base % 3 == 0:
continue
steps = unique_hash(base)
k = target - steps - 2
if k < 0:
continue
if (pow(2, k + 1, 3) * (base % 3)) % 3 != 1:
continue
candidate = ((base << (k + 1)) - 1) // 3
if candidate in seen:
continue
if isPrime(candidate):
primes.append(candidate)
seen.add(candidate)
if len(primes) == count:
return primes
raise RuntimeError(
"Prime search exhausted; increase max_trials, base_bits, or adjust RNG seed"
)
def format_numbers(values: List[int]) -> str:
lines = []
for idx, value in enumerate(values, 1):
lines.append(f"{idx:02d}: dec={value} hex={value:x}")
return "\\n".join(lines)
def main() -> None:
parser = argparse.ArgumentParser(description="Helper utilities for p34kC0nj3c7ur3")
parser.add_argument("hash_of_hash", type=int, help="Printed unique_hash(myHash)")
parser.add_argument(
"--target",
type=int,
help="Concrete myHash value once identified (must be <= 10000)",
)
parser.add_argument(
"--count",
type=int,
default=10,
help="How many numbers to generate (default: 10)",
)
parser.add_argument(
"--base-limit",
type=int,
default=2000,
help="Odd base search bound for composite generation",
)
parser.add_argument(
"--mode",
choices=["composite", "prime"],
default="composite",
help="Type of witnesses to generate once target is known",
)
parser.add_argument(
"--prime-trials",
type=int,
default=500_000,
help="Random base samples when searching for primes",
)
parser.add_argument(
"--prime-bits",
type=int,
default=256,
help="Bit-size of random bases used for prime generation",
)
args = parser.parse_args()
candidates = candidates_for_second_hash(args.hash_of_hash)
print(f"hash_of_hash={args.hash_of_hash} -> {len(candidates)} candidate myHash values")
if len(candidates) < 25:
print("candidates:", candidates)
else:
print("first few candidates:", candidates[:10], "...")
if args.target is None:
return
if args.target not in candidates:
raise ValueError("Provided target is not compatible with the leaked hash-of-hash")
if args.mode == "composite":
values = composite_preimages(args.target, args.count, args.base_limit)
else:
values = prime_preimages(args.target, args.count, args.prime_trials, args.prime_bits)
print(format_numbers(values))
if __name__ == "__main__":
main()
>Remote Exploitation Walkthrough
- Grab the banner:
bash
$ nc [remote.infoseciitr.in](http://remote.infoseciitr.in/) 4002
This is my hash of hash: 25- Enumerate candidates:
python3 solver.py 25→ 64 possibilities, largest ~4301. - Probe via
2^k: A quick script looped through the candidate list (largest to smallest). The first "interesting" response was atk = 4017:
Correct!→ would imply composite secret.Well Well, you failed!→ meansisPrime(message)isTrue. (The server responds “failed” when parity differs.)
We got the latter, so message is prime and myHash = 4017.
- Generate primes:
python3 solver.py 25 --target 4017 --mode prime --count 10 --prime-trials 2000000 --prime-bits 256 > primes.txt
- Random structured reverse steps gave ten huge primes in a few seconds.
- Send solutions automatically:
bash
python3 send_remote.py # small pwntools helper that replays primes.txtEach submission returned "Correct!", and after the tenth the server emitted the flag.
Result:
Wow! you know my message is: b'flag{1r0n_m4n_f0r_c0ll4tz_3ndg4m3_0f_cryp70gr4phy_1s_p34k_r16h7_313}'