1986 - LA CTF Reverse Engineering Writeup

Category: Reverse Engineering Difficulty: Medium Points: 158 Solves: 122 Platform: pstorm Flag: lactf{3asy_3nough_7o_8rute_f0rce_bu7_n0t_ea5y_en0ugh_jus7_t0_brut3_forc3} Solved by: Smothy @ 0xN1umb

"They said 'retro computing is dead.' They were wrong."

Challenge Description

Dug around the archives and found a floppy disk containing a long-forgotten LA CTF challenge. Perhaps you may be the first to solve it in decades.

We're given a floppy disk image from 1986 containing a DOS executable flag checker. Time to dust off those 16-bit reversing skills and crack open a piece of CTF history.

TL;DR

Extract CHALL.EXE from a 1.44MB FAT12 floppy image. Reverse a 16-bit DOS flag checker that hashes the full input into a 20-bit LFSR seed, generates a keystream, and XOR-compares against embedded ciphertext. The 20-bit state space means only ~1M possibilities to brute force. Watch out for the CS != DS segment trap when extracting the ciphertext. Retro reversing go brrr.

Initial Recon

Downloaded CHALL.IMG - a classic 1.44MB floppy disk image.

One file: CHALL.EXE, dated February 2nd, 1986. A 9990-byte MS-DOS MZ executable. Extracted it with 7z e CHALL.IMG.

Quick strings check revealed the game plan immediately:

Classic flag checker. Input flag, get validated. Let's tear it apart.

Step 1: Parsing the MZ Header

This is a real-deal 16-bit DOS executable compiled with what looks like Turbo C (based on the startup code patterns and "Stack Overflow!" / "NULL assignment detected" error strings).

Key findings from the header:

• Entry Point: CS:IP = 0000:02C2 - standard Turbo C entry
• 4 Relocations - all pointing to segment 0x239 (the data segment)
• Code segment (CS): starts at paragraph 0x0000
• Data segment (DS): starts at paragraph 0x0239

That segment difference becomes critical later. Spoiler: it nearly cost us the solve.

Step 2: Disassembly & Program Flow

No DOSBox available, so we went full static analysis with Capstone for 16-bit disassembly. The main function lives at code offset 0x00B0.

The program flow is clean:

1. Print banner - "UCLA NetSec presents: LACTF '86 Flag Checker"
2. Read input - fgets-style, up to 74 characters
3. Prefix check - Verifies first 6 chars are lactf{ (byte-by-byte comparison against 0x6c, 0x61, 0x63, 0x74, 0x66, 0x7b)
4. Hash the entire input - Custom hash function producing a 20-bit value
5. LFSR keystream + XOR loop - Steps an LFSR, XORs each input byte with the keystream, compares against 73 embedded ciphertext bytes
6. Win/Lose - All bytes match = flag correct

Step 3: The Hash Function

The hash function at code offset 0x0010 is beautifully simple:

def custom_hash(s):
    h = 0
    for c in s:
        h = (h * 67 + c) & 0xFFFFF  # mod 2^20
    return h

The multiplication by 67 is implemented as (hash << 6) + (hash << 1) + hash - classic bit-shift multiplication trick from the 80s when multiply instructions were expensive. The result is masked to 20 bits (16-bit low word + 4-bit high nibble).

For the homies who haven't touched 16-bit assembly: shl bx, 1; rcl di, 1 is a 32-bit left shift using two 16-bit registers with the carry flag chaining them together.

Step 4: The 20-bit LFSR

The LFSR (Linear Feedback Shift Register) at code offset 0x007B is the keystream generator:

def lfsr_step(state):
    feedback = ((state >> 0) ^ (state >> 3)) & 1
    new_state = (state >> 1) | (feedback << 19)
    return new_state

• 20-bit state with taps at positions 0 and 3
• Feedback bit = bit[0] XOR bit[3]
• Shifts right by 1, feeds the XOR result into bit 19
• Keystream byte = low 8 bits of state after each step

This is a textbook Galois/Fibonacci LFSR with characteristic polynomial x^20 + x^3 + 1.

Step 5: The Encryption Scheme

Here's where it gets interesting. The full algorithm:

1. Compute seed = hash(entire_input) - a 20-bit value
2. For each character position i = 0, 1, 2, ... 72:
   • Step the LFSR: state = lfsr_step(state)
   • Extract keystream byte: key = state & 0xFF
   • Compare: input[i] XOR key == expected[i]

The chicken-and-egg problem: we need the full input to compute the hash seed, but we need the seed to decrypt the input. Classic self-referential crypto.

But here's the thing - 20 bits means only 1,048,576 possible seeds. That's nothing.

Step 6: The Segment Trap (Almost Got Us)

This is where things got spicy. The ciphertext is loaded with:

mov cx, 0x24          ; 36 words + 1 byte = 73 bytes
mov si, 0x146         ; source offset
rep movsw             ; copy from DS:SI to ES:DI
movsb

First instinct: grab 73 bytes from code offset 0x146. WRONG.

In this MZ executable, CS != DS. The code segment starts at paragraph 0x0000, but the data segment is at 0x0239. That's a 0x2390 byte offset. The mov si, 0x146 loads from DS:0x146, not CS:0x146.

The code segment bytes looked like gibberish when decrypted. The data segment bytes produced the flag.

For the homies who haven't touched DOS segmented memory: in real mode x86, a segment:offset pair translates to physical address segment * 16 + offset. Different segment registers (CS, DS, SS, ES) can point to completely different memory regions.

Step 7: The Brute Force

With the correct ciphertext extracted, the solve is clean:

# Actual ciphertext from DS:0x146
expected = bytes([
    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
])

Strategy:

1. For each of 1,048,576 possible 20-bit states
2. Step LFSR 6 times, decrypt first 6 bytes
3. Check if they equal lactf{ (fast filter - eliminates 99.9999% of candidates)
4. If prefix matches: decrypt all 73 bytes, verify hash
5. If hash(plaintext) == initial_state: we got the flag

Result: State 0xF3FB5 produces a valid flag with matching hash. One unique solution.

The Flag

Leetspeak decode: "easy enough to brute force but not easy enough just to brute force"

The flag itself is meta commentary on the challenge design - the 20-bit keyspace is small enough to brute force, but the segmented memory model and 16-bit reversing make it non-trivial to even reach that point. Respect.

The Solve Script

#!/usr/bin/env python3
"""
LACTF 1986 Solver
Smothy @ 0xN1umb

Brute-forces the 20-bit LFSR state to decrypt the flag
from a DOS-era flag checker.
"""

expected = bytes([
    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
])

def lfsr_step(state):
    feedback = ((state >> 0) ^ (state >> 3)) & 1
    return (state >> 1) | (feedback << 19)

def custom_hash(s):
    h = 0
    for c in s:
        h = (h * 67 + c) & 0xFFFFF
    return h

prefix = b"lactf{"

for init_state in range(1 << 20):
    state = init_state
    ok = True
    for i in range(6):
        state = lfsr_step(state)
        if (expected[i] ^ (state & 0xFF)) != prefix[i]:
            ok = False
            break
    if not ok:
        continue

    # Full decrypt
    state = init_state
    plaintext = bytearray()
    for i in range(len(expected)):
        state = lfsr_step(state)
        plaintext.append(expected[i] ^ (state & 0xFF))

    try:
        text = plaintext.decode('ascii')
    except:
        continue

    if text.endswith('}') and custom_hash(plaintext) == init_state:
        print(f"Flag: {text}")
        break

The Graveyard of Failed Attempts

Attempt 1: Wrong Ciphertext

Grabbed 73 bytes from code segment offset 0x146 instead of data segment offset 0x146. Got code bytes (01 00 eb 02 31 c0...) instead of actual ciphertext (b6 8c 95 8f 9b 85...). Brute force returned zero results. Spent a hot minute staring at the screen before the segment math clicked.

Attempt 2: Misunderstanding the Hash Width

Initially considered the hash might be 32-bit (full dx:ax without the and si, 0xf mask). That would've been 4 billion states to check instead of 1 million. Thankfully, re-reading the code showed the and si, 0xf clearly limiting it to 20 bits.

Key Takeaways

1. 16-bit DOS reversing requires understanding segmented memory. CS, DS, SS, and ES can all point to different places. Always check which segment register is active for memory accesses.

2. MZ EXE relocations tell you where segment references live in the binary. The relocation table is your friend for understanding the memory layout.

3. Small keyspaces are deadly - a 20-bit LFSR seed means ~1M possibilities. Even in Python, that brute forces in seconds. The challenge author knew this: the flag literally says "easy enough to brute force."

4. Turbo C startup code has recognizable patterns - "Stack Overflow!", "NULL assignment detected", the segment initialization dance. Knowing your compiler signatures helps skip past boilerplate.

5. Self-referential crypto (hash of plaintext used as encryption key) creates a chicken-and-egg problem that brute force neatly bypasses when the keyspace is small.

6. Capstone is excellent for 16-bit x86 disassembly when you can't fire up IDA or Ghidra. Just remember to use CS_MODE_16.

Tools Used

• 7z - floppy image extraction
• file / strings - initial recon
• Python 3 + capstone - 16-bit disassembly
• Python 3 - custom solver script
• Manual hex analysis - MZ header parsing
• Way too much caffeine

Writeup by Smothy from 0xN1umb team. Who knew a floppy disk from 1986 would teach us about segmented memory in 2025. Respect to the challenge author for the retro vibes. GG.