cryptofreehard

Guess the Taste

kitctf

Task: a 1000-bit prime field leaks five modular inverses of the form (a+r_i)^(-1) with the lower 430 bits truncated. Solution: model it as an MIHNP instance, build the published n=4,d=2,t=0 sublattice, recover e0 modulo many small primes from LLL-derived row polynomials via Groebner bases, then CRT and reconstruct the flag.

$ ls tags/ techniques/
modular_inversecrtlatticelllmihnpgroebner_basistruncated_leakbilinear_polynomial
crt_reconstructionmihnp_sublattice_constructionpairwise_eliminationlll_relation_recoverygroebner_over_finite_fields

$ cat /etc/rate-limit

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

Guess the Taste — GPN24 CTF (KITCTF)

Description

You come into a restaurant but what is that, no menu? Your server tells you to just guess the taste...

We are given a Python script and one concrete instance. The script prints local_taste and then, for five random samples, leaks truncated values related to

y_i = (a + r_i)^(-1) mod P, where a = int(flag_bytes, 16) + local_taste.

Only the upper bits of each inverse are revealed: the lower 430 bits are zeroed. The goal is to recover the flag.

Analysis

The challenge code does:

  • choose a 1000-bit prime P
  • print local_taste
  • set a = int(FLAG.encode().hex(), 16) + local_taste
  • for 5 samples:
    • choose a huge s_i
    • reduce r_i = s_i mod P
    • compute y_i = (a + r_i)^(-1) mod P
    • publish b_i = y_i with its lower 430 bits cleared

So for each sample,

y_i = b_i + e_i, with 0 <= e_i < 2^430

and therefore

(a + r_i)(b_i + e_i) ≡ 1 (mod P).

At first glance this looks like a bilinear small-root problem in (a, e_i). I tried the obvious known-prefix / Herrmann-May style route first, but it was not reliable enough on the real instance.

The better viewpoint is the Modular Inverse Hidden Number Problem (MIHNP). Eliminate a pairwise by equating

(b_i + e_i)^(-1) - r_i ≡ (b_j + e_j)^(-1) - r_j (mod P).

After clearing denominators, for j = 1..4 with sample 0 as the anchor,

(r_0-r_j)(b_0+e_0)(b_j+e_j) - (b_j+e_j) + (b_0+e_0) ≡ 0 (mod P).

These are four bilinear equations in the five unknown truncation errors e_0,...,e_4, each bounded by 2^430.

...

$ grep --similar

Similar writeups