Unremarable

Task description

The file was recovered without any accompanying notes. Nothing about it was considered significant at the time.

Starting Evidence

The challenge supplied a 4725 by 3150 RGB PNG and this description:

The file was recovered without any accompanying notes. Nothing about it was considered significant at the time.

Prior work had already established:

• A red-channel LSB string at the beginning of the image is an explicit decoy.
• The PNG has valid chunks and no appended payload.
• Its DEFLATE stream is byte-identical to an ordinary level-9 recompression.
• PNG filter choices encode a checksummed AFT2 record.
• The original photograph is Vecteezy’s “View of green mountains” by Jozef Jankola, resource 2133216.
• Comparing the image with that JPEG isolates 131 green-channel LSB changes near (3319, 2198) and 683 red-channel bit-1 changes near (1021, 2489), besides the decoy.

The successful continuation began with this evidence rather than repeating generic bit-plane extraction, watermark detection, or source-image searches. The source-image comparison was a discovery aid, not a dependency of the eventual decoder.

Layer 1: PNG Filters

Inflate the concatenated IDAT chunks. Each RGB8 scanline consists of a filter byte followed by width * 3 filtered pixel bytes. Let t[i] be its filter byte.

For the first 344 transitions:

d[i] = (t[i + 1] - t[i]) mod 5
byte[j] = 125*d[4*j] + 25*d[4*j+1] + 5*d[4*j+2] + d[4*j+3]

This produces 86 bytes beginning 78 da. Zlib decompression gives an 85-byte record beginning AFT2. Its last four bytes are a little-endian CRC32 of the preceding 81 bytes.

Important fields, with zero-based byte offsets:

Offset	Value	Interpretation Used
0x00	AFT2	Magic
0x05	55 00	Record length, 85
0x07	fc	RGB mask, 252
0x08	4d 96 1d	Luminance weights 77, 150, 29
0x0b	08	Luminance right shift
0x0c	Nine signed bytes	Sobel X kernel
0x15	Nine signed bytes	Sobel Y kernel
0x1e	72 00	Edge threshold, 114
0x21	f7 0c 96 08	Bootstrap seed (3319, 2198)
0x25	00 01 02 03 04 05 06 07	Bootstrap neighbor order
0x2d	37 00	Compressed bootstrap length, 55 bytes
0x30	00 01 02 03 04 05 06 07	Second traversal neighbor order
0x51	17 92 7d 3e	Record CRC32

Some metadata fields are not needed to recover this supplied instance. The final solver does not claim a complete implementation of every possible record option.

An important correction to the earlier interpretation was that fc 4d 96 1d is not a random 32-bit seed: it specifies an RGB mask and three grayscale coefficients. Similarly, f7 0c 96 08 is two coordinates, not a random seed.

Stable Edge Map

Clear both low bits in every RGB channel before deriving traversal features:

R' = R & 252
G' = G & 252
B' = B & 252
Y = (77*R' + 150*G' + 29*B') >> 8

Use the embedded kernels:

Kx = [-1  0  1]       Ky = [-1 -2 -1]
     [-2  0  2]            [ 0  0  0]
     [-1  0  1]            [ 1  2  1]

Define edge strength S = abs(Kx * Y) + abs(Ky * Y) and keep pixels with S >= 114. The low-bit mask ensures that embedding changes cannot alter this map. Both hidden pixel regions use this same threshold.

Direction IDs are north first, clockwise:

0 N, 1 NE, 2 E, 3 SE, 4 S, 5 SW, 6 W, 7 NW

Layer 2: Breadth-First Bootstrap

Perform breadth-first search from (x=3319, y=2198) over the eligible eight-neighbor graph, marking vertices visited when enqueued. Use direction order 0..7 and include the seed in the output order.

The carrier is not the green bit alone:

carrier = (G XOR B) & 1

Group seven consecutive carrier bits and compute their Hamming syndrome:

symbol = XOR of all j for which carrier[j-1] == 1, j = 1..7

Write each symbol as three bits, most significant first, then pack into bytes. Read ceil(55*8/3) * 7 = 1029 pixels and retain the first 55 decoded bytes.

This is matrix embedding: each group carries three message bits while requiring at most one image-bit change. The source-image diff confirmed that all 131 green changes occupy distinct seven-pixel groups under exactly this traversal. This distinguished the correct traversal from plausible but wrong neighbor orders and explained why raw bit extraction had looked random.

The 55 bytes begin 78 da and inflate to this 46-byte record:

444a4b3101fd03b90901004145443105010102030405060728010000
a7058ceb0004e4e436c86aeccc7a0ef06e60

It has magic DJK1, an embedded AED1 record, and a valid trailing CRC32. Relevant fields:

Offset	Value	Meaning
0x05	fd 03 b9 09	Next seed (1021, 2489)
0x09	01 00	Base edge cost, 1
0x0b	AED1	Embedded extraction record magic
0x18	28 01 00 00	Recovered archive length, 296
0x1c	a7 05 8c eb	Archive CRC32, eb8c05a7
0x2a	0e f0 6e 60	Record CRC32, 606ef00e

Layer 3: Weighted Traversal

Use Dijkstra’s algorithm from (1021, 2489) over the same eligible-pixel graph. For adjacent vertices u and v:

cost(u, v) = 1 + abs(S[u] - S[v])

The output order is the settled-vertex order. Heap entries must sort as (distance, y, x). Tie-breaking matters: insertion-order or (distance, x, y) ordering produces a different carrier stream. Settled vertices are skipped when encountered again in the heap.

Use the carrier:

carrier = ((R XOR B) >> 1) & 1

Apply the same seven-pixel Hamming extraction. Collect ceil(296*8/3) * 7 = 5530 settled pixels and retain 296 bytes. The image diff again confirms at most one modification per seven-pixel group, across all 683 red changes.

The output begins PK 03 04: a ZIP whose CRC32 equals eb8c05a7, exactly the value in the bootstrap. Both ZIP members pass their internal CRC checks:

flag.txt:
hiCTF{fr0nt13rs_f4d3_but_w31ght3d_p4ths_r3m41n}

note.txt:
The first answer was only the surface.

The flag’s reference to weighted paths is consistent with the traversal, but was not used as a guess or an extraction oracle.

Eliminated Alternatives

• Raw green/red bit streams and extraction from the wrong channel parity do not yield the payload; cross-channel XOR with blue is essential.
• DFS and priority-by-strength traversal do not explain the bootstrap’s modification grouping. North-first clockwise BFS does.
• Treating the opaque-looking filter fields as PRNG seeds, and trying common XOR keystreams or bit/byte permutations, did not validate a payload.
• Reed-Solomon hypotheses based on the short integer list did not produce a checksum-valid message; no Reed-Solomon step is needed for this instance.
• BFS for the red region and Dijkstra with intensity difference, inverse edge strength, or alternative tie-breaking fail the exact group alignment.
• The original broad raster/bit-plane, generic watermark, and compression investigations remain documented in the prior notes and were not repeated.

Complete solver

The solver reads only the challenge PNG. It decodes all three layers — filter-byte record, BFS bootstrap, Dijkstra traversal — and verifies every CRC before extracting the flag:

from collections import deque
from pathlib import Path
import heapq, io, struct, zipfile, zlib

import cv2
import numpy as np
from PIL import Image

DIRECTIONS = [(-1, 0), (-1, 1), (0, 1), (1, 1),
              (1, 0), (1, -1), (0, -1), (-1, -1)]

def hamming(image, coords, channel, bit, length):
    y, x = np.array(coords).T
    carrier = ((image[y, x, channel] ^ image[y, x, 2]) >> bit) & 1
    blocks = carrier.reshape(-1, 7)
    symbols = np.bitwise_xor.reduce(blocks * np.arange(1, 8), axis=1)
    bits = ((symbols[:, None] >> np.arange(2, -1, -1)) & 1).astype(np.uint8)
    return np.packbits(bits.ravel()).tobytes()[:length]

def main():
    png = Path('chall.png').read_bytes()
    pos = 8
    idat = []
    while pos < len(png):
        length, = struct.unpack_from('>I', png, pos)
        kind = png[pos + 4:pos + 8]
        body = png[pos + 8:pos + 8 + length]
        if kind == b'IDAT':
            idat.append(body)
        pos += length + 12
    image = np.array(Image.open('chall.png').convert('RGB'))
    height, width, _ = image.shape

    # Layer 1: PNG filter-byte transitions -> AFT2 record
    raw = zlib.decompress(b''.join(idat))
    filters = np.frombuffer(raw, np.uint8).reshape(height, width * 3 + 1)[:, 0].astype(int)
    digits = (filters[1:345] - filters[:344]) % 5
    compressed = bytes((digits.reshape(-1, 4) @ np.array([125, 25, 5, 1])).tolist())
    recipe = zlib.decompress(compressed)
    assert recipe[:4] == b'AFT2'
    assert zlib.crc32(recipe[:-4]) == int.from_bytes(recipe[-4:], 'little')

    # Build stable edge map from masked RGB
    rgb = (image & recipe[7]).astype(np.int32)
    gray = (rgb * np.array(list(recipe[8:11]))).sum(axis=2) >> recipe[11]
    kx = np.frombuffer(recipe[12:21], np.int8).reshape(3, 3).astype(float)
    ky = np.frombuffer(recipe[21:30], np.int8).reshape(3, 3).astype(float)
    strength = (abs(cv2.filter2D(gray.astype(float), cv2.CV_64F, kx))
                + abs(cv2.filter2D(gray.astype(float), cv2.CV_64F, ky))).astype(np.int32)
    threshold = int.from_bytes(recipe[30:32], 'little')
    eligible = strength >= threshold

    # Layer 2: BFS from bootstrap seed, Hamming extraction -> DJK1 record
    sx, sy = struct.unpack_from('<HH', recipe, 33)
    green_length = int.from_bytes(recipe[45:47], 'little')
    required = ((green_length * 8 + 2) // 3) * 7
    queue = deque([(sy, sx)])
    seen = {(sy, sx)}
    coords = []
    while queue and len(coords) < required:
        y, x = queue.popleft()
        coords.append((y, x))
        for direction in recipe[37:45]:
            dy, dx = DIRECTIONS[direction]
            yy, xx = y + dy, x + dx
            if 0 < yy < height - 1 and 0 < xx < width - 1 and eligible[yy, xx] and (yy, xx) not in seen:
                seen.add((yy, xx))
                queue.append((yy, xx))
    green = zlib.decompress(hamming(image, coords, 1, 0, green_length))
    assert green[:4] == b'DJK1'
    assert zlib.crc32(green[:-4]) == int.from_bytes(green[-4:], 'little')

    # Layer 3: Dijkstra from second seed, Hamming extraction -> ZIP
    sx, sy = struct.unpack_from('<HH', green, 5)
    base_cost = int.from_bytes(green[9:11], 'little')
    red_length, expected_crc = struct.unpack_from('<II', green, 24)
    required = ((red_length * 8 + 2) // 3) * 7
    queue = [(0, sy, sx)]
    distances = {(sy, sx): 0}
    settled = set()
    coords = []
    while queue and len(coords) < required:
        distance, y, x = heapq.heappop(queue)
        if (y, x) in settled:
            continue
        settled.add((y, x))
        coords.append((y, x))
        for direction in recipe[48:56]:
            dy, dx = DIRECTIONS[direction]
            yy, xx = y + dy, x + dx
            if not (0 < yy < height - 1 and 0 < xx < width - 1) or not eligible[yy, xx] or (yy, xx) in settled:
                continue
            candidate = distance + base_cost + abs(int(strength[y, x]) - int(strength[yy, xx]))
            if candidate < distances.get((yy, xx), float('inf')):
                distances[(yy, xx)] = candidate
                heapq.heappush(queue, (candidate, yy, xx))
    archive = hamming(image, coords, 0, 1, red_length)
    assert zlib.crc32(archive) == expected_crc
    with zipfile.ZipFile(io.BytesIO(archive)) as recovered:
        assert recovered.testzip() is None
        flag = recovered.read('flag.txt').decode().strip()
    print(f'AFT2: {len(recipe)} bytes, CRC valid')
    print(f'DJK1: {len(green)} bytes, zlib and CRC valid')
    print(f'ZIP: {len(archive)} bytes, CRC {expected_crc:08x}, member CRCs valid')
    print(flag)

if __name__ == '__main__':
    main()