Rating:

# Cactus
## Weird approximate gcd problem

Note: I didn't solve this challenge during the ctf. Since there aren't any write-ups available at the time of writing, I decided to write one.

We get a script cactus.py:
python
import random
from math import log

class Oracle:

def __init__(self, secret, bits=512):
self.secret = secret
self.bits = bits
self.range = 2*self.bits

def sample(self, w):
r = random.randint(0, 2^self.range)
idx = range(self.bits)
random.shuffle(idx)
e = sum(1<>> bin(l[78])
0b100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000010000000001000000000001000000000000000000000000100000000000000000000000000000100000000000000000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000001000100000011111010100110101000011100101101001101101111011101000110110010010010010101000000110101001101101010010111011100000000101001000100111101001111111100000001011000100110101101000010011101011100000010100010110010010001000111011101010000100110100010010010000001111011101010100000101110010001001010111011101100

So, supposedly, the 7 first set bits come from e. Thus, we only need to brute-force the last 3 bits coming from e!

Here is my first try:
python
# a is l[78] starting from the 8th bit set.
a=int('1000100000011111010100110101000011100101101001101101111011101000110110010010010010101000000110101001101101010010111011100000000101001000100111101001111111100000001011000100110101101000010011101011100000010100010110010010001000111011101010000100110100010010010000001111011101010100000101110010001001010111011101100',2)
for i in range(313):
for j in range(i):
for k in range(j):
x = a-2**i-2**j-2**k # x is a minus 3 random bits.
for d in get_div(x): # get_div returns the divisors of x smaller than 1026.
s=long_to_bytes(x//d) # we divide a by a divisor to get a potential flag.
if b'ctf' in s: # we check if 'ctf' is a substring.
print('divisor: '+str(d))
print(s)

Running this, we get outputs looking like this:

divisor: 604
b"sctf{wi\xe23\xd4z'\x81\xf8O\xaf\xb5\xed\xe1\xc8O.\t\x16\x1bk\xc4\xdc\x1ba\x8b<'\xb10n}"
41
divisor: 604
b"sctf{wi\xe23\xd4z'\x81\xf8O\xaf\xb5\xed\xe1\xc8O.\t\x16\x1bk\xc4\xdc\x1ba\x8b<'E\x96'E"
divisor: 604
b"sctf{wi\xe23\xd4z'\x81\xf8O\xaf\xb5\xed\xe1\xc8O.\t\x16\x1bk\xc4\xdc\x1ba\x8b<'E\x96 }"
divisor: 604
b"sctf{wi\xe23\xd4z'\x81\xf8O\xaf\xb5\xed\xe1\xc8O.\t\x16\x1bk\xc4\xdc\x1ba\x8b<'E\x94uE"

We see the beginning of a flag starting with sctf, always with the divisor 604. We guess that this is the real value of r and stop looking for other divisors, which speeds up the brute-force. Finally, we only print strings containing only printable characters:
python
from string import printable
for i in range(313):
for j in range(i):
for k in range(j):
x = a-2**i-2**j-2**k
s=long_to_bytes(x//604)
if b'ctf' in s and all([chr(le) in printable for le in s]):
print(s)

which outputs

b'sctf{wh00ps_th4t_w4sntzSxp0nent1ati0n}'
b'sctf{wh00ps_th4t_w4snt_3xp0nent1ati0n}'

I guess that the second one is probably the flag (it hints that 2^self.range actually was a typo).

### Post-mortem:
During the ctf, I tried way more complex methods, researching the *approximate gcd problem* which is used in some crypto algorithm. In my head it was clear that I should use many numbers in the output and somehow find the flag by computing their approximate gcd.

As we can see in this write-up, we actually only need one of the output (albeit smartly chosen so that a lot of the highest bits come from the error e) and that the solution can be found using a simple brute-force search on r and e.

All in all, the solution isn't that interesting, but it's a good lesson for me that I shouldn't immediatly over-complicate things and first try the direct approach to solve a problem.