Super Computer V2 - Write-up#

Mô Tả Challenge#

• Cho: prime p, vectors a,b (độ dài m), iv, ct
• PRNG: Python random.seed(seed) → randbytes(16) làm AES-CBC key
• Update: y = [x] + y[:0:-1] (phản chiếu!)

Sai Lầm Ban Đầu#

Ban đầu tính y_{2K}[0] (bước chẵn) nên seed lệch nửa chu kỳ → plaintext vô nghĩa.

Cách Tiếp Cận Đúng: Theo Dõi Dãy Lẻ#

Định nghĩa x_t = phần tử đầu tiên sau mỗi bước. Theo dõi dãy lẻ: s_K := x_{2K+1}

Hằng Số#

• 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]

Công Thức Truy Hồi (mod p)#

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

Index cho Seed#

• n = 2^T (chẵn)
• Key lấy tại bước lẻ cuối: seed = x_{n-1} = x_{2K-1} với K = 2^{T-1}
• Cần s_{K-1} làm seed!

Dạng Đóng#

Với K = 2^{T-1}:

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

Tấn Công#

1. Tính X0, D, C1, a0 → s0, B
2. Tính s_{K-1} qua dạng đóng
3. random.seed(s_{K-1}); key = random.randbytes(16)
4. Giải mã AES-CBC

Flag#

BPCTF{Man1pula7in6_M4tr1X_l1k3_M4gic}

Cạm Bẫy#

• Dùng y_{2K}[0] thay vì x_{2K-1}
• Sai indices trong D/C1
• Quên xử lý trường hợp a0² ≡ 1
• Vấn đề môi trường với pycryptodome