Error Correction - LA CTF Misc Writeup

Category: Misc Difficulty: Medium Points: 237 Solves: 56 Flag: lactf{Th15_15_pr0b481y_n07_wh47_7h3y_m34n7_8y_3rr0r_c0rr3c710n_CVOD5Jp7IOq+XgR} Solved by: Smothy @ 0xN1umb

"They shuffled a QR code and thought error correction wouldn't save us. They were wrong."

Challenge Description

Looks like their error correction's no match for my error creation!

We're given two files: chall.py (the scrambling script) and chall.png (the scrambled QR code). The flag is hidden inside a QR code that's been split into 25 blocks and randomly shuffled. Our job? Put Humpty Dumpty back together again.

TL;DR

A QR code (Version 7, 45x45 modules) gets split into a 5x5 grid of 9x9 blocks and randomly shuffled. We use QR structural patterns (finders, timing, alignment) to fix 13 blocks, determine the flag length (79 chars) by testing padding patterns against segno-generated references, use stable padding pixels to uniquely determine 11 more blocks, force the last one, and RS error correction verifies everything with 0 errors. QR codes go brrr.

Initial Recon

The challenge gives us chall.py which reveals the exact QR generation process:

qr = segno.make(flag, mode='byte', error='L', boost_error=False, version=7)

Key parameters:

• Version 7: 45x45 modules
• Byte mode: flag encoded as raw bytes
• Error correction L: lowest level (20 EC codewords per RS block)
• segno library: auto-selects mask pattern

The scrambling splits the 45x45 QR into 25 chunks of 9x9 pixels each, shuffles them randomly, then reassembles into a new image.

Step 1: Extract the Blocks

First, downscale the 450x450 image back to 45x45 (each module = 10x10 pixels), then extract the 25 blocks of 9x9:

img = Image.open('chall.png').convert('L')
img = img.resize((45, 45), Image.NEAREST)
pixels = np.array(img)

blocks = []
for y in range(5):
    for x in range(5):
        blocks.append(pixels[y*9:(y+1)*9, x*9:(x+1)*9].copy())

Step 2: Structural Pattern Matching

QR codes have fixed structural patterns that are the same regardless of data content:

• 3 Finder patterns (7x7 + separators) at top-left, top-right, bottom-left
• Timing patterns (alternating dark/light) along row 6 and column 6
• 6 Alignment patterns (5x5) at intersections of {6, 22, 38}
• Version information (18 bits) for version >= 7
• Format information (15 bits) encoding EC level and mask
• Dark module at position (37, 8)

For the homies who haven't touched QR internals: these structural pixels have KNOWN values. By generating a reference QR with segno (same version, same mask), we can extract exactly what each structural pixel should be, then check which of our 25 blocks match each grid position.

# Generate reference, compare function pattern pixels
ref = gen_qr("lactf{" + "A"*72 + "}", mask=0)
for pos in all_positions:
    constraints = [(lr, lc, ref[py*9+lr, px*9+lc])
                   for lr, lc if is_function[py*9+lr, px*9+lc]]
    compatible = [bid for bid in range(25) if all_match(bid, constraints)]

Results:

• 11 positions uniquely determined (1 compatible block each)
• 2 positions with 2 options each (resolved by mutual exclusion)
• 12 positions with 0 function pattern pixels (unconstrained!)

After constraint propagation: 13 blocks fixed, 12 still unknown.

Step 3: Determine Flag Length

This was the breakthrough. From CW1 = 0x44, we know mode = byte (0100) and count_hi = 4, so the flag is 64-79 characters.

For each possible length, QR padding bytes (0xEC, 0x11 alternating) fill the unused capacity. These padding bytes produce stable pixels - identical across ANY QR with the same length and mask, regardless of flag content.

The key insight: generate multiple reference QRs with different flag content (but same length), find pixels that are identical across ALL of them, then check if the actual blocks match at those positions.

for count in range(64, 80):
    refs = [gen_qr("lactf{" + ch * (count-7) + "}") for ch in "AzM3qXj9"]
    stable = all_refs_equal(refs)  # Truly stable pixels
    mismatches = check_fixed_blocks(stable, ref_values)

Count = 79 wins by a landslide. Only 2 mismatches out of 232 checked pixels (99.1% match). Every other length has 20%+ mismatch rates.

Step 4: Solve the Remaining Blocks

With count=79 confirmed, the truly stable pixels (750 data pixels + 457 function pixels) give us constraints for the 12 remaining positions:

11 positions uniquely determined! Position (1,1) had 0 compatible blocks due to the 2 stable pixel mismatches, but block 8 is the only remaining block. We force it in and let RS handle any bit errors.

Step 5: Reconstruct and Decode

Assemble the 25 blocks in the correct order, read data via the QR zigzag pattern, de-interleave into two RS blocks, and decode:

# De-interleave into RS blocks
block1_data = [all_cws[i*2] for i in range(78)]
block2_data = [all_cws[i*2+1] for i in range(78)]
block1_ec = [all_cws[156 + i*2] for i in range(20)]
block2_ec = [all_cws[156 + i*2+1] for i in range(20)]

# RS decode
rs = RSCodec(20)
b1 = rs.decode(bytes(block1_data + block1_ec))  # 0 errors!
b2 = rs.decode(bytes(block2_data + block2_ec))  # 0 errors!

Block 1: RS decode OK, 0 errors corrected Block 2: RS decode OK, 0 errors corrected

Both blocks decode perfectly clean. The forced block 8 at position (1,1) didn't introduce any actual data errors - the 2 "mismatches" were in non-critical stable pixel positions.

The Flag

Leetspeak decode: "This is probably not what they meant by error correction"

The irony is beautiful - the challenge title "error correction" refers to QR error correction, but we literally used error correction to SOLVE the challenge. The flag acknowledges this was probably not the intended use case for RS codes. Respect to the challenge author.

The Solve Script

"""
LACTF Error Correction Solver
Smothy @ 0xN1umb

Reconstructs a shuffled QR code by:
1. Matching blocks to positions via QR structural patterns (13/25)
2. Determining flag length via padding pixel analysis (count=79)
3. Using stable padding pixels to uniquely assign remaining blocks (11/12)
4. Forcing the last block and RS-verifying the result (0 errors)
"""
import numpy as np
from PIL import Image
import segno, tempfile, os
from reedsolo import RSCodec

img = Image.open('chall.png').convert('L').resize((45, 45), Image.NEAREST)
pixels = np.array(img)
blocks = [pixels[y*9:(y+1)*9, x*9:(x+1)*9].copy() for y in range(5) for x in range(5)]

# Build function pattern mask (V7)
size = 45
is_function = np.zeros((size, size), dtype=bool)
is_function[0:8, 0:8] = True; is_function[0:8, 37:45] = True; is_function[37:45, 0:8] = True
is_function[6, 8:37] = True; is_function[8:37, 6] = True
for cr, cc in [(6,22),(22,6),(22,22),(22,38),(38,22),(38,38)]:
    is_function[cr-2:cr+3, cc-2:cc+3] = True
is_function[37, 8] = True
for pos in [(8,0),(8,1),(8,2),(8,3),(8,4),(8,5),(8,7),(8,8),(7,8),(5,8),(4,8),(3,8),(2,8),(1,8),(0,8)]:
    is_function[pos] = True
for pos in [(44,8),(43,8),(42,8),(41,8),(40,8),(39,8),(38,8),(8,37),(8,38),(8,39),(8,40),(8,41),(8,42),(8,43),(8,44)]:
    is_function[pos] = True
for i in range(18):
    is_function[i//3, 34+i%3] = True; is_function[34+i%3, i//3] = True

def gen_qr(flag_str):
    qr = segno.make(flag_str, mode='byte', error='L', boost_error=False, version=7, mask=0)
    with tempfile.NamedTemporaryFile(suffix='.txt', delete=False) as f:
        tmpname = f.name
    qr.save(tmpname, border=0)
    with open(tmpname) as f: txt = f.read()
    os.unlink(tmpname)
    return np.array([0 if ch=='1' else 255 for ch in txt if ch in '01']).reshape(45, 45)

# Step 1: Structural matching -> 13 fixed blocks
ref = gen_qr("lactf{" + "A"*72 + "}")
fixed = {}
for py in range(5):
    for px in range(5):
        constraints = [(lr, lc, ref[py*9+lr, px*9+lc])
                       for lr in range(9) for lc in range(9) if is_function[py*9+lr, px*9+lc]]
        compatible = [bid for bid in range(25)
                      if all(blocks[bid][lr,lc]==exp for lr,lc,exp in constraints)]
        if len(compatible) == 1:
            fixed[(py,px)] = compatible[0]
# Constraint propagation resolves ambiguities -> 13 fixed

# Step 2: Flag length = 79 (determined by padding pixel analysis)
# Step 3: Use stable pixels to assign remaining blocks
refs = [gen_qr("lactf{" + ch*72 + "}") for ch in "AzM3qXj9bReW5kPn1G"]
stable = np.all([r == refs[0] for r in refs[1:]], axis=0)

# Complete assignment (derived from analysis)
full = {
    (0,0):24,(0,1):21,(0,2):10,(0,3):9,(0,4):15,
    (1,0):11,(1,1):8,(1,2):12,(1,3):2,(1,4):14,
    (2,0):0,(2,1):23,(2,2):1,(2,3):6,(2,4):7,
    (3,0):3,(3,1):22,(3,2):16,(3,3):17,(3,4):4,
    (4,0):5,(4,1):18,(4,2):20,(4,3):13,(4,4):19,
}

# Reconstruct and decode
qr_grid = np.zeros((45,45), dtype=np.uint8)
for (py,px),bid in full.items():
    qr_grid[py*9:(py+1)*9, px*9:(px+1)*9] = blocks[bid]
Image.fromarray(qr_grid).resize((450,450), Image.NEAREST).save('reconstructed.png')

import pyzbar.pyzbar as pyzbar
print(pyzbar.decode(Image.open('reconstructed.png'))[0].data.decode())

The Graveyard of Failed Attempts

1. Assumed flag length was 78 - Spent ages computing padding patterns that didn't match because the flag is actually 79 chars. The off-by-one from hell.

2. Used only 2 references for "stable" pixels - With just 2 reference QRs, about 50% of non-padding pixels coincidentally matched, polluting the constraint set. Needed 18+ references to filter out false positives.

3. Expected padding bytes from first principles - My padding byte calculation said CW81=0xEC, but segno actually produces a different interleaving. Should have trusted the library output instead of my manual encoding.

4. Tried RS recovery directly - With only 13/25 blocks known, we had ~70 unknown CWs per block but only 20 EC CWs. RS can only handle 20 erasures. Would need ~18/25 blocks known for RS alone.

5. Wrong version info bit ordering - Initially placed version info bits in row-major MSB-first order instead of LSB-first column-major. Caused several block positions to have 0 compatible blocks.

Key Takeaways

1. QR structural patterns are your friend - Finders, timing, alignment, version info, and format info together uniquely identify over half the blocks just from fixed pixel values.

2. Padding bytes create stable pixels - QR padding (0xEC/0x11 alternating) is content-independent. By generating multiple reference QRs and finding pixels that stay the same across all of them, you get powerful constraints.

3. Flag length matters A LOT - The padding boundary shifts with every character. Testing all possible lengths and checking which one's stable pixels match your actual blocks is the key to cracking this.

4. Don't compute when you can compare - Instead of manually computing expected QR data, generate reference QRs with the actual library used by the challenge and compare directly.

5. RS error correction is the ultimate safety net - Even with a forced block placement, RS decoded both blocks with 0 errors. The QR spec's error correction is robust.

Tools Used

• Python 3 with numpy, PIL, segno, pyzbar, reedsolo
• matplotlib for screenshots
• A deep understanding of QR code internals (Version 7, mask patterns, RS blocks, data interleaving)
• Way too much caffeine

Writeup by Smothy from 0xN1umb team. They said error correction was no match for their error creation. Turns out it was the other way around. GG.