Скоростные Пазлы – 3 (Fast Puzzles – 3)

Platform: bug-makers | Category: Misc | Type: Challenge | Difficulty: Medium | OS: NA | Author: XESXOR | Date: 2026-05-29 | Status: Solved Techniques: api_reverse_engineering, automated_puzzle_solving, fft_cross_correlation_template_matching, hungarian_assignment, integral_image_energy

Summary

Task: web-based 16x16 (256-piece) timed jigsaw puzzle; API serves the original image plus shuffled base64 JPEG pieces and must be solved in 60s. Solution: localize each piece in the original with FFT cross-correlation template matching (integral-image energy term), then Hungarian assignment of pieces to grid cells to enforce a valid permutation.

Скоростные Пазлы – 3 (Fast Puzzles – 3) — bug-makers

Description

Чтобы получить флаг, нужно успеть собрать весь пазл за 1 минуту. Количество пазлов: 256 шт. Адрес: https://fast-puzzles-3.t1.bug-makers.ru

English summary: A web-based drag-and-drop jigsaw puzzle game. The player must correctly assemble a 16×16 grid (256 pieces) within 60 seconds to receive the flag. This is round 3 of the Fast Puzzles series; round 1 (4×4) is documented in 20260525_bug_makers_skorostnye_pazly_1.

Analysis

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

The site is an Express/Node.js application (x-powered-by: Express). The front-end script.js exposes two API endpoints:

1. GET /api/new-game — starts a session (tracked via the connect.sid cookie) and returns JSON:

   • success: boolean
   • puzzle: array of 256 objects, each with id (random UUID), image (base64 JPEG of that piece), width, height
   • originalImage: base64 JPEG of the complete, unshuffled image
   • gridSize: 16 (a 16×16 grid)
   • pieceSize: 34 or 35 depending on the session (the original image is 544×544 or 560×560 — it varies per game) ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

2. POST /api/check-solution — accepts {"solution": [<piece ids in row-major grid order>]} and returns {success, flag, time, timeUp}. The same requests.Session must be reused so the session cookie matches the game.

Because the API hands over the full original image, the puzzle can be solved programmatically by matching each piece against the original — no visual drag-and-drop needed.

Why the round-1 approach fails here (the key difficulty)

Round 1 (4×4) used simple greedy MSE matching: crop each grid cell from the original at exact integer boundaries (row*pieceSize, col*pieceSize) and pick the piece with the lowest pixel MSE. That works only when pieces are large and visually distinct. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

For 16×16 this breaks down. Naive grid-aligned crop matching — greedy or Hungarian on pixel L2/MSE — reconstructs only ~70% correctly. Dark, uniform, and low-detail tiles get swapped because their content is nearly identical.

A sliding-window search on a single piece revealed the root cause: the best match for piece 0 was at pixel (67, 336) — not a multiple of 34, i.e. not grid-aligned. Two things are happening:

• Pieces are not cut at exact integer grid boundaries of the displayed original. The effective tiling step is (W - pieceSize) / (gridSize - 1), which produces slight overlap, so integer grid-aligned crops do not line up with where pieces were actually extracted.
• Each piece is independently JPEG-recompressed, introducing a small per-piece color shift. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

Together these make exact grid-aligned MSE unreliable on ambiguous tiles.

Solution

The robust fix is sub-pixel-accurate FFT-based template localization of each piece in the original, followed by Hungarian assignment to grid cells to enforce a valid bijection (every cell gets exactly one piece).

Steps:

1. Fetch /api/new-game; decode the original image and all 256 piece images into numpy arrays. Read W, H, gridSize, pieceSize dynamically (sizes vary per session).
2. For each piece, find its exact pixel location in the original via template matching expressed through cross-correlation:
   • MSE(x,y) = windowed_sum(orig²) − 2·crosscorr(orig, piece) + sum(piece²)
   • Cross-correlation per channel with scipy.signal.fftconvolve(orig[:,:,c], piece[::-1,::-1,c], mode="valid").
   • The windowed_sum(orig²) energy term is computed with an integral image (cumsum) for speed.
   • argmin over the MSE map gives (x, y) for each piece. All 256 pieces are located in ~2.6 s.
3. Compute the effective grid step step = (W - pieceSize) / (gridSize - 1).
4. Build a cost matrix (piece × cell) where cost = squared distance from a piece's found (x, y) to each cell center (col*step, row*step). Solve with the Hungarian algorithm (scipy.optimize.linear_sum_assignment) — this guarantees a perfect permutation even when several pieces map near the same region.
5. Order the piece UUIDs by cell index (row-major) and POST to /api/check-solution. ‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

End-to-end solve time was ~6.9 s, well within the 60 s limit. The server returned {"success":true,"flag":"BugCTF{REDACTED}","time":"2.21"}.

 python read-only • copy allowed Copy
#!/usr/bin/env python3
import requests, base64, io, time, numpy as np
from PIL import Image
from scipy.signal import fftconvolve
from scipy.optimize import linear_sum_assignment

BASE = "https://fast-puzzles-3.t1.bug-makers.ru"
s = requests.Session()
t0 = time.time()
d = s.get(BASE + "/api/new-game").json()
grid = d["gridSize"]
pieces_meta = d["puzzle"]
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

def decode(u):
    return Image.open(io.BytesIO(base64.b64decode(u.split(",", 1)[1]))).convert("RGB")

orig = np.asarray(decode(d["originalImage"])).astype(np.float32)
H, W, _ = orig.shape
pieces = [np.asarray(decode(p["image"])).astype(np.float32) for p in pieces_meta]
ps = pieces[0].shape[0]

def windowed_sumsq(o):
    o2 = o**2
    cs = np.cumsum(np.cumsum(o2, 0), 1)
    cs = np.pad(cs, ((1, 0), (1, 0)))
    return cs[ps:, ps:] - cs[:-ps, ps:] - cs[ps:, :-ps] + cs[:-ps, :-ps]

oe = sum(windowed_sumsq(orig[:, :, c]) for c in range(3))
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

locs = []
for p in pieces:
    cc = sum(fftconvolve(orig[:, :, c], p[::-1, ::-1, c], mode="valid") for c in range(3))
    mse = oe - 2 * cc + (p**2).sum()
    idx = np.unravel_index(np.argmin(mse), mse.shape)
    locs.append((idx[1], idx[0]))  # x, y

step = (W - ps) / (grid - 1)
cost = np.zeros((len(pieces), grid * grid), dtype=np.float64)
for pi, (x, y) in enumerate(locs):
    for cell in range(grid * grid):
        cr, ccol = cell // grid, cell % grid
        cost[pi, cell] = (x - ccol * step) ** 2 + (y - cr * step) ** 2
‍​‌‌​​‌​​​‌‌​​‌​​​​‌‌​‌​​​​‌‌‌​​‌​​‌‌​​​‌​​‌‌‌​​​​​‌‌​‌‌​​​‌‌​​​​‍

row, col = linear_sum_assignment(cost)
order = [None] * (grid * grid)
for pi, cell in zip(row, col):
    order[cell] = pieces_meta[pi]["id"]

resp = s.post(BASE + "/api/check-solution", json={"solution": order})
print(resp.text)  # {"success":true,"flag":"BugCTF{REDACTED}",...}
print("total", time.time() - t0)

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