Nonograms | DiceCTF 2025

README.md

Nonograms | DiceCTF 2025

tl;dr:

• Use gauss in Z2 to find any solution per row, and the kernel
• Using the kernel find a solution for columns without breaking rows, and also find the kernel
• Using the new kernel find a solution that matches known qrcode requirements
• profit

---

Write Up: Pending

data.json

{"vs": ["0xc4cf", "0x899f", "0x133f", "0x1b1a", "0xb50", "0x2bc4", "0x6aec", "0xe8bc", "0x1a55", "0x9ce", "0x2ef8", "0x6094", "0xfc4c", "0xf899", "0xf133", "0xe267", "0xb27", "0x2b2a", "0x6b30", "0xeb04", "0xd609", "0xac13", "0x5827", "0x8d2a", "0xc29a"], "rows": ["0x6d5c", "0xe1f4", "0xe05", "0x4c83", "0x801c", "0x9d09", "0xd041", "0x7680", "0xa050", "0x2024", "0x7a61", "0x9c87", "0xf321", "0x98e0", "0x3698", "0xef35", "0x5c48", "0x86aa", "0x80c7", "0x5be", "0xc22d", "0xb6a4", "0xf609", "0xf01a", "0x501a"], "cols": ["0xa050", "0xffc6", "0xd3be", "0x3249", "0xd4b7", "0x92ab", "0x9553", "0x5eaa", "0x4a10", "0xaf30", "0x8384", "0x9af1", "0xd098", "0xfb91", "0x1bbd", "0x55f0", "0x58f2", "0xad51", "0xd041", "0x494e", "0xeaf5", "0x210c", "0xc29a", "0xc1a4", "0x464f"]}

gauss.py

# Plot this matrix using matplotlib
import matplotlib.pyplot as plt
import json


constraints = """
#######.000000000.#######
#.....#.000000000.#.....#
#.###.#.000000000.#.###.#
#.###.#.000000000.#.###.#
#.###.#.000000000.#.###.#
#.....#.000000000.#.....#
#######.#.#.#.#.#.#######
........000000000........
000000#000000000000000000
000000.000000000000000000
000000#000000000000000000
000000.000000000000000000
000000#000000000000000000
000000.000000000000000000
000000#000000000000000000
000000.000000000000000000
000000#000000000000000000
........000000000...00000
#######.000000000.#.00000
#.....#.000000000...00000
#.###.#.00000000000000000
#.###.#.00000000000000000
#.###.#.00000000000000000
#.....#.00000000000000000
#######.00000000000000000
"""


icareabout = 0
qrtarget = 0
bit = -1
for line in constraints.strip(" \n").split("\n"):
    for c in line:
        bit += 1
        if c != "0":
            icareabout |= 1 << bit
            if c == "#":
                qrtarget ^= 1 << bit

with open("data.json", "r") as f:
    data = json.load(f)

V = [int(x, 16) ^ 0xFFFF for x in data["vs"]]
R = [int(x, 16) ^ 0xFFFF for x in data["rows"]]
C = [int(x, 16) ^ 0xFFFF for x in data["cols"]]
C = list(reversed(C))

n = len(V)
assert n == len(V) == len(R) == len(C)


class Gauss:
    def __init__(self, size):
        self.base = [0] * size
        self.who = [0] * size

        self.size = size
        self.inserted = 0

    def add(self, x):
        who = 1 << self.inserted
        self.inserted += 1

        for i in range(self.size):
            if x & (1 << i):
                if self.base[i] == 0:
                    self.base[i] = x
                    self.who[i] = who
                    return True, who

                else:
                    x ^= self.base[i]
                    who ^= self.who[i]

        return False, who

    def add2(self, x, icareabout):
        who = 1 << self.inserted
        self.inserted += 1

        for i in range(self.size):
            if icareabout & (1 << i):
                if x & (1 << i):
                    if self.base[i] == 0:
                        self.base[i] = x
                        self.who[i] = who
                        return True, who

                    else:
                        x ^= self.base[i]
                        who ^= self.who[i]

        return False, who


def gen(v, mask):
    assert v < 2**16
    x = 0
    for i in range(n):
        if mask & (1 << i):
            x ^= v << (i * 16)
    return x


full = Gauss(16 * n)
data = []

target = 0
for i in range(n):
    target ^= C[i] << (i * 16)

answer = [0] * n


qrcode = Gauss(n * n)
qrcode_data = []

filter = (1 << n) - 1

for i in range(n):
    g = Gauss(16)
    for j in range(n):
        inserted, mask = g.add(V[j])
        assert (mask & filter) == mask

        if not inserted:
            ins, who = full.add(gen(V[i], mask))
            data.append((i, mask, mask << (i * n)))

            if not ins:
                nvec = 0  # n^2 bits
                for k in range(len(data)):
                    if who & (1 << k):
                        nvec ^= data[k][2]
                qrcode.add2(nvec, icareabout)
                qrcode_data.append(nvec)

    inserted, who = g.add(R[i])
    assert not inserted

    answer[i] = who

    assert (who & filter) != who
    who &= filter

    target ^= gen(V[i], who)


inserted, who = full.add(target)
assert not inserted

for i in range(len(data)):
    if who & (1 << i):
        ix, mask, _ = data[i]
        answer[ix] ^= mask

ans = 0
for i in range(n):
    answer[i] &= (1 << n) - 1
    assert answer[i] < 2**n
    ans ^= answer[i] << (i * n)


qrtarget ^= ans

inserted, who = qrcode.add2(qrtarget, icareabout)
assert not inserted

for i in range(len(qrcode_data)):
    if who & (1 << i):
        ans ^= qrcode_data[i]

frow = [0] * n
fcol = [0] * n

for i in range(n):
    for j in range(n):
        bit = (ans >> (i * n + j)) & 1
        print(bit, end="")
        assert isinstance(bit, int) and 0 <= bit <= 1
        if bit:
            assert bit == 1
            frow[i] ^= V[j]
            fcol[j] ^= V[i]

    print()

assert frow == R
assert fcol == C

mat = [[0] * n for _ in range(n)]

for i in range(n):
    for j in range(n):
        mat[i][j] = 1 - ((ans >> (i * n + j)) & 1)


plt.imshow(mat, cmap="gray")
plt.show()