cryptofreehard

Just Follow the Recipe

kitctf

Task: SIS/Ajtai hash flag_hash = A*secret mod Q (Q=12289, secret in 0..9^164) printed at connect; a hash oracle returns A*v mod Q but the optimized AVX2 mat_mul is miscompiled by gcc -O3 (wrong stride), so naive matrix recovery yields a wrong A. Solution: recover the TRUE A consistent with the naive-computed flag_hash by querying columns via multi_hash with n<=4 batches (cleanup loop only), then solve the bounded SIS via Kannan embedding + progressive fplll BKZ.

$ ls tags/ techniques/
dockerlatticelllbkzsiskannan_embeddingajtai_hashshort_integer_solutioncompiler_bugavx2autovectorization_bugoracle_matrix_recoveryfplllusvpbddntt
oracle_matrix_recoverykannan_embeddingprogressive_bkzqary_kernel_latticegaussian_elimination_mod_qempirical_bug_characterizationdocker_amd64_replica

$ cat /etc/rate-limit

Rate limit reached (20 reads/hour per IP). Showing preview only — full content returns at the next hour roll-over.

Just Follow the Recipe — GPN24 CTF (KITCTF)

Description

Cooking is easy they say. Just follow the recipe they say. If you follow the recipe nothing can go wrong. And still, I end up with chemical weapons instead of dinner and they complain. But it's not my fault that my kitchen is shit. But they dont want to hear that excuse.

The binary is there for a reason, LOOK at it.

We connect over TLS (ncat --ssl <host>.gpn24.ctf.kitctf.de 443). Each connection forks a fresh process with alarm(200) and regenerates a random matrix A and a random short secret. At connect the server prints flag_hash = A · secret mod Q. The menu lets us hash arbitrary vectors (an A·v oracle) and submit a guess for secret. Recovering the secret exactly yields the flag — but everything must happen on a single 200-second connection because each new connection regenerates A and secret.

Full source was provided: main.c, mat.c, mat.h, a Dockerfile, and a non-stripped x86-64 ELF challenge.

The Math — SIS / Ajtai-style hash

Constants: N=64, M=164, Q=12289 (prime, NTT-friendly = 2^12·3+1), beta=10.

  • A is a random 64×164 matrix over Z_Q, generated per-instance with getrandom then reduced mod Q. It is never printed.
  • secret_vec has length M=164, with every entry in {0..9} (generate_random_vector then vec32_mod(secret_vec, beta=10)).
  • flag_hash = A · secret mod Q (length 64), printed at connect time, computed with mat_mul_naive (the naive, correct multiply).

Goal: recover secret exactly.

This is the Short Integer Solution (SIS) problem / Ajtai's hash. It is information-theoretically unique: 64 · log2(12289) ≈ 870 bits of equations exceed 164 · log2(10) ≈ 545 bits of secret entropy. The centered secret (secret − 4) has L2 norm ≈ 37.4 — a clean unique-SVP / BDD instance.

...

$ grep --similar

Similar writeups