#【AIS3 Pre-Exam 2026 Writeup】Crypto - EasyPAINT

I started by trying to recover the source from app.bin.

file app.bin
checksec --file=app.bin

app.bin is a stripped PIE ELF. It has Full RELRO, canary, NX, PIE, FORTIFY, SHSTK, and IBT. For a moment it looked like normal binary reversing, but the strings and runtime behavior did not feel like a small C program. It was a Nuitka onefile app.

GDB was not very useful at first. I could see the ELF loader and Python runtime, but not a clean Python source. No useful glibc printf path either. This was a crypto app wrapped as a GUI. No trigger, no path.

The onefile extractor I tried first produced broken filenames. I went back and parsed the Nuitka onefile layout manually. The real child binary is in correct_extract/app.bin.

file correct_extract/app.bin
checksec --file=correct_extract/app.bin

The child binary is still stripped. Direct disassembly was noisy. Runtime hook was easier.

An LD_PRELOAD hook on nanosleep worked better. When Python was initialized, the hook ran a small Python script inside the process and dumped __main__ globals. The dump gave the important constants and function names.

Useful globals:

DIM = 512
P = 257
Q = 127707000586261266406140258152342164811114836442218367658989756920303451547391
LWE_VALUE_BYTES = 33
ENC_MAGIC = b"BDRW"
STR_A_TO_Z = "abcdefghijklmnopqrstuvwxyz_0OABCDEFG"
PASSWORD_SHA256 = "fed99ec1e1ba1e504a432aede0f32956f2562d51b485aef41fdbc04e5ba33697"

There were also functions like:

derive_secret
build_matrix
mat_vec_mul
encrypt_payload
decrypt_payload
stream_xor_encrypt
stream_xor_decrypt
pack_encrypted_payload
unpack_encrypted_payload

The GUI says the password is 64 bytes. That was wrong. Runtime testing showed the real check wants 512 bytes. I patched the hash check in memory once to enter the app and inspect the crypto functions.

enc.bin has a simple format.

python3 - <<'PY'
from pathlib import Path
b = Path("enc.bin").read_bytes()
print(len(b), b[:4], int.from_bytes(b[4:8], "big"))
print((len(b) - 8 - int.from_bytes(b[4:8], "big")) // 33)
PY

The result:

17416 b'BDRW' 512
512

So it is:

BDRW || ciphertext_len || ciphertext || 512 LWE values

Each LWE value is 33 bytes, big endian.

The encryption logic became clear after probing the functions.

secret[j] = int.from_bytes(sha256(bytes([password[j]])).digest(), "big")
product = matrix * secret mod Q
lwe[i] = product[i] + key[i] + 257 * error[i] mod Q
ciphertext = stream_xor_encrypt(plaintext, key)

The stream cipher uses plaintext feedback.

pt[0] = ct[0] ^ key[0]
pt[i] = ct[i] ^ ((key[i] * pt[i - 1]) & 0xff)

At this point I first thought about recovering the password from the SHA256 hash. The alphabet has 36 chars, and the password length is 512. That is not happening directly.

I also tried some clue-based guesses. The challenge text mentions a whale and a sentence like “must imagine … happy”. Some candidate flags and password phrases looked natural, but the stream constraint rejected many of them. Guessing was too weak.

Another dead end was taking lwe[i] % 257 as the key. That would work only if product[i] was zero mod 257. The decrypted bytes were garbage. So the matrix/product part mattered.

I visualized residues and bit patterns too. It looked random. No image hiding in enc.bin.

The part I missed for a while: secret has 512 entries, but each entry only comes from one password byte. The password byte must be in:

abcdefghijklmnopqrstuvwxyz_0OABCDEFG

So secret[j] has only 36 possible values:

H[ch] = int.from_bytes(sha256(ch.encode()).digest(), "big")

For one row of the matrix, the product is not really a 512-dimensional unknown if I only care about counts of each password character in that row.

It can be written as:

sum(count[ch] * H[ch]) mod Q

where count[ch] is bounded. This turns each LWE row into a 36-dimensional bounded knapsack / CVP problem.

Now the problem was small enough for lattice tools.

fpylll was enough for the CVP part:

python3 -m venv .tools/venv
.tools/venv/bin/pip install fpylll cysignals

The lattice basis used one coordinate per possible password character and one large coordinate for the modular sum. After LLL, CVP.closest_vector gave a product close to each LWE value.

The residual is:

residual = product - lwe[i]

From the formula:

lwe[i] = product[i] + key[i] + 257 * error[i] mod Q

the key byte is:

key[i] = (-residual) % 257

The error part vanishes modulo 257.

This recovered 506 of 512 key bytes. The first six were unstable, but the plaintext after that already looked readable:

say_happy_brute_day_to_...

The feedback stream lets me work backwards from the first stable byte. With the known prefix AIS3{, there was only one printable solution for the missing front:

AIS3{whale_will_s

After filling those six keys, the whole plaintext decrypted.

Full exploit:

#!/usr/bin/env python3
from hashlib import sha256
from pathlib import Path
import re
import string

from fpylll import CVP, LLL, IntegerMatrix


Q = 127707000586261266406140258152342164811114836442218367658989756920303451547391
STR_A_TO_Z = "abcdefghijklmnopqrstuvwxyz_0OABCDEFG"
LWE_VALUE_BYTES = 33
DIM = 512


def unpack(path: str):
    blob = Path(path).read_bytes()
    assert blob[:4] == b"BDRW"
    ciphertext_len = int.from_bytes(blob[4:8], "big")
    ciphertext = blob[8 : 8 + ciphertext_len]
    off = 8 + ciphertext_len
    lwe = [
        int.from_bytes(blob[off + i * LWE_VALUE_BYTES : off + (i + 1) * LWE_VALUE_BYTES], "big")
        for i in range(DIM)
    ]
    return ciphertext, lwe


def recover_known_keys(lwe):
    # The 512 secret entries only take 36 possible values: sha256(single password
    # byte).  Each LWE row can therefore be solved as a 36-dimensional bounded
    # knapsack count vector instead of a 512-dimensional binary row.
    hashes = [int.from_bytes(sha256(ch.encode()).digest(), "big") for ch in STR_A_TO_Z]
    bound = 32
    scale = 2048
    n = len(hashes)

    basis = IntegerMatrix(n + 1, n + 1)
    for i, h in enumerate(hashes):
        basis[i, i] = scale
        basis[i, n] = h
    basis[n, n] = Q
    LLL.reduction(basis)

    target_prefix = [(bound // 2) * scale] * n
    keys = []
    for c in lwe:
        v = CVP.closest_vector(basis, tuple(target_prefix + [c]))
        counts = [round(v[i] / scale) for i in range(n)]
        residual = v[-1] - c
        ok = -65790 <= residual <= 0 and all(0 <= x <= bound for x in counts)
        key = (-residual) % 257 if ok else None
        keys.append(key if key is not None and key < 256 else None)
    return keys


def decrypt(ciphertext, keys):
    out = bytearray(len(ciphertext))
    out[0] = ciphertext[0] ^ keys[0]
    for i in range(1, len(ciphertext)):
        out[i] = ciphertext[i] ^ ((keys[i] * out[i - 1]) & 0xFF)
    return bytes(out)


def fill_first_keys(ciphertext, keys):
    # CVP recovers bytes 6..511.  Work backwards from the first stable plaintext
    # byte and use the AIS3{ prefix to determine the six missing stream keys.
    rough_keys = [k if k is not None else 0 for k in keys]
    rough = decrypt(ciphertext, rough_keys)

    candidates = {rough[16]: bytes([rough[16]])}
    printable = list(range(32, 127))
    for i in range(16, 5, -1):
        key = keys[i]
        nxt = {}
        for plain_i, suffix in candidates.items():
            target = ciphertext[i] ^ plain_i
            for prev in printable:
                if ((key * prev) & 0xFF) == target:
                    nxt[prev] = bytes([prev]) + suffix
        candidates = nxt

    prefix = b"AIS3{"
    for suffix in candidates.values():
        known = prefix + suffix
        trial = keys[:]
        trial[0] = ciphertext[0] ^ known[0]
        ok = True
        for i in range(1, 6):
            target = ciphertext[i] ^ known[i]
            prev = known[i - 1]
            sols = [k for k in range(256) if ((k * prev) & 0xFF) == target]
            if not sols:
                ok = False
                break
            trial[i] = sols[0]
        if ok:
            return trial
    raise RuntimeError("failed to recover first six keys")


def main():
    ciphertext, lwe = unpack("enc.bin")
    keys = recover_known_keys(lwe)
    assert sum(k is not None for k in keys) == 506
    keys = fill_first_keys(ciphertext, keys)
    flag = decrypt(ciphertext, keys).decode()
    assert re.fullmatch(r"AIS3\{.*\}", flag, re.DOTALL)
    print(flag)


if __name__ == "__main__":
    main()

Run:

.tools/venv/bin/python solve.py

The flag is 512 bytes. Short exact form:

AIS3{whale_will_say_happy_brute_day_to_ + "u" * 468 + _owo}