Too Many Errors

Platform: cryptohack | Category: Crypto | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-23 | Status: Solved Techniques: coupon_collector, fault_differential_analysis, majority_voting, prng_reset_attack

Summary

Task: LWE oracle over GF(127) with PRNG reset. After reset, same a and e are generated, but with 50% chance one a[j] is randomly replaced. Solution: reset 300 times, majority-vote to recover true a and b; for faulty samples, compute FLAG[j] = (b_faulty - b_true) * (v - a_true[j])^{-1} mod 127.

Too Many Errors — CryptoHack (Post-Quantum / LWE)

Description

I've set up a server to give you LWE samples. See if you can recover the flag.

Interactive server at socket.cryptohack.org:13390. The server implements a faulty LWE sample generator:

 python read-only • copy allowed Copy
SEED = getrandbits(32)
FLAG = b'crypto{????????????????????}'
q = 127

class Challenge:
    def __init__(self):
        self.rand = random.Random(SEED)

    def challenge(self, your_input):
        if your_input["option"] == "reset":
            self.rand.seed(SEED)
            return {"success": "The distribution has been reset"}
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

        elif your_input["option"] == "get_sample":
            a = [self.rand.randint(0, q-1) for _ in range(len(FLAG))]
            e = self.rand.randint(-1, 1)

            self.rand.seed(getrandbits(32))  # NEW random seed
            if self.rand.randint(0, 1):      # 50% chance
                j = self.rand.randint(0, len(a)-1)
                a[j] = self.rand.randint(0, q-1)  # replace one element

            b = sum(a[i] * FLAG[i] for i in range(len(FLAG))) + e
            b %= q
            return {"a": a, "b": b}

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

The key vulnerability is the PRNG reset. After calling reset, the PRNG state returns to the original SEED. The first get_sample after reset always generates the same a_orig and e_orig (deterministic from SEED).

After generating a and e, a new random seed is set. Then with 50% probability, one element a[j] is replaced with a random value v. The inner product b = a · FLAG + e mod q is computed with the (possibly modified) a.

Two cases after each reset + get_sample: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

1. No fault (50%): a = a_true, b = b_true = a_true · FLAG + e_true mod q
2. Fault at position j (50%): a[j] = v (random), so:

   b_faulty = b_true + (v - a_true[j]) * FLAG[j]  mod q
   

Recovery strategy:

1. Recover a_true: Reset many times (300+), collect samples. For each position, the majority value is a_true[i] (faulty samples only change one random position).

2. Recover b_true: The most common b value across all samples is b_true (unfaulted samples all produce the same b). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

3. Recover FLAG[j]: For each faulty sample where a[j] ≠ a_true[j]:

   b_faulty - b_true = (v - a_true[j]) * FLAG[j]  mod q
   FLAG[j] = (b_faulty - b_true) * (v - a_true[j])^{-1}  mod q
   

By the coupon collector argument, ~300 samples ensure all 28 positions are covered by at least one fault.

Solution

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import json
from pwn import remote
from collections import Counter

q = 127
NUM_SAMPLES = 300

conn = remote('socket.cryptohack.org', 13390)
conn.recvline()
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

samples = []
for _ in range(NUM_SAMPLES):
    # Reset PRNG
    conn.sendline(json.dumps({"option": "reset"}).encode())
    conn.recvline()

    # Get sample
    conn.sendline(json.dumps({"option": "get_sample"}).encode())
    resp = json.loads(conn.recvline())
    samples.append((resp["a"], resp["b"]))

conn.close()

n = len(samples[0][0])  # flag length (28)

# Step 1: Recover a_true via majority vote per element
a_true = []
for i in range(n):
    counter = Counter(s[0][i] for s in samples)
    a_true.append(counter.most_common(1)[0][0])
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# Step 2: Recover b_true (most common b value)
b_counter = Counter(s[1] for s in samples)
b_true = b_counter.most_common(1)[0][0]

# Step 3: Recover FLAG via differential analysis
flag = [None] * n
for a, b in samples:
    if b == b_true:
        continue  # unfaulted sample, no info about individual positions

    # Find which position was faulted
    diffs = [i for i in range(n) if a[i] != a_true[i]]
    if len(diffs) != 1:
        continue  # skip ambiguous samples

    j = diffs[0]
    v = a[j]
    delta_a = (v - a_true[j]) % q
    delta_b = (b - b_true) % q
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

    if delta_a == 0:
        continue

    # FLAG[j] = delta_b / delta_a mod q
    flag[j] = (delta_b * pow(delta_a, -1, q)) % q

# Verify and print
flag_bytes = bytes(flag)
print(f"Flag: {flag_bytes.decode()}")

‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍