# Alpacahack Round 5 (Crypto) - Writeups (all solved)
## Xorshift Stream
---
### Summary
This challenge implements a toy stream cipher using a **64-bit Xorshift** PRNG. The plaintext is:
1. `key.hex().encode()` (ASCII hex, only `0-9a-f`)
2. `strxor(key, FLAG)` (key XOR flag)
Ciphertext is `plaintext XOR keystream`, and the keystream is produced by the Xorshift outputs.
---
### Key observations
#### 1) Flag length from ciphertext length
Let `L = len(FLAG)`.
- key length is `L`
- `key.hex()` length is `2L` bytes (ASCII)
- `key XOR FLAG` length is `L`
Total plaintext length is `3L`, hence ciphertext length is also `3L`.
So:
- `L = len(ciphertext) / 3`
---
#### 2) The first 2L bytes must be hex ASCII
Since the plaintext begins with `key.hex().encode()`, every early plaintext byte is one of:
```
0123456789abcdef
```
With `C[i] = P[i] XOR KS[i]`, we get:
- `KS[i] = C[i] XOR P[i]`
Thus each constrained `KS[i]` has only **16 possible values**.
---
#### 3) Xorshift is linear over GF(2)
Xorshift uses only XOR and shifts, which are linear over GF(2). Therefore, each keystream bit is a linear XOR-combination of the 64 seed bits.
We can model “keystream byte equals value” as a system of linear equations over GF(2).
---
### Attack approach
1. **Build a linear basis**:
- For each `j` in `[0..63]`, set seed to `1<<j` and generate some output bytes.
- This gives basis streams, one per seed bit.
2. **Hex constraints**:
- Use ~126 constrained bytes.
- Each position provides 16 candidates for `KS[i]`.
3. **Backtracking + incremental GF(2) elimination**:
- Branch on the position with the fewest feasible candidates.
- Each chosen byte adds 8 equations.
- Backtrack on contradiction.
- Once rank hits 64, extract the seed and verify.
4. **Decrypt and recover flag**:
- Generate full keystream and decrypt plaintext.
- Parse `key` from the hex prefix.
- Compute `FLAG = (key XOR FLAG) XOR key`.
---
## Solver (Python)
Save as `solve.py`, then run:
```bash
python3 solve.py output.txt
```
```python
#!/usr/bin/env python3
import sys
MASK64 = (1 << 64) - 1
HEXCHARS = b"0123456789abcdef"
def xorshift_next(state: int) -> int:
state &= MASK64
state ^= ((state << 13) & MASK64)
state ^= (state >> 7)
state ^= ((state << 17) & MASK64)
return state & MASK64
def gen_keystream(seed: int, nbytes: int) -> bytes:
nblocks = (nbytes + 7) // 8
st = seed & MASK64
out = bytearray()
for _ in range(nblocks):
st = xorshift_next(st)
out += st.to_bytes(8, "little")
return bytes(out[:nbytes])
# --------- GF(2) linear basis (XOR Gaussian elimination) ----------
def add_equation(basis, mask: int, rhs: int) -> bool:
"""basis: list of (mask, rhs) rows, kept in (rough) RREF by pivot elimination."""
m = mask
r = rhs & 1
# Reduce by existing rows
for bm, br in basis:
piv = bm.bit_length() - 1
if (m >> piv) & 1:
m ^= bm
r ^= br
if m == 0:
return (r == 0)
piv = m.bit_length() - 1
# Eliminate this pivot from other rows
new_basis = []
for bm, br in basis:
if (bm >> piv) & 1:
bm ^= m
br ^= r
new_basis.append((bm, br))
new_basis.append((m, r))
new_basis.sort(key=lambda x: x[0].bit_length(), reverse=True)
basis[:] = new_basis
return True
def add_byte_assignment(basis, byte_bit_masks, pos: int, value: int) -> bool:
"""Add constraints: output_byte[pos] == value."""
for bit in range(8):
mask = byte_bit_masks[pos][bit]
rhs = (value >> bit) & 1
if not add_equation(basis, mask, rhs):
return False
return True
def solve_from_basis(basis) -> int:
"""
Produce one solution by setting free vars = 0 and back-substituting.
Works because we keep a pivot-eliminated basis.
"""
rows = [(m, r, m.bit_length() - 1) for (m, r) in basis]
rows.sort(key=lambda x: x[2]) # low pivot -> high pivot
values = [0] * 64
solved = [False] * 64
for m, r, piv in rows:
acc = r
mm = m & ~(1 << piv)
while mm:
lsb = mm & -mm
idx = lsb.bit_length() - 1
if solved[idx]:
acc ^= values[idx]
# free var assumed 0
mm ^= lsb
values[piv] = acc & 1
solved[piv] = True
seed = 0
for i, v in enumerate(values):
if v:
seed |= 1 << i
return seed
# --------- Build linear masks for keystream bytes (first 16 blocks = 128 bytes) ----------
def build_byte_bit_masks(nblocks: int = 16):
nbytes = nblocks * 8
# basis_bytes[i] = keystream bytes when seed = 1<<i
basis_bytes = []
for i in range(64):
seed = 1 << i
st = seed
out = bytearray()
for _ in range(nblocks):
st = xorshift_next(st)
out += st.to_bytes(8, "little")
basis_bytes.append(bytes(out))
byte_bit_masks = [[0] * 8 for _ in range(nbytes)]
for pos in range(nbytes):
for bit in range(8):
m = 0
for i in range(64):
if (basis_bytes[i][pos] >> bit) & 1:
m |= 1 << i
byte_bit_masks[pos][bit] = m
return byte_bit_masks
def dfs_find_seed(c: bytes, byte_bit_masks):
# Constrain first 126 bytes: plaintext must be hex chars
allowed = []
for i in range(126):
allowed.append([c[i] ^ h for h in HEXCHARS])
allowed_sets = [set(x) for x in allowed]
positions = list(range(126))
def stream126(seed: int) -> bytes:
return gen_keystream(seed, 126)
# DFS with heuristic: pick position with minimum feasible candidates
def rec(basis, unassigned):
if len(basis) == 64:
seed = solve_from_basis(basis)
s = stream126(seed)
for pos in unassigned:
if s[pos] not in allowed_sets[pos]:
return None
return seed
if not unassigned:
return solve_from_basis(basis)
best_pos = None
best_vals = None
best_len = 10**9
for pos in unassigned:
feas = []
for v in allowed[pos]:
b2 = basis.copy()
if add_byte_assignment(b2, byte_bit_masks, pos, v):
feas.append(v)
if len(feas) >= best_len:
break
if not feas:
return None
if len(feas) < best_len:
best_len = len(feas)
best_pos = pos
best_vals = feas
if best_len == 1:
break
rest = [p for p in unassigned if p != best_pos]
for v in best_vals:
b2 = basis.copy()
if not add_byte_assignment(b2, byte_bit_masks, best_pos, v):
continue
ans = rec(b2, rest)
if ans is not None:
return ans
return None
return rec([], positions)
def main():
if len(sys.argv) < 2:
print(f"Usage: {sys.argv[0]} output.txt")
sys.exit(1)
c_hex = open(sys.argv[1], "r", encoding="utf-8").read().strip()
c = bytes.fromhex(c_hex)
if len(c) % 3 != 0:
raise ValueError("Ciphertext length is not multiple of 3; unexpected.")
L = len(c) // 3
byte_bit_masks = build_byte_bit_masks(nblocks=16) # 128 bytes covers first 126 constraints
seed = dfs_find_seed(c, byte_bit_masks)
if seed is None:
raise RuntimeError("Failed to recover seed.")
ks = gen_keystream(seed, len(c))
pt = bytes(ci ^ ki for ci, ki in zip(c, ks))
key_hex = pt[: 2 * L]
key = bytes.fromhex(key_hex.decode())
key_xor_flag = pt[2 * L :]
flag = bytes(a ^ b for a, b in zip(key, key_xor_flag))
print("seed =", seed)
print("flag =", flag.decode(errors="replace"))
if __name__ == "__main__":
main()
```
---
## Output
Running the solver prints the recovered seed and the flag:
`Alpaca{I'v3_n3v3r_seen_4_c1ient_51d3_CryptoWeb_ch4ll3ng3_0nce!}`
## NNNN
### 1. Challenge summary
The script generates four RSA moduli:
- `n0 = p * q` where `p, q` are 768-bit primes.
- For three more moduli, it samples `delta < 2^192` until both `p+delta` and `q+delta` are prime, then:
- `n1 = (p+δ1)(q+δ1)`
- `n2 = (p+δ2)(q+δ2)`
- `n3 = (p+δ3)(q+δ3)`
The flag is split into 4 chunks. Each chunk is encrypted with `e=65537` under its modulus, producing `c0..c3`.
Goal: factor each `ni`, derive private exponents, decrypt `ci`, then concatenate the plaintext chunks.
---
### 2. Key observation
All moduli share the same hidden primes, shifted by the same delta on both sides.
Let:
- `P = n0 = pq`
- `S = p + q`
For `i = 1..3`:
$$
n_i = (p+\delta_i)(q+\delta_i)=pq+\delta_i(p+q)+\delta_i^2
$$
Define:
$$
D_i = n_i - n_0 = \delta_i S + \delta_i^2 = \delta_i(S+\delta_i)
$$
Since `δi < 2^192` while `S` is about `2^768`, we have `δi << S`. So:
$$
\frac{D_1}{D_2}=\frac{\delta_1(S+\delta_1)}{\delta_2(S+\delta_2)}\approx\frac{\delta_1}{\delta_2}
$$
The relative error is on the order of `δ/S ≈ 2^-576`, extremely small. This is why rational recovery works.
---
### 3. Recover δ1/δ2 via continued fractions
We know `δ1, δ2 < 2^192`. Therefore the reduced fraction `δ1/δ2 = a/b` has `b < 2^192`.
Compute `D1=n1-n0`, `D2=n2-n0`, then take the best rational approximation to `D1/D2` with denominator bounded by `2^192-1`.
In Python:
```python
Fraction(D1, D2).limit_denominator(2**192 - 1)
```
This returns `a/b`, which with overwhelming probability equals the reduced ratio:
$$
\frac{a}{b}=\frac{\delta_1}{\delta_2},\quad gcd(a,b)=1
$$
So there exists an integer scale `t`:
$$
\delta_1 = ta,\quad \delta_2 = tb
$$
---
### 4. Compute the scale t without knowing p or q
Use:
$$
D_1=ta(S+ta),\quad D_2=tb(S+tb)
$$
Eliminate `S`:
$$
bD_1-aD_2=t^2ab(a-b)
$$
Thus:
$$
t^2=\frac{bD_1-aD_2}{ab(a-b)}
$$
The right-hand side is an exact perfect square, so `t = sqrt(t^2)` is an integer.
Then:
- `δ1 = t*a`
- `δ2 = t*b`
---
### 5. Recover S and factor n0
From:
$$
D_1=\delta_1(S+\delta_1)
\Rightarrow S=\frac{D_1}{\delta_1}-\delta_1
$$
Now we have:
- `S = p+q`
- `P = pq`
So `p` and `q` are roots of:
$$
x^2 - Sx + P = 0
$$
Compute:
$$
\Delta = S^2 - 4P = (p-q)^2
$$
Let `r = sqrt(Δ)` (integer), then:
$$
p=\frac{S+r}{2},\quad q=\frac{S-r}{2}
$$
---
### 6. Recover δ3, factor remaining moduli, decrypt
For `D3`:
$$
D_3=\delta_3(S+\delta_3)\Rightarrow \delta_3^2+S\delta_3-D_3=0
$$
Discriminant:
$$
\Delta_3=S^2+4D_3
$$
Positive root:
$$
\delta_3=\frac{-S+\sqrt{\Delta_3}}{2}
$$
Then factor each modulus:
- `n0 = p*q`
- `n1 = (p+δ1)(q+δ1)`
- `n2 = (p+δ2)(q+δ2)`
- `n3 = (p+δ3)(q+δ3)`
Decrypt each chunk:
- `phi = (p_i-1)(q_i-1)`
- `d = e^{-1} mod phi`
- `m = c^d mod n`
- Convert `m` back to bytes and concatenate.
Byte-join note:
`bytes_to_long()` drops leading zero bytes. When converting back, pad the first three chunks to the same byte length.
### 7. Solver (Python)
```python
from fractions import Fraction
from math import isqrt
def parse_output(path="output.txt"):
vals = {}
with open(path, "r", encoding="utf-8") as f:
for line in f:
line = line.strip()
if "=" not in line:
continue
k, v = line.split("=", 1)
vals[k.strip()] = int(v.strip())
ns = [vals[f"n{i}"] for i in range(4)]
cs = [vals[f"c{i}"] for i in range(4)]
return ns, cs
def long_to_bytes(n: int) -> bytes:
if n == 0:
return b"\x00"
out = bytearray()
while n:
out.append(n & 0xff)
n >>= 8
return bytes(reversed(out))
def main():
ns, cs = parse_output("output.txt")
e = 0x10001
n0 = ns[0]
P = n0
D1, D2, D3 = ns[1] - P, ns[2] - P, ns[3] - P
B = 2**192 - 1
frac = Fraction(D1, D2).limit_denominator(B)
a, b = frac.numerator, frac.denominator # δ1/δ2 = a/b (reduced)
# bD1 - aD2 = t^2 * a*b*(a-b)
num = b * D1 - a * D2
den = a * b * (a - b)
if den < 0:
den = -den
num = -num
t2 = num // den
t = isqrt(t2)
delta1 = t * a
delta2 = t * b
S = D1 // delta1 - delta1 # p+q
disc = S * S - 4 * P
r = isqrt(disc)
p = (S + r) // 2
q = (S - r) // 2
disc3 = S * S + 4 * D3
r3 = isqrt(disc3)
delta3 = (-S + r3) // 2
deltas = [0, delta1, delta2, delta3]
chunks = []
for i in range(4):
pi = p + deltas[i]
qi = q + deltas[i]
phi = (pi - 1) * (qi - 1)
d = pow(e, -1, phi)
m = pow(cs[i], d, ns[i])
chunks.append(long_to_bytes(m))
L = max(len(chunks[0]), len(chunks[1]), len(chunks[2]))
for i in range(3):
chunks[i] = chunks[i].rjust(L, b"\x00")
flag = b"".join(chunks)
print(flag.decode(errors="replace"))
if __name__ == "__main__":
main()
```
---
### 8. Flag
`Alpaca{lattice_reductionNnnnnNnnNnnNnNNnNnNNnNn_solves_approximationNnnNNnnnNnnNNnnnNnnNNnn}`
## SchnorrLCG
### Overview
This service implements **Schnorr signatures**. You are allowed to request signatures (`option 1`) for arbitrary messages **except**:
- `b"give me flag"`
If you provide a valid Schnorr signature for that exact message via `option 2 (verify)`, the server reveals the flag.
The vulnerability: the signing nonce `k` is generated by an **LCG**, so nonces satisfy a linear recurrence. With enough signatures, we can recover the private key `x`, then forge the forbidden signature.
---
### Proof-of-Work (hashcash)
Before you can access the menu, the service asks for a **hashcash** token (strength 27):
- The server prints a `<challenge>`
- You submit a hashcash token for that challenge
- If valid, the service proceeds
In practice, you can generate the token with:
```bash
hashcash -mb27 <challenge>
```
---
### Schnorr scheme used
Parameters:
- The server picks prime `q` and searches for a safe prime `p = 2q + 1`.
- `g` is a fixed generator (in the source: `2**2`).
- Secret key: `x`
- Public key: `y = g^x mod p`
Signing:
1. Pick nonce `k`
2. `r = g^k mod p`
3. `e = H(m || r) mod q`
4. `s = (k + x·e) mod q`
Verification:
- Compute `r' = g^s · y^{-e} mod p`
- `e' = H(m || r') mod q`
- Accept iff `e' == e`
---
### Core bug: LCG nonces
Nonces `k` must be unpredictable in Schnorr. Here they come from an **LCG**:
- `state = (a·state + b) mod q`
So consecutive nonces satisfy:
- `k_{i+1} = a·k_i + b (mod q)`
From Schnorr:
- `s_i = k_i + x·e_i (mod q)`
- so `k_i = s_i − x·e_i (mod q)`
Thus, the correct secret key `x` makes the recovered nonce sequence consistent with one LCG.
---
### Recovering the private key (math)
Collect signatures `(e_i, s_i)`.
From signing:
- `k_i = s_i − x·e_i (mod q)`
Define differences:
- `Δk_i = k_{i+1} − k_i`
- `Δs_i = s_{i+1} − s_i`
- `Δe_i = e_{i+1} − e_i`
Since `s_i = k_i + x·e_i`:
- `Δs_i = Δk_i + x·Δe_i`
- `Δk_i = Δs_i − x·Δe_i`
LCG property implies:
- `Δk_{i+1} = a · Δk_i (mod q)`
Substitute and eliminate `a`:
- `(Δs_2 − xΔe_2)(Δs_0 − xΔe_0) = (Δs_1 − xΔe_1)^2 (mod q)`
This yields a **quadratic equation in x modulo prime q**. With 4 signatures you can build 3 difference pairs, derive `c2 x^2 + c1 x + c0 = 0 (mod q)`, then solve using a modular square root (Tonelli–Shanks).
---
### Candidate validation
Quadratic solving may return up to two candidates. Validate each candidate `x` by:
1. Reconstruct all nonces:
- `k_i = s_i − x·e_i (mod q)`
2. Derive `a,b` from any triple where `k1 != k0`:
- `a = (k2 − k1) / (k1 − k0) (mod q)`
- `b = k1 − a·k0 (mod q)`
3. Check the full recurrence:
- `k_{i+1} == a·k_i + b (mod q)` for all i
Only the correct `x` will satisfy the recurrence for the entire nonce sequence.
---
### Forging the flag signature
Once `x` is known:
1. Pick random `k`
2. `r = g^k mod p`
3. `e = H("give me flag" || r) mod q`
4. `s = k + x·e mod q`
Submit `(e,s)` to `option 2` for message `"give me flag"` to obtain the flag.
---
### End-to-end steps
1. Connect to the service.
2. Solve hashcash PoW.
3. Parse `p,g,pub_key`.
4. Request 8–12 signatures on harmless messages.
5. Solve and validate `x`.
6. Forge a signature for `"give me flag"`.
7. Verify and get the flag.
---
### Solver (Python)
> Standalone solver with PoW + key recovery + forging.
```python
#!/usr/bin/env python3
import argparse
import hashlib
import re
import secrets
import socket
import subprocess
import time
from typing import List, Optional, Tuple
GIVE_ME_FLAG = b"give me flag"
Sig = Tuple[int, int] # (e, s)
def long_to_bytes(n: int) -> bytes:
return n.to_bytes((n.bit_length() + 7) // 8 or 1, "big")
def H_int(msg: bytes) -> int:
return int.from_bytes(hashlib.sha256(msg).digest(), "big")
def modinv(a: int, m: int) -> int:
a %= m
return pow(a, -1, m)
def legendre_symbol(a: int, p: int) -> int:
return pow(a % p, (p - 1) // 2, p)
def mod_sqrt(a: int, p: int) -> Optional[int]:
a %= p
if a == 0:
return 0
if legendre_symbol(a, p) != 1:
return None
if p % 4 == 3:
return pow(a, (p + 1) // 4, p)
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
z = 2
while legendre_symbol(z, p) != p - 1:
z += 1
m = s
c = pow(z, q, p)
x = pow(a, (q + 1) // 2, p)
t = pow(a, q, p)
while t != 1:
i = 1
t2 = pow(t, 2, p)
while t2 != 1:
t2 = pow(t2, 2, p)
i += 1
if i >= m:
return None
b = pow(c, 1 << (m - i - 1), p)
x = (x * b) % p
t = (t * b * b) % p
c = (b * b) % p
m = i
return x
def schnorr_hash(q: int, msg: bytes, r: int) -> int:
return H_int(msg + long_to_bytes(r)) % q
class Remote:
def __init__(self, host: str, port: int, debug: bool = False):
self.s = socket.create_connection((host, port))
self.s.settimeout(1.0)
self.buf = b""
self.debug = debug
def close(self):
try:
self.s.close()
except Exception:
pass
def _recv_some(self) -> bytes:
return self.s.recv(4096)
def recvline(self, deadline: float) -> bytes:
while b"\n" not in self.buf:
if time.time() > deadline:
raise TimeoutError("recvline deadline exceeded")
try:
chunk = self._recv_some()
if not chunk:
raise EOFError("connection closed")
self.buf += chunk
except TimeoutError:
continue
i = self.buf.index(b"\n") + 1
out, self.buf = self.buf[:i], self.buf[i:]
if self.debug:
print(out.decode(errors="ignore"), end="")
return out
def recv_until(self, needle: bytes, deadline: float) -> bytes:
while needle not in self.buf:
if time.time() > deadline:
raise TimeoutError("recv_until deadline exceeded")
try:
chunk = self._recv_some()
if not chunk:
raise EOFError("connection closed")
self.buf += chunk
except TimeoutError:
continue
j = self.buf.index(needle) + len(needle)
out, self.buf = self.buf[:j], self.buf[j:]
if self.debug:
print(out.decode(errors="ignore"), end="")
return out
def sendline(self, data: bytes):
if self.debug:
print(f"[send] {data!r}")
self.s.sendall(data + b"\n")
def get_hashcash_token(bits: int, challenge: str) -> str:
try:
tok = subprocess.check_output(["hashcash", f"-mb{bits}", challenge], stderr=subprocess.DEVNULL)
return tok.decode().strip()
except FileNotFoundError:
print("[!] 'hashcash' binary not found.")
print(f" Run manually: hashcash -mb{bits} {challenge}")
return input(" Paste hashcash token: ").strip()
def try_candidates_from_4(q: int, sig4: List[Sig]) -> List[int]:
es = [e for e, s in sig4]
ss = [s for e, s in sig4]
A = [(ss[i + 1] - ss[i]) % q for i in range(3)]
B = [(es[i + 1] - es[i]) % q for i in range(3)]
c2 = (B[1] * B[1] - B[0] * B[2]) % q
c1 = (-2 * A[1] * B[1] + A[0] * B[2] + A[2] * B[0]) % q
c0 = (A[1] * A[1] - A[0] * A[2]) % q
if c2 == 0:
if c1 == 0:
return []
return [(-c0 * modinv(c1, q)) % q]
D = (c1 * c1 - 4 * c2 * c0) % q
r = mod_sqrt(D, q)
if r is None:
return []
inv_2c2 = modinv((2 * c2) % q, q)
x1 = ((-c1 + r) * inv_2c2) % q
x2 = ((-c1 - r) * inv_2c2) % q
return [x1] if x1 == x2 else [x1, x2]
def validate_x(q: int, sigs: List[Sig], x: int) -> bool:
ks = [(s - (x * e) % q) % q for (e, s) in sigs]
if all(k == ks[0] for k in ks):
return True
a = b = None
for i in range(len(ks) - 2):
d = (ks[i + 1] - ks[i]) % q
if d != 0:
a = ((ks[i + 2] - ks[i + 1]) * modinv(d, q)) % q
b = (ks[i + 1] - a * ks[i]) % q
break
if a is None:
return False
for i in range(len(ks) - 1):
if ks[i + 1] != (a * ks[i] + b) % q:
return False
return True
def recover_x(q: int, sigs: List[Sig]) -> int:
for i in range(len(sigs) - 3):
for x in try_candidates_from_4(q, sigs[i:i + 4]):
if validate_x(q, sigs, x):
return x
raise RuntimeError("Failed to recover private key x.")
def forge(p: int, g: int, q: int, x: int, msg: bytes) -> Sig:
k = secrets.randbelow(q - 1) + 1
r = pow(g, k, p)
e = schnorr_hash(q, msg, r)
s = (k + (x * e) % q) % q
return e, s
def main():
ap = argparse.ArgumentParser()
ap.add_argument("host", nargs="?", default="34.170.146.252")
ap.add_argument("port", nargs="?", type=int, default=26727)
ap.add_argument("--debug", action="store_true")
ap.add_argument("--sigs", type=int, default=10)
args = ap.parse_args()
io = Remote(args.host, args.port, debug=args.debug)
deadline = time.time() + 60
bits = None
challenge = None
while time.time() < deadline:
line = io.recvline(deadline).decode(errors="ignore").strip()
m = re.search(r"hashcash\s+-mb(\d+)\s+([A-Za-z0-9_.]+)", line)
if m:
bits = int(m.group(1))
challenge = m.group(2)
break
if bits is None:
raise RuntimeError("Could not parse PoW line.")
io.recv_until(b"hashcash token", time.time() + 30)
token = get_hashcash_token(bits, challenge)
io.sendline(token.encode())
# Parse p,g,y (safe prime gen may be slow)
deadline = time.time() + 240
p = None
while time.time() < deadline:
line = io.recvline(deadline).decode(errors="ignore").strip()
if line.startswith("p="):
p = int(line.split("=", 1)[1])
break
if p is None:
raise TimeoutError("Timed out waiting for p=")
g = int(io.recvline(time.time() + 30).decode(errors="ignore").split("=", 1)[1])
y = int(io.recvline(time.time() + 30).decode(errors="ignore").split("=", 1)[1])
q = (p - 1) // 2
io.recv_until(b"option> ", time.time() + 30)
sigs: List[Sig] = []
for i in range(args.sigs):
io.sendline(b"1")
io.recv_until(b"message(in hex)> ", time.time() + 30)
msg = bytes([i + 1])
io.sendline(msg.hex().encode())
e_line = io.recvline(time.time() + 30).decode(errors="ignore").strip()
s_line = io.recvline(time.time() + 30).decode(errors="ignore").strip()
e = int(e_line.split("=", 1)[1])
s = int(s_line.split("=", 1)[1])
sigs.append((e, s))
io.recv_until(b"option> ", time.time() + 30)
x = recover_x(q, sigs)
print("[+] recovered priv_key =", x)
e_f, s_f = forge(p, g, q, x, GIVE_ME_FLAG)
io.sendline(b"2")
io.recv_until(b"message(in hex)> ", time.time() + 30)
io.sendline(GIVE_ME_FLAG.hex().encode())
io.recv_until(b"e> ", time.time() + 30)
io.sendline(str(e_f).encode())
io.recv_until(b"s> ", time.time() + 30)
io.sendline(str(s_f).encode())
out_deadline = time.time() + 30
out = b""
while time.time() < out_deadline:
try:
out += io.recvline(out_deadline)
except Exception:
break
if b"flag" in out.lower():
break
print(out.decode(errors="ignore"))
io.close()
if __name__ == "__main__":
main()
```
### Flag
`Alpaca{5chn0rr_s1gn4tur3_1s_st1ll_s3cur3_t0_th15_d4y}`
## NTRU Broadcast Attack
### 1) Challenge Summary
The challenge implements an NTRU-like scheme over:
- Ring:
$$
R = \mathbb{Z}[x]/(x^N - 1)
$$
- Parameters: **N = 509**, **q = 2048 = 2¹¹**, **p = 3**
- Message `msg` is a **binary** (0/1) polynomial of length N.
- For **777 recipients**, it generates:
- public key \(h_i\)
- random binary blinding \(r_i\)
- ciphertext:
$$
c_i = h_i * r_i + m \pmod q
$$
- **Core vulnerability:** the same message \(m\) is reused for all recipients.
The flag is then encrypted with AES-CTR:
```python
key = sha256(str(msg).encode()).digest()[:16]
enc = nonce(8 bytes) || ciphertext
```
---
### 2) Why This Breaks
NTRU relies on the random blinding \(r_i\) to hide the message. But when the **same message** is sent to many recipients, we can build **many independent equations** involving the same unknown \(m\), and eliminate the randomness algebraically.
This becomes especially convenient because:
- \(q\) is a **power of two**, allowing fast polynomial inversion modulo \(2^k\) via Newton/Hensel lifting.
---
### 3) Notation
For recipient \(i\):
- public key \(h_i\)
- ciphertext \(c_i\)
- blinding $$(r_i \in \{0,1\}^N)$$
- message $$(m \in \{0,1\}^N)$$
Encryption:
$$
c_i = h_i * r_i + m \pmod q
$$
`*` denotes cyclic convolution modulo $$(x^N-1)$$.
---
### 4) Attack Idea (Broadcast Attack)
#### Step A : Invert \(h_i\) modulo \(q = 2^{11}\)
Compute:
$$
u_i = h_i^{-1} \pmod q
$$
Since \(q\) is a power of 2:
1) compute inverse modulo 2 in GF(2)
2) lift to \(2^{11}\) using Newton iteration:
$$
u_{k+1} = u_k (2 - h u_k) \pmod {2^t}
$$
until modulus 2048.
#### Step B : Remove the \(h_i\) factor
Multiply ciphertext by the inverse:
$$
b_i = u_i * c_i = r_i + u_i*m \pmod q
$$
Now `b_i` is “noise + linear transform(message)”.
#### Step C : Linearization with correlation variables
Broadcast attacks derive quadratic relations that eliminate \(r_i\) and yield expressions involving:
- the message bits \(m_0,\dots,m_{N-1}\)
- correlation variables:
$$
x_j = \sum_k m_k m_{k+j}
$$
Because of circulant/symmetric structure, only $$j = 1.. \lfloor (N-1)/2 \rfloor$$ are needed.
Unknown count:
- \(N = 509\) message variables
- \(254\) correlation variables
Total = **763** unknowns.
We have **777 equations** from 777 ciphertexts, which is enough (typically full rank).
#### Step D : Work modulo 1024
Due to symmetry, the derived equations are always even, so we divide by 2 and solve modulo:
$$
2^{10} = 1024
$$
---
### 5) Solving Efficiently (GF(2) + Hensel Lifting)
1) Solve modulo 2 with bitset Gaussian elimination:
$$
A_2Y_2 = S_2 \pmod 2
$$
2) Lift the solution step-by-step to \(2^{10}\):
- compute residual
- solve a correction \(\Delta\) in GF(2)
- update:
$$
Y \leftarrow Y + 2^t\Delta
$$
The recovered message coefficients \(m_k\) are exactly 0/1, with Hamming weight 260 for this instance.
---
### 6) AES Decryption (Key Pitfall)
After recovering \(m\), you must rebuild **exactly** the same `str(msg)` format Sage produced.
Then compute the AES key as **only the first 16 bytes** of SHA-256:
```python
key = sha256(str(msg).encode()).digest()[:16]
nonce = enc[:8]
ct = enc[8:]
pt = AES.new(key, AES.MODE_CTR, nonce=nonce).decrypt(ct)
```
Using the full 32-byte hash will produce garbage plaintext.
### 7) Solver (Python)
```python
import re
import numpy as np
from hashlib import sha256
from Crypto.Cipher import AES
from pathlib import Path
# ===== Parameters (from chall.sage) =====
N = 509
q = 2048
qmask = q - 1
mod1024 = 1024
mmask = mod1024 - 1
inv3 = pow(3, -1, q)
n_x = (N - 1) // 2 # 254
n_vars = n_x + N # 763
# ===== Helpers: parse polynomial strings into coefficient arrays mod q =====
def parse_poly(s):
expr = s.replace(' ','')
expr = expr.replace('-', '+-')
if expr.startswith('+-'):
expr = expr[1:]
parts = [p for p in expr.split('+') if p!='']
coeffs = [0]*N
for part in parts:
if 'x^' in part:
if '*x^' in part:
coef_str, pow_str = part.split('*x^')
else:
coef_str, pow_str = part.split('x^')
powv = int(pow_str)
if coef_str in ('', '+'):
coef = 1
elif coef_str == '-':
coef = -1
else:
coef = int(coef_str)
coeffs[powv] = coef & qmask
elif 'x' in part:
if '*x' in part:
coef_str = part.split('*x')[0]
else:
coef_str = part.split('x')[0]
if coef_str in ('', '+'):
coef = 1
elif coef_str == '-':
coef = -1
else:
coef = int(coef_str)
coeffs[1] = coef & qmask
else:
coeffs[0] = int(part) & qmask
return np.array(coeffs, dtype=np.int64)
def poly_rev(a):
# transpose circulant => reverse except index 0
return np.concatenate(([a[0]], a[:0:-1]))
# ===== GF(2) polynomial inverse (bitset) =====
def gf2_deg(p: int) -> int:
return p.bit_length() - 1
def gf2_divmod(a: int, b: int):
if b == 0:
raise ZeroDivisionError
da = gf2_deg(a)
db = gf2_deg(b)
qv = 0
r = a
while da >= db and r:
shift = da - db
qv ^= 1 << shift
r ^= b << shift
da = gf2_deg(r) if r else -1
return qv, r
def gf2_mul(a: int, b: int) -> int:
res = 0
while b:
if b & 1:
res ^= a
b >>= 1
a <<= 1
return res
def gf2_mod(a: int, mod: int) -> int:
_, r = gf2_divmod(a, mod)
return r
def gf2_inv_mod(a: int, mod: int) -> int:
r0, r1 = mod, a
t0, t1 = 0, 1
while r1:
qv, r2 = gf2_divmod(r0, r1)
r0, r1 = r1, r2
t0, t1 = t1, t0 ^ gf2_mul(qv, t1)
if r0 != 1:
raise ValueError("no inverse")
return gf2_mod(t0, mod)
def arr_to_bits_mod2(a):
bits = 0
for i, v in enumerate(a):
if int(v) & 1:
bits |= 1 << i
return bits
def bits_to_arr_mod2(bits):
return np.array([(bits >> i) & 1 for i in range(N)], dtype=np.int64)
# modulus poly in GF2: x^N - 1 == x^N + 1 in char2
mod_poly_bits = (1 << N) | 1
# ===== cyclic convolution using FFT (mod power-of-2 => use & mask) =====
def cyclic_conv_pow2(a, b, mod=q):
fa = np.fft.fft(a)
fb = np.fft.fft(b)
c = np.fft.ifft(fa * fb).real
c = np.rint(c).astype(np.int64)
return c & (mod - 1)
one = np.zeros(N, dtype=np.int64); one[0] = 1
two = np.zeros(N, dtype=np.int64); two[0] = 2
def invert_mod_power2_fast(f_arr, q=q, max_iter=20):
f_bits = arr_to_bits_mod2(f_arr)
inv_bits = gf2_inv_mod(f_bits, mod_poly_bits)
h = bits_to_arr_mod2(inv_bits).astype(np.int64) & (q - 1)
for _ in range(max_iter):
r = cyclic_conv_pow2(h, f_arr, mod=q)
if np.array_equal(r, one):
return h
h = cyclic_conv_pow2(h, (two - r) & (q - 1), mod=q)
raise RuntimeError("inverse did not converge")
# ===== GF(2) solver using bitrows =====
def gf2_prepare_rowbits(A2):
row_bits = []
m, n = A2.shape
for i in range(m):
bits = 0
row = A2[i]
for j in range(n):
if row[j]:
bits |= 1 << j
row_bits.append(bits)
return row_bits
def gf2_solve_from_rowbits(row_bits, b_bits, n):
m = len(row_bits)
rows = [row_bits[i] | (int(b_bits[i]) << n) for i in range(m)]
pivots = []
r = 0
for c in range(n):
pivot_row = None
for i in range(r, m):
if (rows[i] >> c) & 1:
pivot_row = i
break
if pivot_row is None:
continue
rows[r], rows[pivot_row] = rows[pivot_row], rows[r]
piv = rows[r]
for i in range(m):
if i != r and ((rows[i] >> c) & 1):
rows[i] ^= piv
pivots.append(c)
r += 1
if r == n:
break
sol = 0
for ridx, c in enumerate(pivots):
rhs = (rows[ridx] >> n) & 1
if rhs:
sol |= 1 << c
y = np.fromiter(((sol >> j) & 1 for j in range(n)), dtype=np.uint8, count=n)
return y
# ===== Load output.txt =====
raw = Path("output.txt").read_text()
raw_nl = raw.replace("\n", "")
pk_start = raw_nl.find("public keys: [")
ct_start = raw_nl.find("ciphertexts: [")
enc_start = raw_nl.find("encrypted flag:")
pk_list_str = raw_nl[len("public keys: "):ct_start]
ct_list_str = raw_nl[ct_start+len("ciphertexts: "):enc_start].strip()
enc_hex = raw_nl[enc_start+len("encrypted flag:"):].strip()
def split_list(list_str):
assert list_str[0] == "[" and list_str[-1] == "]"
inner = list_str[1:-1]
return [p.strip() for p in inner.split(",") if p.strip()]
pks_parts = split_list(pk_list_str)
cts_parts = split_list(ct_list_str)
pks = np.stack([parse_poly(s) for s in pks_parts], axis=0)
cts = np.stack([parse_poly(s) for s in cts_parts], axis=0)
M = pks.shape[0]
A_mat = np.empty((M, n_vars), dtype=np.uint16)
b_vec = np.empty(M, dtype=np.uint16)
# ===== Build linear system modulo 1024 =====
for i in range(M):
h = pks[i]
c = cts[i]
hinv = invert_mod_power2_fast(h)
hinv_rev = poly_rev(hinv)
b = cyclic_conv_pow2(hinv, c, mod=q)
w = cyclic_conv_pow2(hinv_rev, b, mod=q)
a = cyclic_conv_pow2(hinv_rev, hinv, mod=q)
a0 = int(a[0])
K = (a0 + inv3) & qmask # even
K2 = (K >> 1) & mmask
c1 = int(np.sum(c) & qmask)
bTb = int(np.sum((b*b) & qmask) & qmask)
t = ((inv3 * c1) - bTb) & qmask # even
b_vec[i] = (t >> 1) & mmask
A_mat[i, :n_x] = (a[1:n_x+1] & mmask).astype(np.uint16)
A_mat[i, n_x:] = ((K2 - (w & mmask)) & mmask).astype(np.uint16)
# ===== Solve via Hensel lifting (mod 2 -> mod 1024) =====
A2 = (A_mat & 1).astype(np.uint8)
b2 = (b_vec & 1).astype(np.uint8)
row_bits = gf2_prepare_rowbits(A2)
y = gf2_solve_from_rowbits(row_bits, b2, n_vars).astype(np.int64)
A_int = A_mat.astype(np.int64)
b_int = b_vec.astype(np.int64)
for tpow in range(1, 10): # lift to 2^10
mod_next = 1 << (tpow + 1)
mask = mod_next - 1
Ay = (A_int @ y) & mask
r = (b_int - Ay) & mask
rhs_delta = (r >> tpow) & 1
delta = gf2_solve_from_rowbits(row_bits, rhs_delta, n_vars).astype(np.int64)
y = y + (delta << tpow)
y1024 = y & mmask
m_bits = y1024[n_x:] # last 509 vars are m0..m508
assert set(np.unique(m_bits)).issubset({0,1})
print("Recovered m sum =", int(m_bits.sum()))
# ===== Rebuild Sage-style polynomial string =====
def sage_poly_str_from_bits(bits):
terms = []
for power in range(N-1, -1, -1):
if bits[power] == 0:
continue
if power == 0:
term = "1"
elif power == 1:
term = "x"
else:
term = f"x^{power}"
terms.append(term)
return "0" if not terms else " + ".join(terms)
msg_str = sage_poly_str_from_bits(m_bits)
# ===== Decrypt flag =====
key = sha256(msg_str.encode()).digest()[:16] # <-- IMPORTANT
blob = bytes.fromhex(enc_hex)
nonce = blob[:8]
ct = blob[8:]
pt = AES.new(key, AES.MODE_CTR, nonce=nonce).decrypt(ct)
print("FLAG =", pt.decode(errors="replace"))
```
---
### 8) Flag
**`Alpaca{N7RU_ha5_m4ny_in73re571n6_vuln3r4bil1t13s^^}`**
---
Sign in with Wallet
Connect another wallet