positive-thinking — uiuc2026

Description

Here when adventuring, we like positive thinking, even when you can't know the thoughts of others. We'll let you put other's thoughts through something that gets you something positive!

The service generated a uniformly random integer s in [0, 2^50), encrypted it as a one-slot TenSEAL CKKS vector, and published both the encrypted value and an encryption-only context. For each of at most 100 chosen ciphertexts x, it revealed one bit:

[ \operatorname{sign}\left(T_8\left(\frac{x}{2^{49}}\right)\right), ]

where Positive meant that the decrypted polynomial result was greater than zero. After every sign response, the client could submit one exact integer guess. The goal was therefore to turn the oscillating Chebyshev sign into a reliable comparison oracle without exhausting the CKKS modulus chain.

Analysis

1. Exact oracle and CKKS parameters

The relevant challenge parameters were:

Parameter	Value
Polynomial modulus degree	16384
Coefficient-modulus bit sizes	[60, 40, 40, 40, 40, 40, 40, 60]
Global CKKS scale	2^40
Secret interval	[0, 2^50)
Query limit	100

The server evaluated the submitted object exactly as follows:

normalized = ciphertext * (1.0 / 2**24) * (1.0 / 2**25)
result = normalized.polyval(
    [1, 0, -32, 0, 160, 0, -256, 0, 128]
).decrypt()[0]
positive = result > 0

The two normalization multiplications together divide by

[ D=2^{24}2^{25}=2^{49}. ]

Until the interval became a singleton, the solver sent -1 at each guess prompt, which could never equal the nonnegative secret.

2. The outer Chebyshev root is locally monotone

For

[ T_8(y)=128y^8-256y^6+160y^4-32y^2+1, ]

the roots are

[ \cos\left(\frac{(2k-1)\pi}{16}\right),\qquad k=1,\ldots,8. ]

Following the solver's notation, the two largest positive roots are

[ r_4=\cos(\pi/16)\approx0.9807852804, \qquad r_3=\cos(3\pi/16)\approx0.8314696123. ]

Above r4, T8 is always positive. Immediately below it, throughout (r3,r4), T8 is negative. Define the corresponding input-domain gap

[ G=(r_4-r_3)D\approx 8.4057248402353\times10^{13}. ]

For an integer threshold t, place the mathematical crossing at the half-integer t-1/2:

[ x=r_4D+A\left(s-(t-\tfrac12)\right). ]

After the server divides by D, every s >= t lies strictly above r4 and therefore returns Positive. Every integer s < t lies below r4. If the current candidate interval is [L,H) and

[ A\left((t-\tfrac12)-L\right)<G, ]

then its entire lower half remains inside the single negative band (r3,r4), so Not positive means s < t. This one-sided interval invariant avoids all of the other sign changes of T8.

3. Why ordinary CKKS multiplication fails

The fresh ciphertext has seven data moduli; the eighth prime in the parameter list is SEAL's special prime. The server's two normalizations and generic degree-eight polyval consume six chain steps. A query must therefore arrive at the top level.

TenSEAL scalar multiplication performs multiplication followed by rescaling, so even encrypted_secret * 2 drops one modulus. The server then reaches scale out of bounds before completing its fixed-depth circuit.

Ciphertext addition does not rescale. Powers of two can instead be built by doubling:

powers = [encrypted_secret]

def encrypted_power_of_two(exponent):
    while len(powers) <= exponent:
        powers.append(powers[-1] + powers[-1])
    return powers[exponent]       # encrypts 2^exponent * s, still top-level

Plaintext additions are also level-free. Large constants were added in two pieces, -A*t and the root term, to avoid losing low bits by first combining them into one very large binary64 value.

4. CKKS approximation moves the crossing

An ideal-real-arithmetic comparator was not enough. Local tests used the exact server evaluator and the same public-context serialization path. At the mathematical outer root, the decrypted polynomial result was about +4.24e-4; the observed zero crossing was displaced by roughly 5.8e9 secret-input units. An unamplified final-bit comparison could consequently return the wrong sign even though the threshold was placed at a half-integer.

The implementation adopted a deliberately conservative root-error envelope

[ E=2^{38}, ]

almost fifty times the measured displacement. It retained an overlap around each uncertain crossing and increased the affine coefficient as the interval contracted. Once the error expressed in secret units fell below 1/2, the half-integer split made every subsequent comparison exact.

There is a simple level-free route that does not modify serialized coefficients. Split [0,2^50) into 14 buckets of width

[ B=\left\lfloor\frac{2^{50}}{14}\right\rfloor =80421421917330<G. ]

Query the 13 boundaries in increasing order and stop at the first Not positive; before that point the secret is above each boundary, and at the first boundary above it the distance is less than B. This identifies one safe outer-root bucket. Repeated-addition amplification then resolves the bucket in at most 47 more comparisons, for a hard bound of 60 queries. This method is implemented by solve.py and validated by solve_scaled_local.py.

5. Level-free division by 8 in NTT/RNS form

The final solver removed the 13-query localization phase. A serialized TenSEAL CKKSVector is a small protobuf envelope whose field 2 contains a Microsoft SEAL Ciphertext. After Zstandard decompression, the ciphertext is in NTT/RNS form with:

• ciphertext size 2;
• polynomial degree 16384;
• seven data moduli;
• two arrays of one residue per coefficient and modulus.

For every residue x modulo q_i, multiply by 8^-1 mod q_i. Every relevant SEAL prime satisfies q_i = 1 mod 8, so this can be calculated without a wide-integer multiplication:

[ k=(-x)\bmod 8, \qquad x'=\frac{x+kq_i}{8}. ]

The numerator is divisible by eight, and

[ 8x'\equiv x\pmod{q_i}. ]

Moreover, 0 <= k <= 7, so the challenge's roughly 60-bit largest data prime keeps x+k*q_i within an unsigned 64-bit word. Applying this operation to every coefficient of both ciphertext components preserves RNS/CRT coherence, the parameter ID, all modulus levels, and the original CKKS scale. For the small affine plaintext used here, it divides the encrypted value by eight.

This is not a metadata-only scale patch. Merely changing the protobuf scale field does not coherently change the encrypted plaintext and does not produce the successful comparator.

Before the coefficient transform, build

[ x_{\mathrm{pre}} =2^e s-2^e t+8r_4D+2^{e-1}. ]

After multiplying all residues by 8^-1, the server receives a ciphertext of

[ x_{\mathrm{post}} =r_4D+\frac{2^e}{8}\left(s-(t-\tfrac12)\right). ]

At the first midpoint, e=0 is globally safe: the farthest lower candidate moves downward from r4 by less than 1/8 = 0.125, while r4-r3 is approximately 0.1493157. The first query can therefore bisect the full interval directly. As the interval shrinks, e increases and reduces the root uncertainty in secret units.

6. Adaptive exponent and uncertainty-aware interval updates

Let A=2^e, split=t-1/2, and left_span=split-L. The solver chose the largest nonnegative power-of-two exponent satisfying the conservative outer-band condition:

[ A\leq\frac{8(G-2E)}{\text{left_span}}. ]

After division by eight, the uncertainty in secret units was bounded by

[ U=\frac{8E}{A}+\frac14, ]

where the final quarter-unit covers floating-point constant construction. If U < 1/2, the response is an exact integer comparison and the normal updates are used:

Positive      -> L = t
Not positive  -> H = t

Before that point, both branches retain all integers in the root-error band:

Positive      -> L = max(L, ceil(split - U))
Not positive  -> H = min(H, floor(split + U) + 1)

Thus CKKS approximation can temporarily slow interval contraction but cannot discard the real secret under the adopted envelope. A local random instance finished in 50 queries; the conservative worst branch needs 51, still far below the service limit.

Solution

Coherent serialized-ciphertext transform

The exact implementation is in test_coeff_scale.py. The central operation is the following; the surrounding helper parses protobuf field 2 and rebuilds the envelope afterward:

import struct
import numpy as np
import zstandard as zstd

POLY = 16384
SCALE = 2**40

# Deterministic SEAL CoeffModulus::Create output. A top-level ciphertext uses
# the first seven entries; the final entry is the special prime.
MODULI = [
    1152921504606683137,
    1099505827841,
    1099506352129,
    1099506515969,
    1099507695617,
    1099508121601,
    1099510054913,
    1152921504606748673,
]

def divide_ciphertext_by_8(inner: bytes, zstd_level: int = 3) -> bytes:
    assert inner[:2] == b"\x5e\xa1" and inner[5] == 2
    raw = bytearray(zstd.ZstdDecompressor().decompress(inner[16:]))

    is_ntt = raw[32]
    size, degree, mod_count, scale, correction = struct.unpack_from(
        "<QQQdQ", raw, 33
    )
    assert is_ntt == 1
    assert size == 2 and degree == POLY and mod_count == 7
    assert scale == SCALE and correction == 1

    # Ciphertext members end at offset 73. The nested DynArray contributes
    # a 16-byte SEAL header and an 8-byte element count.
    nested = 73
    count = struct.unpack_from("<Q", raw, nested + 16)[0]
    assert count == size * mod_count * degree
    coeffs = np.frombuffer(
        raw, dtype="<u8", count=count, offset=nested + 24
    ).reshape(size, mod_count, degree)

    for index in range(mod_count):
        q = np.uint64(MODULI[index])
        values = coeffs[:, index, :]
        k = (-values) & np.uint64(7)
        values[:] = (values + k * q) >> np.uint64(3)

    payload = zstd.ZstdCompressor(level=zstd_level).compress(raw)
    header = bytearray(inner[:16])
    struct.pack_into("<Q", header, 8, 16 + len(payload))
    return bytes(header) + payload

Comparator construction and bisection

solve_coeff_raw.py used only ciphertext additions before applying the serialized transform:

from fractions import Fraction
import math

D = 2**49
N = 2**50
R4 = math.cos(math.pi / 16)
R3 = math.cos(3 * math.pi / 16)
ROOT_INPUT = R4 * D
GAP_INPUT = (R4 - R3) * D
ROOT_ERROR = 2**38
FLOAT_ERROR = Fraction(1, 4)

powers = [encrypted_secret]

def power(exponent):
    while len(powers) <= exponent:
        powers.append(powers[-1] + powers[-1])
    return powers[exponent]

def comparator_blob(threshold, exponent):
    factor = 1 << exponent
    query = power(exponent) + float(-factor * threshold)
    query = query + float(8 * ROOT_INPUT + factor / 2)
    return divide_vector_by_8(query)

def ceil_fraction(value):
    return -((-value.numerator) // value.denominator)

lo, hi = 0, N
while hi - lo > 1:
    threshold = (lo + hi) // 2
    split = Fraction(2 * threshold - 1, 2)
    left_span = split - lo

    maximum_factor = 8 * (GAP_INPUT - 2 * ROOT_ERROR) / float(left_span)
    exponent = max(0, math.floor(math.log2(maximum_factor)))
    factor = 1 << exponent

    positive = oracle(comparator_blob(threshold, exponent))
    uncertainty = Fraction(8 * ROOT_ERROR, factor) + FLOAT_ERROR

    if uncertainty < Fraction(1, 2):
        if positive:
            lo = threshold
        else:
            hi = threshold
    elif positive:
        lo = max(lo, ceil_fraction(split - uncertainty))
    else:
        upper = split + uncertainty
        hi = min(hi, upper.numerator // upper.denominator + 1)

assert hi - lo == 1
submit_guess(lo)

The production file adds TLS framing, Base64 transport, invariant checks, and the rule that the final guess is submitted while the service is still waiting at the current query's Secret: prompt.

Optional transport optimization

The coefficient transform is the cryptographic exploit. Separately, compact_ckks.py losslessly decompresses the modified SEAL frame and recompresses it with standards-compatible Zstandard level 19. This reduced a typical binary query from about 1.449 MB to 1.243 MB; it did not alter a coefficient, scale, level, or oracle response.

The service sent roughly 20.2 MB before the first prompt, and the provided jail relied on nsjail's default 600-second wall limit. The controller's route was too slow for the startup data and 50 adaptive uploads. The same solver was therefore run from an authorized higher-throughput host. No proxy, parser bug, or service-side modification was required.

Reproduction and remote result

The final and validation artifacts are:

• solve_coeff_raw.py — final dependency-light TLS solver;
• solve_coeff_local.py — exact local recovery with the RNS transform;
• test_coeff_scale.py — protobuf/SEAL parser and coefficient transform;
• compact_ckks.py — optional lossless Zstandard-19 recompression;
• solve.py and solve_scaled_local.py — simpler at-most-60-query route.

From the challenge directory:

$ python3 -m pip install tenseal==0.3.17 numpy zstandard
$ python3 solve_coeff_local.py
...
recovered=<RANDOM_SECRET> correct=True queries=50

$ python3 solve_coeff_raw.py \
    --host positive-thinking.chal.uiuc.tf --port 1337
...
recovered secret=<RECOVERED_INTEGER> in 50 queries
uiuctf{REDACTED}

The recorded remote run received 50 valid sign responses, recovered the exact service integer 516915461286446, submitted it at the pending guess prompt, and received the flag recorded only in this writeup's YAML frontmatter.

Failed and eliminated approaches

• Naive outer-root bisection: candidates far below a threshold cross other T8 sign bands, while candidates near the crossing are affected by the measured CKKS displacement. Both issues invalidate blind exact updates.
• Distance-band scans: explicit scans of all Chebyshev bands were too expensive and unnecessary once the adjacent outer-root invariant was used.
• Ordinary scalar multiplication: it consumed a modulus level, after which the server's fixed-depth polynomial failed with scale out of bounds.
• Seeded, size-one, lower-modulus, or transparent ciphertexts: none both retained dependence on the encrypted secret and supplied the seven data moduli required by the evaluator. RLWE entropy imposed the payload floor.
• Sparse or low-bit-cleared RNS limbs: independent residue damage broke CRT coherence and destroyed the comparison signal.
• Malformed CKKSVector shapes: local auditing found out-of-bounds and uninitialized tail reads, but not an endpoint-visible leak through decrypt()[0], a write primitive, code execution, or a secret overwrite.

Lessons Learned

• An oscillating polynomial can still implement a comparator if all candidates on one side are confined to its outermost adjacent sign band.
• Half-integer thresholds separate integer candidates only after numerical root displacement is bounded and propagated through every interval update.
• CKKS levels and CKKS scale are distinct: direct coherent residue arithmetic can change the encrypted value while retaining both the scale and chain.
• Keep cryptographic correctness separate from delivery engineering. Here the RNS transform enabled the near-minimal query count; stronger Zstandard and a faster authorized runner only made those queries arrive in time.