# LACTF 1986 (rev) — Writeup

## Overview
The provided artifact is a 1.44MB floppy image containing a DOS executable that checks a flag. The flag check uses:
- A prefix check for `lactf{`.
- A 20-bit hash of the input.
- A 20-bit LFSR to generate a keystream.
- An XOR check against a 73-byte table stored in the binary.

Solving the challenge reduces to recovering the input that satisfies a fixed-point condition between the hash and the LFSR seed.

## Step 1: Extract the executable from the floppy image
The image is a FAT12 DOS floppy. The root directory contains a single file, `CHALL.EXE`. A small Python extractor can read the BPB, FAT, and clusters to reconstruct the file. (Any FAT12 tool also works.)

## Step 2: Identify the flag checking logic
Disassembling `CHALL.EXE` (16-bit MZ) shows:
- The program prints a banner and prompts for input.
- It reads a string into a stack buffer.
- It verifies the prefix `lactf{`.
- It computes a 20-bit hash of the whole input.
- It runs a 20-bit LFSR to generate a byte stream.
- It XORs that stream against a 73-byte table embedded in the binary and compares the result to the user input.

Important constants and data:
- The XOR table is 73 bytes long, copied from DS:0x146 into the stack at program start.
- The check loops for up to 0x49 (73) bytes.

## Step 3: Reconstruct the hash and LFSR
### Hash function
The input hash uses 20-bit arithmetic (mask `(1<<20)-1`), starting at 0, and for each byte `b`:

```
state = (state * 67 + b) & ((1 << 20) - 1)
```

### LFSR
The LFSR state is also 20-bit. Each byte uses one step:
- New bit = bit0 XOR bit3 (LSB and bit 3).
- Shift right by 1.
- Insert new bit into bit 19.

```
newbit = (state ^ (state >> 3)) & 1
state = (state >> 1) | (newbit << 19)
state &= (1 << 20) - 1
```

Each generated byte is `state & 0xFF`.

### Check condition
For each position `i` (0..72):

```
state = lfsr_step(state)
ch = table[i] ^ (state & 0xFF)
```

The computed `ch` must equal the input byte. The program compares on the fly and aborts on mismatch.

The initial LFSR seed is exactly the 20-bit hash of the user input. That means the input must satisfy a fixed-point relation:

```
seed = hash(input)
input[i] = table[i] ^ (lfsr_step(seed at step i) & 0xFF)
```

## Step 4: Solve by brute force over 20-bit seeds
The seed space is only 2^20 (~1M), which is trivial to brute force. For each candidate seed:
1. Generate 73 bytes using the LFSR and the table.
2. Enforce the known prefix `lactf{` early to prune.
3. Compute the hash of the generated string.
4. Accept if `hash == seed`.

This yields a single valid solution.

## Solver snippet (Python)
```python
from time import time

table = [
    0xb6,0x8c,0x95,0x8f,0x9b,0x85,0x4c,0x5e,0xec,0xb6,0xb8,0xc0,0x97,0x93,0x0b,0x58,
    0x77,0x50,0xb0,0x2c,0x7e,0x28,0x7a,0xf1,0xb6,0x04,0xef,0xbe,0x5c,0x44,0x78,0xe8,
    0x99,0x81,0x04,0x8f,0x03,0x40,0xa7,0x3f,0xfa,0xb7,0x08,0x01,0x63,0x52,0xe3,0xad,
    0xd1,0x85,0x9f,0x94,0x21,0xd5,0x2a,0x5c,0x20,0xd4,0x31,0x12,0xce,0xaa,0x16,0xc7,
    0xad,0xdf,0x29,0x5d,0x72,0xfc,0x24,0x90,0x2c
]

prefix = b"lactf{"
mask = (1 << 20) - 1

def lfsr_step(state):
    return ((state >> 1) | (((state ^ (state >> 3)) & 1) << 19)) & mask

def hash20(sbytes):
    h = 0
    for b in sbytes:
        h = (h * 67 + b) & mask
    return h

for seed in range(1 << 20):
    state = seed
    h = 0
    ok = True
    for i in range(73):
        state = lfsr_step(state)
        ch = table[i] ^ (state & 0xFF)
        if ch == 0:
            ok = False
            break
        if i < 6 and ch != prefix[i]:
            ok = False
            break
        h = (h * 67 + ch) & mask
    if ok and h == seed:
        # Rebuild the full flag
        state = seed
        s = bytearray()
        for i in range(73):
            state = lfsr_step(state)
            s.append(table[i] ^ (state & 0xFF))
        print(s.decode())
        break
```

## Flag
```
lactf{3asy_3nough_7o_8rute_f0rce_bu7_n0t_ea5y_en0ugh_jus7_t0_brut3_forc3}
```