Twin Spirit — Crypto Writeup

Name: Twin Spirit Channels Category: Crypto (RSA oracle + BBS) Flag: Africc{sp1r1t_ch4nn3ls_bbs_0r4cl3}

1. Challenge overview

We connect to a TCP service that prints the modulus M at startup and offers a menu:

1. Seek wisdom from the Ancestral Archive  ->  returns n and the encrypted flag
2. Query the Twin Spirit Channels          ->  an RSA decryption oracle
3. Leave the Shrine

Only 1500 menu actions are allowed (counter <= 1500).

The server code (server.py) contains two components:

ChaosRelic — a BBS (Blum–Blum–Shub) generator

self.p = getPrime(8);  self.q = getPrime(8)
self.M = self.p * self.q        #   M is printed
self.x0 = getPrime(15)          # 15-bit prime
self.x  = self.x0

def next_state(self):
    self.x = pow(self.x, 2, self.M)

def get_bit(self):
    self.next_state()
    return self.x % 2

ObsidianSeers — an RSA decryption oracle

def sacred_decryption(self, c):
    return pow(c, self.d, self.n)

def HighSeerVision(self, c):          # class="hljs-string">"greater than half"
    return int(self.sacred_decryption(c) > self.n // 2)

def FateSeerWhisper(self, c):        # LSB / parity
    return self.sacred_decryption(c) % 2

def divine_prophecy(self, a_bit, c):
    return self.FateSeerWhisper(c) if a_bit == 0 else self.HighSeerVision(c)

def consult_seers(self, c):
    next_bit = self.relic.get_bit()          # BBS beta bit selects the oracle
    return self.divine_prophecy(next_bit, c)

So on each query the server:

advances the BBS by one bit,
if the BBS bit is 0 → returns the parity of the plaintext,
if the BBS bit is 1 → returns whether the plaintext is > n//2.

The flag is available as pow(FLAG, e, n).

2. Core idea: both oracles leak the same thing

For odd n (product of two odd primes) let x = m · 2^k mod n. Because n is odd:

parity((2x) mod n) = 0   ⇔   x < n/2
parity((2x) mod n) = 1   ⇔   x > n/2

and obviously

(2x mod n) > n//2        ⇔   x in the upper half of [0, n)

So if we query with a whichever scaled ciphertexts we get either the parity of the current value or the "> n//2" bit, and the two are the same decision bit. Hence both oracle types expose:

[a  > n/2]    where   a = m·2^k mod n

The standard MSB/half-oracle bisection, run for n.bit_length() rounds with the ciphertext multiplied by (2)^e each round, recovers the whole plaintext m.

The critical detail is that the oracle type alternates (chosen by the BBS). We need to know before each query whether the answer is parity or "> half" so we pick the correct input value (m·2^k for the half-oracle, m·2^{k+1} for the parity oracle, whose parity then equals the "> half" bit of m·2^k).

3. Recovering the BBS seed

The oracle type is chosen by the BBS bit, and the BBS is predictable:

M is printed to us (product of two 8-bit primes, so M < 2^16),
the BBS seed x0 = getPrime(15) is a 15-bit prime, only ~1500 candidates.

We can observe the BBS stream by sending a ciphertext whose plaintext is known, e.g., ciphertext = 1 (we possess e and n, so we can encrypt any value we like).

plaintext 1, parity oracle → 1 % 2 = 1
plaintext 1, ">half" oracle → 1 > n//2 = 0

Therefore a query of ciphertext = 1 returns 1 iff the BBS bit was 0. We can read the BBS output bits directly: bbs_bit = 1 - answer.

We brute-force the seed x0 over all primes in [2^14, 2^15), simulating the recurrence

x = x0
for obs in observed_bits:
    x = (x * x) % M
    assert x % 2 == obs

until exactly one seed matches. In the solving run this happened after a handful of bits:

selected x0: 16879

Now every future BBS bit (and hence which oracle will run) is known in advance.

4. Recovery

With the BBS stream pinned, for recovery step k:

sel = predicted_bbs_bit_for_this_query
if sel == 1:                    # class="hljs-string">">half" oracle -> ask about m·2^k
    c = (ct * pow(pow(2, k, n), e, n)) % n
else:                           # parity oracle  -> ask about m·2^(k+1)
    c = (ct * pow(pow(2, k+1, n), e, n)) % n
resp = oracle(c)
# resp == 1  ⇔  m·2^k mod n > n//2

Collecting these bits over k = 0 … n.bit_length()+12 yields the binary expansion of m:

val = sum bit_k * 2^(len-1-k)
m   = round(n * val / 2^len)

Finally verify pow(m, e, n) == ct for m ± small delta and print the flag.

5. Full solution script

Full exploit: ./solve.py in this directory.

6. Result

M = 40301, n bits: 1024
selected x0 = 16879
FLAG: Africc{sp1r1t_ch4nn3ls_bbs_0r4cl3}

The recovered plaintext:

0x4166726963637b7370317231745f6368346e6e336c735f6262735f307234636c337d

decodes to Africc{sp1r1t_ch4nn3ls_bbs_0r4cl3}.

7. Why the counter limit is fine

calibration: a handful of 1 queries
recovery: ~`n.bit_length() + 12 ≈ 1036` queries
plus menu entries

Total ≈ 1050 < 1500 ✓

8. Takeaways

BBS with a published modulus and a small seed is trivially brute-forced.
An RSA decryption oracle that leaks only the parity or only the "half" bit of the plaintext still fully reveals it via repeated multiplication of the ciphertext — never publish a decryption/padding oracle.
When an oracle alternates between types via an unknown sequence, the sequence itself was the weak point: a 15-bit seed breaks instantly, turning the combined oracle back into a single deterministic breaking tool.

AFRICC Qualifiers 2027 - Twin Spirit Channels Writeup