← Back to Writeups
CUSTOMMediumMisc
Bookmark

Сломанный QR-код (Broken QR code)

XESXOR9/2/20267 min read
#misc#custom#medium#qr_reconstruction#reed_solomon_erasure_decoding#per_bit_reliability_recovery#format_info_bch_decode#codeword_deinterleaving#ec_constrained_bruteforce#full_symbol_reencode_verificat

Сломанный QR-код (Broken QR code)

Platform: hackerlab | Category: Misc | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-06-02 | Status: Solved Techniques: qr_reconstruction, reed_solomon_erasure_decoding, per_bit_reliability_recovery, format_info_bch_decode, codeword_deinterleaving, ec_constrained_bruteforce, full_symbol_reencode_verification

Summary

Task: a Version-4 QR code with an oversized opaque spider/shield logo covering the center; all standard decoders fail. Solution: rebuild the 33x33 module matrix, BCH-decode format info, de-interleave 4 blocks, Reed-Solomon erasure-decode the readable blocks, then recover the logo-covered block via per-bit reliability + EC-constrained brute force, and verify by full-symbol re-encode against all reliable modules.

Сломанный QR-код (Broken QR code) — hackerlab

Description

Мы хотели сделать брендированный QR-код, но, кажется, переборщили с размером логотипа...

English summary: We are given task.zip → task.png, a 300×300 RGBA PNG containing a QR code with a large branded logo (an orange shield plus gray spider legs) drawn over the center. The logo is opaque, so it physically destroys many data modules. Every off-the-shelf decoder (zbarimg, pyzbar, OpenCV QRCodeDetector) returns nothing. The goal is to recover the flag (format CODEBY{...}) by reconstructing the QR using its built-in Reed-Solomon error correction plus structural knowledge of the QR standard. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Analysis

The logo is opaque — gray legs are ~RGB(93,93,93) and the orange shield has R>180, B<120 — so the covered modules are genuinely lost, not merely tinted. No amount of image cleanup recovers them. The only path is QR's error-correction machinery.

QR geometry recovery:

  • Quiet zone = 10px; the QR region spans pixels [10, 290] in both axes; module size ≈ 8.48px.
  • Run-length analysis of a finder pattern (the 1:1:3:1:1 ratio) confirms the grid.
  • 33×33 modules ⇒ QR Version 4.
  • Sampling each module center (majority vote in a small window) yields a 33×33 binary matrix (1 = dark). Logo pixels (non-pure-black) initially read as light. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Crucially, while building the matrix we also build a per-module logo-coverage fraction map (logofrac.npy): for each module, what fraction of its pixels falls under the logo. This reliability map is the key to the whole solve.

Solution

Step 1 — Format information (BCH)

Both 15-bit format-info copies (around the finders) are read, XORed with the mask 0b101010000010010, and matched to the nearest BCH(15,5) codeword. Both copies agree:

  • EC level Q, mask pattern 100 (mask 4).
  • Mask 4 inverts a module where ((row//2 + col//3) % 2 == 0). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 2 — Block structure (Version 4-Q)

Version 4-Q has 100 total codewords, interleaved into 4 blocks of 25 codewords each (9 data + 16 EC) → 36 data codewords total + 7 remainder bits. Interleave order is round-robin: all block[i][0] data codewords first, then block[i][1], …, then EC codewords the same way.

Step 3 — Read stream, de-interleave, RS erasure decode

Unmask with mask 4, walk the standard zig-zag module order skipping function patterns, and de-interleave into the 4 blocks. A codeword is marked an erasure if any of its 8 bits is under the logo. reedsolo.RSCodec(16) with erase_pos=[...] corrects up to 16 erasures per block: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

  • block0: 12 erasures ≤ 16 → OK → data 2032344ae84504decc
  • block1: 16 erasures = 16 → OK → data 4ccccdd7d45497d8cc
  • block2: 22 erasures > 16 → fails
  • block3: 20 erasures > 16 → fails (but it is pure padding)

Step 4 — Parse the partial message

De-interleaving the recovered data bytes and parsing the QR bitstream:

  • Mode 0010 (alphanumeric), length 6 → CODEBY
  • Mode 0100 (byte), length 19 → flag body (19 chars incl. braces)

Blocks 0+1 give the first 11 content chars: {1337_QR_c0. Block3 decodes (structurally) to pure padding EC 11 EC 11 … — it lies past the message, so it needs no recovery. The unknowns are content chars 11..18 (8 chars) plus the closing }, all in block 2. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Step 5 — The key trick: per-BIT reliability

Block 2 was flagged with 22 erasures only because a codeword counts as erased if any of its 8 bits is covered. But the thin logo strokes touch only a few bits per byte — most individual bits are read reliably. Switching from per-codeword to per-bit reliability (a bit is uncertain only if its module's logo-coverage fraction > 0.5) collapses the unknown space. Enumerating only the uncertain bits of each content char, and keeping only printable flag characters, gives tiny per-char candidate sets: ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

11 ∈ {d,e}            15 ∈ {0,4,8,D,H,L,P,T,X,d,h,l,p,t,x}
12 ∈ {3,7}            16 ∈ {0,2,4,6}
13 ∈ {K,O,_}          17 ∈ {C,G,S,W,c,g,s,w}
14 ∈ {d,f}            18 = }

Total ≈ 17,280 combinations — trivially brute-forceable.

Step 6 — Constrain with EC bytes, then verify with full re-encode

Two block-2 EC codewords (positions 14 and 15) are reliably read. For each candidate, re-encode block 2 with RSCodec(16) and require those EC bytes to match. Two survivors remain: CODEBY{REDACTED} and CODEBY{REDACTEDOdh6W} (the latter matched the 2 EC bytes only by chance). ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Final disambiguation — reconstruct the ENTIRE QR (all 4 data+EC blocks, re-masked) for each candidate and compare against every reliably-read module (coverage ≤ 0.3):

  • CODEBY{REDACTED} → 475/475 reliable bits match, 0 mismatches ✓
  • CODEBY{REDACTEDOdh6W} → 23 mismatches ✗

The flag is leet-speak for "QR code flag" (c0d3_fl4g).

Winning solver (factored brute-force + EC filter)

 python 
import numpy as np, qrlib, itertools
from reedsolo import RSCodec

N = 33
m  = np.load('matrix2.npy')      # 33x33 module matrix (1=dark)
lf = np.load('logofrac.npy')     # per-module logo-coverage fraction
func = qrlib.build_function_mask()
mf   = qrlib.mask_func(4)         # mask pattern 100
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

# zig-zag module order (skip function patterns)
positions = []
col = N - 1; up = True
while col > 0:
    if col == 6: col -= 1
    for r in (range(N-1, -1, -1) if up else range(N)):
        for c in (col, col-1):
            if func[r, c]:
                continue
            positions.append((r, c))
    up = not up; col -= 2

def rb(si, bp):
    r, c = positions[si*8 + bp]
    v = int(m[r, c])
    if mf(r, c): v ^= 1           # unmask
    return v, float(lf[r, c])

# de-interleave: 4 blocks of 9 data + 16 EC
blk_idx = {b: [] for b in range(4)}; idx = 0
for _ in range(9):
    for b in range(4): blk_idx[b].append(idx); idx += 1
for _ in range(16):
    for b in range(4): blk_idx[b].append(idx); idx += 1
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

LFT = 0.5
ALNUM = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ $%*+-./:'

# reliably-read EC bytes of block 2
ec_known = []
for jj in range(16):
    si = blk_idx[2][9 + jj]
    bits = [rb(si, bp) for bp in range(8)]
    if all(l <= LFT for v, l in bits):
        val = 0
        for v, l in bits: val = (val << 1) | v
        ec_known.append((jj, val))

prefix = '{1337_QR_c0'           # content chars 0..10 from blocks 0,1
cand = {
    11: ['d','e'], 12: ['3','7'], 13: ['K','O','_'], 14: ['d','f'],
    15: list('048DHLPTXdhlptx'), 16: ['0','2','4','6'],
    17: list('CGSWcgsw'), 18: ['}'],
}
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def build_data36(content19):
    bits = '0010' + format(6, '09b')          # alnum mode, len 6
    s = 'CODEBY'
    for i in range(0, 6, 2):
        v = ALNUM.index(s[i])*45 + ALNUM.index(s[i+1]); bits += format(v, '011b')
    bits += '0100' + format(19, '08b')          # byte mode, len 19
    for ch in content19: bits += format(ord(ch), '08b')
    bits += '0000'                              # terminator
    while len(bits) % 8: bits += '0'
    data = [int(bits[i:i+8], 2) for i in range(0, len(bits), 8)]
    pad = [0xEC, 0x11]; pi = 0
    while len(data) < 36: data.append(pad[pi % 2]); pi += 1
    return data[:36]
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

rsc = RSCodec(16); sols = set()
keys = [11,12,13,14,15,16,17,18]
for combo in itertools.product(*[cand[k] for k in keys]):
    content = prefix + ''.join(combo)            # 19 chars
    b2 = build_data36(content)[18:27]            # block 2 data (9 bytes)
    ec = list(rsc.encode(bytearray(b2))[9:])
    if all(ec[jj] == val for jj, val in ec_known):
        sols.add('CODEBY' + content)

for f in sorted(sols):
    print('FLAG:', f)
# Survivors filtered by full-symbol re-encode vs all reliable modules ->
# CODEBY{REDACTED} = 475/475 reliable bits match

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