Super Computer V2 - Write-up

Challenge Description

• Given: prime p, vectors a,b (length m), iv, ct
• PRNG: Python random.seed(seed) → randbytes(16) as AES-CBC key
• Update: y = [x] + y[:0:-1] (reflection!)

Initial Mistake

Initially calculated y_{2K}[0] (even steps) so seed was off by half cycle → meaningless plaintext.

Correct Approach: Track Odd Sequence

Define x_t = first element after each step. Track odd sequence: s_K := x_{2K+1}

Constants

• X0 = sum(a[i] * b[i] for i=0..m-1)
• D = sum(a[i] * b[i] for i=1..m-1)
• C1 = sum(a[i] * b[m-i] for i=1..m-1)
• a0 = a[0]

Recurrence Formula (mod p)

s_K ≡ (a0²)·s_{K-1} + B (mod p)
where s_0 ≡ a0·X0 + C1 (mod p)
      B ≡ a0·D + C1 (mod p)

Index for Seed

• n = 2^T (even)
• Key taken at last odd step: seed = x_{n-1} = x_{2K-1} with K = 2^{T-1}
• Need s_{K-1} as seed!

Closed Form

With K = 2^{T-1}:

• If a0² ≢ 1 (mod p):
  • e = (K-1) mod (p-1)
  • s_{K-1} ≡ (a0²)^e · s_0 + B · [(a0²)^e - 1] / [a0² - 1]
• If a0² ≡ 1 (mod p):
  • s_{K-1} ≡ s_0 + (K-1)·B

Attack

1. Calculate X0, D, C1, a0 → s0, B
2. Calculate s_{K-1} via closed form
3. random.seed(s_{K-1}); key = random.randbytes(16)
4. Decrypt AES-CBC

Flag

BPCTF{Man1pula7in6_M4tr1X_l1k3_M4gic}

Pitfalls

• Using y_{2K}[0] instead of x_{2K-1}
• Wrong indices in D/C1
• Forgot to handle a0² ≡ 1 case
• Environment issues with pycryptodome