Точечный выбор (Pointed Selection)
Точечный выбор (Pointed Selection)
Platform: hackerlab | Category: Misc | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2024-03-08 | Status: Solved Techniques: codeset_abc_state_machine, dotcode_decoder_from_zint, dotcode_lattice_detection, idat_scanline_overread, parity_lattice_identification, png_ihdr_height_falsification
Summary
Task: a PNG of a black-dot grid (DotCode 2D barcode) whose IHDR height is falsified to hide a second symbol below the declared image. Solution: re-decode IDAT past the fake height to reveal the hidden symbol, then build a DotCode decoder by reversing zint's dotcode.c; the visible top symbol is a decoy, the hidden bottom symbol holds the real flag.
Точечный выбор (Pointed Selection) — hackerlab
Description
QR-коды вышли из моды, что же теперь мы придумали?
English: "QR codes are out of fashion, so what have we come up with now?" The only artifact is a single PNG (834x563 RGBA) showing a grid of black dots on a white background. Flag format is CODEBY{...}.
Analysis
Semantic clue
- Title "точечный выбор" = "dot / point selection".
- "QR out of fashion, what did we invent" → an alternative dot-based 2D barcode rather than connected QR modules. This points directly to DotCode (the GS1/ISO DotCode standard), a grid of isolated dots.
Identifying the DotCode lattice
- Dot centroids were detected with
scipy.ndimage(label+center_of_mass): 307 dots. - The grid is uniform 27 rows × 40 cols with ~20.85 px spacing.
- Key signature: every dot satisfies
(row + col) % 2 == 0— all dots sit on a single checkerboard parity. This even-parity lattice is the defining property of DotCode (dots only occupy one parity of the grid).
The hidden second symbol (the main twist)
Standard barcode readers (zbarimg, dmtxread, zxing-cpp) all FAIL — none of them support DotCode.
The real trick is in the PNG container:
- All chunk CRCs were valid and
IENDwas clean, but the declaredIHDRheight (563) was false. - Decompressing all
IDATdata produced 1168 scanlines, not 563 → 605 hidden rows below the declared image. - Reconstruction: concatenate IDAT,
zlib.decompress, manually un-filter the PNG scanlines (filter types 0–4, including Paeth), reshape to the true height. This reveals a second DotCode symbol stacked below the visible one.
Practically: patch the IHDR height (or re-decode IDAT past the declared height) with any tool that ignores the height field, and the extra barcode renders at the bottom.
Two DotCode symbols
- TOP (visible): 40 wide × 27 tall, 307 dots, all even-parity.
- BOTTOM (hidden): 42 wide × 29 tall, 340 dots, all even-parity.
- Both satisfy DotCode's rule that width and height have opposite parity.
Solution
Building a DotCode decoder (none exists publicly)
zxing-cpp (Python 3.0.0 and the C++ source) and BoofCV only encode DotCode (via libzint); there is no public DotCode reader. The solution was to reverse-engineer zint's dotcode.c encoder and implement the inverse decoder:
- Unfold the dot lattice — exact inverse of zint's
dc_fold_dotstream(horizontal folding for odd height; the 6 reserved corner dots are placed last). Validated by round-tripping a zint-renderedhackerlabsymbol: the folded matrix matched the render byte-for-byte. - Parse the bitstream — first 2 bits = mask id, then 9-bit Annex-C dot patterns matched against the 113-entry pattern table → masked codewords.
- Unmask — subtract the weighting step (mask 1 → step 3, mask 2 → step 7, mask 3 → step 17) modulo 113 (GF(113)).
- Code Set A/B/C state machine — initial mode is Code Set C; codeword 106 latches to Code Set B → ASCII.
Decode parameters discovered:
- TOP: mask 2, data length 37.
- BOTTOM: mask 1, data length 43.
zint --verbose output (codewords, mask, binary) plus its open-source dotcode.c served as a perfect oracle to learn the exact bit layout and codeword order.
Decoder (reverses zint dotcode.c)
python read-only • copy allowed#!/usr/bin/env python3 # dotcode_decode.py — DotCode decoder built by reversing zint's dotcode.c import numpy as np DC_GF = 113 dc_dot_patterns = [ 0x155,0x0ab,0x0ad,0x0b5,0x0d5,0x156,0x15a,0x16a,0x1aa,0x0ae, 0x0b6,0x0ba,0x0d6,0x0da,0x0ea,0x12b,0x12d,0x135,0x14b,0x14d, 0x153,0x159,0x165,0x169,0x195,0x1a5,0x1a9,0x057,0x05b,0x05d, 0x06b,0x06d,0x075,0x097,0x09b,0x09d,0x0a7,0x0b3,0x0b9,0x0cb, 0x0cd,0x0d3,0x0d9,0x0e5,0x0e9,0x12e,0x136,0x13a,0x14e,0x15c, 0x166,0x16c,0x172,0x174,0x196,0x19a,0x1a6,0x1ac,0x1b2,0x1b4, 0x1ca,0x1d2,0x1d4,0x05e,0x06e,0x076,0x07a,0x09e,0x0bc,0x0ce, 0x0dc,0x0e6,0x0ec,0x0f2,0x0f4,0x117,0x11b,0x11d,0x127,0x133, 0x139,0x147,0x163,0x171,0x18b,0x18d,0x193,0x199,0x1a3,0x1b1, 0x1c5,0x1c9,0x1d1,0x02f,0x037,0x03b,0x03d,0x04f,0x067,0x073, 0x079,0x08f,0x0c7,0x0e3,0x0f1,0x11e,0x13c,0x178,0x18e,0x19c, 0x1b8,0x1c6,0x1cc, ] pat2cw = {p: i for i, p in enumerate(dc_dot_patterns)} def is_corner(column, row, width, height): if column == 0 and row == 0: return 1 if height & 1: if (column == width-2 and row == 0) or (column == width-1 and row == 1): return 1 else: if column == width-1 and row == 0: return 1 if height & 1: if column == 0 and row == height-1: return 1 else: if (column == 0 and row == height-2) or (column == 1 and row == height-1): return 1 if (column == width-2 and row == height-1) or (column == width-1 and row == height-2): return 1 return 0 def fold_order(width, height): """Inverse of zint dc_fold_dotstream: stream position -> flat dot index.""" order = [] if height & 1: # horizontal folding (odd height) for row in range(height): for column in range(width): if not ((column+row) & 1): if not is_corner(column, row, width, height): order.append(((height-row-1)*width) + column) order += [width-2, (height*width)-2, (width*2)-1, ((height-1)*width)-1, 0, (height-1)*width] else: # vertical folding (even height) for column in range(width): for row in range(height): if not ((column+row) & 1): if not is_corner(column, row, width, height): order.append((row*width) + column) order += [((height-1)*width)-1, (height-2)*width, (height*width)-2, ((height-1)*width)+1, width-1, 0] return order def unfold(flat, width, height): order = fold_order(width, height) return ''.join('1' if flat[i] == '1' else '0' for i in order) def unmask(masked, mask): step = {0:0, 1:3, 2:7, 3:17}[mask] out, weight = [], 0 for v in masked: out.append((v - weight) % DC_GF) weight += step return out def parse_stream(stream): mask = int(stream[0:2], 2) bp, masked = 2, [] while bp+9 <= len(stream): chunk = int(stream[bp:bp+9], 2) if chunk in pat2cw: masked.append(pat2cw[chunk]); bp += 9 else: break return mask, masked, bp def setA(cw): return chr(cw+32) if cw < 64 else chr(cw-64) def shiftB(cw): if cw <= 95: return chr(cw+32) if cw == 96: return '\r\n' return {97:'\t', 98:chr(28), 99:chr(29), 100:chr(30)}.get(cw, '?') def decode_codewords(cws): out, mode, i, n = [], 'C', 0, len(cws) while i < n: cw = cws[i] if mode == 'C': if cw <= 99: out.append('%02d' % cw); i += 1 elif cw == 101: mode = 'A'; i += 1 elif cw == 102: mode = 'B'; i += 1 elif cw in (103,104,105): nx = cw-101; i += 1 for _ in range(nx): if i < n: out.append(shiftB(cws[i])); i += 1 elif cw == 106: mode = 'B'; i += 1 else: i += 1 elif mode == 'A': if cw <= 95: out.append(setA(cw)); i += 1 elif cw == 106: mode = 'C'; i += 1 elif cw == 102: mode = 'B'; i += 1 else: i += 1 elif mode == 'B': if cw <= 95: out.append(chr(cw+32)); i += 1 elif cw == 101: i += 1 if i < n: out.append(setA(cws[i])); i += 1 elif cw == 102: mode = 'A'; i += 1 elif cw == 106: mode = 'C'; i += 1 else: i += 1 return ''.join(out) def load_matrix(path): rows = [ln.strip() for ln in open(path) if ln.strip() and not ln.startswith('#')] h, w = len(rows), len(rows[0]) flat = [c for r in rows for c in r] return flat, w, h for name, path in [('TOP','top_matrix.txt'), ('BOT','bot_matrix.txt')]: flat, w, h = load_matrix(path) stream = unfold(flat, w, h) mask, masked, bp = parse_stream(stream) total = len(masked) dl = next((d for d in range(1, total) if d + (3 + d//2) == total), total) data = unmask(masked, mask)[:dl] print(f"{name} {w}x{h} mask={mask} data_len={dl}: {decode_codewords(data)!r}")
PNG reconstruction (reveal the hidden symbol)
python read-only • copy allowedimport zlib, struct, numpy as np raw = open('task.png','rb').read() # concatenate all IDAT chunk payloads idat, off = b'', 8 while off < len(raw): length = struct.unpack('>I', raw[off:off+4])[0] ctype = raw[off+4:off+8] if ctype == b'IDAT': idat += raw[off+8:off+8+length] off += 12 + length data = zlib.decompress(idat) width = 834 stride = width*4 + 1 # RGBA + 1 filter byte true_h = len(data) // stride # 1168, not the IHDR 563 # un-filter scanlines (0=None,1=Sub,2=Up,3=Avg,4=Paeth) and reshape to true_h x width