ctf-crypto-prng

Files (1)

• SKILL.md

SKILL.md (first lines)

# CTF Crypto — PRNG Attacks

Mersenne Twister state recovery, time-seeded brute force, LCG, V8 Math.random.

---

## Phase 1: Identify PRNG Type

```python
# Python random (Mersenne Twister):
import random
# Generated: random.random(), random.randint(), random.choice()
# Internal state: 624 32-bit integers

# C rand() (LCG):
# state = state * 1103515245 + 12345
# output = (state >> 16) & 0x7fff

# JavaScript Math.random (V8 XorShift128+):
# 128-bit state, outputs doubles

# Custom PRNG (identify from source):
# LCG: x[n+1] = (a*x[n] + c) mod m
# LFSR: shift register with XOR taps
```

---

## Phase 2: Mersenne Twister State Recovery

```python
# Need: 624 consecutive 32-bit outputs (from random.getrandbits(32))

def untemper(y):
    """Reverse the Mersenne Twister temper operation."""
    # Inverse of y ^= y >> 18:
    y ^= y >> 18
    # Inverse of y ^= (y << 15) & 0xefc60000:
    y ^= (y << 15) & 0xefc60000
    # Inverse of y ^= (y << 7) & 0x9d2c5680:
    y ^= (y << 7) & 0x9d2c5680
    y ^= (y << 14) & (0x9d2c5680 & (0x9d2c5680 << 7))
    # Inverse of y ^= y >> 11:
    y ^= y >> 11
    y ^= y >> 22
    return y & 0xFFFFFFFF

# Collect 624 outputs from target:
outputs = [int(input(f"Output {i}: "), 16) for i in range(624)]

# Recover internal state:
state = [untemper(y) for y in outputs]

# Reconstruct random module state:
import random

# Inject recovered state:
state_formatted = [3, *state, 624]
random.setstate((3, tuple(state_formatted), None))

# Now predict all future outputs:
print("Next:", random.getrandbits(32))
print("Next:", random.getrandbits(32))
```

---

## Phase 3: Time-Seeded PRNG Brute Force

```python
import random, time, ctypes

# UNIX timestamp seeded:
TARGET_TOKENS = [...]    # observed tokens from target

def crack_seed_unix(tokens, window=3600):
    """Try timestamps in a window around now."""
    now = int(time.time())
    
    for seed in range(now - window, now + 1):
        random.seed(seed)
        candidate_tokens = [random.randint(0, 2**32) for _ in range(len(tokens))]
        if candidate_tokens == tokens:
            print(f"Seed: {seed} (unix timestamp)")
            return seed
    return None

# C rand() seeded (use ctypes to sync with libc):
libc = ctypes.CDLL("libc.so.6")

def crack_c_rand(target_values, window=3600):
    now = int(time.time())
    
    for seed in range(now - window, now + 1):
        libc.srand(seed)
        candidates = [libc.rand() for _ in range(len(target_values))]
        if candidates == target_values:
            print(f"C rand() seed: {seed}")
            return seed
    
# Millisecond precision from file metadata:
import os
stat = os.stat("generated_file.txt")
mtime_ms = int(stat.st_mtime * 1000)

for seed in range(mtime_ms - 100, mtime_ms + 100):
    random.seed(seed)
    # test...
```

---

## Phase 4: LCG Parameter Recovery

```python
# LCG: x[n+1] = (a * x[n] + c) mod m
# Given several consecutive outputs, recover a, c, m

def recover_lcg(outputs):

From Yoraexe/ceobe, MIT.

More from Yoraexe/ceobe