Maojui

SecurityFest 2019 - Cactus (Crypto, 1065)

2019-05-23

Discription

1
2
integer arithmetic is hard
Download: cactus.tar.gz

given file : cactus.py, output.txt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import random

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<<i for i in idx[:w])
        return self.secret*r+e

o = Oracle(10)
for i in range(100):
    print(o.sample(10))

Observe the file output.txt bit-length, the bits parameter of Oracle instance is probably to be 1024, and the w parameter is actually 10.

1
2
3
4
bits = [0] * 1030
for o in output:
    for idx,b in enumerate(bin(o)[2:].rjust(1030,'0')):
        bits[idx] += int(b)

Next, observe the bits distribution of outputs will find that they gather at [-313:]

-> len(flag) + ~10

guess the flag’s bit-length is 304

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# recover r
avg = int(s2b('sctf{').ljust(304,'0'),2)
# '111001101100011011101000110011000000000 ... 00000'

r_list = []
for i,data in enumerate(output) :
    total_zero = 0
    cand_r = 0
    for r in range(1,2048):
        # if r is correct, this segment will be clear.
        test = bin(abs(data - avg*r))[2:][-304:-304+32].count('0')
        if test > total_zero :
            total_zero = test
            cand_r = r
    r_list.append(cand_r)

after getting those multiplier, we can find the flag bytes by bytes.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
cand_flag = 'sctf{'
for _ in range( (304 - 8*5)//8 )  :
    nextchar = ''
    totalzero = 0
    for s in 'abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPWRSTUVWXYZ1234567890_{}' :
        tmp = cand_flag + s
        avg = int(s2b(tmp).ljust(304,'0'),2)
        counter = 0
        for i,o in enumerate(output):
            o -= avg*r_list[i]
            counter += bin(o)[-304:-304+len(cand_flag)*8].count('0')
        if counter > totalzero :
            totalzero = counter
            nextchar = s
    cand_flag += nextchar
    print(cand_flag)

sctf{wh00ps_th4t_w4snt_3xp0nent1ati0n}

Tags: Brute-force Typo
← Volga 2019 - blind (Crypto, 200) AIS3 2019 - Tcash (Crypto, 100) →