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.*