It's RSA Time

Task description

An RSA server encrypts the reversed-byte flag and lets you submit any ciphertext; each submission leaks exactly one bit of its decryption, at a position that depends on the current server time.

The oracle

hour = time.hour + 1       # 1 to 24
minute = time.minute + 1   # 1 to 60
if m & 2**(hour+minute):
    print("contains a 1 at this position")
else:
    print("does not")

Standard 1024-bit RSA, with the flag stored as m = bytes_to_long(FLAG[::-1]), reversed so its most significant bits (where an oracle like this one is weakest) don’t line up with the predictable CTF2026[ prefix. Whatever ciphertext is submitted, the server decrypts it and reports a single bit, at position hour + minute, somewhere between 2 and 84 depending on when the request happens to land.

A single-bit decryption oracle sounds like it should leak almost nothing. It’s actually enough to recover the entire plaintext: this is a classical result (Alexi, Chor, Goldreich and Schnorr, 1988) showing that recovering any one bit of an RSA plaintext is, in the worst case, exactly as hard as recovering the whole thing, because RSA’s own multiplicative structure lets an attacker shift which bit the oracle is really answering about.

Choosing which bit the oracle reveals

RSA is multiplicative: decrypt(c * r^e mod N) = m * r mod N for any chosen r. Picking r = 2^k for some small k just shifts m left by k bits (as long as that shift doesn’t push the result past N and wrap around), so asking the oracle about its fixed bit position pos after such a shift is the same as asking about bit pos - k of the real m.

Reading the low bits directly

Since the flag’s roughly 160 to 200-bit value is far smaller than the 1024-bit modulus, shifting it left by any amount up to the oracle’s current bit position never wraps, so every bit from 0 up through the current pos can be read directly this way, one query per bit. A quick sanity check along the way: the lowest 8 bytes of the recovered value should read as CTF2026[ once decoded (the flag’s reversed byte order puts its known prefix at the low end).

Binary-searching the rest

Bits above whatever pos happens to be at any given moment can’t be reached by a plain shift. For those, the attack splits m into a known low part and an unknown high part, m = m_high * 2^S + m_low, and binary-searches m_high directly: pick a multiplier f chosen so that f * m sits right around N, in a position where whether or not a modular reduction actually occurred (something we can predict from the known low bits) tells us which side of the current guess m_high falls on. Each oracle query this way halves the remaining search range for the high bits.

There’s a wrinkle: at any single fixed bit position pos, this binary search eventually stalls, with one bit it genuinely can’t distinguish. But the server’s clock keeps advancing, the oracle’s pos grows by one roughly once a minute, and that extra bit of resolution is exactly what unsticks the stalled search and lets it keep narrowing down, matching the challenge’s own hint: “can you solve this at any time of day?”

Verifying and recovering the flag

Once a candidate m survives both phases, a direct check, pow(m, e, N) == enc, confirms it’s correct. Reversing its bytes back (undoing the server’s own reversal) gives the flag’s actual text.

The exploit

from pwn import remote
from Crypto.Util.number import long_to_bytes
import re

r = remote('chal.live.hackultet.hr', 14024)
data = r.recvuntil(b'Enkriptirana poruka> ').decode()
N = int(re.search(r'N = (\d+)', data).group(1))
e = int(re.search(r'e = (\d+)', data).group(1))
enc = int(re.search(r'enk_poruka = (\d+)', data).group(1))

def query(c):
    r.sendline(str(c).encode())
    resp = r.recvuntil(b'Enkriptirana poruka> ').decode()
    pos = int(re.search(r'na poziciji (\d+)', resp).group(1))
    return pos, 0 if 'ne sadrzi' in resp else 1

c2e = pow(2, e, N)
known = {}
pos, bit = query(enc)
known[pos] = bit

# phase 1: shift m left bit by bit, reading each position directly until pos stops advancing
for b in range(pos, -1, -1):
    if b in known: continue
    p, bv = query((enc * pow(c2e, pos - b, N)) % N)
    known[b] = bv

S_exp = max(known) + 1
S = 1 << S_exp
m_low = sum(known.get(b, 0) << b for b in range(S_exp))

# phase 2: binary-search the high bits, multiplying by f so N/f straddles the current guess
lo, hi = 0, 1 << (320 - S_exp)
while hi - lo > 1:
    mid = (lo + hi) // 2
    m_mid = mid * S + m_low
    f = N // m_mid
    mask = (1 << (pos + 1)) - 1
    pred_no = ((f * m_low) & mask) >> pos & 1
    pred_red = (((f * m_low) - N) & mask) >> pos & 1
    if pred_no == pred_red:
        continue   # nudge f until the two predictions diverge, then query as below
    p, bv = query((enc * pow(f, e, N)) % N)
    if bv == pred_no:
        hi = mid
    else:
        lo = mid

for delta in range(-5, 6):
    m = (lo + delta) * S + m_low
    if m > 0 and pow(m, e, N) == enc:
        print(long_to_bytes(m)[::-1])
        break

Trimmed to the shape of the two phases; the real solver also re-reads bits when pos advances mid-search and nudges f by small deltas whenever a guess lands exactly on an indistinguishable boundary.

Why the time dependence doesn’t help

Changing which bit is revealed, instead of always leaking the same one, looks like it should slow an attacker down, since no single query can be repeated to confirm an answer at leisure. In practice it costs nothing: the low bits are read directly regardless of which pos happens to be active at the time, and the high-bit binary search actively benefits from pos creeping forward, since each new position supplies the next bit of resolution the search needed anyway. A oracle that changes over time is not the same thing as a oracle that’s actually harder to exploit.